Coupon replication systems

ABSTRACT

Motivated by the study of peer-to-peer file swarming systems à la BitTorrent, we introduce a probabilistic model of coupon replication systems. These systems consist of users aiming to complete a collection of distinct coupons. Users enter the system with an initial coupon provided by a bootstrap server, acquire other coupons from other users, and leave once they complete their coupon collection. For open systems, with exogenous user arrivals, we derive stability condition for a layered scenario, where encounters are between users holding the same number of coupons. We also consider a system where encounters are between users chosen uniformly at random from the whole population. We show that sojourn time in both systems is asymptotically optimal as the number of coupon types becomes large. We also consider closed systems with no exogenous user arrivals. In a special scenario where users have only one missing coupon, we evaluate the size of the population ultimately remaining in the system, as the initial number of users Ngoes to infinity. We show that this size decreases geometrically with the number of coupons K. In particular, when the ratio K/log(N) is above a critical threshold, we prove that this number of leftovers is of order log(log(N)). These results suggest that, under the assumption that the bootstrap server is not a bottleneck, the performance does not depend critically on either altruistic user behavior or on load-balancing strategies such as rarest first.

REFERENCES

• 1: eDonkey. [Online]. Available: http://www.edonkey2000.com/index. html
• 2: KaZaA. [Online]. Available: http://www.kazaa.com/
• 3: A. Müller and D. Stoyan, Comparison Methods for Stochastic Models and Risks, ser. Wiley Series in Probability and Statistics. New York: Wiley, 2002.
• 4: N. Alon and J. Spencer, The Probabilistic Method, ser. Wiley Interscience Series in Discrete Mathematics and Optimization, 2nd ed. New York: Wiley Interscience, 2000.
• 5: B. Cohen, "Incentives build robustness in BitTorrent," May 2003 [On-line]. Available: http://www.bittorrent.org/bittorrentecon.pdf
• 6: Supratim Deb , Muriel Médard , Clifford Choute, Algebraic gossip: a network coding approach to optimal multiple rumor mongering, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2486-2507, June 2006 [doi>10.1109/TIT.2006.874532]
• 7: Dongyu Qiu , R. Srikant, Modeling and performance analysis of BitTorrent-like peer-to-peer networks, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 8: G. Hardy, J. E. Littlewood, and G. Pólya, Inequalities, 2nd ed. Cambridge, U.K.: Cambridge Univ. Press, 1952, Cambridge Mathematical Library.
• 9: Ronald L. Graham , Donald E. Knuth , Oren Patashnik, Concrete Math, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 10: J. Hofbauer and K. Sigmund, Evolutionary Games and Population Dynamics . Cambridge, U.K.: Cambridge Univ. Press, 1998.
• 11: J. A. Pouwelse, P. Garbacki, D. H. J. Epema, and H. J. Sips, "A measurement study of the BitTorrent peer-to-peer file-sharing system," in Proc. 4th Int. Workshop on Peer-to-Peer Systems (IPTPS), Feb. 2005, Vol. 3640, LNCS.
• 12: H. K. Khalil, Nonlinear Systems, 3rd ed. Upper Saddle River, NJ: Prentice-Hall, 2002.
• 13: T. Kurtz, Approximation of Population Processes, ser. CBMS-NSF Regional Conference Series in Applied Mathematics. Philadelphia, PA: SIAM, 1981, vol. 36.
• 14: R. Loynes, "The stability of a queue with non-independent interarrival and service times," Proc. Cambr. Phil. Soc., vol. 58, no. 3, pp. 497-520, 1962.
• 15: M. Izal, G. Urvoy-Keller, E. W. Biersack, P. A. Felber, A. Al Hamra, and L. GarcésErice, "Dissecting BitTorrent: Five months in a torrent's life," in Proc. PAM, Antibes, France, 2004, pp. 1-11.
• 16: J. Mundinger and R. Weber, "Efficient file dissemination using peer-topeer technology," Univ. of Cambridge, Cambridge, U.K., Tech. Rep. 2004-01, 2004.
• 17: X. Yang and G. deVeciana, "Service capacity of peer to peer networks," in Proc. IEEE INFOCOM, Hong Kong, 2004, vol. 4, pp. 2242-2252.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
      D.4.4 Communications Management
      D.4.8 Performance

General Terms:
Design, Management, Performance

Keywords:
content distribution, file dissemination, file swarming, peer-to-peer