Paxos Made Simple
Consensus derived from its own invariants in nine pages - and the log everyone actually builds sketched in the last two.
Read the original ↗A nine-page note with a one-sentence abstract, written because the 1998 version had not landed. It is the shortest complete statement of how a group of machines agrees on one value - and it is not the reason anybody finds Paxos hard.
Included with a plan
This discussion is included with a plan. The first three lessons of every track are free, with their boards and videos. A plan unlocks every lesson, board, video, lab and paper for one price.
Related on chalk
The same idea as a board, lab, video or lesson.
- BoardWho Holds the Penmajority overlap and the epoch number, which are the paper's two mechanisms with different names
- BoardConsistency and Consensustotal order broadcast as repeated consensus, and FLP - the reason the paper can promise safety and not termination
- BoardLeader Electionthe lease that gets a distinguished proposer elected, which is the liveness half the paper leaves to you
- BoardThe Two Ledgers Must Agreetwo-phase commit blocks when the coordinator dies; this is the protocol that does not
- BoardReplication and Durabilitythe ISR, which commits on all of a shrinking set rather than a majority of a fixed one - the deliberate refusal of this paper's quorum
- LabWho holds the penrun the split brain the majority-intersection argument exists to make impossible
- LabThe cut phone linethe majority side keeps serving and the minority freezes - safety kept, liveness spent
- LabThe two ledgers must agreethe blocking coordinator, which is what agreement looks like without this paper
- VideoConsensus: who holds the penone pen, five clerks, a fence
- VideoCAP: the cut phone linethe partition, and which side of it a quorum lands on
- VideoDistributed transactions: the two ledgers must agreethe crash that lands between two writes
- LessonRaft 01: Leader ElectionUses the board Who Holds the Pen
- LessonRaft Capstone: EverythingUses the board Who Holds the Pen
- LessonWho holds the pen (consensus & Raft)Uses the board Who Holds the Pen
- LessonConsistency and ConsensusUses the board Consistency and Consensus
- LessonBuild Your Own RaftUses the board Consistency and Consensus
- LessonRaft 02: Log ReplicationUses the board Consistency and Consensus
- LessonScheduler 04: Leader ElectionUses the board Leader Election
- LessonRaft 04: A Key-Value Store on TopUses the board Leader Election
- LessonThe Two Ledgers Must Agree (Distributed Transactions)Uses the board The Two Ledgers Must Agree
- LessonKafka: Replication and DurabilityUses the board Replication and Durability
Further reading
Read the original for the full argument and its evidence.
- Paxos Made Simple (PDF) ↗The 2001 note itself. Nine pages, and the abstract is one sentence. Read section 2 with a pencil: the derivation from P1 to P2c is the part worth the time.
- The Part-Time Parliament (PDF) ↗The 1998 original, with the Greek island intact, plus the editor's note explaining the eight-year delay. Read it second, for what the re-explanation was reacting to.
- Paxos Made Live - An Engineering Perspective ↗Google, 2007. The honest accounting of what it took to turn this paper into Chubby, and the clearest available statement of how much the algorithm leaves out.
- Flexible Paxos: Quorum Intersection Revisited ↗Howard, Malkhi and Spiegelman, 2016. The result that majorities were never the requirement - worth reading purely for how long it sat unnoticed.