Consensus and Paxos: How a Decision Survives a Failed Leader

Three replicas need to agree on the next command in a log. One leader sends a proposal, two replicas store it, and the leader crashes before announcing the result. Can its replacement choose a different command?

Paxos answers this by making future proposals respect evidence stored at acceptors. Understanding that evidence is more useful than memorizing “a majority agrees.” First, however, it helps to see what timing assumptions change.

1. What must consensus guarantee?

Each process proposes a value. A decision is final: the process cannot later replace it.

Definitions vary slightly between texts. Here, agreement includes a process that decides and subsequently crashes. We assume crash failures, not processes that lie or send malicious messages. The input constraint rules out the useless algorithm “always decide 0.”

Synchronous means known bounds on message delay and process steps, sufficient to run timed rounds. Asynchronous means no such bounds are available. These are system assumptions, unrelated to whether an API uses async or blocks a thread.

2. Why synchronous consensus takes f + 1 rounds

Assume N processes, at most f < N crash-stop failures, and reliable communication. A non-faulty sender’s messages arrive at non-faulty recipients before the round ends. A sender that crashes during its send loop may reach only some recipients.

Every process keeps a set of known input values. During each round it sends newly learned values to everyone, then incorporates what it receives. After completing f + 1 rounds, every survivor chooses the minimum in its set.

known = {my_input}
new_values = {my_input}

repeat f + 1 times:
    send new_values to every process
    received = union of values received during this round
    new_values = received - known
    known = known union received

decide min(known)

The choice of min is simply a deterministic rule everyone shares. The important result is that survivors finish with the same set.

Example: one crash hides a value for one round

Let f = 1. A starts with 0; B and C start with 1.

sequenceDiagram
    participant A as A: input 0
    participant B as B: input 1
    participant C as C: input 1
    Note over A,C: Round 1
    A->>B: Send 0
    Note over A: Crashes before sending to C
    B->>C: Send 1
    C->>B: Send 1
    Note over B: known = {0, 1}
    Note over C: known = {1}
    Note over B,C: Round 2
    B->>C: Forward newly learned 0
    Note over B,C: Both have {0, 1}. Both decide 0

Stopping after round 1 would let B decide 0 and C decide 1. The second round removes that difference.

Why does this generalize? Suppose one survivor learns a value only in the final round and another still lacks it. The sender must have crashed after sending to only one of them. For that sender not to have spread the value earlier, it must itself have learned it in the previous round through another partial send and crash. Following this hidden chain backward requires f + 1 distinct crashes. That contradicts the limit of f.

This proof depends on the round boundary. With unbounded delays, a missing message does not tell us that a sender failed.

3. Paxos separates votes from the decision

Basic Paxos chooses one value for one instance, such as one log position. Repeating it for different positions creates a replicated log; a ballot number is not a log position.

A single machine can perform all three roles. With three acceptors, a majority is two; with five, it is three. In general, 2f + 1 acceptors leave a majority available after f failures. Availability alone does not guarantee progress under arbitrary delays or endless proposer competition.

An acceptor retains its highest promised ballot and highest accepted (ballot, value). For recovery after a crash, these records must survive and be stored before the corresponding acknowledgment is sent. Ballots must remain unique across proposer restarts. A pair such as (counter, proposer ID), ordered consistently, is a common way to distinguish proposers.

4. Two phases, then learning

Phase 1: prepare and promise. A proposer sends prepare(n). An acceptor that has not promised a higher ballot can promise to reject future accept requests below n. It reports its highest accepted proposal, if any.

After collecting promises for n from a majority, the proposer selects its value:

• If any reply reports an accepted proposal, use the value with the highest accepted ballot among those replies.
• If none does, choose a new proposed value.

Phase 2: accept. The proposer sends accept(n, value). An acceptor can accept it unless it has already promised a higher ballot. A majority accepting the same proposal makes its value chosen.

