zbMATH — the first resource for mathematics

The missing piece syndrome in peer-to-peer communication. (English) Zbl 1291.68033
Summary: Typical protocols for peer-to-peer file sharing over the internet divide files to be shared into pieces. New peers strive to obtain a complete collection of pieces from other peers and from a seed. In this paper we investigate a problem that can occur if the seeding rate is not large enough. The problem is that, even if the statistics of the system are symmetric in the pieces, there can be symmetry breaking, with one piece becoming very rare. If peers depart after obtaining a complete collection, they can tend to leave before helping other peers receive the rare piece. Assuming that peers arrive with no pieces, there is a single seed, random peer contacts are made, random useful pieces are downloaded, and peers depart upon receiving the complete file, the system is stable if the seeding rate (in pieces per time unit) is greater than the arrival rate, and is unstable if the seeding rate is less than the arrival rate. The result persists for any piece selection policy that selects from among useful pieces, such as rarest first, and it persists with the use of network coding.

68M11 Internet topics
68M12 Network protocols
Full Text: DOI arXiv
[1] Ahlswede, R., Cai, N., Li, S.-Y., and Yeung, R. (2000). Network information flow. IEEE Transactions on Information Theory 46 , 4 (July), 1204-1216. · Zbl 0991.90015
[2] Cohen, B. (2003). Incentives build robustness in BitTorrent. P2PECON Workshop .
[3] Deb, S., Médard, M., and Choute, C. (2006). Algebraic gossip: A network coding approach to optimal multiple rumor mongering. IEEE Transactions on Information Theory 52 , 6 (June), 2486-2502. · Zbl 1293.94009
[4] Gkantsidis, C. and Rodriguez, P. (2005). Network coding for large scale content distribution. In Proceedings INFOCOM 2005 . Vol. 4 , 2235-2245 vol. 4.
[5] Hajek, B. Notes for ECE 567: Communication network analysis. Available at .
[6] Kingman, J. (1962). Some inequalities for the queue GI/G/1. Biometrika 49 , 3/4, 315-324. · Zbl 0122.13802
[7] Kurtz, T. G. (1981). Approximation of population processes . CBMS-NSF Regional Conference Series in Applied Mathematics, Vol. 36 . Society for Industrial and Applied Mathematics (SIAM), Philadelphia, Pa. · Zbl 0465.60078
[8] Leskelä, L., Robert, P., and Simatos, F. (2010). Interacting branching processes and linear file-sharing networks. Advances in Applied Probability 42 , 3, 834-854. · Zbl 1214.60044
[9] Massoulié, L. and Vojnović, M. (2005). Coupon replication systems. In SIGMETRICS ’05: Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems . ACM, New York, NY, USA, 2-13.
[10] Massoulié, L. and Vojnović, M. (2008). Coupon replication systems. IEEE/ACM Trans. Networking 16 , 3, 603-616.
[11] Menasché, D. S., de Aragão Rocha, A. A., de Souza e Silva, E., Leão, R. M. M., Towsley, D. F., and Venkataramani, A. (2010). Estimating self-sustainability in peer-to-peer swarming systems. .
[12] Meyn, S. and Tweedie, R. (2009). Markov Chains and Stochastic Stability (Cambridge Mathematical Library) , 2 ed. Cambridge University Press. · Zbl 1165.60001
[13] Norros, I., Reittu, H., and Eirola, T. (2011). On the stability of two-chunk file-sharing systems. Queueing Systems 67 , 3, 183-206. · Zbl 1225.60145
[14] Qiu, D. and Srikant, R. (2004). Modeling and performance analysis of BitTorrent-like peer-to-peer networks. In SIGCOMM ’04 . ACM, New York, NY, USA, 367-378.
[15] Yang, X. and de Veciana, G. (2004). Service capacity of peer to peer networks. In IEEE INFOCOM , 1-11.
[16] Yang, X. and de Veciana, G. (2006). Performance of peer-to-peer networks: Service capacity and role of resource sharing policies. Performance Evaluation 63 , 3, 175-194.
[17] Zhu, J. and Hajek, B. (2011). Stability of a peer-to-peer communication system. In Proceedings SIGACT-SIGOPS Symposium on Principles of Distributed Computing . · Zbl 1291.68033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.