Randomized protocols for asynchronous consensus

James Aspnes. Randomized protocols for asynchronous consensus. Invited survey paper for Distributed Computing PODC 20th anniversary issue, 16:(2–3):165–175, September 2003. Available as arXiv:cs.DS/0209014.

Abstract

The famous Fischer, Lynch, and Paterson impossibility proof shows that it is impossible to solve the consensus problem in a natural model of an asynchronous distributed system if even a single process can fail. Since its publication, two decades of work on fault-tolerant asynchronous consensus algorithms have evaded this impossibility result by using extended models that provide (a) randomization, (b) additional timing assumptions, (c) failure detectors, or (d) stronger synchronization mechanisms than are available in the basic model. Concentrating on the first of these approaches, we illustrate the history and structure of randomized asynchronous consensus protocols by giving detailed descriptions of several such protocols.

BibTeX

Download
@article(Aspnes2003,
title="Randomized protocols for asynchronous consensus",
author="James Aspnes",
journal="Distributed Computing",
volume=16,
number={2--3},
pages={165--175},
month=sep,
year=2003
)

Consolidated BibTeX file
Return to James Aspnes's publications
Return to James Aspnes's home page