Learning. Acceptance reports or a decision announcement let learners discover the result. An announcement communicates the decision; it is not the event that creates it.

sequenceDiagram
    participant P as Proposer
    participant A as Acceptor A
    participant B as Acceptor B
    participant L as Learner
    P->>A: prepare(7)
    P->>B: prepare(7)
    A-->>P: promise 7. No accepted proposal
    B-->>P: promise 7. No accepted proposal
    Note over P: Majority replies. Choose X
    P->>A: accept(7, X)
    P->>B: accept(7, X)
    Note over A,B: Both persist acceptance: X is chosen
    A-->>P: accepted(7, X)
    B-->>P: accepted(7, X)
    P-->>L: chosen X
    Note over L: X is now learned here

The third acceptor is omitted from this diagram. Two of three are sufficient. The lecture presents an election, bill, and law analogy; the precise distinction here follows the prepare/accept rules in Lamport’s Paxos Made Simple.

5. Worked failure: the leader disappears before announcing X

Assume acceptors A, B, C. Ballot 7 has already completed its prepare phase.

The new proposer does not need to prove that ballot 7 reached a majority. B’s accepted proposal is enough to constrain this attempt. The value-selection rule uses accepted evidence, not only announced decisions.

flowchart LR
    Old["Old majority: A + B"] --> B["B remembers accepted X"]
    B --> New["New prepare majority: B + C"]
    New --> Keep["Ballot 8 must carry X"]

Why the highest accepted ballot matters

Suppose only A accepted (7, X). X is not yet chosen. A proposer for ballot 8 can prepare with B and C, find no accepted proposal there, and get (8, Y) accepted by both. Y is now chosen.

For ballot 9, a prepare quorum of A and B reports (7, X) and (8, Y). The proposer must choose Y. Picking any reported value would allow X to overwrite an already chosen Y.

Quorum intersection supplies a shared acceptor. The promise and value-selection rules determine what its evidence means. Together they preserve the invariant: once a proposal chooses X, every higher ballot that succeeds must choose X. A shared acceptor may later report a higher ballot, so the safety argument also relies on carrying that same value forward through intervening ballots.

6. Safety can hold while progress stops

Two proposers can repeatedly interrupt each other. P completes prepare 10; Q completes prepare 11 before P’s accept requests arrive. P is rejected, tries 12, and preempts Q. No conflicting decision occurs, but no value is chosen.

A stable proposer that can communicate with a responsive majority, without continual higher-ballot interference, can complete the protocol. Practical systems use leader selection, retries, and timing assumptions to obtain that situation. A timeout can justify another attempt; it cannot prove the previous proposer has died.

Multi-Paxos applies this machinery across a sequence of log positions and can amortize preparation under a stable leader. It still has to preserve prior accepted values during takeover. Consensus also does not by itself deduplicate client retries or make an external payment happen exactly once.

The FLP proof explains why no deterministic algorithm can promise termination for every permitted asynchronous execution with even one possible crash.

Check your understanding

1. A majority accepts X, but every acknowledgment is delayed. Is X chosen? Yes. Acceptance creates the fact; replies let other processes learn it.
2. One acceptor reports X in prepare. May the proposer ignore it because no majority is known? No. It follows the highest accepted ballot rule across its prepare quorum.
3. Does a higher ballot erase an earlier decision? No. It orders attempts and must preserve any chosen value.
4. Does “eventually” imply a fixed deadline? No. In Paxos, progress additionally depends on suitable communication and leadership conditions; asynchrony alone gives no unconditional termination guarantee.

Reading basis

These notes develop the supplied Cloud Computing Concepts, Part 1 lectures 3.1 The Consensus Problem, 3.2 Consensus in Synchronous Systems, and 3.3 Paxos, Simply, using their slides and transcripts. The examples and diagrams are redrawn teaching examples. The accepted/chosen/learned distinction and precise proposal rule are cross-checked against Paxos Made Simple, sections 2.2–2.4, linked above.