Paxos: the two phases and the Phase 2a constraint

What it is

Paxos is a protocol for getting a set of processes to agree on a single value even though some of them may crash, restart, or have their messages delayed or reordered arbitrarily. That agreement is called consensus, and the guarantee Paxos provides is that once a value has been chosen, no other value can ever be chosen, no matter what sequence of failures follows.

The confusion worth clearing up first: Paxos and Raft solve the same problem and have the same safety guarantee. They are not competing on correctness. Raft is a different arrangement of the same ideas, chosen so the arrangement is easier to teach and implement. If you understand Raft, you already understand what Paxos does; what you may not have is the vocabulary Paxos-family systems use, which is what this page supplies.

The second confusion, and the one that trips people up in interviews: "Paxos" usually means one of three different things.

Name	What it agrees on	Where you meet it
Single-decree Paxos	Exactly one value, once	Papers, exam questions, this page's mechanics
Multi-Paxos	A sequence of values (a log)	Actual replicated state machines
Paxos-derived protocols	A log, plus operational fixes	Chubby, Spanner, ZAB, Raft, EPaxos, Flexible Paxos

Nobody runs single-decree Paxos in production, because a system that agrees on one value once is not useful. Every production system runs a Multi-Paxos variant. The single-decree version is worth learning anyway, because the safety argument lives there and everything else is optimisation on top.

The problem it solves

You have three replicas of a database. A client writes x = 5 to replica A; another client writes x = 7 to replica B. The network partitions. Both replicas accept. When the partition heals, the system has two irreconcilable histories, and no amount of later cleverness recovers the fact that one of those clients was told "committed" and should not have been.

The naive fix is a designated leader: only the leader accepts writes. That fails when the leader crashes, because now you need to agree on who the new leader is, which is itself a consensus problem. The naive fix for that is a lock service or a coordinator, and it fails the same way, because the coordinator can crash or be partitioned while a replica still believes it holds the lock.

The FLP impossibility result (Fischer, Lynch, Paterson, 1985) proves this cannot be solved perfectly: in an asynchronous network with even one crash failure, no deterministic protocol can guarantee it will reach agreement in bounded time. Paxos's response is to give up liveness in the worst case while never giving up safety. It may take arbitrarily long to decide (and in adversarial timing, may never), but it will never decide two different values. That trade is the right one: a system that stalls is recoverable, a system that has forked is not.

Mechanics

Three roles, which are usually the same physical processes wearing different hats:

Proposers propose values.
Acceptors vote. A majority of acceptors is a quorum. With 5 acceptors, any 3 form a quorum, and crucially any two quorums intersect in at least one acceptor. That intersection is the entire trick.
Learners find out what was chosen.

Each proposal carries a proposal number n, globally unique and increasing. The usual construction is (round_counter, server_id), compared lexicographically, so different servers can never generate the same number.

Phase 1: Prepare / Promise

The proposer picks a number n higher than any it has used and sends prepare(n) to at least a quorum of acceptors.

An acceptor receiving prepare(n):

If n is not greater than the highest prepare it has already promised, it ignores the message (or replies with a rejection carrying the higher number, an optimisation that lets the proposer skip ahead).
Otherwise it promises never to accept any proposal numbered less than n, and replies with the highest-numbered proposal it has already accepted, if any: the pair (n_accepted, v_accepted).

That reply is the crux. It is how information about possibly-chosen values leaks out of the past and constrains the future.

Phase 2: Accept / Accepted

The proposer collects promises from a quorum, then must choose what value to propose. This is the rule that makes Paxos correct, and it is the one people forget:

The Phase 2a constraint. If any acceptor in the promise quorum reported a previously accepted value, the proposer must propose the value that came with the highest n_accepted among those replies. Only if every acceptor reported "I have accepted nothing" is the proposer free to propose its own value.

The proposer then sends accept(n, v) to a quorum. An acceptor accepts it unless it has since promised a higher number.

Once a quorum accepts (n, v), v is chosen. Note that no single participant necessarily knows this at the moment it happens; chosen-ness is a property of the system state, and learners find out through a subsequent round or through acceptors broadcasting accepted values.

Why the Phase 2a constraint is the whole safety argument

Suppose value v was chosen with proposal number n. Some quorum Q1 accepted it. Now a later proposer runs with number m > n and gets promises from quorum Q2.

Q1 and Q2 are both majorities, so they share at least one acceptor a. That acceptor accepted (n, v). Two cases:

