Paxos Prepare and Accept: What the Promises Are For

Paxos is usually described as two rounds of messages, and the description is accurate enough to implement from but not accurate enough to debug from. The protocol’s correctness rests on a single restriction that the first round enforces: an acceptor will not accept a proposal numbered lower than one it has already promised to consider. Everything else, including the majority requirement, the proposal numbering, and the leader’s freedom to choose any value in phase two, is downstream of that promise. Understanding why the promise must be about all lower numbers, rather than just about the last one accepted, is the difference between a working implementation and one that violates safety under an unlucky interleaving.

The problem the promises solve

A set of acceptors each stores a value it has accepted, initially nothing. Clients propose values. The safety requirement is that the acceptors never end up in a state where two different values have each been accepted by a majority, because a learner that reads a majority could then observe either value and the system would have decided twice.

Majority intersection alone does not prevent this. Two majorities overlap, so at least one acceptor sees both proposals, but seeing both is not the same as refusing the second. If acceptors accepted every proposal they were sent, every acceptor would end up with two values and the overlap would be useless. The protocol needs a rule that makes the overlapping acceptor reject the later proposal when accepting it would be unsafe, and the rule has to be enforceable with local information.

The local information available is: which proposals this acceptor has already promised, which it has already accepted, and what it learned from those. That is the entire state. Paxos’s insight is that these three facts, combined with a total order on proposal numbers, are sufficient to make the decision safe without any global coordination.

The two phases in message terms

Phase one. A proposer chooses a proposal number n larger than any number it has used before, and sends a prepare request carrying n to a majority of acceptors. An acceptor that receives prepare for n compares it against its recorded promise. If n is at least the promised number, it records the promise (durably, along with any value it has already accepted) and replies with the highest-numbered proposal it has accepted so far, or an indication that it has accepted nothing. If n is lower than the promised number, it replies with a rejection carrying the higher promised number so the proposer can retry with a larger one.

Phase two. The proposer collects replies from a majority. If any reply carried an accepted value, the proposer must adopt the value from the reply with the highest proposal number among those; otherwise it may use its own proposed value. It then sends an accept request carrying (n, value) to a majority. An acceptor that receives accept for n accepts if and only if it has not promised a number greater than n; it records the acceptance durably and replies.

The critical constraint is in phase one’s reply: the acceptor reports the value it has accepted, not the value it promised. Promises carry no value, because at prepare time the acceptor does not know what the proposer intends to propose. The proposer learns values only from acceptances.

Why the proposer must adopt a value it did not choose

The rule that the proposer must use the highest-numbered accepted value from the phase-one replies is the one that looks like an implementation detail and is actually the whole safety argument.

Suppose a value v has been accepted by some majority. A new proposer runs phase one with number n and gets replies from a majority. The two majorities intersect in at least one acceptor a. That acceptor accepted v at some proposal number m, so its recorded promise is at least m, and it will only answer a prepare for a number at or above its promise. A new proposer whose phase one succeeds therefore has n ≥ m, and since proposal numbers are unique, n > m whenever the two proposals are distinct. Acceptor a will report v, or a value it accepted at an even higher number, in its phase-one reply.

If the proposer ignored those reported values and proposed its own value w, then the acceptors in its phase-two majority that had accepted v would accept w, and now a majority has accepted v and a majority has accepted w. Safety is gone. The adoption rule is what prevents this: because the proposer must pick the highest-numbered accepted value it saw, and the intersection guarantees it sees v if v was accepted at a lower number, it can only propose v or something accepted at a still higher number, which by induction is itself consistent.

The induction is the actual proof, and its shape explains the phrase “highest-numbered” rather than “any”. A proposer that adopted the lowest-numbered accepted value it saw would be picking a value that a later round may have superseded. The total order on proposal numbers is what makes “highest” meaningful, which is why proposal numbers must be unique across proposers and not merely increasing per proposer.

What happens without phase one

Collapsing the two phases into a single accept round produces a protocol that appears to work in every test and violates safety under concurrency. Each proposer sends its value to a majority and the majority accepts whichever arrives first; with two concurrent proposers and a five-node cluster, the acceptors can split 3–2 and 2–3, giving two majorities with different values. The intersection node accepted both values, and there is no rule that makes either one win.

The two-phase structure exists because the first phase is the only point at which a proposer can learn what has already happened. A single-round protocol has no such point, so it has no way to avoid overwriting a value that some other proposer already committed. This is not a matter of tuning or of adding a tiebreak after the fact; the information is simply not available at the time the accept is sent.

