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,
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.
This research is supported in part by an NSF grant CNS-0430450.
 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.
 Pesech Feldman and Silvio Micali. An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement. In SIAM Journal of Computing, pp 873--933, 1997.
 Michael Fischer and Nancy Lynch. A Lower Bound for the Time to Assure Interactive Consistency. In Information Processing Letters, pp 183--186, 1982.
 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.
 Shafi Goldwasser and Vinod Vaikuntanathan. Authenticated Byzantine Agreement in O(log n) Rounds Tolerating a Majority of Faults. In Preparation.