a accepted (n, v) before promising m. Then its promise reply includes (n, v), and by the Phase 2a constraint the new proposer must propose v (or something accepted at an even higher number, which by induction is also v).
a promised m before accepting (n, v). But then a would have refused the accept(n, ...) since n < m, so a is not in Q1. Contradiction.

So every later proposal proposes v. Once chosen, always chosen. The proof is four lines long and it rests entirely on quorum intersection plus the rule that a proposer is not free to propose its own value when the past has already spoken.

Here is the acceptor, which is the only stateful part and is about 20 lines:

class Acceptor:
    def __init__(self, storage):
        self.storage = storage          # must survive crash: fsync before replying
        self.promised = storage.get("promised", None)      # highest n promised
        self.accepted_n = storage.get("accepted_n", None)  # highest n accepted
        self.accepted_v = storage.get("accepted_v", None)

    def on_prepare(self, n):
        if self.promised is not None and n <= self.promised:
            return ("nack", self.promised)
        self.promised = n
        self.storage.put_sync("promised", n)   # durable BEFORE the reply is sent
        return ("promise", self.accepted_n, self.accepted_v)

    def on_accept(self, n, v):
        if self.promised is not None and n < self.promised:
            return ("nack", self.promised)
        self.promised = n
        self.accepted_n, self.accepted_v = n, v
        self.storage.put_sync_all(promised=n, accepted_n=n, accepted_v=v)
        return ("accepted", n)

The put_sync calls are not incidental. If an acceptor promises, crashes, restarts having forgotten the promise, and then accepts an older proposal, safety is gone. Every acceptor state change must be durable before the reply goes out, which is why consensus latency has an fsync in it and why people care so much about the write path of the underlying log.

And the proposer's Phase 2a decision:

def choose_value(promises, my_value):
    """promises: list of (accepted_n, accepted_v) from a quorum."""
    seen = [(n, v) for (n, v) in promises if n is not None]
    if not seen:
        return my_value                      # free choice: nothing was ever accepted
    return max(seen, key=lambda p: p[0])[1]  # forced: highest-numbered accepted value

Those three lines are the difference between a correct implementation and a data-loss bug. It is a common exam question precisely because "return my_value" looks so natural.

A worked example: a proposer that must abandon its own value

Five acceptors, A through E. Proposal numbers written as (round, server).

Round 1. Proposer S1 uses n = (1, S1) and proposes "blue".

prepare((1,S1)) to all five. A, B, C reply promise with nothing accepted. D and E are slow, their replies are still in flight.
S1 has a quorum of promises, all empty, so it is free: it sends accept((1,S1), "blue").
Only A and B receive it before S1 crashes. A and B accept.

State now: A and B have accepted (1,S1) → "blue". C, D, E have accepted nothing. "blue" is not chosen, because 2 out of 5 is not a quorum. But it might be, from the perspective of anyone who cannot see all five, and that ambiguity is exactly what the protocol must survive.

Round 2. Proposer S2 wants to propose "red". It uses n = (2, S2).

prepare((2,S2)) reaches B, C, D. That is a quorum.
B replies: promise, and I already accepted ((1,S1), "blue").
C replies: promise, nothing accepted.
D replies: promise, nothing accepted.

S2 now applies the Phase 2a constraint. One acceptor reported a prior accepted value, so S2 must propose "blue", not "red". It sends accept((2,S2), "blue") to B, C, D. All three accept. "blue" is now chosen by a quorum, and S2's own value never enters the system.

What if S2 had ignored the constraint? Suppose S2 proposes "red" and gets B, C, D to accept. Now imagine a third proposer S3 that talks to A, B and E, or a learner that queried A and B during round 1. The system contains a quorum-accepted "red" and an acceptor set that at some point looked like "blue" was on its way to being chosen. Different learners reading different subsets can be told different answers, and if S1 had actually completed its round to C before crashing, two distinct values would both have been chosen by legitimate quorums. That is the fork.

The stall. Notice also what happens if S1 recovers and retries with n = (3, S1), while S2 retries with (4, S2), and so on. Each prepare invalidates the other's in-flight accept. This is the dueling proposers livelock, and it is the concrete face of FLP: safety holds forever, progress may not. The standard fix is to elect a distinguished proposer (a leader) with randomised backoff, which is precisely what Multi-Paxos and Raft do.

Multi-Paxos in one paragraph, because this is what actually runs

