Paxos — Part 1: Foundations & Core Concepts
maang.io System Design Series
What is this?
Picture six friends trying to pick one restaurant for tonight, and their only tool is a laggy group chat. Messages arrive out of order. Two people's phones die mid-conversation. Someone suggests "Thai," someone else fires off "Sushi" a second later, and both messages cross in flight. You've lived this: without some discipline, half the group shows up at the Thai place and half at the sushi bar. The dinner is split-brained.
Now add the brutal constraint that makes this a computer-science problem, not a social one: you must guarantee that everyone who commits to a venue commits to the same venue — even though people drop offline, messages get delayed, and nobody is in charge. You can't just "ask the leader," because the leader's phone might be the one that died. You can't wait for everyone, because some are gone for good. You need a protocol that, using only a majority of the people who happen to be reachable, pins down exactly one answer that can never be contradicted later.
That protocol is Paxos. It's the algorithm that lets a set of unreliable machines agree on a single value, and it's the bedrock under Google's Chubby lock service, Spanner, and Cassandra's lightweight transactions. It has a fearsome reputation for being hard to understand — but the core is just the dinner vote, done carefully.
The one-line idea: Paxos lets a group of machines agree on one value despite crashes and delays, by having proposers ask a majority of acceptors for permission before proposing, and forcing every later proposer to honour any value a majority might already have chosen. Majority overlap is the whole trick — any two majorities share at least one member, so no two conflicting values can both win.
We'll keep coming back to the dinner vote through all three chapters. Let's first see why we even need something this careful.
1. Why Paxos exists — the problem it solves
The problem is consensus: getting multiple machines to agree on a single value, such that the decision is permanent and unanimous in effect. This sounds trivial until you remember what a distributed system actually is — computers connected by a network that can:
- drop, delay, duplicate, or reorder messages (the group chat is laggy),
- and crash any participant at any time (phones die).
Paxos assumes crash faults — nodes stop, messages are lost — but it assumes nobody lies (no forged or corrupted messages). Tolerating liars is the harder Byzantine problem, a different algorithm family; we'll flag that boundary but Paxos does not cross it.
Here's what was painful before a correct consensus protocol. Say you're replicating a database across three nodes for fault tolerance. A client says "set balance = 100." If the three replicas apply writes in different orders, or one misses a write while another crashes and recovers with stale data, your replicas silently diverge — and now which one is "the truth"? The naive fixes all break:
- "Just use a single leader." Fine until the leader crashes. Now you must agree on who the new leader is — which is itself a consensus problem. You haven't escaped; you've recursed.
- "Take a majority vote." Closer! But a plain vote doesn't handle timing: two proposals racing, a proposer that crashes half-way through, a node that voted, went offline, and comes back not knowing the outcome. You need rules for exactly these races.
Paxos is the set of rules that makes majority voting safe under every possible interleaving of crashes and delays. Its guarantee is precise and worth memorizing:
💡 Paxos never returns a wrong answer — it only ever risks returning no answer yet. It guarantees safety (at most one value is ever chosen, and once chosen it never changes) unconditionally. It only guarantees liveness (a value eventually gets chosen) when the network behaves for long enough. That split — always safe, eventually live — is the heart of Paxos and comes straight out of the famous FLP impossibility result, which proved no protocol can guarantee both in a fully asynchronous network with even one crash.
2. Core concepts & vocabulary
Paxos assigns every participant one or more roles. In the dinner vote, one person can wear several hats, but the roles are distinct jobs:
| Role | Dinner-vote job | What it does |
|---|---|---|
| Proposer | A friend who suggests a venue | Tries to get a value chosen. Drives the two phases below. |
| Acceptor | A member whose vote counts | The "memory" of the system. Votes on proposals and remembers its promises. A majority of acceptors decides everything. |
| Learner | Anyone who needs the final plan | Finds out which value was ultimately chosen (so they can act on it — e.g. apply the write). |
Two more pieces of vocabulary do the heavy lifting:
- Proposal number (
n). Every proposal carries a unique, ever-increasing number — think of it as taking a numbered ticket at the deli counter. Higher numbers outrank lower ones. These numbers must be globally unique per proposer (a common trick:n = (round_counter, server_id), so two proposers can never mint the same number). They order proposals in logical time, which is how Paxos resolves races without a shared clock. - Majority quorum. Any decision needs the agreement of more than half the acceptors. With 5 acceptors, a quorum is 3. The magic property: any two majorities overlap in at least one acceptor. That single shared acceptor is the thread that ties the whole protocol's safety together — it's the person who was in both votes and remembers what already happened.
💡 The quorum size sets your fault tolerance. With
2f + 1acceptors you tolerateffailures and still form a majority. So 5 acceptors tolerate 2 down; 3 acceptors tolerate 1 down. That's why production Paxos groups are almost always an odd number — an even count buys you no extra fault tolerance, just a bigger quorum to wait for.
3. How it actually works — the two phases
Paxos reaches agreement in two phases, each a round trip to a majority of acceptors. Keep the dinner vote in mind:
Phase 1 — Prepare / Promise ("may I even propose?"). A proposer picks a fresh number n and asks a majority of acceptors: "Will you promise to consider proposal n?" Each acceptor, if n is the highest it has seen, promises not to entertain anything lower — and crucially, it reports back any value it has already accepted. This is the friend saying: "Sure, I'll hear your #7 — but heads up, I already agreed to Sushi under proposal #4."
Phase 2 — Accept / Accepted ("okay, let's lock it in"). If a majority promised, the proposer sends an Accept request: "Accept value V under proposal n." But here's the rule that makes Paxos correct: if any acceptor reported an already-accepted value in Phase 1, the proposer must propose that value (the one from the highest-numbered prior proposal), not its own. Only if nobody had accepted anything is the proposer free to propose its own choice. Once a majority accepts, the value is chosen — permanently.
Notice what just happened in that diagram: our proposer wanted to suggest Thai, but because an acceptor revealed that "Sushi" was already accepted under an earlier proposal, the proposer was forced to abandon its own preference and re-propose Sushi. That is not a bug — it is the entire safety mechanism. A value that might already be chosen can never be overwritten; every new proposer either discovers it and re-affirms it, or (if truly nothing was chosen yet) is free to pick. We'll prove to ourselves why this is airtight in Part 2.
⚠️ A single, complete Paxos run — both phases — decides exactly one value, once. It is not a loop, and it is not a way to agree on a sequence of things. If you want to agree on a log of many values (which is what real systems need), you run many Paxos instances, one per log slot. That's Multi-Paxos, and it's where the practical engineering lives — Part 2.
4. A concrete peek — Cassandra's lightweight transaction
You don't write Paxos by hand; you use systems built on it. The most tangible example in this tier is Cassandra's lightweight transaction (LWT), which uses Paxos under the hood to make a compare-and-set safe. Two users race to claim the same username:
-- Only ONE of two concurrent callers can win this.
INSERT INTO users (username, user_id)
VALUES ('neo', 550e8400-...)
IF NOT EXISTS;
That innocent IF NOT EXISTS is the trigger. Without it, Cassandra does last-write-wins and both inserts "succeed," one silently clobbering the other. With it, Cassandra runs a Paxos round across the replicas of that partition at SERIAL consistency — Prepare/Promise, then Accept/Accepted — to linearize the two racers so that exactly one sees the row as absent and wins. It's correct, and it's expensive: roughly four round trips instead of one, which is why you reach for it surgically, never as your default write path. (We dig into the Cassandra internals in the Apache Cassandra topic; this is the same Paxos, applied.)
That's the everyday face of Paxos: a narrow, costly door to agreement that you open only when correctness genuinely depends on it.
5. When to reach for it — and when not
Consensus is a big hammer. You want it precisely when several machines must agree on one thing and being wrong is unacceptable:
- Leader election — agreeing on who is the primary (so you don't get two leaders, a "split brain").
- Replicated state machines — a cluster of replicas applying the same commands in the same order (the basis of fault-tolerant databases, config stores, lock services).
- Distributed locks & configuration — Chubby and ZooKeeper-style services that hand out locks and store the one authoritative copy of critical metadata.
- Compare-and-set on replicated data — exactly Cassandra's LWT above.
And when not to:
| If you need… | Don't use Paxos — use… |
|---|---|
| Agreement across independent databases in one atomic transaction | Two-Phase Commit / distributed transactions (a different problem — see below) |
| The understandable, log-first version of this exact algorithm | Raft — same guarantees, designed to be teachable, now the default in etcd, Consul, CockroachDB |
| Tolerance of malicious/corrupt nodes, not just crashes | A Byzantine fault-tolerant protocol (PBFT and kin) |
| Just "eventually consistent," high-availability replication | Plain quorum replication / gossip — no consensus needed (see the Replication and Gossip Protocol topics) |
💡 Paxos vs. Two-Phase Commit — don't confuse them. 2PC (in the Distributed Transactions topic) makes different participants agree to all commit or all abort one transaction, and it blocks if the coordinator dies. Paxos makes interchangeable replicas agree on one value, and it survives a minority of failures without blocking. 2PC is about atomicity across parties; Paxos is about fault-tolerant agreement among replicas. Interviewers love to see you draw that line cleanly.
6. Key takeaways
- Paxos solves consensus: getting unreliable machines to agree on one value, permanently and consistently, despite crashes and a lossy network — assuming crash faults, not lying (Byzantine) nodes.
- Three roles, two numbers: proposers drive, acceptors vote and remember, learners find out the result; every proposal has a unique proposal number, and every decision needs a majority quorum. Majority overlap is the safety mechanism.
- Two phases: Prepare/Promise (get permission from a majority and learn any value already accepted) then Accept/Accepted (lock in a value). The killer rule: a proposer must re-propose any value that might already be chosen, never overwrite it.
- Safe always, live eventually: Paxos never chooses two different values (safety is unconditional), but it can stall under bad timing (liveness isn't guaranteed) — that's the FLP result, not a flaw.
- One round decides one value. Real systems need a log of values, so they run many instances — Multi-Paxos — with a stable leader. That's Part 2, along with why the overlap makes it all provably correct.
Next, Part 2 opens the hood: the exact acceptor state, the full two-phase protocol with a worked majority example, why overlap guarantees safety, the dueling-proposers liveness trap, and how Multi-Paxos turns this one-shot vote into an efficient replicated log.