How to Learn Paxos Consensus: Proposers, Acceptors, Quorums, Prepare–Accept Rounds, Safety and Multi-Paxos Engineering

How can several machines agree on one value when messages can be delayed, duplicated or lost and some machines can crash halfway through the conversation? Paxos is a foundational answer to that consensus problem. Its difficulty is not that the core rules are enormous. The difficulty is learning which rule protects safety, which mechanism merely helps progress, and what must remain true across failures.

This Learning Hall article develops classic Paxos from a three-machine thought experiment to quorum reasoning, prepare/accept rounds, crash recovery and Multi-Paxos engineering. It complements the broader Distributed Algorithms article and the separate Raft Consensus article; it does not replace either wider job.

Quick Read

Paxos solves consensus: processes must choose one value without allowing two different values to be chosen.
Proposers suggest values; acceptors participate in the voting protocol; learners discover chosen values. These are logical roles and may share physical processes.
Proposal or ballot numbers impose an order on competing rounds.
A value becomes chosen when a quorum—classically a majority—of acceptors accepts the same proposal.
Majority quorums intersect, so a later successful round cannot avoid all evidence from an earlier chosen round.
Phase 1 gathers promises and prior accepted evidence; Phase 2 asks acceptors to accept the value selected under the Paxos rule.
Safety and liveness are different. Paxos protects agreement under asynchronous message behaviour, but progress needs additional practical mechanisms such as stable leadership and failure detection assumptions.
Multi-Paxos amortises leadership/Phase-1 work across a sequence of consensus instances.

1. Beginner Level: What Does Consensus Need to Guarantee?

Imagine three replicas, A, B and C. A client wants them to agree that the next command is X. Another client may concurrently propose Y. Messages can arrive in different orders. One machine may stop responding.

The central safety requirement is simple to state:

Once a value is chosen, no different value may ever be chosen for that same consensus instance.

Consensus protocols may also require validity and eventual progress under stated assumptions, but agreement is the first line that must never be crossed. A system that sometimes pauses is inconvenient. A system that commits two incompatible histories has lost the meaning of consensus.

2. Why “Ask Everyone and Take the Majority” Is Not Enough

Suppose proposer P1 sends X and receives some replies. Before it finishes, proposer P2 sends Y with a newer round number. If each proposer simply counts whatever replies it sees, delayed messages can create inconsistent partial views.

Paxos needs more than majority counting. It needs acceptors to remember promises about newer rounds and to report evidence of values they have already accepted. The protocol is designed so a later proposer is constrained by that earlier evidence.

3. The Three Logical Roles

Proposer: initiates a proposal round and tries to get a value chosen.
Acceptor: responds to prepare requests and may accept proposals while obeying its promise rules.
Learner: discovers which value has been chosen so the system can act on it.

These names describe protocol responsibilities, not necessarily separate servers. A production node can perform more than one role. Keeping the roles conceptually separate first makes the safety argument easier to see.

4. Proposal Numbers Create an Ordered Contest

Each proposal round has a unique, totally ordered number n. Two concurrent proposers must not accidentally use the same number for different rounds. A common construction combines a local counter with a proposer identifier so numbers remain unique while still being comparable.

Higher numbers do not mean a value is “more correct.” They order protocol rounds so acceptors can decide which old messages should no longer influence their promises.

5. Phase 1: Prepare and Promise

A proposer chooses a fresh proposal number n and sends a prepare request to acceptors. An acceptor that can honour n promises not to accept future proposals numbered below n. It also reports the highest-numbered proposal it has already accepted, if any, including that proposal’s value.

The proposer waits for replies from a quorum. The reports are not administrative metadata. They are the evidence that decides which value the proposer is allowed to carry into Phase 2.

6. The Value-Selection Rule Is the Safety Hinge

After obtaining a quorum of Phase-1 replies:

If none of those acceptors reports a previously accepted proposal, the proposer may use its own candidate value.
If one or more reports a previously accepted proposal, the proposer must use the value belonging to the highest-numbered accepted proposal among those reports.

This rule is easy to omit in a shallow explanation and impossible to omit from a correct one. It is how a later round carries forward the value that may already have become chosen.

7. Phase 2: Accept Request and Accepted

