An Optimal Basis For Efficient Peer-To-Peer Content Distribution Algorithms

Peer-to-peer content distribution has become extremely popular, thanks to its highly scalable performance. In this paper, we derive a lower bound on the performance of chunk-based peer-to-peer content distribution systems and develop an algorithm that is within 1 round of the lower bound in special cases, and within 1 + log₂ ² (I) rounds in the general case, where I is the number of peers. We consider the performance of our algorithm also in a heterogeneous bandwidth environment and under churn. We show that our algorithm always achieves good performance and does not impose an undue burden on fast peers, thus providing a natural incentive for all peers to participate.