Engineering Atlas › System Design Fundamentals

Paxos consensus explained

13 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

Roles and the quorum idea

There are three roles, usually co-located on every node: proposers suggest values, acceptors vote and remember, and learners find out what was chosen. A value is chosen once a majority of acceptors have accepted it under the same ballot. Any two majorities of N acceptors overlap in at least one node, and that overlap carries knowledge from one ballot to the next. With 5 acceptors you tolerate 2 failures; with 3 you tolerate 1. Five is the common production choice: a typical Chubby cell runs five replicas (Paxos Made Live).

Phase 1: prepare and promise

A proposer picks a ballot number n that is unique and higher than any it has used. A common choice is (round, nodeId) compared lexicographically. It sends Prepare(n) to the acceptors. An acceptor that has not promised anything higher replies Promise(n, acceptedBallot, acceptedValue) and records that it will ignore any ballot below n. That promise must be written to stable storage before replying, or a reboot will let it break the promise. Lamport is explicit that an acceptor must remember its highest promise and highest accepted proposal even if it fails and restarts (Paxos Made Simple).

Phase 2: accept and accepted

With promises from a majority, the proposer looks at the replies. If any acceptor reported a previously accepted value, the proposer must use the value with the highest accepted ballot. Only if none did may it use its own value. It sends Accept(n, v). An acceptor accepts unless it has since promised a higher ballot, persists (n, v), and notifies learners. Once a majority accept, v is chosen and can never change, because every later ballot's Phase 1 will hit at least one acceptor that holds v.

Why liveness can fail

Proposer A finishes Phase 1 with ballot 5. Before its Accept lands, B finishes Phase 1 with ballot 6, so A's Accept is rejected. A retries with 7, which kills B's Accept, and so on. This is the FLP impossibility result in practice. Paxos always keeps safety and gets liveness from randomised backoff or a single distinguished proposer. Lamport notes that any reliable way to elect that proposer must use randomness or real time, such as timeouts, while safety holds whether or not the election works (Paxos Made Simple).

Multi-Paxos

A replicated log needs one Paxos instance per slot. Running both phases for every slot costs two round trips per write. Multi-Paxos elects a leader that runs Phase 1 once for all future slots, then issues only Phase 2 for each new entry. Steady state is one round trip to a majority. Phase 1 reruns only on leader change.

Majorities are sufficient but not necessary. Flexible Paxos showed that only quorums from different phases must intersect, so with N acceptors any Phase 1 quorum of size Q1 and Phase 2 quorum of size Q2 work when Q1 + Q2 > N (Howard, Malkhi and Spiegelman). Because Phase 1 is rare in Multi-Paxos, a system can shrink the Phase 2 quorum that every write pays for and enlarge the Phase 1 quorum it pays for only on leader change.

Down the stack

Layer 1The contract

Single-decree Paxos makes three safety promises: only a proposed value can be chosen, at most one value is chosen, and a learner never learns a value that was not chosen. They hold under loss, duplication, reordering, delay, and crash-recovery, provided acceptors keep state on stable storage and nobody lies. It makes no liveness promise: a value is chosen only once a single proposer runs both phases against a majority without being pre-empted.

Multi-Paxos turns this into a replicated log. Each slot is fixed once chosen, the state machine applies slots in index order, and a client sees success only after a majority has durably accepted the entry. The latency envelope is one round trip plus one disk flush per write in steady state, two round trips after a leader change, and an unavailability window bounded by the failure-detection timeout. A timed-out request has an unknown outcome, not a failed one.

Layer 2The mechanism

Lamport labels the steps Phase 1(a), 1(b), 2(a) and 2(b), so implementations call the messages 1a (Prepare), 1b (Promise), 2a (Accept) and 2b (Accepted). An acceptor needs three fields per slot: promised, acceptedBallot, acceptedValue. Ballots are usually packed into a 64-bit integer as (round << 16) | nodeId so they compare with one instruction and are unique without coordination.

The Multi-Paxos trick is that promised is kept once per acceptor rather than per slot. A single 1a then reserves every future slot, and the 1b reply carries all accepted-but-not-known-committed entries above the leader's commit point. The new leader re-proposes the highest-ballot value it finds for each slot and fills slots nobody accepted with a no-op, so the log has no permanent holes. Commit knowledge is piggybacked on the next 2a, much like Raft's leaderCommit.

