Overcoming free-riding behavior in peer-to-peer systems

ABSTRACT

While the fundamental premise of peer-to-peer (P2P) systems is that of voluntary resource sharing among individual peers, there is an inherent tension between individual rationality and collective welfare that threatens the viability of these systems. This paper surveys recent research at the intersection of economics and computer science that targets the design of distributed systems consisting of rational participants with diverse and selfish interests. In particular, we discuss major findings and open questions related to free-riding in P2P systems: factors affecting the degree of free-riding, incentive mechanisms to encourage user cooperation, and challenges in the design of incentive mechanisms for P2P systems.

REFERENCES

• 1: Adar, E. and Huberman, B. A. (2000). Free Riding on Gnutella. First Monday, 5(10).
• 2: Aditya Akella , Srinivasan Seshan , Richard Karp , Scott Shenker , Christos Papadimitriou, Selfish behavior and stability of the internet:: a game-theoretic analysis of TCP, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 3: Nazareno Andrade , Miranda Mowbray , Aliandro Lima , Gustavo Wagner , Matei Ripeanu, Influences on cooperation in BitTorrent communities, Proceeding of the 2005 ACM SIGCOMM workshop on Economics of peer-to-peer systems, August 22-22, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080192.1080198]
• 4: Andreoni, J. (1989). Giving with Impure Altruism: Applications to Charity and Ricardian Equivalence. Journal of Political Economy, 97(6):1447-58.
• 5: Buchegger, S. and LeBoudec, J.-Y. (2004). A Robust Reputation System for Peer-to-Peer and Mobile Ad-Hoc Networks. In Workshop on Economics of Peer-to-Peer Systems.
• 6: Levente Buttyán , Jean-Pierre Hubaux, Enforcing service availability in mobile ad-hoc WANs, Proceedings of the 1st ACM international symposium on Mobile ad hoc networking & computing, November 20, 2000, Boston, Massachusetts
• 7: Camerer, C. F. (2003). Behavioral Game Theory. Princeton University Press.
• 8: Castro, M., Druschel, P., Ganesh, A., Rowstron, A., and Wallach, D. S. (2002). Security for Structured Peer-to-Peer Overlay Networks. In Proceedings of Multimedia Computing and Networking 2002 (MMCN '02).
• 9: Miguel Castro , Peter Druschel , Anne-Marie Kermarrec , Animesh Nandi , Antony Rowstron , Atul Singh, SplitStream: high-bandwidth multicast in cooperative environments, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 10: Alice Cheng , Eric Friedman, Sybilproof reputation mechanisms, Proceeding of the 2005 ACM SIGCOMM workshop on Economics of peer-to-peer systems, August 22-22, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080192.1080202]
• 11: Christin, N. and Chuang, J. (2005). A cost-based analysis of overlay routing geometries. In IEEE INFOCOM.
• 12: Nicolas Christin , Jens Grossklags , John Chuang, Near rationality and competitive equilibria in networked systems, Proceedings of the ACM SIGCOMM workshop on Practice and theory of incentives in networked systems, September 03-03, 2004, Portland, Oregon, USA [doi>10.1145/1016527.1016536]
• 13: Yang-hua Chu , John Chuang , Hui Zhang, A case for taxation in peer-to-peer streaming broadcast, Proceedings of the ACM SIGCOMM workshop on Practice and theory of incentives in networked systems, September 03-03, 2004, Portland, Oregon, USA [doi>10.1145/1016527.1016535]
• 14: Byung-Gon Chun , Kamalika Chaudhuri , Hoeteck Wee , Marco Barreno , Christos H. Papadimitriou , John Kubiatowicz, Selfish caching in distributed systems: a game-theoretic analysis, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011771]
• 15: Clarke, E. (1971). Multipart Pricing of Public Goods. Public Choice, 1:17-33.
• 16: Cohen, B. (2003). Incentives build robustness in bittorrent. In Workshop on Economics of Peer-to-Peer Systems.
• 17: Cole, R., Dodis, Y., and TimRoughgarten (2003). Pricing Networks with Selfish Routing. In Workshop on Economics of Peer-to-Peer Systems.
• 18: Chrysanthos Dellarocas, Immunizing online reputation reporting systems against unfair ratings and discriminatory behavior, Proceedings of the 2nd ACM conference on Electronic commerce, p.150-157, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352889]
• 19: Dellarocas, C. and Resnick, P. (2003). Online Reputation Mechanisms: A Roadmap for Future Research. Summary Report of the First Interdisciplinary Symposium on Online Reputation Mechanisms. In Workshop on economics of peer-to-peer networks.
• 20: John R. Douceur, The Sybil Attack, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.251-260, March 07-08, 2002
• 21: Alex Fabrikant , Ankur Luthra , Elitza Maneva , Christos H. Papadimitriou , Scott Shenker, On a network creation game, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.347-351, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872088]
• 22: Joan Feigenbaum , Christos Papadimitriou , Rahul Sami , Scott Shenker, A BGP-based mechanism for lowest-cost routing, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571856]
• 23: Joan Feigenbaum , Christos H. Papadimitriou , Scott Shenker, Sharing the cost of multicast transmissions, Journal of Computer and System Sciences, v.63 n.1, p.21-41, August 2001 [doi>10.1006/jcss.2001.1754]
• 24: Joan Feigenbaum , Scott Shenker, Distributed algorithmic mechanism design: recent results and future directions, Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570810.570812]
• 25: Michal Feldman , John Chuang, The Evolution of Cooperation under Cheap Pseudonyms, Proceedings of the Seventh IEEE International Conference on E-Commerce Technology (CEC'05), p.284-291, July 19-22, 2005 [doi>10.1109/ICECT.2005.91]
• 26: Michal Feldman , John Chuang , Ion Stoica , Scott Shenker, Hidden-action in multi-hop routing, Proceedings of the 6th ACM conference on Electronic commerce, p.117-126, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064022]
• 27: Michal Feldman , Kevin Lai , Ion Stoica , John Chuang, Robust incentive techniques for peer-to-peer networks, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988788]
• 28: Michal Feldman , Christos Papadimitriou , John Chuang , Ion Stoica, Free-riding and whitewashing in peer-to-peer systems, Proceedings of the ACM SIGCOMM workshop on Practice and theory of incentives in networked systems, September 03-03, 2004, Portland, Oregon, USA [doi>10.1145/1016527.1016539]
• 29: Pedro Ferreira , Marvin Sirbu, Inefficiency in provisioning interconnected communication networks, Proceedings of the 6th ACM conference on Electronic commerce, p.137-146, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064024]
• 30: Friedman, E. and Resnick, P. (1998). The Social Cost of Cheap Pseudonyms. Journal of Economics and Management Strategy, 10(2):173-199.
• 31: Friedman, E. and Shenker, S. (1997). Learning and implementation on the internet. In Manuscript. New Brunswick: Rutgers University, Department of Economics.
• 32: Philippe Golle , Kevin Leyton-Brown , Ilya Mironov, Incentives for sharing in peer-to-peer networks, Proceedings of the 3rd ACM conference on Electronic Commerce, p.264-267, October 14-17, 2001, Tampa, Florida, USA [doi>10.1145/501158.501193]
• 33: Groves, T. (1973). Incentives in Teams. Econometrica, 41:617-663.
• 34: Minaxi Gupta , Paul Judge , Mostafa Ammar, A reputation system for peer-to-peer networks, Proceedings of the 13th international workshop on Network and operating systems support for digital audio and video, June 01-03, 2003, Monterey, CA, USA [doi>10.1145/776322.776346]
• 35: Daniel Hughes , Geoff Coulson , James Walkerdine, Free Riding on Gnutella Revisited: The Bell Tolls?, IEEE Distributed Systems Online, v.6 n.6, p.1, June 2005 [doi>10.1109/MDSO.2005.31]
• 36: Jakobsson, M., Hubaux, J.-P., and Buttyan, L. (2003). A Micro-Payment Scheme Encouraging Collaboration in Multi-Hop Cellular Networks. In Financial Cryptography.
• 37: Seung Jun , Mustaque Ahamad, Incentives in BitTorrent induce free riding, Proceeding of the 2005 ACM SIGCOMM workshop on Economics of peer-to-peer systems, August 22-22, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080192.1080199]
• 38: Radu Jurca , Boi Faltings, Reputation-based pricing of P2P services, Proceeding of the 2005 ACM SIGCOMM workshop on Economics of peer-to-peer systems, August 22-22, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080192.1080206]
• 39: Sepandar D. Kamvar , Mario T. Schlosser , Hector Garcia-Molina, The Eigentrust algorithm for reputation management in P2P networks, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775242]
• 40: Morselli, R., Katz, J., and Bhattacharjee, B. (2004). A game-theoretic framework for analyzing trust-inference protocols. In 2nd Workshop on Economics of Peer-to-Peer Systems.
• 41: Ngan, T.-W. J., Wallach, D. S., and Druschel, P. (2004). Incentive-compatible peer-to-peer multicast. In Workshop on Economics of Peer-to-Peer Systems.
• 42: Noam Nisan , Amir Ronen, Algorithmic mechanism design (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.129-140, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301287]
• 43: Rosenschein, J. S. and Zlotkin, G. (1994). Rules of Encounter. MIT Press.
• 44: Saroiu, S., Gummadi, P. K., and Gribble, S. D. (2002). A Measurement Study of Peer-to-Peer File Sharing Systems. In Proceedings of Multimedia Computing and Networking 2002 (MMCN '02).
• 45: Shneidman, J. and Parkes, D. C. (2004). Overcoming rational manipulation in mechanism implementation.
• 46: Varian, H. R. (1995). Economic Mechanism Design for Computerized Agents. In Proc. of Usenix Workshop on Electronic Commerce.
• 47: Vickrey, W. (1961). Counterspeculation, Auctions, and Competitive Sealed Tenders. Journal of Finance, 16:8-37.
• 48: Bin Yu , Munindar P. Singh, A Social Mechanism of Reputation Management in Electronic Communities, Proceedings of the 4th International Workshop on Cooperative Information Agents IV, The Future of Information Agents in Cyberspace, p.154-165, July 07-09, 2000
• 49: Zhong, S., Chen, J., and Yang, Y. R. (2003). Sprite: A Simple, Cheat-Proof, Credit-Based System for Mobile Ad-Hoc Networks. In 22nd Annual Joint Conference of the IEEE Computer and Communications Societies.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Data sharing

  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.4 System Management

General Terms:
Design, Economics, Management, Theory

Keywords:
algorithms, cooperation, design, economics, game-theory, hidden-action, hidden-information, incentives, peer-to-peer, performance, reliability