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.
