P2P systems provide a scalable solution for distributing large files in a network. The file is split into many chunks, and peers contact other peers to collect missing chunks to eventually complete the entire file. The so-called 'rare chunk' phenomenon, where a single chunk becomes rare and prevents peers from completing the file, is a threat to the stability of such systems. A protocol that forces peers to download the rarest chunk in the network first would solve this issue, however this solution requires global chunk availability information that is not readily available. We look for a distributed approximation to this solution. Although heuristics exist which perform well in practice, formal proofs of stability of such systems were lacking. In this document, we demonstrate a new system based on an approximate rare-chunk rule, allowing for completely distributed file sharing while retaining scalability and stability. We assume non-altruistic peers and the seed is required to make only a minimal contribution.




Download Full History