The proposer sends an accept request containing proposal number n and the selected value v. An acceptor accepts it unless it has already promised not to accept proposals below some higher number. If a quorum accepts the same numbered proposal/value pair, that value is chosen.

Learners can be informed through several communication arrangements. The learning mechanism affects message cost and recovery behaviour, but it must not redefine what “chosen” means.

8. Why Majority Quorums Matter

With three acceptors, any majority contains at least two. Any two majorities must share at least one acceptor. More generally, any two majority quorums intersect.

Suppose X was chosen by one majority. A later proposer completing Phase 1 must contact another majority. Because the two quorums intersect, the later proposer cannot gather a quorum while avoiding every acceptor from the earlier chosen quorum. The Paxos value-selection rule uses the accepted evidence carried through this intersection so that later successful proposals remain compatible with the chosen value.

Quorum intersection is the geometry underneath the protocol. The messages are machinery built around that set-theoretic fact.

9. A Worked Three-Acceptor Trace

Let A, B and C be acceptors.

P1 starts proposal 10 with candidate X.
A and B promise proposal 10; neither reports a prior accepted value.
P1 sends accept(10, X).
A and B accept. X is now chosen by a majority.
Later P2 starts proposal 20 with its own desired candidate Y.
P2 receives promises from B and C.
B reports that it accepted (10, X).
P2 must therefore propose X in Phase 2, not Y.

The later proposer can have a different client preference, a higher proposal number and a different quorum. It still cannot overwrite the already chosen value.

10. The Safety Invariant in Plain Language

A useful way to hold Paxos in memory is:

A later successful round must discover enough of the past to avoid choosing a value incompatible with an earlier chosen round.

Proposal numbers order rounds, quorum intersection guarantees overlap, acceptors preserve accepted evidence, and the proposer’s highest-accepted-value rule carries the relevant value forward. Removing any one of those pieces without replacing its safety function changes the proof, not just the implementation.

11. Simplified Pseudocode

PROPOSER(n, candidate):
    send PREPARE(n) to acceptors
    promises = wait for a quorum of valid replies

    if any promise reports a prior accepted proposal:
        value = value from the highest-numbered accepted proposal
    else:
        value = candidate

    send ACCEPT(n, value) to acceptors
    if a quorum accepts:
        value is CHOSEN

ACCEPTOR STATE:
    highest_promised
    accepted_number
    accepted_value

ON PREPARE(n):
    if n > highest_promised:
        highest_promised = n
        persist required state
        reply PROMISE(n, accepted_number, accepted_value)

ON ACCEPT(n, value):
    if n >= highest_promised:
        highest_promised = n
        accepted_number = n
        accepted_value = value
        persist required state
        reply ACCEPTED(n, value)

This pseudocode is for reasoning, not a drop-in distributed-system implementation. Real systems must define message identity, persistence boundaries, retransmission, membership, state transfer and many other details explicitly.

12. Crash Recovery Means Some State Cannot Be Forgotten

If an acceptor can crash and later restart as part of the same protocol identity, it cannot safely return with amnesia about promises and accepted proposals that the safety argument assumes survive. Production designs therefore define which acceptor state is durable and exactly when it must reach stable storage relative to sending replies.

This is a general lesson in distributed algorithms: a proof about a state machine is only as good as the implementation’s guarantee that the state survives the failure model claimed by the system.

13. Safety Is Not Liveness

Two proposers can repeatedly pre-empt each other with higher proposal numbers. The system can remain safe—never choosing two different values—while failing to make progress quickly. Network partitions can also leave no reachable quorum on one side.

Practical systems use leader-election or leader-stabilisation mechanisms, retries, timeouts and failure detectors to improve liveness. Timeouts do not prove a remote machine is dead; they are operational signals used under additional timing assumptions. Keeping safety and liveness arguments separate prevents many distributed-systems misconceptions.

14. From Single-Decree Paxos to Multi-Paxos

One instance of classic Paxos chooses one value. Replicated logs need an ordered sequence of decisions. Multi-Paxos runs consensus across log slots while exploiting a stable leader/ballot so the expensive preparation work can be amortised rather than repeated from scratch for every normal-case command.

