Incentivizing outsourced computation

ABSTRACT

We describe different strategies a central authority, the boss, can use to distribute computation to untrusted contractors. Our problem is inspired by volunteer distributed computing projects such as SETI@home, which outsource computation to large numbers of participants. For many tasks, verifying a task's output requires as much work as computing it again; additionally, some tasks may produce certain outputs with greater probability than others. A selfish contractor may try to exploit these factors, by submitting potentially incorrect results and claiming a reward. Further, malicious contractors may respond incorrectly, to cause direct harm or to create additional overhead for result-checking.

We consider the scenario where there is a credit system whereby users can be rewarded for good work and fined for cheating. We show how to set rewards and fines that incentivize proper behavior from rational contractors, and mitigate the damage caused by malicious contractors. We analyze two strategies: random double-checking by the boss, and hiring multiple contractors to perform the same job.

We also present a bounty mechanism when multiple contractors are employed; the key insight is to give a reward to a contractor who catches another worker cheating. Furthermore, if we can assume that at least a small fraction h of the contractors are honest (1% - 10%), then we can provide graceful degradation for the accuracy of the system and the work the boss has to perform. This is much better than the Byzantine approach, which typically assumes h > 60%.

REFERENCES

• 1: Amitanand S. Aiyer , Lorenzo Alvisi , Allen Clement , Mike Dahlin , Jean-Philippe Martin , Carl Porth, BAR fault tolerance for cooperative services, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 2: Mira Belenkiy , Melissa Chase , C. Chris Erway , John Jannotti , Alptekin Küpçü , Anna Lysyanskaya , Eric Rachlin, Making p2p accountable without losing privacy, Proceedings of the 2007 ACM workshop on Privacy in electronic society, October 29-29, 2007, Alexandria, Virginia, USA [doi>10.1145/1314333.1314339]
• 3: M. Belenkiy, M. Chase, C. Erway, J. Jannotti, A. Küpçü, and A. Lysyanskaya. Incentivizing Outsourced Computation. Technical Report CS-08-03, Brown University Dep't of Computer Science, June 2008.
• 4: BOINC. http://boinc.berkeley.edu.
• 5: Distributed.net. http://www.distributed.net.
• 6: 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
• 7: Kevin Lai , Lars Rasmusson , Eytan Adar , Li Zhang , Bernardo A. Huberman, Tycoon: An implementation of a distributed, market-based resource allocation system, Multiagent and Grid Systems, v.1 n.3, p.169-182, August 2005
• 8: Harry C. Li , Allen Clement , Edmund L. Wong , Jeff Napper , Indrajit Roy , Lorenzo Alvisi , Michael Dahlin, BAR Gossip, Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation, p.14-14, November 06-08, 2006, Seattle, WA
• 9: David Molnar. The SETI@Home problem. ACM Crossroads, Sep 2000.
• 10: F. Monrose, P. Wyckoff, and A. Rubin. Distributed execution with remote audit. ISOC NDSS, 1999.
• 11: Patch-free-processing. http://web.archive.org/web/20070207064618/http://home.hccnet.nl/a.alfred/p-free-p1pfp.html.
• 12: Anatol Rapoport. Prisoner's dilemma - recollections and observations. Game Theory as a Theory of Conflict Resolution, 1974.
• 13: Ori Regev , Noam Nisan, The POPCORN market.: online markets for computational resources, Decision Support Systems, v.28 n.1-2, p.177-189, March 2000 [doi>10.1016/S0167-9236(99)00067-6]
• 14: Rosetta@home. http://boinc.bakerlab.org/rosetta/.
• 15: Seti@home. http://setiathome.berkeley.edu.
• 16: truXoft Calibrating BOINC Core Client. http://boinc.truxoft.com/core-cal.htm.
• 17: Carl A. Waldspurger , Tad Hogg , Bernardo A. Huberman , Jeffrey O. Kephart , W. Scott Stornetta, Spawn: A Distributed Computational Economy, IEEE Transactions on Software Engineering, v.18 n.2, p.103-117, February 1992 [doi>10.1109/32.121753]

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

General Terms:
Design, Economics, Performance, Security

Keywords:
currency, distributed computation, incentives, outsourcing