Abstract
We consider a BitTorrent type file sharing algorithm with randomized chunk copying process. The system functions in completely distributed way without any ‘Tracker’, just relying on randomness. In such case the stability becomes an issue. It may happen, say, that some chunk becomes rare. This problem can persist and cause accumulation of peers in the system, resulting in unstable system. The considered algorithms result in processes similar to urn-processes. The rare chunk phenomenon corresponds to Polya-urn type process, where common chunks are favored. However, some urn-processes like the Friedman-urn can provide good balance by favoring rare chunks in copying process. Recently, we showed that an algorithm based on Friedman-urn is efficient in two chunk case. We generalize this algorithm for the more realistic case of many chunks. It shows good performance in terms of balance of chunks in an open system with constant flow of incoming peers. Further, the system is able to cope with instances like ‘flash crowd’, with large burst of incoming peers. The open system can also quickly reach equilibrium after an initial imbalance, when the system starts from a state with one rare chunk. We constructed a simplified model, assuming a good balance of chunks, and get results surprisingly close to simulations for Friedman-urn based random process.
Chapter PDF
Similar content being viewed by others
References
Cohen, B.: BitTorrent specification (2006), http://www.bittorrent.org
Qiu, D., Srikant, R.: Modeling and Performance Analysis of BitTorrent-Like Peer-to-Peer Networks. In: Proc. ACM Sigcomm, Portland, OR (2004)
Mundinger, J., Weber, R., Weiss, G.: Analysis of peer-to-peer file dissemination. Performance Evaluation Review, Special Issue on MAMA 2006 (2006)
Norros, I., Prabhu, B., Reittu, H.: Flash crowd in a file sharing system based on random encounters. In: Inter-Perf, Pisa, Italy (2006), http://www.inter-perf.org
Reittu, H., Norros, I.: Urn models and peer-to-peer file sharing. In: Proc. IEEE PHYSCOMNET 2008, Berlin (2008)
Massoulie, L., Vojnovic, M.: Coupon Replication Systems. In: Proc. ACM SIGMETRICS, Banff, Canada (2005)
Pemantle, R.: A survey of random processes with reinforcement. Probability Surveys 4, 1–79 (2007)
Reittu, H., Norros, I.: Toward moldeling of a single file broadcasting in a closed network. In: Proceedings of IEEE SPASWIN 2007, Limassol, Cyprus (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 IFIP International Federation for Information Processing
About this paper
Cite this paper
Reittu, H. (2009). A Stable Random-Contact Algorithm for Peer-to-Peer File Sharing. In: Spyropoulos, T., Hummel, K.A. (eds) Self-Organizing Systems. IWSOS 2009. Lecture Notes in Computer Science, vol 5918. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-10865-5_16
Download citation
DOI: https://doi.org/10.1007/978-3-642-10865-5_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-10864-8
Online ISBN: 978-3-642-10865-5
eBook Packages: Computer ScienceComputer Science (R0)