Paxos — Part 2: Internals & The Protocol

maang.io System Design Series

What is this?

Back to our six friends and the laggy group chat. In Part 1 we watched a value get chosen and saw that a later proposer was forced to re-affirm an already-accepted venue. Now we open the hood and answer the questions a Staff engineer must be able to answer cold: What state does each acceptor actually keep? What exactly do the messages say? And why — precisely — is it impossible for two different venues to both win?

The beautiful thing about Paxos is that the entire protocol lives in the acceptor's tiny memory and two simple rules. Get those rules exactly right and the safety proof falls out of one fact you already know: any two majorities of a group must share at least one member. That shared member is the group's conscience — it remembers what happened and refuses to let history be rewritten.

The one-line idea: each acceptor persists just two things — the highest proposal number it has promised and the last value it accepted (with its number) — and follows two rules (never promise backwards, always report what you accepted). From those, majority overlap guarantees at most one value is ever chosen. Everything else — Multi-Paxos, leaders, the log — is engineering built on top of that core.

Let's follow the state, then the protocol, then the proof, then a worked run with real numbers.