Paxos a very part-time parliament
Paxos a part time parliament published in 1998 by Leslie Lamport is the one of the landmark white papers on distributed consensus. It's the backbone of many modern systems, from databases to cloud services. Being seminal doesn't mean it's easy to understand. Nor does it mean the white paper describing it was well written. It notoriously isn't, but as a foundational work it is useful for anyone trying to understand both the history and theory of distributed systems.
White Papers
Various papers that can help with understanding as we go through the protocol.
Paxos Papers
The Part‑Time Parliament
Lamport's original paper wrapped in an allegory about an ancient Greek
parliament. It's dense and and rambling, with some brilliant insights
along with asides that add nothing. But that's why this website
exists.
Paxos The
Part‑Time Parliament ↗
Paxos Made Simple
After watching thousands struggle with his first paper, Lamport tried
to simplify it but just ended up writing math proofs with no
explination. Math PHDs please read, normal computer science people
try, but it's not you.
Get the
"Simple" Version ↗
From Theory to Practice
Paxos Made Moderately Complex
The perfect bridge between academic theory and real-world code. This
paper pulls back the curtain on the engineering details you'll
actually need when building production systems. It reads like a
commented walkthrough of how to actually implemented paxos for a
production system.
Paxos Made Moderately
Complex ↗
Paxos Made Practical
This paper digs into the operational challenges, failure modes, and
pragmatic choices you'll face when deploying Paxos in the wild.
Essential reading if you're thinking about actually using this in
production.
Paxos Made Practical ↗
Other distributed systems algorithms
In Search of an Understandable Consensus Algorithm (Raft)
The paper that asked: "Does consensus really need to be this hard?"
Raft was designed with understandability as a first-class concern, and
it shows. It became wildly popular for good reason.
Raft ↗
Viewstamped Replication
Developed independently around the same time as Paxos, It's another
foundational consensus algorithm—a perfect example of how similar
solutions emerge from the same hard problems.
Viewstamped Replication
↗
Foundational Antecedent Papers
Fischer-Lynch-Paterson (FLP) Impossibility
The theoretical bedrock. FLP proves that perfect consensus is
mathematically impossible in a fully asynchronous system where any
single node can fail. This is why Paxos has to be so clever—it's
working around an actual impossibility proof.
FLP ↗