Every protocol in the previous chapters leaned on something that had to be agreed: who the leader is, whose decision stands, what order transactions were sequenced in. Consensus is getting a set of processes to agree on a value despite crashes and message loss; it is the primitive that turns unreliable machines into one reliable service, and replicated logs, leader election, distributed locks and transaction coordinators are all consensus in a costume.

This chapter builds from broadcast primitives to the three protocols you will actually meet (ZAB in ZooKeeper, Paxos in Chubby and Spanner, Raft in etcd and CockroachDB), explains why they are correct in terms of quorum intersection, and ends with what changes when participants can lie.

In one minute

• Consensus needs agreement, validity and termination. FLP says no deterministic protocol guarantees all three in an asynchronous system with one crash; real protocols stay safe always and terminate when the network behaves.
• Broadcast guarantees escalate: best-effort, reliable, atomic (total-order). Atomic broadcast is equivalent to consensus.
• ZAB is a leader-based atomic broadcast with epochs: discovery, synchronisation, then broadcast where followers ack after persisting and the leader commits on a quorum.
• Paxos: a prepare phase claims a ballot and learns of previously accepted values, then an accept phase. Majority quorums intersect, so a chosen value is always rediscovered by later ballots.
• Multi-Paxos keeps a leader to skip prepare; Fast Paxos lets clients talk to acceptors with larger quorums; EPaxos is leaderless and orders by dependencies; Flexible Paxos only needs the two phases' quorums to intersect each other.
• Raft: terms, randomised election timeouts, AppendEntries with a consistency check enforcing the log matching property, commit on majority replication in the leader's term, election restriction, joint consensus, snapshots.
• PBFT tolerates f Byzantine nodes with 3f + 1 replicas: pre-prepare, prepare, commit with 2f + 1 quorums, view changes, checkpoints.

Consensus and broadcast

Definitions and limits

A correct process follows the protocol and has not crashed. Consensus guarantees agreement (correct processes decide the same value), validity (the value was proposed by someone) and termination (correct processes eventually decide). The first two are safety properties, the third is liveness. The FLP result (Fischer, Lynch and Paterson, 1985) shows that in a fully asynchronous system no deterministic protocol can guarantee all three if even one process may crash. Practical protocols assume partial synchrony (delays are bounded, the bound unknown) and use timeout-based failure detectors; they never violate safety because of a slow network, they only stall.

With crash failures, 2f + 1 processes tolerate f failures (a majority must remain); with Byzantine failures, where faulty processes send arbitrary messages, 3f + 1.

Best effort and reliable broadcast

Best-effort broadcast sends to everyone once; if the sender crashes mid-way, some receive and some do not. Reliable broadcast adds agreement: if any correct process delivers a message, all do. Eager reliable broadcast has every process re-broadcast on first delivery, so any receiver completes the job, at N squared messages; gossip reduces this with probabilistic guarantees. Neither says anything about order.

Atomic broadcast

Atomic broadcast (total-order broadcast) adds atomicity (all correct processes deliver a message or none does) and total order (if any process delivers m1 before m2, all do). A replicated log is exactly atomic broadcast, and atomic broadcast and consensus are equivalent: a consensus instance per log slot yields atomic broadcast, and atomic broadcast decides consensus by taking the first delivered proposal. Feed the same commands in the same order to deterministic replicas and they stay identical, which is why "consensus protocol" and "replicated state machine" are used interchangeably.

Virtual synchrony

