Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 36 ยท Consensus and Coordination

Consensus and Paxos

Understand the consensus problem, why FLP says it cannot be fully solved, and how single-decree Paxos stays safe. Run a Paxos simulation in your browser.

Sooner or later every distributed system needs its nodes to agree on something: who the leader is, which transaction committed, what the next entry in the log is. Agreement sounds easy until messages get lost, delayed or reordered and nodes crash at the worst moment. The problem of getting a group of unreliable nodes to settle on one value is called consensus, and it is the foundation under databases like etcd, ZooKeeper, Spanner and CockroachDB.

This lesson explains what consensus requires, why it is theoretically impossible to guarantee in every case, and how Paxos, the best known consensus algorithm, gets around that. You will run a small Paxos simulation and see why a value, once chosen, can never be un-chosen.

The consensus problem

Each node can propose a value. A consensus protocol must satisfy three properties:

  • Agreement: no two nodes decide different values.
  • Validity: the decided value was proposed by some node (no inventing values).
  • Termination: every non-faulty node eventually decides.

The first two are safety properties: nothing bad ever happens. Termination is a liveness property: something good eventually happens. Keep that split in mind, because it is the key to Paxos.

FLP impossibility in plain language

In 1985 Fischer, Lynch and Paterson proved a famous result, known as FLP. In a fully asynchronous system, where messages can take arbitrarily long and there is no bound on how slow a node can be, no deterministic algorithm can guarantee consensus if even one node may crash.

The intuition is about not being able to tell slow from dead. Suppose the protocol is waiting for a reply from node X. If it waits forever, it may never finish. If it gives up and decides without X, X may have been alive and decided something else. An adversarial schedule of message delays can keep the protocol undecided forever.

FLP does not say consensus is impossible in practice. It says you cannot have guaranteed termination and safety under a completely asynchronous model. Real protocols keep safety always and get liveness whenever the network is reasonably well behaved. See failure and system models for the partially synchronous model that makes this work.

The consensus checklist

Agreement Nobody decides a different value.
Validity The value was really proposed.
Termination Everyone alive eventually decides.

Agreement and validity are safety. Termination is liveness.

1 / 2

Single-decree Paxos

Paxos decides one value (a "single decree"). Longer logs run many independent Paxos instances, which is called Multi-Paxos. There are three roles, and one machine often plays all of them:

  • Proposers suggest values.
  • Acceptors vote. A value is chosen when a majority of acceptors accept it.
  • Learners find out what was chosen.

Every proposal has a unique, increasing proposal number n. Each acceptor remembers three things: the highest number it has promised (promised), and the highest proposal it has accepted (accepted_n, accepted_v).

Phase 1: prepare and promise

A proposer picks a number n and sends prepare(n) to the acceptors. An acceptor that has not promised anything >= n replies with a promise: it will never accept a proposal numbered below n. The reply also carries the proposal it has already accepted, if any.

Phase 2: accept

If the proposer receives promises from a majority, it sends accept(n, v). The value v is not entirely free:

  • If any promise reported an already accepted value, the proposer must use the value with the highest accepted number.
  • Only if no acceptor reported a value may the proposer use its own.

An acceptor accepts accept(n, v) unless it has promised a higher number since. When a majority has accepted the same proposal, the value is chosen.

sequenceDiagram
    participant P as Proposer
    participant A1 as Acceptor 1
    participant A2 as Acceptor 2
    participant A3 as Acceptor 3
    P->>A1: prepare n
    P->>A2: prepare n
    A1-->>P: promise plus any accepted value
    A2-->>P: promise plus any accepted value
    P->>A1: accept n and v
    P->>A2: accept n and v
    A1-->>P: accepted
    A2-->>P: accepted

Two phases: promises first, then accepts. Two of three acceptors are enough.

Why the second phase is safe

Any two majorities overlap in at least one acceptor. So a new proposer's prepare reaches at least one acceptor that took part in any earlier successful accept, and that acceptor tells the newcomer the old value. The rule "adopt the highest accepted value" forces the newcomer to re-propose it. A chosen value therefore keeps being re-proposed forever, which is exactly the agreement property.

A Paxos simulation

Here three acceptors take part. Proposer P1 can only reach a1 and a2, and wants blue. Later, P2 wants red and reaches a2 and a3 with a higher number.

Python A later proposer must adopt the chosen value

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

P1 wins with blue because a1 and a2 form a majority. P2 is in a different majority (a2 and a3), yet the two overlap at a2. That acceptor reports blue in its promise, so P2 abandons red and proposes blue. Both proposers end up with the same chosen value, and a3 learns it too. Change the starting values or the order and try to make red win: you can't, and that is what safety means.

Safety versus liveness

Paxos keeps agreement no matter how messages are lost or reordered. What it cannot promise is progress. Two proposers can keep interrupting each other: P1 prepares with n, P2 prepares with a larger number, which makes the acceptors reject P1's accept, so P1 retries with an even larger number, and so on. This is the dueling proposers livelock, and it is FLP showing up in practice.

Python Dueling proposers and the fix

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In every round the acceptors promise to the higher number, so P1's accept is rejected and nothing is ever accepted. Nobody has chosen a wrong value, and nobody has chosen any value. The usual fix is randomized backoff or electing a single distinguished proposer (a leader). With one proposer running alone, the protocol finishes in two rounds. That is exactly why Multi-Paxos and Raft elect a stable leader first: it removes the duel on the normal path while keeping the same safety argument.

Where Paxos fits

  • Multi-Paxos runs one Paxos instance per log slot and keeps a stable leader so phase 1 only runs once.
  • Raft reaches the same goals with a design that is easier to teach and implement.
  • A cluster of 2f + 1 nodes survives f crashes, because a majority (f + 1) is still alive. Three nodes tolerate one failure, five tolerate two.
  • Consensus costs latency: every decision needs a round trip to a majority. Systems use it for small, critical state (leaders, configuration, commit order), not for every byte of data.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which property of consensus is a liveness property?

    Termination says that something good eventually happens (everyone decides). Agreement and validity say that nothing bad ever happens, which makes them safety properties.
  2. 2. What does the FLP result say?

    FLP is about guaranteed termination in the asynchronous model. Real protocols keep safety always and get progress when the network behaves.
  3. 3. In phase 2 of Paxos, a proposer receives a promise that reports an accepted value 'blue' with proposal number 1. What must it do?

    Adopting the highest accepted value is what carries a possibly chosen value into every later proposal, which keeps agreement.
  4. 4. Why can two proposers prevent progress without breaking safety?

    Each prepare invalidates the other's pending accept. No wrong value is ever chosen, but nothing is chosen either, until backoff or a leader breaks the tie.
  5. 5. How many failures can a five-node Paxos cluster tolerate?

    A majority of five is three. With two nodes down, three remain, which is still a majority.

Summary

  • Consensus means agreement, validity and termination; the first two are safety, the last is liveness.
  • FLP shows that in a fully asynchronous system you cannot guarantee termination with even one possible crash, so protocols protect safety first.
  • Paxos has two phases: prepare/promise and accept. A proposer must adopt the highest accepted value reported by a majority.
  • Overlapping majorities are why a chosen value can never change.
  • Dueling proposers can stall progress; backoff or a stable leader fixes it. Multi-Paxos and Raft build on this.

Next: Raft Step by Step.