An online backup system should be quick and reliable in both saving and
restoring users’ data. To do so in a peer-to-peer implementation, data transfer
scheduling and the amount of redundancy must be chosen wisely. We formalize the
problem of exchanging multiple pieces of data with intermittently available
peers, and we show that random scheduling completes transfers nearly optimally
in terms of duration as long as the system is sufficiently large. Moreover, we
propose an adaptive redundancy scheme that improves performance and decreases
resource usage while keeping the risks of data loss low. Extensive simulations
show that our techniques are effective in a realistic trace-driven scenario
with heterogeneous bandwidth.