Paxos

Each round has a unique proposal number (a monotonically increasing integer, often (round, server_id) tuple to break ties). The proposer drives the round through two phases:

# PHASE 1: Prepare
proposer → ALL acceptors: PREPARE(n)         # "I want to lead with proposal n"

# Each acceptor:
if n > max_seen_n:
    max_seen_n = n
    return PROMISE(n, accepted_n, accepted_v)
    # "OK, I won't accept anything < n.
    #  Here's the highest-numbered value I've already accepted (if any)."
else:
    return REJECT(max_seen_n)

# Once proposer has PROMISE from majority:

# PHASE 2: Accept
v = highest accepted_v among the PROMISES, or your own desired value
proposer → ALL acceptors: ACCEPT(n, v)       # "Vote to accept (n, v)"

# Each acceptor:
if n >= max_seen_n:
    accepted_n = n
    accepted_v = v
    return ACCEPTED(n, v)

# When proposer has ACCEPTED from majority: value is CHOSEN.
# Proposer broadcasts CHOSEN(v) to learners.

The two key invariants:

• P1: An acceptor accepts proposal (n, v) only if it hasn't promised a higher number.
• P2: If a proposal (n, v) has been chosen, every higher-numbered proposal must propose the same v. The proposer enforces this by reading the highest accepted value from its prepare quorum.

One phase isn't enough because two competing proposers might each get majority acceptance for different values. Paxos prevents this with the prepare phase: before proposing v, you must learn what (if anything) was already chosen, and propose that value if it exists.

The brilliant part is what happens during contention. Suppose proposer A has its (n=5, v=X) accepted by acceptors 1, 2, 3 (a majority). Then proposer B starts a new round with n=6:

Acceptor 1: PROMISE(6, accepted=(5, X))
Acceptor 2: PROMISE(6, accepted=(5, X))
Acceptor 4: PROMISE(6, accepted=None)         # B's prepare quorum

# B's quorum overlaps A's commit quorum by majority intersection.
# Therefore at least one acceptor in B's quorum already accepted (5, X).
# B sees (5, X) as the highest accepted, MUST propose v=X.
# Result: even if B "wins" the round, X is still chosen.

proposer B → ACCEPT(6, X)        # forced to keep X

The majority intersection guarantee is the entire safety proof: any two majorities of N nodes must overlap by at least one node, so a learner with a fresher round can always see what was chosen previously.

Multi-Paxos optimizes for the common case of a stable leader. Instead of running Phase 1 every decision, the leader runs Phase 1 once (covering an entire range of slots), then Phase 2 alone for each subsequent value:

# Multi-Paxos with stable leader L:

# At leader election (rare):
#   L → ALL: PREPARE(n)           # n covers ALL future slots
#   L receives PROMISE from majority, learns highest accepted per slot
#   L "completes" any previously chosen-but-not-fully-replicated values

# Per request (common case):
#   client → L: REQUEST(value)
#   L picks next free slot s
#   L → ALL: ACCEPT(n, s, value)   # phase 2 only — 1 RTT
#   L receives ACCEPTED from majority
#   L → ALL: CHOSEN(s, value)
#   L → client: REPLY(success)

This is why Multi-Paxos is "the same speed as Raft" — the steady-state cost is one RTT plus disk fsyncs, identical to Raft's AppendEntries. The difference is conceptual cleanliness, not performance.

Before Paxos, the standard approach to consensus was 2-phase commit (2PC) or 3-phase commit (3PC). These require all nodes to participate. If any node is down or slow, the whole system blocks.

Lamport's insight: you don't need everyone — you need a majority. Any two majorities overlap, which is enough to preserve safety across leadership changes. This makes Paxos:

• Asynchronous-safe: arbitrary message delays don't cause incorrect decisions.
• Live with f=⌊(N-1)/2⌋ failures: as long as a majority stays up, progress is possible.
• No coordinator dependency: any node can become a proposer; rounds with higher numbers preempt lower ones.

This was a fundamental shift. Every consensus protocol since (Raft, Zab, View-Stamped Replication, EPaxos, Flexible Paxos) is a refinement of "majority quorum + monotonic round numbers."

