If the final outcome doesn't need to be perfectly unbiased, but instead may have a bias of up to say 10 percent, then there are good algorithms, even if the people have unlimited computational power (which renders cryptographic methods ineffective). For example, the following baton-passing algorithm works well. At the start, give the baton to an arbitrary person (say the first person). At each step, the current baton-holder gives the baton to a random person who has not yet held the baton. Whoever receives the baton last gets to make the collective coin flip.
If the number of saboteurs is fewer than $n / log n$, then this algorithm is known to produce a low-biased coin. Mike Saks proposed and analyzed this algorithm, and Miki Ajtai and Nati Linial refined the analysis. Here are the references:
M. Saks (1989), A robust non-cryptographic protocol for collective coin flipping, SIAM Journal on Discrete Mathematics 2, pages 240-244.
M. Ajtai and N. Linial (1993), The influence of large coalitions, Combinatorica 13, pages 129-145.
You can find a scanned copy of the Ajtai-Linial paper at Linial's homepage:
http://www.cs.huji.ac.il/~nati/.
Babu Narayanan and I showed that there exists an algorithm that can handle up to 49 percent of the players being saboteurs and yet still produces a low-biased coin. Here is the reference:
R. Boppana and B. Narayanan (2000), Perfect-Information Leader Election with Optimal Resilience, SIAM Journal on Computing 29:4, pages 1304-1320.
No comments:
Post a Comment