Paxos Fundamentals: Single-Decree Consensus

By the end of this lesson, you will be able to...

• Trace prepare, promise, accept, and chosen for one Paxos decision.

• Decide when a later proposer may choose a new value and when it must carry an earlier value forward.

• Separate Paxos safety from the conditions that let one proposer make progress.

Idea in one sentence: A later Paxos attempt may get a newer ballot, but it must first learn the accepted history held by an overlapping quorum and continue that history safely.

Core Insight

Three acceptors must choose one value for a configuration switch. The choices are deliberately small: X means “use configuration X”; Y means “use configuration Y.” Two proposers can be active because an earlier proposer can pause, a retry can begin, or two machines can both suspect that they should lead.

At first, a newer attempt seems simple. Proposer P2 chooses ballot 11, which is higher than P1's ballot 10, so perhaps P2 may simply send accept(11, Y) and move on.

That model works only when no earlier attempt has left safety-relevant evidence. It breaks when P1 may already have caused X to be accepted by enough acceptors to be chosen. A late message cannot erase that fact. If P2 chose Y independently, the system could have two different chosen values for the same decision.

Paxos prevents that outcome with a small discipline: before issuing a value at ballot 11, P2 asks a majority what they have already accepted and obtains promises that they will not accept lower ballots. The responses constrain the value P2 may issue. A higher ballot orders the attempt; it does not give its proposer permission to overwrite history.

The Small Situation: One Decision, Three Roles

This is single-decree Paxos: one run chooses one value. It is not yet a replicated log. The same process may play more than one role in a real system, but separating the roles makes the mechanism easier to inspect.

With three acceptors, any two are a majority. The important fact is not the number three. It is intersection:

earlier majority: A1 A2
later majority:      A2 A3

overlap: A2

Any majority that might choose a value and any later majority that prepares an attempt share at least one acceptor. That shared acceptor is the path by which evidence can travel from an old attempt to a new one.

An acceptor keeps two pieces of state, durably in a practical crash-recovery implementation:

highest promised ballot
highest accepted proposal, if any: (ballot, value)

The durable-storage detail matters. If A2 forgot a promise or an accepted proposal after a restart, a later attempt could fail to discover the very evidence the safety argument needs. The example assumes crash faults and uncorrupted messages, not Byzantine acceptors that lie about their state.

The Initial Model: The Newest Ballot Wins

We might first think: “Ballot 11 is newer than ballot 10, so P2 can choose its preferred value Y.” This fits a quiet system where P1 never received any acceptance, or where P2 has already checked a majority and learned that none of them accepted anything.

It becomes insufficient when messages are delayed. P1 may have sent an accept(10, X) request before it paused. P2 cannot tell from its own local state whether that request reached one acceptor, two acceptors, or none. A proposal accepted by a majority is chosen; one accepted by only one acceptor is not chosen, but it can still constrain the next attempt.

That last point is intentionally conservative. Paxos does not ask P2 to solve the harder question “was X definitely chosen?” before acting. It uses a rule that preserves any accepted value that could be relevant through the quorum evidence it gathers.

The missing mechanism is therefore not a clock or a winner announcement. It is a way to make a later attempt inherit the only history it can safely continue.

The Better Mechanism: Prepare, Promise, Then Accept

Plain meaning: Before proposing a value, ask enough durable witnesses what they remember and ask them not to accept an older competing attempt.

In this scenario: P2 asks a majority, for example A2 and A3, about ballot 11. Each useful reply both raises the acceptor's promise and reports its highest accepted proposal.

Technical name: This first round is Phase 1, or prepare/promise. The proposal round is Phase 2, or accept/accepted.

Phase 1: establish a safe attempt

P2 chooses a proposal number that is unique and higher than any it knows it has used:

P2 -> A2, A3: prepare(11)

If an acceptor has not already promised a higher ballot, it persists and returns:

promise: do not accept future proposals numbered below 11
accepted: my highest accepted (ballot, value), if I have one

