Abstract | ||
---|---|---|
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 bitsnecessary and sufficient to elect a leader in an anonymous network of processors by a probabilisticalgorithm with overwhelming probability. Our main result is a proof that a constant number ofrandom bits is actually sufficient to elect a leader on any network of processors.Keywords: Distributed Leader... |
Year | Venue | Keywords |
---|---|---|
1997 | OPODIS | distributed computing |
Field | DocType | Citations |
Computer science,Parallel computing,Distributed algorithm,Computation,Randomness,Distributed computing | Conference | 1 |
PageRank | References | Authors |
0.35 | 4 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Bruno Codenotti | 1 | 619 | 49.92 |
Peter Gemmell | 2 | 675 | 108.87 |
Petr Pudlak | 3 | 10 | 1.04 |
Janos Simon | 4 | 368 | 50.45 |