# Wait-free consensus with infinite arrivals

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.

## 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
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.

- STOC '02 proceedings version:
**PDF**.

## BibTeX

Download@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}
)

Consolidated BibTeX file

Return to James Aspnes's publications

Return to James Aspnes's home page