The promise controls the future. Once A2 promises ballot 11, it will not later accept a ballot 10 request that arrives late. The accepted report describes the past. Both parts are needed: reporting old evidence without blocking older accepts leaves a race; blocking older accepts without reporting old evidence loses the reason for the rule.

When P2 receives promises from a majority, it selects its Phase 2 value as follows:

no responder reports an accepted proposal
  -> P2 may use any proposed value, such as Y

one or more responders report accepted proposals
  -> P2 must use the value from the highest-numbered accepted proposal reported

The choice is based on the highest accepted ballot in the replies, not merely the highest promise and not P2's personal preference. In a valid run, all values that this rule can carry forward are compatible with any already chosen value.

Phase 2: try to make that safe value chosen

Only after that selection does P2 issue a proposal:

P2 -> A2, A3: accept(11, selected value)

An acceptor accepts it unless it has already promised a ballot higher than 11. If the same (11, selected value) is accepted by a majority, that proposal and its value are chosen.

chosen != every replica or client has heard the result

Chosen is a fact about majority acceptance. Learners may discover it later through acceptor messages or a designated learner. This distinction lets a choice remain safe even when the news of the choice is delayed.

A Worked Trace: Two Similar Delays, Two Different Safe Choices

The following values and message timings are illustrative. They expose why Paxos distinguishes “accepted somewhere” from “chosen by a majority.”

Trace A: X was not chosen, so P2 may choose Y

P1 completed an earlier prepare round for ballot 10 and sent accept(10, X). Only A1 receives and accepts it before P1 pauses.

At time 1, X has one acceptance, not a majority. In Phase 1, the majority A2,A3 reports no accepted proposal. Because all majorities intersect, an already chosen X could not be hidden entirely outside that preparing majority: a majority that chose X would share an acceptor with A2,A3, and that acceptor would report an accepted proposal.

Therefore P2 may choose Y, and it becomes chosen when A2 and A3 accept it. A1 may later receive old messages, but its earlier lone acceptance of X cannot turn X into a conflicting chosen value; A2 and A3 have promised not to accept ballot 10 after their prepare replies.

Trace B: X was chosen, so P2 must carry it forward

Change one delivery. Before pausing, P1 reaches both A1 and A2 with accept(10, X). That already chooses X, even if no learner has yet heard the result. Later P2 prepares ballot 11 with A2,A3.

P2 wanted Y, but Phase 1 found (10, X) at the overlapping acceptor A2. The correct Phase 2 request is accept(11, X), not accept(11, Y). A later ballot may re-propose X; it cannot create a second chosen value.

So far: quorum intersection makes it impossible for a previously chosen value to be invisible to a later preparing majority. The prepare replies expose that evidence, and the selection rule turns the evidence into a constraint on the new proposal.

What the Mechanism Changes

Before this mechanism, a retrying proposer could treat silence and its own newer attempt as permission to overwrite the past. After it, a proposer may move forward only after a quorum gives it a consistent view of the accepted history relevant to safety.

This is why Phase 1 is more than leader election. It gives an attempt priority over lower ballots, but it also transfers an obligation: if the quorum reports an accepted value, the new proposer inherits it. Ballots, promises, and quorum intersection work together; removing any one of them breaks the simple argument.

Cost, Limits, and Signals

This improves safety under message delay, retries, crashes, and overlapping proposers. The trade-off is explicit: Phase 1 needs a majority of replies before a proposer can issue its value, and acceptors must persist promises and accepted proposals before relying on them after restart.

It also does not guarantee progress. Two proposers can repeatedly preempt one another: P1 prepares ballot 10, P2 prepares 11, P1 retries with 12, and neither completes Phase 2. The previous FLP lesson explains why timeouts and a stable leader are progress assumptions, not safety proofs. Paxos gets liveness when, for long enough, a distinguished proposer can communicate with a majority using a sufficiently high ballot.

