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.