The optimization does not abolish the safety obligations. Leadership can change, old messages can reappear, replicas can lag, and holes can exist in a log. A correct implementation must recover the state needed to continue each slot safely.

15. Paxos and Raft: Compare the Learning Jobs Carefully

Raft and Paxos both support fault-tolerant replicated state machines, but they package the reasoning differently. Raft makes leader election, log replication and safety rules explicit in a particular protocol structure. Paxos is often studied through ballots, quorums and value-selection constraints, then extended into Multi-Paxos systems.

The useful comparison is not “which name is better?” It is whether a learner can identify the safety invariant, quorum requirement, leadership assumptions, persistent state and recovery behaviour in either system.

16. Production Failure Modes to Simulate

Delayed messages: an old prepare or accept arrives after a newer ballot.
Duplicate messages: retries must not create duplicate logical decisions.
Reordered messages: network arrival order cannot be treated as protocol order.
Crash after persistence but before reply: recovery must remain safe.
Crash after reply but before a later write: exposes incorrect persistence ordering.
Competing proposers: tests pre-emption and liveness behaviour.
Minority partition: should not invent a majority.
Replica lag: learners and state machines may need catch-up mechanisms.
Proposal-number reuse: breaks assumptions about round identity.
Membership change: quorum intersection across configurations must be reasoned about explicitly.

17. Engineering Is Larger Than the Core Pseudocode

Google’s “Paxos Made Live” account is valuable because it documents the distance between a concise consensus description and a production fault-tolerant database. Real systems need configuration management, durable storage, recovery, observability, testing, operator behaviour and handling of unexpected interactions between algorithmic and engineering assumptions.

This does not make the core algorithm unimportant. It means professional competence has two layers: preserve the proof obligations, and then engineer the surrounding system so reality does not violate the model those obligations depended on.

18. How to Test a Consensus Implementation

Unit tests are necessary but insufficient. A strong test programme can generate message delays, drops, duplication, process crashes and restarts while checking invariants over the resulting histories. Deterministic simulation makes rare interleavings reproducible. Model checking or exhaustive state exploration on a small system can reveal traces that ordinary happy-path tests almost never reach.

The test oracle should focus on safety properties—such as never learning two different chosen values for the same slot—as well as progress under the timing/failure assumptions the implementation claims to support.

19. Learn Paxos by Tracing Evidence, Not Memorising Messages

For beginners, start with three acceptors and paper cards. Predict what each acceptor remembers after every message. Run a worked trace. Investigate where two quorums overlap. Modify the trace by delaying a message or introducing a second proposer. Only after those states are visible should the learner implement a simulator.

This matches a broader lesson from programming education: worked examples are most useful when their support fades. A learner should eventually reconstruct the protocol from invariants and failure cases rather than from remembered message order.

20. Beginner-to-Professional Progression

Beginner: explain consensus, majority intersection and why chosen values cannot later change.
Intermediate: trace prepare/promise and accept/accepted rounds with two competing proposers.
Advanced: state the safety invariant, reason about crash/restart persistence, implement a deterministic simulator and test adversarial message schedules.
Professional: build Multi-Paxos-style log reasoning, define durability and membership semantics, separate safety from liveness, instrument recovery paths and validate the system under fault injection and reproducible distributed traces.

21. Practice Problems

With five acceptors, what is the smallest majority quorum? Prove that any two such majorities intersect.
Construct a trace in which P1 starts first but P2 completes a higher-numbered prepare before P1’s accept requests arrive.
Show why a proposer cannot simply choose its own value after discovering a previously accepted value in its Phase-1 quorum.
Simulate an acceptor crash and restart. Which fields must survive for your stated failure model?
Create a deterministic message scheduler that explores duplicate and reordered messages.
Explain a scenario that is safe but temporarily not live.
Describe what a stable Multi-Paxos leader can amortise and which safety evidence still matters when leadership changes.

22. Sources and Further Reading

Final idea: Paxos becomes much easier to reason about when every message is connected to an invariant. Quorums guarantee overlap. Acceptors preserve evidence. Ballot numbers order competing rounds. Later proposers carry forward the value that the past may already have made irreversible. The professional skill is preserving those truths even when the network behaves in the least convenient order imaginable.

Small Group Tutorials