﻿ Butler Lampson - The ABCDs of Paxos

The ABCDs of Paxos

Butler W. Lampson


Citation. Presented at Principles of Distributed Computing, 2001, as one of the papers celebrating Leslie Lamport’s 60th birthday.

Links: Abstract, Acrobat, Web page, Word. Slides for a talk are here.




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.