The ABCDs of Paxos
Citation. Presented at Principles
of Distributed Computing, 2001, as one of the papers celebrating
Links: Abstract, Acrobat, Web page, Word. Slides for a talk are here.
Email: blampson@microsoft.com. This paper is at http://research.microsoft.com.
Abstract:
We
explain how consensus is used to implement replicated state machines, the
general mechanism for fault-tolerance. We describe an abstract version of
Lamport’s Paxos algorithm for asynchronous consensus. Then we derive the Byzantine,
classic, and disk versions of Paxos from the abstract one, show how they are
related to each other, and discuss the safety, liveness, and performance of
each one.