We know of a multitude of situations in distributed computing where it is impossible to solve a problem deterministically but for which randomized (and in many cases, very efficient) protocols do exist. Some well-known examples are the impossibility of asynchronous distributed consensus in the presence of even one fail-stop process [1], and the impossibility of synchronous distributed consensus in less than t+1 rounds (where t is the number of faulty processes in the system). This works seeks to answer the following question: To reap the benefits of randomness in distributed computing settings, is it necessary to have perfect randomness? Can we do with imperfect randomness all that we can do with perfect randomness, and with comparable efficiency?

Progress

We answer the above question in the affirmative, for the (important) problem of distributed consensus, in a variety of settings -- synchronous/ asynchronous network models and networks with private authenticated channels/ in the full-information model. We construct distributed consensus protocols that achieve the same fault-tolerance, and are as efficient as the ones that use perfect randomness, while requiring the players to have only imperfect randomness.

Future Work

We plan to investigate if imperfect randomness suffices to solve other important distributed computing problems, such as leader election. Also, the adversarial model could be made more powerful -- in fact, there could be a continuum of adversarial models -- parametrized by how much the adversary "knows" about the randomness of the good players.

References

[1] Michael J. Fischer, Nancy A. Lynch and Mike Paterson, Impossibility of Distributed Consensus with One Faulty Process, Journal of ACM, 1985.

[2] Yevgeniy Dodis, Shien Jin Ong, Manoj Prabhakaran and Amit Sahai, On the (Im)possibility of Cryptography with Imperfect Randomness. FOCS 2004.