skip to main content
article

Coupon replication systems

Published: 01 June 2008 Publication History

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]
S. Deb, M. Médard, and C. Choute, "Algebraic gossip: A network coding approach to optimal multiple rumor mongering," IEEE/ACM Trans. Networking, vol. 14, no. 3 (Special Issue on Networking and Information Theory), pp. 2486-2507, Jun. 2006.
[7]
D. Qiu and R. Srikant, "Modeling and performance analysis of Bit-Torrent-like peer-to-peer networks," in Proc. ACM SIGCOMM 2004, Portland, OR, 2004, pp. 367-378.
[8]
G. Hardy, J. E. Littlewood, and G. Pólya, Inequalities, 2nd ed. Cambridge, U.K.: Cambridge Univ. Press, 1952, Cambridge Mathematical Library.
[9]
R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics . Reading, MA: Addison Wesley, 1998.
[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.

Cited By

View all
  • (2024)Rarest-First With Probabilistic-Mode-Suppression (RFwPMS)IEEE Transactions on Information Theory10.1109/TIT.2024.336000570:4(2936-2966)Online publication date: 1-Apr-2024
  • (2020)Stable and Efficient Piece-Selection in Multiple Swarm BitTorrent-like Peer-to-Peer NetworksIEEE INFOCOM 2020 - IEEE Conference on Computer Communications10.1109/INFOCOM41043.2020.9155253(1153-1162)Online publication date: 6-Jul-2020
  • (2019)A New Stable Peer-to-Peer Protocol With Non-Persistent Peers: The Group Suppression ProtocolIEEE Transactions on Information Theory10.1109/TIT.2019.294665666:1(614-632)Online publication date: 20-Dec-2019
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 16, Issue 3
June 2008
249 pages

Publisher

IEEE Press

Publication History

Published: 01 June 2008
Published in TON Volume 16, Issue 3

Author Tags

  1. content distribution
  2. file dissemination
  3. file swarming
  4. peer-to-peer

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 15 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Rarest-First With Probabilistic-Mode-Suppression (RFwPMS)IEEE Transactions on Information Theory10.1109/TIT.2024.336000570:4(2936-2966)Online publication date: 1-Apr-2024
  • (2020)Stable and Efficient Piece-Selection in Multiple Swarm BitTorrent-like Peer-to-Peer NetworksIEEE INFOCOM 2020 - IEEE Conference on Computer Communications10.1109/INFOCOM41043.2020.9155253(1153-1162)Online publication date: 6-Jul-2020
  • (2019)A New Stable Peer-to-Peer Protocol With Non-Persistent Peers: The Group Suppression ProtocolIEEE Transactions on Information Theory10.1109/TIT.2019.294665666:1(614-632)Online publication date: 20-Dec-2019
  • (2015)Queueing analysis of peer-to-peer swarmsPerformance Evaluation10.1016/j.peva.2015.08.00393:C(47-62)Online publication date: 1-Nov-2015
  • (2014)Rating Protocols in Online CommunitiesACM Transactions on Economics and Computation10.1145/25607942:1(1-34)Online publication date: 1-Mar-2014
  • (2012)Content dynamics in P2P networks from queueing and fluid perspectivesProceedings of the 24th International Teletraffic Congress10.5555/2414276.2414290(1-8)Online publication date: 4-Sep-2012
  • (2011)On the stability and optimality of universal swarmsACM SIGMETRICS Performance Evaluation Review10.1145/2007116.200715139:1(301-312)Online publication date: 7-Jun-2011
  • (2011)Stability of a peer-to-peer communication systemProceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing10.1145/1993806.1993867(321-330)Online publication date: 6-Jun-2011
  • (2011)On the stability and optimality of universal swarmsProceedings of the ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems10.1145/1993744.1993779(341-352)Online publication date: 7-Jun-2011
  • (2010)Demand-aware content distribution on the internetIEEE/ACM Transactions on Networking10.1109/TNET.2009.203504718:2(476-489)Online publication date: 1-Apr-2010

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media