The same argument explains why phase one must contact a majority rather than a single node. A single-node phase one might not intersect the majority that accepted a previous value, so the proposer would learn nothing and propose its own value, splitting the acceptors. The majority requirement in phase one is exactly the requirement that the phase-one quorum intersect every previously successful phase-two quorum.

Proposal numbers and the livelock

Proposal numbers must be globally unique across proposers, not just increasing within one. Two proposers that both pick number 7 will have their acceptances treated as the same proposal by acceptors that already promised 7, and the “highest-numbered” comparison becomes ambiguous. Implementations typically give each proposer a distinct identifier and compose the number from a counter plus that identifier, so that the pair is unique and ordered.

Uniqueness creates the protocol’s best-known liveness problem. Two proposers can alternate: A prepares with 1 and is about to accept when B prepares with 2, causing the acceptors to reject A’s accept; A retries with 3 and B’s accept is rejected; and so on. Neither makes progress. This is not a safety violation, since no value is decided, but it is an availability failure that the basic protocol does not prevent.

The standard mitigation is to designate a single proposer, a distinguished or leader proposer, that is the only one allowed to initiate proposals. The other nodes forward requests to it. This converts Paxos into a leader-based protocol with the same shape as Raft, and it introduces the leader-election problem that Raft handles explicitly. Multi-Paxos goes further: once a leader has completed phase one for a proposal number, it can reuse that number for all subsequent values, so the expensive phase-one round is paid once per leadership tenure rather than once per value. The remaining round is a single accept exchange per value, which is why the protocol’s steady-state cost is one round trip.

A randomized backoff on retry also reduces the collision rate without a designated leader, and is used in settings where no stable leader exists. It does not eliminate the livelock; it makes it unlikely. Systems that need a guarantee rather than a probability use a leader.

Durability and the point of no return

An acceptor’s promise and its accepted value must be durable before the reply is sent. A node that promises 5, crashes, restarts with no memory, and then accepts 3 has undone a promise that another proposer is relying on. The failure is not detectable by the proposer, because the reply it received was a promise that the acceptor then forgot.

This makes each Paxos round cost at least one stable-storage write per participating acceptor, and in the common implementation the promise and the acceptance are two separate writes. Batching helps: a leader that is processing many values can write many acceptances in one fsync. The latency floor is nevertheless the flush, not the network, and this is why Paxos deployments are sensitive to storage latency in a way that is easy to underestimate when reasoning about the protocol on paper.

The number of writes can be reduced by noting that a promise for a higher number subsumes promises for lower ones, and that an acceptance for n implies a promise for n. An implementation can therefore write a single record per acceptor holding the highest promised number and the value accepted at that number, and update it once per round. The safety argument is unchanged as long as the record is durable before the reply leaves.

Learners and the read path

The acceptors are not the only participants. Learners observe the outcome, and the standard arrangement has each acceptor send its acceptance to every learner, or have a distinguished learner collect and redistribute. The first is O(n²) messages per decision; the second is O(n) but adds a hop of latency and a dependency on one node.

The read path is where Paxos differs most visibly from a log-replicating protocol. A learner that has seen an acceptance from a majority knows the value is chosen, but it may not know whether a later proposal has superseded it. Reads therefore either go through the protocol, where a read is a proposal for a no-op that confirms the current value, or require a leader with a valid lease. The lease and read-index techniques are the standard way to serve reads without a round trip, and they depend on assumptions that Paxos itself does not make.

Where the promise rule shows up elsewhere

The same structure appears in protocols that do not call themselves Paxos. A Raft follower’s durable votedFor field is a promise: it will not vote for a second candidate in the same term. Raft’s log-suffix check is the equivalent of the phase-one reply, telling a candidate what the voter already holds. The difference is that Raft makes the value implicit in the log and makes the promise per-term rather than per-proposal-number, which removes the livelock at the cost of requiring an election before any progress.

The promise rule also explains why reconfiguration is hard in Paxos. The set of acceptors is part of the protocol’s configuration, and a promise made by an acceptor in one configuration is not visible to an acceptor in another. Changing the membership while proposals are in flight requires a mechanism that treats the configuration as a value decided by the protocol itself, which is what the joint-consensus and single-server-change approaches do.

The mechanism is small: two rounds, one durable field, one adoption rule. The difficulty is entirely in the interleavings, and the adoption rule is the part that no amount of message reordering can make optional.