Robust incentive techniques for peer-to-peer networks

ABSTRACT

Lack of cooperation (free riding) is one of the key problems that confronts today's P2P systems. What makes this problem particularly difficult is the unique set of challenges that P2P systems pose: large populations, high turnover, a symmetry of interest, collusion, zero-cost identities, and traitors. To tackle these challenges we model the P2P system using the Generalized Prisoner's Dilemma (GPD),and propose the Reciprocative decision function as the basis of a family of incentives techniques. These techniques are fullydistributed and include: discriminating server selection, maxflow-based subjective reputation, and adaptive stranger policies. Through simulation, we show that these techniques can drive a system of strategic users to nearly optimal levels of cooperation.

REFERENCES

• 1: Kazaa. http://www.kazaa.com.
• 2: Limewire. http://www.limewire.com.
• 3: ADAR, E., AND HUBERMAN, B. A. Free Riding on Gnutella. First Monday 5, 10 (October 2000).
• 4: AXELROD,R.The Evolution of Cooperation. Basic Books, 1984.
• 5: Chiranjeeb Buragohain , Divyakant Agrawal , Subhash Suri, A Game Theoretic Framework for Incentives in P2P Systems, Proceedings of the 3rd International Conference on Peer-to-Peer Computing, p.48, September 01-03, 2003
• 6: CASTRO, M., DRUSCHEL,P.,GANESH, A., ROWSTRON, A., AND WALLACH, D. S. Security for Structured Peer-to-Peer Overlay Networks. In Proceedings of Multimedia Computing and Networking 2002 (MMCN '02) (2002).
• 7: COHEN, B. Incentives build robustness in bittorrent. In 1st Workshop on Economics of Peer-to-Peer Systems (2003).
• 8: CROWCROFT, J., GIBBENS, R., KELLY,F.,AND OSTRING,S. Modeling Incentives for Collaboration in Mobile Ad Hoc Networks. In Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (2003).
• 9: 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
• 10: 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]
• 11: 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]
• 12: 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]
• 13: FRIEDMAN, E., AND RESNICK, P. The Social Cost of Cheap Pseudonyms. Journal of Economics and Management Strategy 10,2 (1998), 173---199.
• 14: FUDENBERG, D., AND LEVINE,D.K.The Theory of Learning in Games. The MIT Press, 1999.
• 15: 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]
• 16: GROSS, B., AND ACQUISTI, A. Balances of Power on EBay: Peers or Unquals? In Workshop on economics of peer-to-peer networks (2003).
• 17: GU, B., AND JARVENPAA, S. Are Contributions to P2P Technical Forums Private or Public Goods? -- An Empirical Investigation. In 1st Workshop on Economics of Peer-to-Peer Systems (2003).
• 18: HARDIN, G. The Tragedy of the Commons. Science 162 (1968), 1243---1248.
• 19: JOSEF HOFBAUER AND KARL SIGMUND. Evolutionary Games and Population Dynamics. Cambridge University Press, 1998.
• 20: 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]
• 21: KAN, G. Peer-to-Peer: Harnessing the Power of Disruptive Technologies, 1st ed. O'Reilly & Associates, Inc., March 2001, ch. Gnutella, pp. 94--122.
• 22: KUHN, S. Prisoner's Dilemma. In The Stanford Encyclopedia of Philosophy, Edward N. Zalta, Ed., Summer ed. 2003.
• 23: LEE, S., SHERWOOD, R., AND BHATTACHARJEE, B. Cooperative Peer Groups in Nice. In Proceedings of the IEEE INFOCOM (2003).
• 24: LEVIEN, R., AND AIKEN, A. Attack-Resistant Trust Metrics for Public Key Certification. In Proceedings of the USENIX Security Symposium (1998), pp. 229--242.
• 25: Petros Maniatis , David S. H. Rosenthal , Mema Roussopoulos , Mary Baker , TJ Giuli , Yanto Muliadi, Preserving peer replicas by rate-limited sampled voting, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 26: Sergio Marti , T. J. Giuli , Kevin Lai , Mary Baker, Mitigating routing misbehavior in mobile ad hoc networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.255-265, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345955]
• 27: MICHIARDI,P.,AND MOLVA, R. A Game Theoretical Approach to Evaluate Cooperation Enforcement Mechanisms in Mobile Ad Hoc Networks. In Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (2003).
• 28: NOWAK, M. A., AND SIGMUND, K. Evolution of Indirect Reciprocity by Image Scoring. Nature 393 (1998), 573--577.
• 29: OLSON, M. The Logic of Collective Action: Public Goods and the Theory of Groups. Harvard University Press, 1971.
• 30: RAGHAVAN, B., AND SNOEREN, A. Priority Forwarding in Ad Hoc Networks with Self-Ineterested Parties. In Workshop on Economics of Peer-to-Peer Systems (June 2003).
• 31: RANGANATHAN, K., RIPEANU, M., SARIN, A., AND FOSTER, I. To Share or Not to Share: An Analysis of Incentives to Contribute in Collaborative File Sharing Environments. In Workshop on Economics of Peer-to-Peer Systems (June 2003).
• 32: Michael K. Reiter , Stuart G. Stubblebine, Authentication metric analysis and design, ACM Transactions on Information and System Security (TISSEC), v.2 n.2, p.138-158, May 1999 [doi>10.1145/317087.317088]
• 33: SAROIU, S., GUMMADI, P. K., AND GRIBBLE, S. D. A Measurement Study of Peer-to-Peer File Sharing Systems. In Proceedings of Multimedia Computing and Networking 2002 (MMCN '02) (2002).
• 34: SMITH, J. M. Evolution and the Theory of Games. Cambridge University Press, 1982.
• 35: URPI, A., BONUCCELLI, M., AND GIORDANO, S. Modeling Cooperation in Mobile Ad Hoc Networks: a Formal Description of Selfishness. In Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (2003).
• 36: VISHNUMURTHY, V., CHANDRAKUMAR, S., AND SIRER, E. G. KARMA: A Secure Economic Framework for P2P Resource Sharing. In Workshop on Economics of Peer-to-Peer Networks (2003).
• 37: WANG, W., AND LI, B. To Play or to Control: A Game-based Control-Theoretic Approach to Peer-to-Peer Incentive Engineering. In International Workshop on Quality of Service (June 2003).
• 38: WOODARD, C. J., AND PARKES, D. C. Strategyproof mechanisms for ad hoc network formation. In Workshop on Economics of Peer-to-Peer Systems (June 2003).

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Design, Economics

Keywords:
cheap pseudonyms, collusion, free-riding, incentives, peer-to-peer, prisoners dilemma, reputation, whitewash