Atomic broadcast assumes a fixed group. Virtual synchrony (Birman's Isis) handles dynamic groups: processes belong to a group with a sequence of views, each an agreed membership, and a view change (join, leave, failure) acts as a barrier: all messages sent in view v reach all surviving members before anyone moves to v + 1. It influenced group communication toolkits but databases standardised on leader-based logs.

ZooKeeper atomic broadcast

ZooKeeper is a replicated hierarchical key-value store used for coordination by Kafka, HBase and Hadoop. Its protocol, ZAB (Junqueira, Reed and Serafini, 2011), is an atomic broadcast built for primary-backup: one leader generates all state changes, so the protocol orders one process's proposals rather than arbitrating between proposers.

Roles, epochs and zxids

Processes are leader or followers (plus non-voting observers). Every transaction gets a zxid: the high 32 bits are the epoch, incremented each time a leader is established, and the low 32 bits a counter within the epoch. A higher epoch always wins, which is what stops a deposed leader's proposals from being accepted.

The three phases

1. Discovery. After a fast election favouring the highest zxid, the prospective leader collects from a quorum their last accepted epoch, proposes a new epoch above all of them, and followers acknowledge with their latest zxid, promising not to accept older epochs.
2. Synchronisation. The leader adopts the most recent history from discovery and sends it to followers (diff, truncation or snapshot), so everything committed under earlier leaders is delivered before anything new and uncommitted proposals that reached no quorum are discarded. On a quorum of acks the leader is established.
3. Broadcast. For each write the leader assigns the next zxid and sends PROPOSAL; followers append it to their on-disk log and ACK; on a quorum the leader sends COMMIT and followers deliver in zxid order. FIFO channels (TCP) keep proposals ordered, so a commit costs two message delays.

ZAB provides primary order: one leader's proposals are delivered in the order issued, and a new leader delivers everything its predecessors committed before anything of its own. Unlike classic Paxos there are no gaps between consecutive proposals of a leader, which ZooKeeper clients depend on for dependent writes. Leader failure means a new election plus discovery and synchronisation; writes pause meanwhile, typically well under a second.

Paxos

Roles and ballots

Paxos (Lamport, 1998; "Paxos Made Simple", 2001) decides one value among processes in three roles, which a node may combine: proposers propose and drive rounds, acceptors vote and remember (typically 2f + 1 of them), learners find out what was chosen and act on it. Each round carries a ballot number, unique across proposers (counter plus proposer id) and totally ordered.

The two phases

Phase 1 (prepare, promise). A proposer picks a ballot n above any it has used and sends PREPARE(n). An acceptor that has not promised a higher ballot replies PROMISE: it will accept nothing below n, and it reports the highest-ballot proposal it has already accepted, if any. Otherwise it rejects, telling the proposer to retry higher.

Phase 2 (accept, accepted). With promises from a majority, the proposer picks the value: if any promise reported an accepted proposal, it must use the value of the highest-ballot one; only if none did may it use its own. It sends ACCEPT(n, v). An acceptor accepts unless it has promised a higher ballot since, persists (n, v) and replies ACCEPTED. When a majority has accepted (n, v), the value is chosen, and learners are told.

Why quorum intersection makes it safe

Invariant: once v is chosen at ballot n, every higher-ballot proposal carries v. A later proposer at ballot m needs promises from a majority, which intersects the majority that accepted v in at least one acceptor; that acceptor promised m after accepting v and so reports v. The proposer must adopt the highest-ballot reported value, and by induction every value accepted between n and m was v. Acceptors must persist promises and accepted values before replying, or a forgotten promise could let a stale ballot through.

Failure scenarios

• Acceptor failures. Up to f of 2f + 1 may be down and a majority remains. Beyond that the protocol stalls but stays safe.
• Proposer fails during phase 2. Some acceptors hold (n, v). A new proposer's majority either includes one of them (it learns v and finishes with v) or none (fewer than a majority accepted, so v was never chosen and another value may win). Exactly one value ends up chosen.
• Duelling proposers. Two proposers alternately issue higher ballots, each invalidating the other's promises before phase 2 completes: safe, but nothing is chosen. Remedies are random backoff or a distinguished proposer, which is where Multi-Paxos starts.

Multi-Paxos and leases

Two round trips per value is slow. Multi-Paxos runs one Paxos instance per log slot and does phase 1 once for all future slots: a proposer sends PREPARE for "all slots from i onward" and thereafter runs only phase 2 per value until someone issues a higher ballot. That proposer is the leader, and each decision costs one round trip to a majority, as in Raft and ZAB.

Leaders want to serve reads locally, which is linearizable only while they are still leader. A lease has acceptors promise not to grant a higher ballot for an interval; the leader serves reads until the lease expires on its clock minus maximum drift, so clock assumptions enter. Chubby and Spanner use leader leases.

Fast Paxos

Fast Paxos (Lamport, 2005) lets clients send values directly to acceptors in a fast round the leader has pre-authorised. If acceptors receive the same value first, it is chosen in one round trip from the client; if clients collide, a classic recovery round follows. Safety with concurrent proposals needs larger fast quorums, at least N minus floor(N/4). It trades a message delay in the uncontended case for more acceptors on the critical path and a worse contended case.

Egalitarian Paxos

A single leader is a bottleneck and a penalty for distant clients. EPaxos (Moraru, Andersen and Kaminsky, 2013) has no stable leader: any replica acts as command leader for a command it receives, sending PreAccept with the command and its guess of dependencies (earlier commands touching the same keys) to a fast quorum. If replies agree on the dependencies, the command commits in one round trip; otherwise the leader merges dependency sets and runs a classic accept. Replicas execute by walking the dependency graph, so they converge despite committing in different orders.

Flexible Paxos

The safety proof only ever intersected a phase 1 quorum with a phase 2 quorum. Flexible Paxos (Howard, Malkhi and Spiegelman, 2016) makes that precise: Paxos is safe as long as every phase 1 quorum intersects every phase 2 quorum; phase 2 quorums need not intersect each other. Since phase 1 runs once per leader change and phase 2 per command, shrink phase 2 and enlarge phase 1: with 5 acceptors, a phase 1 quorum of 4 lets phase 2 commit with any 2. Replication latency drops and leader-election fault tolerance drops (4 of 5 must be up). Howard and Mortier's "A Generalised Solution to Distributed Consensus" derives all these variants from one write-once register framework.

Raft

Raft (Ongaro and Ousterhout, 2014) was designed to be understandable and to specify everything an implementation needs. It is a replicated log with a strong leader: clients talk to the leader, entries flow only from leader to followers, and the leader never overwrites its own entries. It underlies etcd (hence Kubernetes), Consul, CockroachDB and TiKV.

Terms and roles

Time is divided into terms, numbered monotonically, each beginning with an election and having at most one leader. Every message carries the sender's term; a process seeing a higher term adopts it and reverts to follower; stale terms are rejected. Terms are Raft's ballot numbers. Persistent state: current term, vote in the current term, the log.

Leader election and split votes

Followers expect heartbeats (empty AppendEntries). If none arrives within the election timeout, a follower increments its term, becomes a candidate, votes for itself and sends RequestVote with its term and the index and term of its last entry. A voter grants at most one vote per term and only to a candidate whose log is at least as up to date. A majority makes a leader, which immediately heartbeats.

Split votes occur when several followers time out together and no one gets a majority. Randomised election timeouts (150 to 300 ms) make one node usually time out first and win before the others wake; after a split, each candidate waits a fresh random timeout. Timeouts must sit well above the broadcast round trip and well below the mean time between failures.

Log replication

The leader appends each command as an entry with its term and the next index, then sends AppendEntries carrying its term, prevLogIndex and prevLogTerm for the entry preceding the new ones, the entries, and its commit index. A follower runs the consistency check: accept only if its log has an entry at prevLogIndex with prevLogTerm. If so it appends, deleting any conflicting entries at those indexes; if not it rejects, and the leader retries with an earlier prefix until the logs agree.

An entry is committed once replicated on a majority. The leader advances its commit index, applies the entry, replies to the client, and piggybacks the commit index on later messages so followers apply too. Only the leader decides what is committed.

The log matching property

The consistency check yields Raft's central invariant: if two logs contain an entry with the same index and term, the entries are identical and so are all preceding entries. The first half holds because a leader creates one entry per index per term and never moves entries; the second follows inductively from the check. Logs have no holes and an index-term pair identifies a prefix exactly.

Safety: the election restriction

Raft needs leader completeness: an entry committed in some term is in every later leader's log. Instead of Paxos's value recovery in phase 1, Raft restricts who may win. A voter grants its vote only if the candidate's log is at least as up to date: higher last term, or equal last term and at least as long. A committed entry is on a majority of logs, and a winning candidate is judged up to date by a majority that intersects it, so the leader has the entry.

A corollary (the paper's Figure 8): a leader may not treat an entry from a previous term as committed merely because it now sits on a majority, since a candidate with a later-term entry could still win and overwrite it. Old-term entries commit indirectly, when a current-term entry after them commits; new leaders append a no-op immediately so this happens at once.

Membership changes and snapshots

Switching configurations in one step is unsafe: the old and new sets may each form a majority and elect two leaders in the same term. The paper's joint consensus first commits a transitional configuration C(old, new) requiring majorities of both sets, then commits C(new). Ongaro's thesis gives the simpler single-server change: add or remove one server at a time, since two configurations differing by one server always have overlapping majorities (with a fix requiring the new leader to commit a no-op before any change). New servers catch up as non-voters before counting toward quorums.

Logs cannot grow forever. Each server independently snapshots its state machine at an applied index, records the last included index, term and configuration, and discards the prefix. A follower too far behind receives InstallSnapshot. No agreement is needed because every server's state at a committed index is identical.

Raft versus Paxos

Aspect	Multi-Paxos	Raft
Leader	Optimisation; any proposer may run a ballot	Mandatory; everything goes through it
Log	Independent slots; gaps allowed	Contiguous; log matching property
Leader change	New leader runs phase 1 and may learn values from acceptors	Election restriction; data never flows to the leader

Underneath they are the same algorithm: claim a ballot or term from a majority, then get a majority to accept. Raft is a specialisation with a particular election rule and log shape, specified completely enough to implement.

Failure scenarios in leader-based consensus

• Leader crash. Followers time out and elect an up-to-date leader. Entries the old leader appended but did not commit may be discarded or completed; clients must not assume a request applied unless they got the response.
• Slow or crashed follower. The leader retries indefinitely; idempotent messages make catch-up natural, and a slow minority does not affect latency.
• Leader in the minority of a partition. It accepts requests but cannot commit; the majority elects a new leader in a higher term. On heal the old leader steps down and its uncommitted entries are overwritten. Reads it served meanwhile were stale unless guarded by a lease or a read index (confirming leadership with a heartbeat round before answering).
• Disk loss. A node that loses its log and rejoins with the same identity can grant votes it should not; it must rejoin as a fresh member.

Byzantine consensus

The model and the 3f + 1 bound

Byzantine faults drop the assumption that faulty processes merely stop: they may send conflicting messages to different peers, replay or collude. The model fits participants from different organisations (permissioned ledgers). The cost: more replicas, more rounds, authenticated messages and quadratic message complexity, because processes cross-check what others claim rather than trusting any sender.

To tolerate f Byzantine replicas the protocol must proceed on N minus f responses, of which f may be lies, so the N minus 2f honest responses must outnumber the f liars: N is at least 3f + 1. Quorums of 2f + 1 then intersect in at least f + 1 replicas, at least one honest: the Byzantine analogue of majority intersection.

PBFT

Practical Byzantine Fault Tolerance (Castro and Liskov, 1999) runs through views; in each, one replica is primary (view number modulo N) and the rest backups. The primary orders client requests; three phases ensure honest replicas agree on that order even if the primary is faulty.

1. Pre-prepare. The primary assigns sequence number n to a request and multicasts PRE-PREPARE with view v, n and the request digest. Backups accept if the view matches, they hold no different pre-prepare for (v, n), and n is within their watermarks.
2. Prepare. Each accepting backup multicasts PREPARE(v, n, digest). A replica is prepared once it holds the pre-prepare plus 2f matching prepares: a quorum has agreed on order n in view v.
3. Commit. Prepared replicas multicast COMMIT(v, n, digest). With 2f + 1 matching commits a replica is committed-local, executes the request in sequence order and replies. The commit phase makes the order survive a view change: if any honest replica committed, at least f + 1 honest replicas prepared, and that reaches the new view.

The client waits for f + 1 matching replies: at most f are faulty, so one is honest, and honest replicas compute identical results.

View changes, checkpoints and recovery

If backups suspect the primary (a request times out), they multicast VIEW-CHANGE(v + 1) with proof: their last stable checkpoint and, for each request prepared since, the pre-prepare plus 2f prepares. The new primary collects 2f + 1 view-change messages, computes which requests must carry over, and multicasts NEW-VIEW with those pre-prepares reissued. The proofs stop a malicious old or new primary from dropping or reordering requests, since 2f + 1 authenticated messages cannot be fabricated.

Every K requests each replica multicasts CHECKPOINT(n, state digest); with 2f + 1 matching messages the checkpoint is stable and earlier protocol messages are discarded. The stable checkpoint sets the low watermark; sequence numbers beyond a fixed window above it are rejected, so a faulty primary cannot exhaust sequence space. A replica that fell behind fetches a stable checkpoint's state, verified against the digests, and replays from there. Descendants such as Tendermint and HotStuff cut message complexity to linear with threshold signatures but keep 3f + 1 replicas, 2f + 1 quorums and view changes.

Design trade-offs

Protocol	Leader	Steady-state cost per decision	Tolerates	Best for
ZAB	yes, with epochs	1 round trip to quorum, FIFO per follower	f of 2f + 1 crashes	Coordination services (ZooKeeper)
Multi-Paxos	yes, via phase 1 lease	1 round trip	f of 2f + 1	Chubby, Spanner groups
Raft	yes, strong	1 round trip to majority	f of 2f + 1	etcd, Consul, CockroachDB, TiKV
PBFT	rotating primary	3 all-to-all rounds	f of 3f + 1 Byzantine	Permissioned ledgers, untrusted peers

Inside a trusted system, Raft or Multi-Paxos; Byzantine protocols pay off only when you cannot trust the other replicas.

Interview angle

• Why does Raft need a majority rather than two fixed acknowledgers? Majorities intersect, so the node carrying a committed entry is in every future election and every future quorum. Two fixed acknowledgers can be disjoint from the next leader's voters.
• Paxos in four sentences. A proposer gets a majority to promise not to accept lower ballots and to report what they already accepted. It proposes the highest-ballot value it heard, or its own if none. A value is chosen when a majority accepts it at one ballot. Overlapping majorities mean any later proposer rediscovers and re-proposes it.
• Why randomise election timeouts? Equal timeouts turn every follower into a candidate at once, each voting for itself, repeatedly. A random range about ten times the RTT lets one node win first.
• How does ZooKeeper reject a deposed leader's writes? zxids carry the epoch in the high bits; followers that acknowledged a new epoch refuse older ones, and synchronisation truncates uncommitted old-epoch proposals.
• Why does PBFT need 3f + 1 when Raft needs 2f + 1? With f possibly silent you proceed on N minus f replies, among which f may lie; honest must outnumber dishonest, so N minus 2f exceeds f. Crash faults never lie, so a majority suffices.
• Design leader election for 500 stateless workers. Do not run consensus across 500 nodes. Run a 3- or 5-node etcd or ZooKeeper and have workers compete for a lease key with a TTL via compare-and-swap; the holder renews before expiry and stops acting if it cannot, allowing for clock skew.

Pitfalls and misconceptions

• Consensus protocols lose data during partitions. Paxos, Raft and ZAB never lose a committed entry; they stop making progress. Safety is unconditional, liveness needs a connected majority.
• A Raft leader can serve reads locally for free. Only with a drift-aware lease or a read index; a deposed leader otherwise serves stale reads.
• A leader may commit an old-term entry once it is on a majority. It must commit a current-term entry after it; skipping this (or the no-op on election) is a classic bug.
• Five nodes are strictly better than three. More fault tolerant and slower: every commit waits for three acks instead of two. Use learners for read scaling.
• Byzantine tolerance is consensus plus signatures. The quorum arithmetic changes, an extra commit phase is needed to survive view changes, clients need f + 1 matching replies, and message complexity is quadratic.

Key terms

Term	Meaning
Consensus	Agreement among processes on a single value with agreement, validity and termination
FLP impossibility	No deterministic protocol guarantees termination in an asynchronous system with one possible crash
Atomic broadcast	Reliable broadcast plus a single delivery order for all processes; equivalent to consensus
ZAB and zxid	ZooKeeper's atomic broadcast; transaction id with epoch in the high bits and counter in the low bits
Proposer, acceptor, learner	Paxos roles: drives rounds, votes and remembers, learns the outcome
Ballot number	Unique, totally ordered proposal number; the analogue of a Raft term
Quorum intersection	Any two quorums share a node, carrying a decision forward across rounds
Flexible Paxos	Only phase 1 and phase 2 quorums need to intersect, allowing smaller replication quorums
Log matching property	Same index and term implies identical entries and identical preceding logs
Election restriction	Votes go only to candidates whose log is at least as up to date as the voter's
PBFT	Byzantine consensus with 3f + 1 replicas, pre-prepare, prepare and commit, view changes and checkpoints

Further reading

• Database Internals, Chapter 14; DDIA Chapter 9 for total-order broadcast and linearizability from the application side.
• Leslie Lamport, "Paxos Made Simple", 2001, https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
• Diego Ongaro and John Ousterhout, "In Search of an Understandable Consensus Algorithm (Extended Version)", 2014, https://raft.github.io/raft.pdf ; visualisation at https://raft.github.io/
• Flavio Junqueira, Benjamin Reed and Marco Serafini, "Zab: High-performance Broadcast for Primary-backup Systems", DSN 2011.
• Heidi Howard, Dahlia Malkhi and Alexander Spiegelman, "Flexible Paxos: Quorum Intersection Revisited", https://arxiv.org/abs/1608.06696
• Heidi Howard and Richard Mortier, "A Generalised Solution to Distributed Consensus", https://arxiv.org/abs/1902.06776
• Iulian Moraru, David Andersen and Michael Kaminsky, "There Is More Consensus in Egalitarian Parliaments", SOSP 2013.
• Michael Fischer, Nancy Lynch and Michael Paterson, "Impossibility of Distributed Consensus with One Faulty Process", JACM 1985.
• Miguel Castro and Barbara Liskov, "Practical Byzantine Fault Tolerance", OSDI 1999, http://pmg.csail.mit.edu/papers/osdi99.pdf