Research Abstracts - 2006

Randomness in Distributed Algorithms

Shafi Goldwasser & Vinod Vaikuntanathan

Randomness is a critical resource in many computational scenarios, enabling solutions where deterministic ones are elusive or even provably impossible. In algorithm design, randomness has been shown to reduce the complexity requirments for solving problems, but it is unclear whether the use of randomization is inherently necessary. The case of using randomness within the field of distributed computing is, in contrast, unambiguous. There are central distributed computing problems for which it is (provably) impossible to obtain a deterministic solution, whereas efficient randomized solutions exist. Even for tasks that can be solved using deterministic algorithms, employing randomness dramatically improves the efficiency of the solution. In this project, we seek to understand the precise nature of randomness that makes it so useful in distributed algorithms.

Specifically, we address the following two issues.

Efficiency of Randomized Distributed Algorithms

We consider the problem of Byzantine Agreement, which is probably the most important problem in distributed computation tolerating faulty behavior. Informally, the problem is to maintain a common view of the world in the presence of faulty processes that strive to prevent the good processes from reaching agreement. Randomization has proven to be a powerful technique to overcome the (provable) limitations of deterministic algorithms in solving Byzantine Agreement. In particular,

• It is known that no deterministic algorithm can solve Byzantine Agreement among n processes tolerating t faults in a synchronous fully-connected network, in less than t+1 rounds of communication [3]. Randomization allows us to overcome this lower bound -- using randomization combined with cryptographic techniques, Feldman and Micali [2] showed a Byzantine Agreement protocol that runs in expected O(1) communication rounds. The question of whether the use of cryptography is necessary to achieve this bound remained open. The best known Byzantine Agreement protocol that did not use cryptographic techniques had a complexity of O(n/log n) rounds, and dates back to 1986.

  In joint work with Michael Ben-Or and Elan Pavlov [1], we construct an O(log n) round randomized protocol that solves Byzantine Agreement against computationally unbounded adversaries that can corrupt upto a linear fraction of bad players. We do not place any restrictions on the computational power of the faulty players (this precludes the use of cryptography) or the information available to them (this precludes the use of secret-sharing techniques). In particular, the faulty players may be infinitely powerful, and they can observe all communication among the honest players.

• It is known that without cryptographic techniques or some form of preprocessing, Byzantine Agreement is not possible if the number t of faulty players is more than n/3 (even if randomization is allowed). One way to overcome this lower bound is to use digital signatures as an authentication mechanism. Dolev and Strong, in 1982, constructed a Byzantine Agreement protocol that tolerated any t faulty players as long as t < n, and runs in t+1 communication rounds. We construct a Byzantine Agreement protocol that tolerates t < (1-ε)n faults and runs in O(log n + 1/ε) rounds.

Quality of Randomness Necessary for Distributed Algorithms

The randomized distributed algorithms discussed above assume access to a source of unbiased, independent coins. Physical sources of randomness, on the other hand, are rarely unbiased and independent although they do seem to exhibit somewhat imperfect randomness. This gap in modeling questions the relevance of current randomized solutions to computational tasks.

We ask whether imperfect randomness, modeled appropriately, is "good enough" for distributed algorithms. Namely, can we do with imperfect randomness all that we can do with perfect randomness, and with comparable efficiency ? We answer this question in the affirmative, for some natural models of imperfect randomness in a distributed setting. Our solutions are essentially as efficient as the best known randomized agreement protocols, despite the defects in the randomness. Specifically, our model postulates that each player has a general weak source of randomness (as defined by Zuckerman), and the sources of any two players are independent.

In future work, we investigate whether the independence assumption is necessary to achieve strong results such as in the previous paragraph.

Research Support

This research is supported in part by an NSF grant CNS-0430450.

References:

[1] Michael Ben-Or, Elan Pavlov and Vinod Vaikuntanathan. Byzantine Agreement in the Full-Information Model in O(log n) Rounds. To Appear in The Proceedings of the ACM Symposium on the Theory of Computing, Seattle, USA, May 2006.

[2] Pesech Feldman and Silvio Micali. An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement. In SIAM Journal of Computing, pp 873--933, 1997.

[3] Michael Fischer and Nancy Lynch. A Lower Bound for the Time to Assure Interactive Consistency. In Information Processing Letters, pp 183--186, 1982.

[4] Shafi Goldwasser, Madhu Sudan and Vinod Vaikuntanathan. Distributed Computing with Imperfect Randomness. In The Proceedings of the International Conference on Distributed Computing, DISC 2005, pp. 288--302 , Krakow, Poland, September 2005.

[5] Shafi Goldwasser and Vinod Vaikuntanathan. Authenticated Byzantine Agreement in O(log n) Rounds Tolerating a Majority of Faults. In Preparation.