Fast Deterministic Consensus in a Noisy Environment
James Aspnes
To appear at Nineteenth Annual
ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC
2000), Portland, Oregon, 16-19 July 2000
Abstract
It is well known that the consensus problem cannot be solved deterministically
in an asynchronous environment, but that randomized solutions are possible.
We propose a new model we call noisy scheduling in which an adversarial
schedule is perturbed randomly, and show that in this model randomness
in the environment can substitute for randomness in the algorithm. In particular,
we show that a simplified, deterministic version of Chandra's wait-free
shared-memory consensus algorithm solves consensus in time at most logarithmic
in the number of active processes. The proof of termination is based on
showing that a race between independent delayed renewal processes produces
a winner quickly. In addition, we show that the protocol finishes in constant
time using quantum and priority-based scheduling on a uniprocessor, suggesting
that it is robust against the choice of model over a wide range.