Wait-free consensus with infinite arrivals
Authors:
Open Access
- 19 May 2002
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 524-533
Abstract
A randomized algorithm is given that solves the wait-free consensus problem for a shared-memory model with infinitely many processes. The algorithm is based on a weak shared coin algorithm that uses weighted voting to achieve a majority outcome with at least constant probability that cannot be disguised even if a strong adversary is allowed to destroy infinitely many votes. The number of operations performed by process i is a polynomial function of i. Additional algorithms are given for solving consensus more efficiently in models with an unknown upper bound b on concurrency or an unknown upper bound n on the number of active processes; under either of these restrictions, it is also shown that the problem can be solved even with infinitely many anonymous processes by prefixing each instance of the shared coin with a naming algorithm that breaks symmetry with high probability. For many of these algorithms, matching lower bounds are proved that show that their per-process work is nearly optimal as a function of i, b, or n. The case of n active processes gives an algorithm for anonymous, adaptive consensus that requires only O(n log2 n) per-process work, which is within a constant factor of the best previously known non-adaptive algorithm for a strong adversary. Finally, it is shown that standard universal constructions based on consensus continue to work with infinitely many processes with only slight modifications. This shows that in infinite distributed systems, as in finite ones, with randomness all things are possible.Keywords
This publication has 18 references indexed in Scilit:
- Time-Lapse SnapshotsSIAM Journal on Computing, 1999
- On the space complexity of randomized synchronizationJournal of the ACM, 1998
- Lower bounds for distributed coin-flipping and randomized consensusJournal of the ACM, 1998
- Wait-Free Consensus Using Asynchronous HardwareSIAM Journal on Computing, 1994
- Are wait-free algorithms fast?Journal of the ACM, 1994
- Time- and Space-Efficient Randomized ConsensusJournal of Algorithms, 1993
- Wait-free synchronizationACM Transactions on Programming Languages and Systems, 1991
- Fast randomized consensus using shared memoryJournal of Algorithms, 1990
- Impossibility of distributed consensus with one faulty processJournal of the ACM, 1985
- Reaching Agreement in the Presence of FaultsJournal of the ACM, 1980