On the Amount of Randomness Needed in Distributed Computations.
Bruno Codenotti, Peter S. Gemmell, Petr Pudlák, Janoš Šimon · 1997
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 with overwhelming probability. Our main result is a proof that a constant number of random bits is actually sufficient to elect a leader on any network of processors. Keywords: Distributed Leader Election, Anonymous Networks, Symmetry Breaking, Randomized Algorithm. Correspondence: Bruno Codenotti, IMC-CNR, Via S.Maria, 46, 56126-Pisa (Italy). E-mail: [email protected]. Istituto di Matematica Computazionale del CNR, Pisa, Italy. Partially supported by ESPRIT Basic Research Action, Project 9072 'GEPPCOM'. e-mail:[email protected] y Sandia National Laboratories. e-mail: [email protected]. z Mathematical Institute, AV CR, Prague, Czech Republic. e-mail: [email protected]. x ...