Complexity Digest 2001.22 - 18
28-May-2001
The Search For E.T. Yields Earthly Cheats, NY Times
Abstract: Computationally expensive tasks
that can be parallelized are most efficiently completed by
distributing the computation among a large number of processors.
The growth of the Internet has made it possible to invite the
participation of just about any computer in such distributed
computations. This introduces the potential for cheating by
untrusted participants. In a commercial setting where participants
get paid for their contribution, there is incentive for dishonest
participants to claim credit for work they have not done. In this
paper, we propose security schemes that defend against this threat
with very little overhead. Our weaker scheme discourages cheating
by ensuring that it does not pay off, while our stronger schemes
let participants prove that they have done (almost) all the work
they were assigned with high probability.