skip to main content
10.1145/1146381.1146394acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
Article

EquiCast: scalable multicast with selfish users

Published: 23 July 2006 Publication History

Abstract

Peer-to-peer (P2P) networks suffer from the problem of "free-loaders", i.e., users who consume resources without contributing anything in return. In this paper, we tackle this problem taking a game theoretic perspective by modeling the system as a non-cooperative game. We introduce Equi-Cast, a wide-area P2P multicast protocol for large groups of selfish nodes. EquiCast is the first P2P multicast protocol that is formally proven to enforce cooperation in selfish environments. Additionally, we prove that EquiCast incurs a low constant load on each user.

References

[1]
EMULE-PROJECT.NET. eMule site. http://www.emule-project.net/.
[2]
A. S. Aiyer, L. Alvisi, A. Clement, M. Dahlin, J.-P. Martin, and C. Porth. Bar fault tolerance for cooperative services. In ACM SOSP, Oct. 2005.
[3]
A. Blanc, Y.-K. Liu, and A. Vahdat. Designing incentives for peer-to-peer routing. In Proceedings of the IEEE Infocom Conference, 2005.
[4]
M. Castro, P. Druschel, A.-M. Kermarrec, A. Nandi, A. Rowstron, and A. Singh. Splitstream: High-bandwidth multicast in a cooperative environment. In ACM SIGOPS Symposium on Operating Systems Principles (SOSP), October 2003.
[5]
Y. Chawathe, S. Ratnasamy, L. Breslau, N. Lanham, and S. Shenker. Making gnutella-like p2p systems scalable. In ACM SIGCOMM, August 2003.
[6]
B. Cohen. Incentives build robustness in BitTorrent. In 1st Workshop on the Economics of Peer-to-Peer Systems, 2003.
[7]
L. Cox and B. Noble. Samsara: Honor among thieves in peer-to-peer storage. In ACM SIGOPS Symposium on Operating Systems Principles (SOSP), 2003.
[8]
J. Feigenbaum, C. H. Papadimitriou, and S. Shenker. Sharing the cost of multicast transmissions. Journal of Computer and System Sciences, 63(1):21--41, 2001.
[9]
J. Friedman. On the second eigenvalue and random walks in random d-regular graphs. Combinatorica, vol. 11, pp. 331--362, 1991.
[10]
D. Fudenberg and J. Tirole. Game Theory. The MIT Press, 1991.
[11]
C. Gkantsidis and P. R. Rodriguez. Network coding for large scale content distribution. In Proceedings of the IEEE Infocom Conference, 2005.
[12]
A. Habib and J. Chuang. Incentive mechanism for peer-to-peer media streaming. In International Workshop on Quality of Service (IWQoS '04), 2004.
[13]
D. Hales and S. Patarin. How to cheat bittorrent and why nobody does. TR UBLCS-2005-12, Department of Computer Science University of Bologna, May 2005.
[14]
T. Karagiannis, P. Rodriguez, and D. Papagiannaki. Should isps fear peer-assisted content distribution? In ACM USENIX IMC, 2005.
[15]
M. Kim and M. Medard. Robustness in large-scale random networks. In Proceedings of the IEEE Infocom Conference, 2004.
[16]
C. Law and K. Siu. Distributed construction of random expander networks. In IEEE Infocom, 2003.
[17]
R. Melamed and I. Keidar. Araneola: A scalable reliable multicast system for dynamic environments. In 3rd IEEE International Symposium on Network Computing and Applications (IEEE NCA), 2004.
[18]
T.-W. J. Ngan, D. S. Wallach, and P. Druschel. Incentives-compatible peer-to-peer multicast. In 2nd Workshop on the Economics of Peer-to-Peer Systems, 2004.
[19]
P. Rodriguez, S.-M. Tan, and C. Gkantsidis. On the feasibility of commercial, legal p2p content distribution. In ACM/SIGCOMM CCR, 2006.
[20]
R. Sherwood, R. Braud, and B. Bhattacharjee. Slurpie: A cooperative bulk data transfer protocol. In Proceedings of IEEE INFOCOM, 2004.
[21]
N. Wormald. Models of random regular graphs. Surveys in Combinatorics, 276:239--298, 1999.

Cited By

View all
  • (2013)Efficient and incentive-compatible resource allocation mechanism for P2P-assisted content delivery systemsFuture Generation Computer Systems10.1016/j.future.2012.08.00829:6(1611-1620)Online publication date: 1-Aug-2013
  • (2012)DCastProceedings of the 2012 ACM conference on Computer and communications security10.1145/2382196.2382256(567-580)Online publication date: 16-Oct-2012
  • (2011)Multistage Congestion Games for Wireless Real-Time StreamingGame Theory for Wireless Communications and Networking10.1201/b10975-24(429-456)Online publication date: 28-Jun-2011
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing
July 2006
230 pages
ISBN:1595933840
DOI:10.1145/1146381
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. incentives
  2. multicast
  3. non-cooperative game
  4. peer-to-peer networks

Qualifiers

  • Article

Conference

PODC06

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)3
  • Downloads (Last 6 weeks)2
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2013)Efficient and incentive-compatible resource allocation mechanism for P2P-assisted content delivery systemsFuture Generation Computer Systems10.1016/j.future.2012.08.00829:6(1611-1620)Online publication date: 1-Aug-2013
  • (2012)DCastProceedings of the 2012 ACM conference on Computer and communications security10.1145/2382196.2382256(567-580)Online publication date: 16-Oct-2012
  • (2011)Multistage Congestion Games for Wireless Real-Time StreamingGame Theory for Wireless Communications and Networking10.1201/b10975-24(429-456)Online publication date: 28-Jun-2011
  • (2011)N-party BAR TransferProceedings of the 3rd International Workshop on Theoretical Aspects of Dynamic Distributed Systems10.1145/2034640.2034647(18-22)Online publication date: 19-Sep-2011
  • (2011)Distributed computing meets game theoryACM SIGACT News10.1145/1998037.199805542:2(69-76)Online publication date: 10-Jun-2011
  • (2011)Sustaining collaboration in multicast despite rational collusionProceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing10.1145/1993806.1993872(337-338)Online publication date: 6-Jun-2011
  • (2011)A design for securing data delivery in mesh-based peer-to-peer streamingComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2011.05.01655:12(2730-2745)Online publication date: 1-Aug-2011
  • (2011)N-party BAR transferProceedings of the 15th international conference on Principles of Distributed Systems10.1007/978-3-642-25873-2_27(392-408)Online publication date: 13-Dec-2011
  • (2010)Towards securing data delivery in peer-to-peer streamingProceedings of the 2nd international conference on COMmunication systems and NETworks10.5555/1831443.1831478(327-336)Online publication date: 5-Jan-2010
  • (2010)Towards securing data delivery in peer-to-peer streaming2010 Second International Conference on COMmunication Systems and NETworks (COMSNETS 2010)10.1109/COMSNETS.2010.5431991(1-10)Online publication date: Jan-2010
  • Show More Cited By

View Options

Login options

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