Real systems add what the paper omits. "Paxos Made Live" describes Chubby's layer: a master lease so reads can be served locally, snapshots to truncate the log, checksums because disks really do return corrupt data, and a rule that a replica with lost state rejoins without voting. It catches up as a non-voting member and starts sending promises again only after it has seen one complete Paxos instance that began after it started rebuilding, so it cannot renege on a promise it forgot (Paxos Made Live). Spanner runs a Paxos state machine per tablet, with long-lived leaders holding time-based leases that default to 10 seconds (Spanner, OSDI 2012). Cassandra's lightweight transactions run Paxos per partition with state in the system.paxos table; the classic implementation needs four round trips for a write (prepare, read, propose, commit). Cassandra 4.1 added a reworked protocol (CEP-14) that needs two round trips for an uncontended write, but it is opt-in: paxos_variant still defaults to v1, and switching to v2 takes a full repair and a rolling restart (cassandra.yaml). Check which variant a cluster actually runs before quoting LWT latency.

Layer 3The machine

Every 1b and 2b must follow a durable write: append, then fdatasync, then reply. A datacenter NVMe drive with power-loss-protected cache can acknowledge a flush in tens of microseconds; a consumer SSD without that protection may take a millisecond or more; a spinning disk costs several milliseconds of rotation; networked block storage adds a network hop on top. So implementations group-commit: entries arriving in a short window share one 2a and one flush.

An Accept with an 8-byte ballot, an 8-byte slot and a 100-byte command fits in one TCP segment on a 1,500-byte MTU. Latency is therefore set by distance: roughly 0.1 to 0.5 ms round trip inside a zone, about a millisecond or two between zones, and tens to over a hundred milliseconds between regions, since light in fibre covers about 200 km per millisecond. The leader also sends every byte to N-1 peers, so its NIC becomes the throughput ceiling before the protocol does. A long GC pause on the leader looks like a crash, so lease timeouts sit well above observed pauses.

Why it's built this way

  1. Networks drop and delay packets and no timeout can tell a slow node from a dead one (FLP), so safety must depend only on quorum intersection, never on timing.
  2. A majority is the smallest set guaranteed to overlap every other majority, so 2f+1 nodes tolerate f failures and every write fans out to all of them.
  3. Overlap carries information only if acceptors remember, so each reply waits for a disk flush, and flush latency is amortised with batching and group commit.
  4. Two round trips per value and duelling proposers are too slow, so Multi-Paxos keeps a stable leader and runs Phase 1 rarely, reintroducing timing (leases) for liveness and local reads but not for safety.

Diagram

sequenceDiagram
    participant P as Proposer
    participant A1 as Acceptor 1
    participant A2 as Acceptor 2
    participant A3 as Acceptor 3
    P->>A1: Prepare(n=7)
    P->>A2: Prepare(n=7)
    P->>A3: Prepare(n=7)
    A1-->>P: Promise(7, none)
    A2-->>P: Promise(7, had ballot 4 value x)
    Note over P: Majority reached, must adopt x
    P->>A1: Accept(7, x)
    P->>A2: Accept(7, x)
    A1-->>P: Accepted(7)
    A2-->>P: Accepted(7)
    Note over P,A3: x is chosen by a majority

Worked example

Five acceptors over three zones in one region, RTT 1 ms, fsync about 0.2 ms. A leader running Multi-Paxos commits a log entry with one round trip to the fastest 2 of 4 peers plus an fsync: roughly 1.5 ms p50. Batching 100 entries per Accept reaches tens of thousands of commits per second; the leader's NIC and disk become the bottleneck.

Now the leader dies. Followers wait for a lease to lapse (say 2 s), one wins Phase 1 with a higher ballot, and it discovers slot 9,812 has value "debit 40" accepted by two acceptors under the old ballot. It must re-propose "debit 40" in slot 9,812 even though no client was told it succeeded. Write unavailability is about 2 to 3 s, dominated by the lease timeout, not by Paxos messages.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
Basic Paxos per decisionSimple proof, no leader needed2 RTT per value, duelling proposersOne-off decisions such as config epochs
Multi-Paxos1 RTT steady state, flexible log holesUnderspecified; every team fills gaps differentlyBuilding a storage engine with an expert team
RaftFully specified, many tested librariesStrict leader, log must be contiguousAlmost any new replicated service
EPaxos / leaderlessNo leader hotspot, good WAN latencyComplex dependency tracking, hard to verifyGeo-distributed writes from every region

Pitfalls in production

Leadership lens

Check yourself

  1. Why must a proposer adopt the highest-ballot accepted value it hears in Phase 1?

    Show answer

    That value may already be chosen by a majority, and the overlap guarantees the proposer would hear it. Re-proposing it ensures a later ballot cannot overwrite a chosen value.

  2. Why does an acceptor need stable storage for promises, not only for accepted values?

    Show answer

    If it forgets a promise after reboot it can accept a lower ballot's value, letting an old proposer complete a value that a newer ballot never saw.

  3. Where does Multi-Paxos save latency compared with Basic Paxos?

    Show answer

    The leader runs Phase 1 once for all future slots, so each new entry needs only the Accept round trip.

  4. What does a five-node group lose when two nodes are down and a third is slow?

    Show answer

    Writes stall until the slow node answers, because a majority of three is required and there is no spare.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →