Consensus I: impossibility and Paxos

Lessons 6 and 7 kept arriving at the same problem. Safe failover needs replicas to agree on a new leader. State machine replication needs them to agree on the next command in the log. Atomic commit needs participants to agree on commit or abort, and lesson 5 showed that a single coordinator makes that agreement fragile. All of these are instances of consensus: getting a group of processes, some of which may fail, to agree on a single value. Consensus is the core problem of fault-tolerant distributed computing. This lesson defines it, explains a famous result showing that it cannot be solved deterministically in a purely asynchronous system, and then presents Paxos, the protocol that solves it in practice by keeping safety always and requiring timing assumptions only for progress. Lesson 9 presents Raft, a more recent protocol designed to be easier to understand and implement, and the coordination services built on these protocols.

The consensus problem

In the consensus problem, each of \(n\) processes may propose a value, and the processes must decide on one. A correct protocol satisfies three properties. Agreement: no two correct processes decide different values. Validity: the decided value was proposed by some process (so a trivial protocol that always decides 0 is ruled out). Termination: every correct process eventually decides. Agreement and validity are safety properties; termination is a liveness property, in the terminology of lesson 1. In the crash-recovery model, processes keep their promises across restarts by writing them to stable storage before acting on them.

Consensus looks easy until failures and asynchrony meet. If every process could reliably learn every other process's proposal, they could all pick the smallest. But a process that has not heard from another cannot tell whether that process has crashed or is merely slow. Waiting forever for a crashed process violates termination; deciding without a slow process risks it later deciding differently from information the others never saw.

The FLP impossibility result

In 1985 Michael Fischer, Nancy Lynch and Michael Paterson proved that in an asynchronous system, no deterministic protocol can solve consensus if even one process may crash. The result, known by the authors' initials as FLP, won the Dijkstra Prize and is one of the most important in the field. The proof shows that any protocol must have a bivalent initial configuration, one from which either value could still be decided depending on the order of events, and that from any bivalent configuration an adversary controlling message delays can always find a step that leads to another bivalent configuration, by delaying the one critical message that would settle the outcome. The protocol can therefore be kept undecided forever, without any process actually crashing; the mere possibility of a crash, which forbids waiting for everyone, is enough.

FLP does not mean consensus is unachievable in practice. It means that something in the model must be relaxed. Practical protocols relax it in one of three ways. They assume partial synchrony: the network eventually behaves within bounds for long enough, and the protocol guarantees termination only then. They use randomization: Ben-Or's 1983 protocol terminates with probability 1 by having processes flip coins when undecided. Or they use failure detectors: Chandra and Toueg showed in 1996 that consensus is solvable with a failure detector that is eventually accurate, even if it makes mistakes for a while. Paxos and Raft follow the first approach. Their safety never depends on timing: however unlucky the delays, two processes never decide different values. Only termination depends on the network eventually settling down.

Quorums and why majorities work

Fault-tolerant consensus protocols rely on a simple combinatorial fact. With \(n = 2f + 1\) acceptors, any two majorities of size \(f + 1\) share at least one acceptor. If a value is accepted by a majority, any later majority that is consulted includes at least one acceptor that knows about it. That shared acceptor is how information about a possibly chosen value survives failures and leadership changes. It also explains the replica count from lesson 1: tolerating \(f\) crash failures needs \(2f + 1\) acceptors, since the protocol must make progress with \(f\) of them down while still having its majorities overlap. Three acceptors tolerate one failure; five tolerate two.

Paxos

Paxos was invented by Leslie Lamport in the late 1980s and described, as the parliament of a fictional Greek island, in The Part-Time Parliament, which was famously difficult to read and was not published until 1998. His 2001 note Paxos Made Simple restated it plainly. Paxos underlies Google's Chubby lock service, Spanner and many other systems. Single-decree Paxos, the basic protocol, decides one value. Processes play three roles, often all on the same machines: proposers suggest values, acceptors vote, and learners find out the outcome.

Each attempt to choose a value is identified by a ballot number (Lamport calls it a proposal number). Ballot numbers are totally ordered and unique to each proposer, for example by pairing a counter with the proposer's identifier. Each acceptor stores, on stable storage, the highest ballot it has promised and the last ballot and value it has accepted. The protocol has two phases.

In phase 1, prepare, a proposer chooses a ballot \(b\) higher than any it has used and sends PREPARE(b) to the acceptors. An acceptor that has not promised a ballot higher than \(b\) promises not to accept any ballot lower than \(b\) and replies PROMISE(b), including the ballot and value it most recently accepted, if any. In phase 2, accept, if the proposer receives promises from a majority, it chooses a value: if any of the promises reported an accepted value, it must use the value from the promise with the highest ballot; only if none did may it use its own value. It sends ACCEPT(b, v) to the acceptors. An acceptor accepts unless it has since promised a higher ballot. When a majority of acceptors have accepted the same ballot, the value is chosen, and learners can be told.

The rule that the proposer must adopt the highest-ballot accepted value is the heart of Paxos. Suppose value \(v\) was chosen at ballot \(b\), meaning a majority accepted it. Any proposer with a later ballot \(b'\) must first get promises from a majority, and that majority overlaps the one that accepted \(v\). At least one acceptor in the overlap reports having accepted \(v\) at ballot \(b\) or later, and by induction every ballot between \(b\) and \(b'\) that got as far as phase 2 also used \(v\). So the proposer adopts \(v\). Once a value is chosen, every later ballot proposes the same value: agreement holds regardless of timing, message loss or how many proposers compete.

# Single-decree Paxos with five acceptors, lossy messages and two competing proposers.
import random

class Acceptor:
    def __init__(self):
        self.promised = 0                       # highest ballot promised
        self.accepted = (0, None)               # (ballot, value) last accepted
    def prepare(self, b):                       # phase 1b
        if b > self.promised:
            self.promised = b
            return ("promise", self.accepted)
        return ("nack", None)
    def accept(self, b, v):                     # phase 2b
        if b >= self.promised:
            self.promised = b
            self.accepted = (b, v)
            return "accepted"
        return "nack"

def propose(acceptors, ballot, my_value, loss, rnd):
    majority = len(acceptors) // 2 + 1
    replies = [a.prepare(ballot) for a in acceptors if rnd.random() > loss]
    promises = [acc for kind, acc in replies if kind == "promise"]
    if len(promises) < majority:
        return None, "phase 1 failed"
    # Key rule: adopt the value with the highest ballot among the promises, if any.
    b_max, v_max = max(promises, key=lambda p: p[0])
    value = v_max if v_max is not None else my_value
    oks = sum(1 for a in acceptors if rnd.random() > loss and a.accept(ballot, value) == "accepted")
    return (value, "chosen") if oks >= majority else (None, "phase 2 failed")

def run(seed, verbose):
    rnd = random.Random(seed)
    acceptors = [Acceptor() for _ in range(5)]
    chosen = set()
    ballot = {"P1": 1, "P2": 2}                 # ballots are unique: P1 uses odd, P2 even
    for step in range(8):
        who = rnd.choice(["P1", "P2"])
        value = "pay" if who == "P1" else "refund"
        v, status = propose(acceptors, ballot[who], value, loss=0.25, rnd=rnd)
        if verbose:
            print(f"  {who} ballot {ballot[who]:2d} wants {value!r:9s} -> {status}{' ' + repr(v) if v else ''}")
        if v: chosen.add(v)
        ballot[who] += 2
    return chosen

print("one run (seed 2):")
print("  values chosen:", run(2, True))
conflicts = sum(len(run(s, False)) > 1 for s in range(1000))
print(f"runs out of 1000 in which two different values were chosen: {conflicts}")

one run (seed 2):
  P1 ballot  1 wants 'pay'     -> chosen 'pay'
  P2 ballot  2 wants 'refund'  -> chosen 'pay'
  P2 ballot  4 wants 'refund'  -> phase 1 failed
  P1 ballot  3 wants 'pay'     -> chosen 'pay'
  P2 ballot  6 wants 'refund'  -> chosen 'pay'
  P2 ballot  8 wants 'refund'  -> chosen 'pay'
  P1 ballot  5 wants 'pay'     -> phase 1 failed
  P2 ballot 10 wants 'refund'  -> chosen 'pay'
  values chosen: {'pay'}
runs out of 1000 in which two different values were chosen: 0

The simulation shows the safety argument at work. Attempts fail when too many messages are lost or when the other proposer has moved to a higher ballot. Once P1's value "pay" is chosen, P2's later successful attempts also choose "pay", although P2 wanted "refund": its promises reported the accepted value and the rule forced P2 to adopt it. Across a thousand randomized runs, no run ever chose two different values.

Liveness and the distinguished proposer

Paxos guarantees safety unconditionally but not progress. Two proposers can pre-empt each other forever: P1 completes phase 1 with ballot 1; P2 completes phase 1 with ballot 2, so P1's accepts are rejected; P1 retries with ballot 3, pre-empting P2's accepts; and so on. This is FLP in action, an adversarial schedule keeping the protocol undecided.

# Dueling proposers: each new prepare pre-empts the other's accept, so nothing is chosen.
class Acceptor:
    def __init__(self): self.promised, self.accepted = 0, (0, None)

acceptors = [Acceptor() for _ in range(3)]
def prepare(b):
    ok = 0
    for a in acceptors:
        if b > a.promised: a.promised = b; ok += 1
    return ok >= 2
def accept(b, v):
    ok = 0
    for a in acceptors:
        if b >= a.promised: a.promised = b; a.accepted = (b, v); ok += 1
    return ok >= 2

b1, b2 = 1, 2
for rnd in range(4):
    p1 = prepare(b1)                   # P1 prepares
    p2 = prepare(b2)                   # P2 prepares with a higher ballot before P1 accepts
    a1 = accept(b1, "X")               # P1's accept is rejected: promised b2
    b1 += 2
    p1b = prepare(b1)                  # P1 retries with a higher ballot...
    a2 = accept(b2, "Y")               # ...which pre-empts P2's accept
    b2 += 2
    print(f"round {rnd}: P1 accept {'ok' if a1 else 'rejected'}, P2 accept {'ok' if a2 else 'rejected'}")
print("No value chosen. Fix: elect a single distinguished proposer (a leader), with randomized backoff.")

round 0: P1 accept rejected, P2 accept rejected
round 1: P1 accept rejected, P2 accept rejected
round 2: P1 accept rejected, P2 accept rejected
round 3: P1 accept rejected, P2 accept rejected
No value chosen. Fix: elect a single distinguished proposer (a leader), with randomized backoff.

The practical remedy is to designate a single distinguished proposer, a leader, through which all proposals pass, and to have competing proposers back off for random intervals. Leader election itself needs only to be eventually accurate: if two processes briefly both believe they are leader, Paxos stays safe and merely wastes a few rounds. Once the network is stable and one leader is recognized, every proposal succeeds in two round trips.

Multi-Paxos and replicated logs

A replicated log needs a sequence of decisions, one per log slot. Running full single-decree Paxos for every slot would cost two round trips per command. Multi-Paxos optimizes this. A stable leader runs phase 1 once for all future slots, using a single ballot; acceptors promise not to accept lower ballots for any slot. Thereafter, each new command needs only phase 2: one round trip from the leader to a majority. If the leader fails, a new leader runs phase 1 with a higher ballot, learns any values that may have been accepted in unfinished slots, completes them, and continues. With a stable leader, Multi-Paxos commits a command in one round trip to a majority, the minimum possible for a crash-tolerant replicated log.

The gap between the elegant single-decree protocol and a production Multi-Paxos system is large. Google's paper Paxos Made Live (Chandra, Griesemer and Redstone, 2007) described building Chubby's replication layer and listed the details the theory leaves out: disk corruption, leader leases for fast reads, snapshots to keep the log from growing forever, membership changes, and extensive testing. That gap is part of what motivated Raft, which specifies these details as part of the protocol.

Variants of Paxos

Paxos has spawned a large family of variants. Fast Paxos (Lamport, 2006) lets clients send directly to acceptors, saving a message delay when there is no contention, at the cost of larger quorums. EPaxos (Moraru, Andersen and Kaminsky, 2013) is leaderless: any replica can commit a command in one round trip if it does not conflict with concurrent commands, which suits geo-replication. Flexible Paxos (Howard, Malkhi and Spiegelman, 2016) observed that phase 1 and phase 2 quorums need only intersect each other, not themselves, so a system can use small phase 2 quorums for fast commits and large phase 1 quorums for rare leader changes. Vertical Paxos reconfigures membership through an auxiliary master. Each trades simplicity for performance in some regime.

Byzantine fault tolerance

Paxos tolerates crashes, not lies. If acceptors may behave arbitrarily, for example because of corrupted memory, compromised software or a malicious operator, stronger protocols are needed. Lamport, Shostak and Pease showed in 1982 that Byzantine agreement among \(n\) processes is possible only if \(n \ge 3f + 1\). The intuition is that a correct process must be able to decide after hearing from \(n - f\) processes (it cannot wait for the \(f\) that may be silent), and among those \(n - f\), up to \(f\) may be lying, so the honest ones must outnumber them: \(n - 2f > f\).

Castro and Liskov's Practical Byzantine Fault Tolerance (PBFT, 1999) was the first protocol efficient enough for real systems. It uses a primary and three phases (pre-prepare, prepare, commit) with quorums of \(2f + 1\) out of \(3f + 1\) replicas, and signed or authenticated messages so that a lying primary can be detected and replaced through a view change. Its message complexity is quadratic in the number of replicas, which limits it to tens of nodes. Later protocols such as Tendermint (2014) and HotStuff (2019), which powered Facebook's planned Diem payment network, reduced the communication cost. Bitcoin's proof-of-work consensus (2008) takes a different approach for open, permissionless membership, replacing votes by computational work and offering probabilistic rather than absolute finality; Ethereum moved in 2022 from proof-of-work to a proof-of-stake protocol with BFT-style finality. Inside a single organization's data centers, where machines are trusted and failures are crashes, crash-tolerant protocols such as Paxos and Raft are almost always used, because Byzantine tolerance costs more replicas, more messages and more cryptography.

Worked examples