Catalog My learning Blog
Distributed Systems Explained: CAP, Clocks and Replication · Phase 3 · Lesson 15 · 5 min read

Paxos Algorithm Explained Simply

On this page
  1. What Paxos solves
  2. Paxos roles: proposers, acceptors and learners
  3. Proposal numbers
  4. The two phases: prepare and accept
  5. Why a chosen value never changes
  6. Paxos in code: the rule that keeps a chosen value
  7. Paxos livelock: dueling proposers
  8. Multi-Paxos: a log, not one value
  9. Check yourself

What Paxos solves

Five servers must agree on a single value, say which of two clients' commands goes first. Any server might crash, messages might be lost or delayed. Leslie Lamport's Paxos (described in "The Part-Time Parliament", published 1998) solves this, and its ideas underpin Chubby, Spanner, Cassandra's lightweight transactions and many others.

Paxos roles: proposers, acceptors and learners

  • Proposers suggest values.
  • Acceptors vote; a value is chosen once a majority of acceptors accept it.
  • Learners find out what was chosen.

One server usually plays all three roles. Five acceptors tolerate two failures.

Proposal numbers

Every proposal carries a unique, increasing number (for example round.serverId, so 7.3 is round 7 from server 3). Higher numbers take precedence. They're how Paxos orders competing proposers without trusting clocks.

The two phases: prepare and accept

Phase 1: prepare and promise.

  1. A proposer picks number n and sends Prepare(n) to the acceptors.
  2. Each acceptor that hasn't promised a higher number replies Promise(n), promising to ignore proposals numbered below n, and reports the highest-numbered proposal it has already accepted, if any.

Phase 2: accept and accepted.

  1. With promises from a majority, the proposer sends Accept(n, v). The value v is not freely chosen: if any promise reported a previously accepted proposal, v must be the value of the highest-numbered one reported. Only if none was reported may the proposer use its own value.
  2. Each acceptor that hasn't promised a higher number accepts and replies Accepted(n, v). Once a majority accepts, v is chosen.
A proposer collects promises from a majority, adopts any previously accepted value, then asks a majority to accept it; overlapping majorities preserve a chosen value.
A proposer collects promises from a majority, adopts any previously accepted value, then asks a majority to accept it; overlapping majorities preserve a chosen value.

Why a chosen value never changes

Any two majorities of the same acceptors overlap in at least one acceptor. Suppose value v was chosen by a majority with proposal n. Any later proposer with a higher number must collect promises from a majority, which includes at least one acceptor that accepted v. That acceptor reports it, and the rule in step 3 forces the new proposer to propose v again. So once chosen, v stays chosen, no matter how many proposers compete or crash.

Paxos in code: the rule that keeps a chosen value

Here's single-decree Paxos with five acceptors. Proposer 1 gets "A" chosen by a bare majority; proposer 2, which never heard of "A", then tries to get "B" chosen through a different majority that overlaps in one acceptor:

Python
# paxos.py: single-decree Paxos acceptors, and a proposer that must adopt a chosen value
class Acceptor:
    def __init__(self):
        self.promised, self.accepted = 0, None            # accepted: (number, value) or None

    def prepare(self, n):
        if n > self.promised:
            self.promised = n
            return ("promise", self.accepted)
        return ("reject", None)

    def accept(self, n, v):
        if n >= self.promised:
            self.promised, self.accepted = n, (n, v)
            return True
        return False

def propose(reachable, n, my_value, cluster_size=5):
    majority = cluster_size // 2 + 1                     # 3 of 5
    replies = [a.prepare(n) for a in reachable]
    promises = [acc for kind, acc in replies if kind == "promise"]
    if len(promises) < majority:
        return f"n={n}: no majority of promises"
    reported = [acc for acc in promises if acc is not None]
    value = max(reported)[1] if reported else my_value  # the rule from step 3
    votes = sum(a.accept(n, value) for a in reachable)
    return f"n={n}: proposed {value!r}, accepted by {votes}" + (" -> chosen" if votes >= majority else "")

acc = [Acceptor() for _ in range(5)]
# Proposer 1 uses n=1 and reaches acceptors 0, 1 and 2 only: 'A' is chosen.
for a in acc[:3]: a.prepare(1)
print("n=1: 'A' accepted by", sum(a.accept(1, "A") for a in acc[:3]), "-> chosen")
# Proposer 2 never heard of 'A' and wants 'B'. It reaches acceptors 2, 3 and 4.
print(propose(acc[2:], 2, "B"))
print("final state:", [a.accepted for a in acc])
Code
n=1: 'A' accepted by 3 -> chosen
n=2: proposed 'A', accepted by 3 -> chosen
final state: [(1, 'A'), (1, 'A'), (2, 'A'), (2, 'A'), (2, 'A')]

Proposer 2 wanted "B", but acceptor 2 reported that it had accepted "A" with number 1, so proposer 2 proposed "A" instead. It couldn't know whether "A" had been chosen; it only knew it might have been, and that was enough. Replace the rule with value = my_value and run it again: the second round reports proposed 'B', accepted by 3 -> chosen. Two different values chosen is the one outcome consensus must never allow.

Paxos livelock: dueling proposers

Two proposers can keep preempting each other: A prepares with 5, B with 6 (A's accept is now rejected), A retries with 7, B with 8, forever. That's the liveness gap FLP predicts (Day 14). The practical fix is to elect a distinguished proposer (a leader) and have others back off with randomized delays.

Multi-Paxos: a log, not one value

Real systems need a sequence of decisions: a replicated log of commands. Multi-Paxos runs a Paxos instance per log slot, with an optimization: a stable leader runs phase 1 once for all future slots, then each new command needs only phase 2, one round trip to a majority. That's the shape of most production systems, and it's what Raft (Day 16) makes explicit and easier to implement.

Check yourself

That value may already have been chosen by a majority without the proposer knowing. Adopting the highest-numbered accepted value it hears about guarantees that once a value is chosen, every later proposal carries the same value, so the decision never changes.

They order competing proposals, so acceptors can promise to ignore anything older than the highest number they've seen. That's how Paxos resolves conflicts without relying on synchronized clocks. Numbers must be unique, for example by combining a counter with the proposer id.

Two proposers can keep preempting each other: each one's prepare invalidates the other's accept, forever. Real systems elect a single distinguished leader to propose, and use randomized backoff so competing proposers rarely collide.

It would get "B" accepted by a majority after "A" was already chosen by another majority, so the cluster would have decided two different values.