James Aspnes, Gauri Shah, and Jatin Shah. Wait-free consensus with infinite arrivals. Thirty-Fourth Annual ACM Symposium on Theory of Computing, May 2002, pp. 524–533.
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 log² 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.
@inproceedings(AspnesSS2002,
title="Wait-free consensus with infinite arrivals",
author="James Aspnes and Gauri Shah and Jatin Shah",
booktitle="Thirty-Fourth Annual ACM Symposium on Theory of Computing",
month=may,
year=2002,
pages={524--533}
)