Running full two-phase Paxos per log entry costs two round trips per write. The observation behind Multi-Paxos is that Phase 1 is not about a particular value, it is about a particular proposer's right to propose. So run Phase 1 once for a range of log slots, and you have elected a leader. That leader then skips straight to Phase 2 for each entry: one round trip per write. If the leader is replaced, the new one runs Phase 1 again, discovers any partially-accepted entries from the old leader's tail, and must re-propose those values by the same Phase 2a constraint. That recovery step is where Multi-Paxos implementations get complicated and where the "Paxos is hard to implement" reputation comes from: the paper describes the single-decree protocol precisely and leaves log management, leader election, membership change and snapshotting as exercises.

Two variants worth being able to name:

Flexible Paxos (Howard, Malkhi, Spiegelman, 2016) proves the quorums for Phase 1 and Phase 2 need only intersect with each other, not within themselves. With 5 acceptors you can use a Phase 1 quorum of 4 and a Phase 2 quorum of 2, which halves steady-state write latency at the cost of a more expensive leader change. Raft's fixed majority is a special case.
EPaxos (Moraru et al., 2013) drops the leader entirely: commands that do not interfere commit in one round trip from any replica, and only conflicting commands need ordering. It is the strongest answer to "how do you avoid the leader being a bottleneck and a latency floor for distant clients," and it is genuinely harder to implement, which is why adoption has been thin.

Production evidence

Google Chubby is the canonical Multi-Paxos deployment: a lock service whose five replicas run Paxos over a replicated log, used by GFS and Bigtable for master election. The paper that matters more than the original Paxos papers for practitioners is Chandra, Griesemer and Redman's "Paxos Made Live" (2007), which documents what the algorithm does not tell you: they needed to add master leases, handle disk corruption explicitly, invent a testing regime, and their final system had thousands of lines of code for an algorithm described in a page of pseudocode. Their reported experience, that the gap between the algorithm and a production system is enormous, is the honest framing for any consensus discussion.

Google Spanner runs a Paxos group per shard ("Paxos group" per tablet), with a long-lived leader holding a lease, and layers two-phase commit across Paxos groups for cross-shard transactions. This is the standard architecture: consensus gives you a fault-tolerant replicated log per partition; a separate mechanism gives you atomicity across partitions.

Apache ZooKeeper uses ZAB, not Paxos, though it is in the same family. ZAB is built around the requirement that ZooKeeper's log be totally ordered and that a new leader's history strictly extends the old one's, which is a slightly stronger property than Paxos provides and is what ZooKeeper's ordering guarantees to clients rest on.

Neo4j, and several others, use Raft explicitly for the reason Ongaro's paper gives: an implementer-friendly decomposition. Ongaro's user study, in which students taught both protocols scored measurably higher on Raft comprehension, is the empirical basis for the field's shift, and it is a legitimate engineering argument. Implementability is a correctness property in practice, because an algorithm you cannot implement correctly does not deliver its guarantees.

The debate

Should you ever implement Paxos yourself? No. This is one of the few places where the answer is close to unconditional. Use etcd, ZooKeeper, Consul, or your database's built-in replication. "Paxos Made Live" is 16 pages of Google engineers explaining why their production implementation dwarfed the algorithm, and that team had unusual resources. The failure mode of a subtly wrong consensus implementation is silent divergence discovered months later, which is about the worst failure mode available.

Paxos versus Raft, honestly. They have identical safety guarantees and comparable performance. Raft's advantages are real but they are pedagogical and engineering advantages: a prescribed leader election, a log that is append-only with a strong "leader's log is truth" rule, and a specification that includes membership change and snapshotting rather than leaving them out. Paxos's advantage is that the underlying framework is more general, which is why the interesting research variants (Flexible Paxos, EPaxos, Fast Paxos) are expressed in Paxos terms. My position: choose Raft for anything you build or operate, and learn Paxos so you can read the literature and understand what Spanner and Chubby are doing.

Where consensus is the wrong tool entirely. Consensus costs a round trip to a quorum on every write, which in a multi-region deployment means tens of milliseconds you cannot optimise away. If your data type tolerates it, a CRDT gives you availability under partition and no coordination at all. If your operation is idempotent and commutative, you may not need agreement on order. Reach for consensus when you need a single authoritative sequence, most often for metadata: leadership, membership, configuration, and shard assignment. The systems that scale well tend to use consensus for a small, low-volume metadata plane and something cheaper for the data plane.

Follow-up Q&A

"Why is a majority the quorum? Could you use fewer?"

