Paxos Made Simple

✨ Summary

Summary

Lamport presents Paxos as a consensus protocol for asynchronous, non-Byzantine distributed systems in which processes may fail, restart, or experience message loss and delay. The protocol separates proposers, acceptors, and learners; uses uniquely numbered proposals; establishes safety through majority quorums and the invariant that higher-numbered proposals preserve the value of an already chosen proposal; and uses prepare and accept phases to coordinate decisions. Persistent storage is required for acceptors to retain promises and accepted proposals across failures. Liveness is not guaranteed by the consensus protocol alone and requires a distinguished proposer or leader, typically selected using timeouts or randomness. The paper also shows how repeated Paxos instances implement a replicated state machine, including command sequencing, no-op gap filling, leader replacement, and reconfiguration.

The paper became a concise reference description of Paxos and influenced subsequent consensus research. Later work developed variants such as Cheap Paxos and Fast Paxos, addressing processor requirements and message-delay trade-offs. (microsoft.com) Google’s engineering report describes using Paxos to build a fault-tolerant database and documents the additional engineering mechanisms required in production, including handling storage, membership, snapshots, and command logs. (research.google) Raft explicitly positions itself as an alternative to Multi-Paxos, retaining comparable fault tolerance and efficiency while restructuring the protocol to improve understandability and practical implementation. (usenix.org) Subsequent formal-specification work has also used Paxos and its variants as case studies for executable specifications and machine-checked safety proofs. (arxiv.org)