Useful signals at this boundary are repeated higher-ballot rejections, prepare retries, and a rising rate of abandoned proposals. They indicate proposer contention or a path that cannot reach a stable majority. They do not mean that Paxos has chosen two values; safety should hold while progress stalls.

Single-decree Paxos also chooses only one decision. A replicated log needs one protected choice per slot. Re-running Phase 1 from scratch for each slot is safe but expensive, which is the pressure behind Multi-Paxos in the next lesson.

Common Confusions

Confusion: “The highest ballot gets to use any value.”

Why it is tempting: A higher ballot blocks lower ballots.

Better model: It gives the attempt priority, but Phase 1 may force its proposer to carry forward the highest accepted value reported by its majority.

Confusion: “An accepted value is already chosen.”

Why it is tempting: One acceptor has durable evidence for that value.

Better model: A value is chosen only when one proposal carrying it is accepted by a majority. A lone acceptance is not chosen, though it may still constrain a later proposer.

Confusion: “Chosen means every machine knows immediately.”

Why it is tempting: A client wants one visible answer.

Better model: Chosen is majority evidence; learning and dissemination are separate message flows and can happen later.

Check Your Understanding

Check: P2 receives Phase 1 replies from A2 and A3. A2 reports accepted (7, X) and A3 reports accepted (9, Y). What value must P2 send in accept(11, ?)?

Think first, then reveal.

Answer: Y. The proposer selects the value associated with the highest-numbered accepted proposal among the majority's replies: ballot 9, not ballot 7 and not a new preferred value.

Check: Why can P2 propose Y in Trace A even though A1 accepted X?

Think first, then reveal.

Answer: The preparing majority A2,A3 reported no accepted proposal. If X had already been chosen, a majority that accepted X would intersect A2,A3; the shared acceptor would report an accepted proposal. A1's single acceptance did not choose X.

Practice: Diagnose a Rejected Proposal

Four acceptors, A1 through A4, use any three as a quorum. P1 has ballot 20 and P2 has ballot 21. P1 completed Phase 1 with A1,A2,A3, but before its Phase 2 requests arrive, P2 completes prepare(21) with A2,A3,A4. None of those replies reports an accepted proposal.

1. What value may P2 issue at ballot 21?
2. What should A2 do if a delayed accept(20, X) arrives after it promised ballot 21?
3. If P2 then receives acceptances from A2,A3,A4, what exactly has been established, and what may still be delayed?

Model answer:

1. P2 may issue any proposed value because its preparing quorum reported no accepted proposal.
2. A2 must not accept it: its promise to ballot 21 rules out lower ballot 20.
3. The proposal (21, chosen-value) is chosen because a quorum accepted that same proposal. A learner, another replica, or the client may still not know it yet; notification is separate from the choice.

Connections

The previous lesson supplied the liveness boundary: silence and timeouts do not prove failure, so a protocol cannot promise progress in every asynchronous execution. Paxos uses that separation carefully—its safety rule does not rely on a timeout being correct.

The next lesson reuses this same evidence-preserving mechanism across many log slots. Multi-Paxos makes the steady path faster by amortizing the expensive prepare phase while a leader remains stable.

Resources

• [PAPER] Paxos Made Simple — Focus: derive Phase 1 from the requirement that a higher proposal preserve already chosen values.
• [PAPER] The Part-Time Parliament — Focus: read the original protocol framing after the two traces are comfortable.
• [ARTICLE/PAPER] Paxos Made Moderately Complex — Focus: connect the single-decree mechanism to a more implementation-oriented presentation.

Key Takeaways

• A single-decree Paxos run chooses one value when one proposal is accepted by a quorum.
• Phase 1 both blocks lower ballots and carries accepted evidence into the newer attempt.
• A newer proposer may choose freely only when its preparing quorum reports no accepted proposal; otherwise it carries forward the highest accepted value it learned.
• Safety can hold while progress fails: competing proposers and an unreachable majority can prevent a choice without allowing conflicting choices.
• Multi-Paxos keeps this safety argument and reduces the repeated Phase 1 cost across a log.