The Paxos Register

The authors introduce the Paxos register to simplify and unify the presentation of Paxos-style consensus protocols. They use their register to show how Lamport's Classic Paxos and Castro and Liskov's Byzantine Paxos are the same consensus protocol, but for different failure models. They also use their register to compare and contrast Byzantine Paxos with Martin and Alvisi's Fast Byzantine Consensus. The Paxos register is a write-once register that exposes two important abstractions for reaching consensus: read and write operations that capture how processes in Paxos protocols propose and decide values and tokens that capture how these protocols guarantee agreement despite partial failures.