On the cost-ineffectiveness of redundancy in commercial P2P computing

ABSTRACT

We present a game-theoretic model of the interactions between server and clients in a constrained family of commercial P2P computations (where clients are financially compensated for work). We study the cost of implementing redundant task allocation (redundancy, for short) as a means of preventing cheating. Under the assumption that clients are motivated solely by the desire to maximize expected profit, we prove that, within this framework, redundancy is cost effective only when collusion among clients, including the Sybil attack, can be prevented. We show that in situations where this condition cannot be met, non-redundant task allocation is much less costly than redundancy.

REFERENCES

• 1: David P. Anderson, BOINC: A System for Public-Resource Computing and Storage, Proceedings of the Fifth IEEE/ACM International Workshop on Grid Computing (GRID'04), p.4-10, November 08-08, 2004 [doi>10.1109/GRID.2004.14]
• 2: David P. Anderson , Jeff Cobb , Eric Korpela , Matt Lebofsky , Dan Werthimer, SETI@home: an experiment in public-resource computing, Communications of the ACM, v.45 n.11, p.56-61, November 2002 [doi>10.1145/581571.581573]
• 3: Berkeley Open Infrastructure for Network Computing (BOINC). http://boinc.berkeley.edu
• 4: D. Bernstein. Protecting Communications Against Forgery. Algorithmic Number Theory, J. Buhler and P. Stevenhagan (Ed.), to appear 2005.
• 5: Sonja Buchegger , Jean-Yves Le Boudec, Performance analysis of the CONFIDANT protocol, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513828]
• 6: J-Y. Cai, A. Nerukar, D. Sivakumar. On the Hardness of Permanent. Proc. 16th Ann. Symp. on Theoretical Aspects of Computer Science, 1999.
• 7: Landon P. Cox , Christopher D. Murray , Brian D. Noble, Pastiche: making backup cheap and easy, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060316]
• 8: R. Dingledine, N. Mathewson, P. Syverson. Tor: The Second-Generation Onion Router. 13th USENIX Security Symp., 2004.
• 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: Distributed.net. http://www.distributed.net
• 11: EBay. http://www.ebay.com
• 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: FightAIDS@home. http://www.fightaidsathome.com
• 14: Folding@home. http://folding.stanford.edu
• 15: I. Foster and A. Iamnitchi. On Death, Taxes, and the Convergence of Peer-to-Peer and Grid Computing. 2nd Intl. Wkshp. on Peer-to-Peer Systems, 2003.
• 16: Philippe Golle , Ilya Mironov, Uncheatable Distributed Computations, Proceedings of the 2001 Conference on Topics in Cryptology: The Cryptographer's Track at RSA, p.425-440, April 08-12, 2001
• 17: Philippe Golle , Stuart G. Stubblebine, Secure Distributed Computing in a Commercial Environment, Proceedings of the 5th International Conference on Financial Cryptography, p.289-304, February 19-22, 2002
• 18: The Google Compute Project. http://www.toolbar.google.com/dc/offerdc.html
• 19: J. Gray. Distributed Computing Economics. Microsoft Research TR-2003-24, March 2003.
• 20: R. Hogg and E. Tanis. Probability and Statistical Inference, 4th Ed. Macmillan Publishing, 1993.
• 21: Ueli M. Maurer, Information-Theoretic Cryptography, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.47-64, August 15-19, 1999
• 22: J. Ledlie, J. Shneidman, M. Seltzer, J. Huth. Scooped, Again. 2nd Intl. Wkshp. on Peer-to-Peer Systems, 2003.
• 23: D. Mookherjee, I. Png. Optimal Auditing, Insurance, and Redistribution. Quarterly J. Economics 104, 399-415, 1989.
• 24: J.F. Nash. Equilibrium Points in N-Person Games. Proc. National Academy of Sciences of the United States of America (36), 1950.
• 25: J.F. Nash. Non-Cooperative Games. Annals of Mathematics (54), 1951.
• 26: M. Osborne, A. Rubenstein. A Course in Game Theory. MIT Press, 1994.
• 27: E. Rasmusen. An Introduction to Game Theory, 3rd Ed. Blackwell Publishing, 2003.
• 28: RSA Secret Key Challenge. http://www.rsasecurity.com/rsalabs/ node.asp?id=2100
• 29: K. Sanzgiri, B. Dahill, D. LaFlamme, B. N. Levine, C. Shields, E. Belding-Royer. A Secure Routing Protocol for Ad hoc Newtorks. IEEE/ACM Journal of Selected Areas in Communications: Special issue on Wireless Ad hoc Networks (JSAC), 2005.
• 30: J. Shneidman and D. Parkes. Rationality and Self-Interest in Peer to Peer Networks. 2nd Intl. Wkshp. on Peer-to-Peer Systems, 2003.
• 31: Jeffrey Shneidman , David C. Parkes, Using redundancy to improve robustness of distributed mechanism implementations, Proceedings of the 4th ACM conference on Electronic commerce, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779997]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)

General Terms:
Security, Theory

Keywords:
P2P computing, collusion, game theory, redundancy