Solving Consensus: A Survey of Techniques for Doing the Impossible

James Aspnes (Yale), Prasad Jayanti (Dartmouth), Sam Toueg (Cornell)

The famous Fischer, Lynch, and Paterson impossibility proof shows that
it is impossible to solve the consensus problem in natural model of an
asynchronous distributed system if even a single process can fail. We
survey nearly two decades of work on consensus algorithms that avoid
this impossibility result by using extended models that provide either
(a) randomization, (b) failure detectors, or (c) stronger
synchronization mechanisms than are available in the basic model.