The Raft paper (Ongaro & Ousterhout 2014) explicitly framed itself as "Paxos but understandable." It's not faster or more correct — it's just easier to specify, implement, and verify. The cost: Raft requires a strict log without gaps, so a single straggler can stall the entire log.

Google's Chubby (Burrows 2006) was the first major production Paxos system — a coarse-grained lock service used by GFS, BigTable, and others for leader election and metadata storage. Chubby exposed a Unix-like file API, with each file being a tiny replicated state machine over Paxos.

Spanner (Corbett 2012) uses Paxos per shard ("tablet") to replicate writes across data centers. Spanner's twist is TrueTime — atomic-clock-derived bounded clock uncertainty — used together with Paxos to provide externally-consistent transactions.

Megastore (Baker 2011) ran a Paxos round per write across geographically distributed data centers, sacrificing latency for strong consistency. Largely superseded by Spanner internally at Google.

Outside Google: Apache ZooKeeper uses Zab (a Paxos-like protocol). Apache Cassandra has lightweight transactions (LWT) implemented via Paxos for compare-and-set semantics.

Liskov & Oki published View-Stamped Replication in 1988 — a year before Lamport's Paxos paper, but framed as a database replication protocol rather than consensus. VSR uses identical ideas: monotonic view numbers (~ proposal numbers), majority quorums, and a "view change" protocol equivalent to Paxos's Phase 1.

The 2012 update "VR Revisited" (Liskov & Cowling) is now the cleanest reference for the VSR-style consensus pattern — and Raft's design borrows directly from it.

Heidi Howard's 2016 paper "Flexible Paxos" relaxed Paxos's quorum requirement. The key observation: safety only requires that Phase 1 quorums and Phase 2 quorums intersect — not that each is a majority.

# Standard Paxos: |Q1| > N/2 AND |Q2| > N/2
# Flexible Paxos: |Q1| + |Q2| > N

# Concrete example with N=5:
#   Standard: Q1=3, Q2=3
#   Flexible: Q1=4, Q2=2  → committed values need only 2 acceptors!
#
# Trade off availability: now 2 unavailable acceptors block leader election,
# but writes only need 2 acceptors.

This is useful when reads dominate and you can tolerate slower leader changes. WAN-deployed systems sometimes use it: small fast write quorum across nearby data centers, large recovery quorum once during election.

Going from "Paxos Made Simple" to a working implementation is where most bugs hide:

• Persistence: acceptors must persist (maxSeenN, acceptedN, acceptedV) to disk before responding. Otherwise a reboot can violate safety.
• Slot completion: a new leader must run Phase 1 then Phase 2 for any "holes" left by previous leaders — even slots where no one has accepted anything yet.
• Duplicate filtering: clients must tag requests with monotonic IDs so a retried request doesn't get applied twice in the state machine.
• Read-only optimization: reading at the leader still costs an RTT to confirm leadership. Lease-based reads (where the leader holds a time-bounded lease and can serve reads locally) are common and require careful clock-skew accounting.
• Membership change: not part of basic Paxos. The standard approach is to make the membership configuration itself a value Paxos decides.

Lamport's "Paxos Made Live" (Chandra et al. 2007) — the Chubby team's experience report — is the best read on what's actually hard. Twenty pages of "we did this, it broke, here's the fix." Required reading before implementing.

Almost no production system uses single-decree Paxos directly. Real systems are replicated state machines: sequence of decisions, each producing a state transition.

# Replicated state machine (RSM) over Paxos:
# - Slot 0: client A wants "set x = 1"  → Paxos decides "set x = 1"
# - Slot 1: client B wants "set y = 2"  → Paxos decides "set y = 2"
# - Slot 2: client A wants "x++"        → Paxos decides "x++"
#
# Each slot is a separate Paxos instance.
# Multi-Paxos pipelines them: leader runs Phase 1 once, then Phase 2 per slot.
#
# State machine applies decisions in slot order:
#   apply slot 0: x = 1
#   apply slot 1: y = 2
#   apply slot 2: x = 2
# Every replica applies in the same order → same final state.

This is the model that Raft inherited and made explicit. Paxos's flexibility (allowing slots to commit out of order) is largely unused in practice because state machines need ordered application anyway.