The requirement is not "majority," it is that any Phase 1 quorum intersects any Phase 2 quorum. Majorities are the simplest way to guarantee that with a single uniform rule, and they maximise fault tolerance for a given size. Flexible Paxos shows you can pick asymmetric quorums: with 5 acceptors, |Q1| = 4 and |Q2| = 2 satisfies |Q1| + |Q2| > N, so writes need only 2 acknowledgements. The cost is that leader election now needs 4 of 5 alive rather than 3, so you tolerate fewer failures during the recovery path. It is a real trade and some systems take it.

"What happens if two proposers keep interrupting each other?"

Livelock, and Paxos has no built-in cure. Each proposer's prepare invalidates the other's pending accept, and this can repeat indefinitely. Practical systems break it by making one proposer distinguished (a leader with a lease) and by randomised exponential backoff before retrying. This is not a defect that Raft fixed by being cleverer; Raft has exactly the same issue with split votes and solves it with the same tool, randomised election timeouts.

"An acceptor crashes and loses its disk. What breaks?"

Safety, potentially, and this is the part people underestimate. An acceptor that returns with amnesia may accept a proposal it previously promised not to accept, which can produce two chosen values. The correct handling is that a disk-loss acceptor must not rejoin as itself: it must either be treated as a new member (going through membership change), or must sit out until it has learned enough state to be safe. "Paxos Made Live" describes exactly this, adding a marker so a replica with a fresh disk cannot participate until it has caught up. Systems that let an amnesiac node silently rejoin have a real, if rare, correctness bug.

"Why does the proposer sometimes have to abandon its own value? That seems wasteful."

It is the safety property, not a waste. The proposer cannot tell the difference between "this value was accepted by a minority and abandoned" and "this value was accepted by a quorum and is already chosen, and I just happen to be talking to a quorum that includes only one of its acceptors." Since it cannot distinguish, it must assume the more constrained case. This is the same reasoning as a Raft candidate needing a log at least as up-to-date as the majority it asks: you can never rule out that what you see a trace of was already committed.

"How does Multi-Paxos handle a leader change mid-log?"

The new leader runs Phase 1 for all slots from its commit index forward. For each slot, the promise replies tell it whether some value was already accepted there. For every such slot it must re-propose that value (Phase 2a again, per slot). Slots with no accepted value can be filled with a no-op, which is important: the leader must fill gaps before serving reads, or a later leader could still commit something into that hole. Getting the gap-filling right is one of the standard Multi-Paxos implementation bugs.

Common misconceptions

"Paxos elects a leader." Single-decree Paxos has no leader concept at all; it agrees on a value. Leadership is an optimisation layered on top in Multi-Paxos, and its purpose is to avoid dueling proposers and skip Phase 1. You can run Paxos with no leader and it is correct, just slow and prone to livelock.

"Once a proposer gets a quorum of promises, its value will be chosen." No. It gets the right to run Phase 2 with some value, and the Phase 2a constraint may force that value to be someone else's. And even then, a higher-numbered prepare can arrive before its accepts land.

"Paxos guarantees the system makes progress." It guarantees safety unconditionally and progress only under synchrony assumptions (eventually, messages arrive within some bound and one proposer runs uncontested). FLP says no protocol can do better in a fully asynchronous model.

"Raft is a simplified Paxos, so it is weaker." It is not weaker. It is a different decomposition with the same guarantee, and in some respects it is stronger: Raft's leader-append-only and log-matching properties are constraints Paxos does not impose, which is what makes Raft easier to reason about and slightly less flexible.

"You need Paxos for replication." You need consensus for a single authoritative order. Plenty of replication is done with leader-follower plus a consensus-based failover decision, which uses consensus for the small metadata problem and simple log shipping for the bulk data. That is what most relational databases with automated failover do, and it is a sound architecture.

Interview delivery note

Say this verbatim: "The safety of Paxos is one sentence: any two quorums intersect, so a proposer that gathers a quorum of promises is guaranteed to learn about any value that might already have been chosen, and it is required to propose that value instead of its own." That sentence demonstrates you understand the mechanism rather than the ritual, and it is the answer to "explain Paxos" that takes fifteen seconds instead of five minutes.

The senior-versus-staff separator is the Phase 2a constraint. A senior engineer describes prepare and accept as two round trips. A staff engineer explains why a proposer sometimes cannot propose its own value, because that is where consensus actually lives, and follows it with "which is why I would never implement this and would use etcd." Pairing deep understanding with a refusal to build it yourself is the credibility signal here, not one or the other.

If asked to choose for a real system, commit: Raft, via an existing implementation, for the metadata plane only, with the data plane using something cheaper. Then name the cost you accepted: a round trip to a quorum on every metadata write, which in multi-region is tens of milliseconds.

The Staff & Team Lead Interview Reference