Paxos Fundamentals: Single-Decree Consensus

The core idea: Single-decree Paxos preserves safety by forcing every new proposal attempt to learn enough accepted history that it cannot choose a conflicting value.

Core Insight

Imagine three acceptors trying to choose one configuration value. Proposer P1 starts with value A and reaches some acceptors, but messages are delayed before the result is widely known. A little later, proposer P2 starts a higher-priority attempt and wants value B.

The danger is not that two proposers exist. Distributed systems often have retries, restarts, and competing leaders. The danger is that a later proposer might act as if earlier attempts left no trace. If value A was already close to being chosen, P2 must not accidentally choose conflicting value B.

Single-decree Paxos is the safety core for that situation. Its message flow is not ceremony. It is a way to transfer the obligation to respect history from older attempts to newer attempts. The trade-off is sharp: Paxos gives an elegant crash-fault safety argument for one decision, but the full two-phase shape is awkward and expensive if repeated from scratch for every log slot.

The Problem: Later Attempts Must Respect Earlier Evidence

Paxos relies on quorum intersection. If one majority might already have accepted a value, any later majority must overlap it somewhere.

With three acceptors:

earlier majority: A1 A2
later majority:      A2 A3

overlap: A2

That overlap is the bridge between attempts. If A2 remembers that an earlier proposal was accepted, a later proposer can discover that fact and avoid choosing a conflicting value.

Ballot numbers give proposal attempts an order:

ballot 10: P1 tries value A
ballot 11: P2 tries value B

A higher ballot is not a wall-clock timestamp and does not mean "my value should win because I arrived later." It means the proposer is trying to run a newer attempt that acceptors may promise to follow. But the newer attempt is constrained: before it freely proposes a value, it has to ask an overlapping quorum what accepted history already exists.

The safety intuition is:

ballots order attempts
quorums overlap attempts
Phase 1 transfers accepted history into the newer attempt

Phase 1: Prepare and Promise

Suppose P2 wants to run ballot 11. It begins with:

P2 -> quorum: prepare(11)

An acceptor that grants the request makes a promise:

I will not accept proposals from ballots lower than 11.

That promise prevents older attempts from continuing underneath the newer one. But the promise is only half the point. The acceptor also reports the highest-numbered proposal it has already accepted, if any.

That second part is the safety payload. It tells P2 whether earlier accepted history constrains the safe value for this attempt.

If the quorum reports no accepted value, P2 can propose its own value. If any acceptor reports an accepted value, P2 must carry forward the value with the highest accepted ballot among the reports.

This is the rule that often feels strange on first read:

The proposer may have to abandon its preferred value.

It does that because leadership in Paxos is not permission to ignore history. Leadership is permission to continue history safely.

Phase 2: Accept and Chosen

After Phase 1, the proposer has either learned that no relevant accepted value exists or adopted the safest value revealed by the quorum. Then it sends:

P2 -> quorum: accept(11, value)

If a quorum accepts the same (ballot, value) pair, that value is chosen.

A compact flow looks like this:

Phase 1:
  proposer -> quorum: prepare(ballot)
  quorum   -> proposer: promise(ballot, highest accepted value if any)

Phase 2:
  proposer -> quorum: accept(ballot, safe value)
  quorum   -> proposer: accepted(ballot, safe value)

The system does not need every acceptor to know immediately that the value is chosen. A value is chosen when the quorum evidence is strong enough. Learning and dissemination can happen afterward. That distinction matters because many protocol bugs come from confusing "some node learned it" with "a quorum made it durable enough that later attempts must preserve it."

Worked Example: Why P2 Cannot Freely Choose B

Use three acceptors: A1, A2, and A3.

P1 sends accept(10, A) to A1 and A2. Suppose A1 accepts, but the message to A2 is delayed. Then P2 starts ballot 11 and contacts A2 and A3.

If A2 had already accepted (10, A), it would report that during Phase 1. Then P2 would be forced to continue with value A, not its preferred value B.

If no acceptor in P2's quorum reports an accepted value, then no earlier chosen value can be hidden from the new quorum. That is the payoff from quorum intersection.

The rule is conservative because uncertainty is the point. Paxos does not ask the proposer to know whether A was definitely chosen. It asks the proposer to preserve any value that might be safety-relevant according to quorum evidence.

Why Single-Decree Paxos Is Not the Whole Log

Single-decree Paxos chooses one value for one decision point. A replicated log needs many decisions:

slot 41 -> command A
slot 42 -> command B
slot 43 -> command C

Running the full leadership contest for every slot would be correct, but expensive. It adds round trips, creates more opportunities for proposer contention, and makes the hot path harder to operate.

That is why the next lesson moves to Multi-Paxos. Multi-Paxos does not throw away the safety argument. It amortizes the expensive leadership setup across many slots when one proposer is stable enough to act as leader.

So the right mental model is:

single-decree Paxos:
  minimal safety core for one chosen value

Multi-Paxos:
  reuse that safety core across a replicated log

Common Misreadings

"The highest ballot always gets to choose its own value" is wrong. A higher ballot gives priority to the attempt, but Phase 1 may force the proposer to continue an earlier accepted value.

"Phase 1 is just leader election" is incomplete. Phase 1 establishes priority, but it also transfers safety-relevant accepted history.

"Chosen means everyone knows" is also wrong. Chosen means the quorum evidence is sufficient. Other replicas and clients may learn the chosen value later.

Connections

This lesson uses the FLP lesson's separation of safety and liveness. Paxos can preserve safety despite delays and competing proposers, but progress depends on the environment eventually allowing one proposer path to complete.

It also sets up Multi-Paxos directly. Once the single-decree safety core is clear, the next optimization is easier to understand: avoid paying Phase 1 for every slot when a stable leader context can be reused.

Resources

• [PAPER] Paxos Made Simple
  • Focus: Read Phase 1 as the mechanism that discovers accepted history.
• [PAPER] The Part-Time Parliament
  • Focus: Use the original framing after the safety story is familiar.
• [ARTICLE] Paxos Made Moderately Complex
  • Focus: Good bridge from the single-decree idea toward implementation details.

Key Takeaways

• Paxos preserves safety by making newer attempts learn accepted history from an overlapping quorum.
• Phase 1 is not ceremony; it both establishes ballot priority and transfers safety obligations.
• Single-decree Paxos is the safety foundation for one value, while replicated logs need optimizations such as Multi-Paxos.