On the Amount of Randomness Needed in Distributed Computations

We treat the number of random bits as a computational resource in distributed computations. We give a concrete application of these ideas by characterizing the number of random bits necessary and sufficient to elect a leader in an anonymous network of processors by a probabilistic algorithm. 1 Introduction The use of randomness in distributed computing is a powerful technique that has been fruitful in diverse settings. There are many situations where the use of randomized algorithms provably helps. For problems like mutual exclusion [15], ring orientation [7], or leader election in highly symmetric networks [3], it is known that no deterministic algorithm can provide a solution, while there are simple and elegant randomized algorithms. In other situations, like routing [17] [10], or Byzantine agreement [12] randomized algorithms provide provably better performance than deterministic ones. However, we do not know how to obtain efficiently the necessary randomness to implement probabili..