Consensus Protocols: How Distributed Systems Agree

TL;DR: Consensus is how a group of nodes agree on one value despite crashes and network delays. Practical protocols (Raft, Multi-Paxos) are always safe but only guarantee liveness when the network is well-behaved enough for a leader to hold its role. Every committed decision costs at least one round trip to a majority, so use consensus sparingly: for the state that must be correct (leader identity, cluster membership, transaction metadata), not for every request. A cluster of 2N+1 nodes tolerates N failures. etcd runs 3 to 5 nodes with a 100 ms heartbeat and < 10 ms WAL fsync p99¹². If you are reaching for consensus per request, you probably do not need strong consistency at that layer.

Learning Objectives

After this module, you will be able to:

• Explain the two phases of Paxos (prepare/promise, accept/accepted) and when each is skipped
• Walk through Raft leader election, log replication, and safety via term numbers
• Pick a cluster size (3, 5, 7) given the failure tolerance you need
• Reason about what a minority partition can and cannot do
• Recognize when you need consensus and when you do not
• Describe how multi-raft sharding scales write throughput beyond a single leader

Intuition

Imagine a jury of five people deliberating a verdict. The judge says: “You must reach a majority decision, and you must do it by passing written ballots, because you cannot all talk at the same time.” One juror is the foreman. She proposes a verdict, writes it on a slip, and passes copies to the other four. Once three of the five (including herself) sign the same slip, the verdict is final.

Now imagine one juror falls asleep mid-deliberation. The remaining four can still reach a majority of three. But if two jurors fall asleep, the awake three are exactly the majority, so one more nap and the jury is stuck. That is why five-member clusters tolerate two failures and no more.

What if the foreman falls asleep? The remaining jurors notice she stopped passing slips. After a random wait (so they do not all shout at once), one of them declares herself the new foreman, asks for votes, and resumes. The old foreman wakes up, sees a newer ballot number, and quietly becomes a regular juror again.

This is consensus. One leader proposes, a majority agrees, and the decision is durable even if some members crash. The rest of this chapter makes that precise.

Theory

What consensus solves

Consensus answers one question: how do N processes agree on a single value when some may crash and messages may be lost or delayed?

Formally, a consensus protocol must satisfy three properties³:

1. Agreement. All correct processes decide the same value.
2. Validity. The decided value was proposed by some process.
3. Termination. Every correct process eventually decides.

The Fischer-Lynch-Paterson (FLP) impossibility result of 1985 proves that no deterministic algorithm in a purely asynchronous system can guarantee all three when even one process may crash³. The intuition: you cannot distinguish a crashed peer from a slow one, so any algorithm must either wait forever (losing termination) or proceed with partial information (risking disagreement).

Practical protocols dodge FLP by assuming partial synchrony: they are always safe (agreement and validity hold no matter what), but only guarantee liveness (termination) when the network behaves well enough for a leader to maintain its role³. This is not a theoretical curiosity. It means your Raft cluster will never corrupt data during a partition, but it may stop accepting writes until the partition heals.

The dominant use of consensus is the replicated state machine (RSM): a group of nodes agrees on an ordered log of commands, each applies those commands deterministically, and the group behaves as a single fault-tolerant machine⁴. Leader election, distributed locks, configuration stores (etcd, ZooKeeper), and strongly-consistent databases (CockroachDB, Spanner) are all RSMs under the hood.

Paxos in 15 minutes

Paxos is the original majority-quorum consensus protocol. It has three roles: proposer, acceptor, and learner. A single-decree Paxos run chooses one value in two phases⁵:

Phase 1 (Prepare/Promise). A proposer picks a ballot number n and asks a majority of acceptors: “Promise not to accept anything numbered lower than n, and tell me the highest value you have already accepted.” If a majority promises, the proposer proceeds.

Phase 2 (Accept/Accepted). The proposer sends accept(n, v) where v is either its own value or the highest previously-accepted value reported in phase 1. Once a majority of acceptors accept, the value is chosen.

sequenceDiagram
    participant P as Proposer
    participant A1 as Acceptor 1
    participant A2 as Acceptor 2
    participant A3 as Acceptor 3
    Note over P,A3: Single-decree Paxos (2 RTTs)
    P->>A1: Prepare(n)
    P->>A2: Prepare(n)
    A1-->>P: Promise(n)
    A2-->>P: Promise(n)
    P->>A1: Accept(n, v)
    P->>A2: Accept(n, v)
    A1-->>P: Accepted
    A2-->>P: Accepted
    Note over P,A3: Multi-Paxos steady state (1 RTT per slot)
    P->>A1: Accept(n, slot k, v')
    P->>A2: Accept(n, slot k, v')
    A1-->>P: Accepted
    A2-->>P: Accepted

A single run takes two round trips. Multi-Paxos amortizes this by electing a stable leader that skips phase 1 for subsequent log slots, leaving one round trip per command in steady state⁵.

The problem with Paxos is not correctness. It is implementability. Google’s “Paxos Made Live” paper documents the engineering gap between the single-decree specification and a production system: leader leases, log corruption handling, membership changes, snapshotting, master recovery, and disk quota all required bespoke solutions not described in the original paper⁶. Multi-Paxos is underspecified in the literature, so every implementation diverges on these details⁴.

EPaxos (Moraru et al., SOSP 2013) removes the single-leader bottleneck: any replica can propose, and non-conflicting commands commit in one round trip⁷. Conflicting commands fall back to a two-round path with an explicit dependency graph. The idea is elegant but the original protocol has known gaps; recent work has had to “fix and simplify” it to restore linearizability⁸.

Raft: designed for understandability

Raft (Ongaro and Ousterhout, 2014) is equivalent to Multi-Paxos in safety and performance⁹. It won adoption by being understandable, not by being fundamentally different.

Terms are the central abstraction. Time is divided into monotonically increasing terms, each starting with an election and producing at most one leader. Every RPC carries a term number. If a node receives a message with a higher term, it immediately reverts to follower. Terms are the distributed clock that orders leadership.

Leader election. Every node is in one of three states: follower, candidate, or leader. A follower that does not hear a heartbeat within a randomized election timeout (chosen from [T, 2T-1], where T is the base timeout) becomes a candidate, increments its term, and solicits votes⁹. The randomization prevents simultaneous elections. A candidate wins when it receives votes from a majority.

sequenceDiagram
    participant F1 as Follower 1
    participant F2 as Follower 2 (candidate)
    participant F3 as Follower 3
    Note over F1,F3: Leader crashes, election timers run
    F2->>F2: Timer fires first (random [T, 2T-1])
    F2->>F2: Become candidate, term = T+1
    F2->>F1: RequestVote(term=T+1, lastIdx, lastTerm)
    F2->>F3: RequestVote(term=T+1, lastIdx, lastTerm)
    F1-->>F2: VoteGranted (log is up-to-date)
    F3-->>F2: VoteGranted
    F2->>F2: Majority reached, become leader
    F2->>F1: AppendEntries (heartbeat, term=T+1)
    F2->>F3: AppendEntries (heartbeat, term=T+1)

The election restriction guarantees safety: vote granters require the candidate’s log to be at least as up-to-date as their own (comparing last log term, then last log index). This ensures the new leader carries every committed entry⁹.

Log replication. The leader appends client commands to its log, sends AppendEntries RPCs to followers, and commits an entry once a majority have persisted it. Raft’s log-matching invariant (same index and term implies same content and identical prefix) is preserved by the leader’s single-writer discipline and by followers overwriting conflicting suffixes¹⁰.

sequenceDiagram
    participant C as Client
    participant L as Leader
    participant F1 as Follower 1
    participant F2 as Follower 2
    C->>L: Propose(x=42)
    L->>L: Append to log at index N
    L->>F1: AppendEntries(prevIdx=N-1, entry=x=42)
    L->>F2: AppendEntries(prevIdx=N-1, entry=x=42)
    F1-->>L: Ack(N)
    F2-->>L: Ack(N)
    L->>L: CommitIndex = N (majority)
    L-->>C: OK
    L->>F1: AppendEntries(commitIndex=N)
    L->>F2: AppendEntries(commitIndex=N)

stateDiagram-v2
    [*] --> Follower
    Follower --> Candidate: election timeout
    Candidate --> Leader: majority votes
    Candidate --> Follower: discover higher term
    Candidate --> Candidate: split vote, new term
    Leader --> Follower: discover higher term
    Leader --> Follower: lose quorum (CheckQuorum)

Membership changes and snapshots

Adding or removing nodes from a running cluster is dangerous: if old and new configurations overlap incorrectly, two independent majorities can form. Raft’s original paper describes joint consensus, where the cluster briefly operates under both old and new configurations simultaneously. In practice, most implementations (including etcd/raft) simplify this to one-node-at-a-time changes, which avoids the joint state at the cost of slower reconfiguration¹¹.

Log compaction prevents unbounded log growth. Periodically, a node snapshots its state machine and discards all log entries up to the snapshot index. If a follower falls far behind, the leader sends the snapshot directly rather than replaying thousands of entries.

Leader leases and ReadIndex

A naive linearizable read requires the leader to confirm it still holds leadership before answering, which costs one round trip to a majority. Two optimizations exist¹¹:

1. ReadIndex. The leader records the current commit index, confirms quorum (one round of heartbeats), then serves the read once its state machine has applied up to that index. Safe but adds one RTT.
2. Lease-based reads. The leader assumes it remains leader for the duration of the election timeout (since no election can succeed while heartbeats are flowing). It serves reads locally without a quorum check. Faster, but depends on bounded clock drift. etcd defaults to ReadIndex because lease reads are unsafe under clock skew¹¹.

Byzantine consensus

Everything above assumes crash-fault tolerance: nodes either follow the protocol or stop. Byzantine consensus tolerates nodes that behave arbitrarily, including maliciously. The cost: you need at least 3f+1 replicas to tolerate f Byzantine faults¹².

PBFT (Castro and Liskov, 1999) uses three phases (pre-prepare, prepare, commit) with O(n^2) messages per decision¹². HotStuff (Yin et al., 2019) replaces the all-to-all phases with a pipelined three-phase vote aggregated by the leader, achieving O(n) communication per decision and O(n) view change¹³. HotStuff underpins Diem/Libra and most production blockchain consensus. Tendermint (CometBFT) is a partially-synchronous BFT protocol with rotating leaders used by Cosmos, reaching consensus one block at a time with instant finality¹⁴.

When do you need BFT? When participants do not trust each other: permissioned blockchains, cross-organization ledgers, multi-cloud coordination where a compromised node could lie. For internal infrastructure where all nodes run your code on your hardware, crash-fault tolerance (Raft/Paxos) is sufficient and dramatically cheaper.

Real-World Example

etcd powering the Kubernetes control plane

Every Kubernetes cluster stores its entire state (pods, services, secrets, config maps) in etcd, a single-Raft-group key-value store. The reference Go library (etcd-io/raft) models Raft as a deterministic state machine: storage, transport, and ticking are the caller’s responsibility¹¹.

Cluster sizing. etcd recommends 3 or 5 members, never more than 7². The default heartbeat interval is 100 ms and the election timeout is 1000 ms, enforcing the 10x RTT rule for stable elections¹. For globally distributed clusters, the election timeout can stretch to 50 seconds¹.

Disk is the bottleneck. The p99 WAL fsync duration target is < 10 ms². If fsync latency exceeds the heartbeat interval, followers time out and force a new election. This is the number-one cause of spurious leader loss in production etcd clusters². Dedicated SSDs and ionice priority are non-negotiable.

Storage limits. The default quota is 2 GB (8 GB suggested maximum)². etcd is designed for small coordination state that fits in memory, not for high-volume data.

Linearizable reads. etcd defaults to ReadIndex: the leader confirms quorum before answering. Followers can serve serializable (stale) reads to scale read throughput, but linearizable reads must route through the leader².

Jepsen results. Kyle Kingsbury’s 2020 analysis of etcd 3.4.3 found key-value operations to be strict serializable under process pauses, crashes, clock skew, and partitions¹⁵. However, etcd’s distributed lock was fundamentally unsafe: process pauses induced approximately 18% lost updates with 2-second lease TTLs, plus a bug where the server did not re-check lease validity after a blocked lock acquisition¹⁵.

flowchart LR
    subgraph Node1[Node 1]
        R1a[Range A leader]
        R2a[Range B follower]
        R3a[Range C follower]
    end
    subgraph Node2[Node 2]
        R1b[Range A follower]
        R2b[Range B leader]
        R3b[Range C follower]
    end
    subgraph Node3[Node 3]
        R1c[Range A follower]
        R2c[Range B follower]
        R3c[Range C leader]
    end
    Node1 -.coalesced heartbeat.-> Node2
    Node2 -.coalesced heartbeat.-> Node3
    Node1 -.coalesced heartbeat.-> Node3

Scaling beyond a single group. CockroachDB shards its keyspace into ranges of approximately 512 MiB, each replicated by its own Raft group using the etcd/raft library¹⁶. A single node may participate in hundreds of thousands of consensus groups simultaneously. The MultiRaft optimization coalesces heartbeats to one exchange per pair of nodes per tick, which is the only way this scales¹⁶. TiKV uses the same pattern with smaller 96 MiB regions¹⁷.

Trade-offs

Common Pitfalls

Exercise

You are building a control plane for a job scheduler that must never double-schedule a job. Design the consensus layer: pick Raft or Paxos, choose cluster size (3, 5, 7), decide how writes and reads flow through the leader, and describe what happens during a 30-second network partition.

Key Takeaways

• Consensus gives you one property: agreement despite crash failures in a minority of nodes. That is expensive (one RTT per commit to a majority), so use it sparingly.
• FLP impossibility means no protocol can guarantee both safety and liveness in a purely asynchronous system. Practical protocols (Raft, Paxos) are always safe but may stall during partitions.
• Raft won by being understandable and having good libraries, not by being fundamentally different from Multi-Paxos.
• A cluster of 2N+1 survives N failures. Five nodes tolerate two failures and is the common sweet spot for production.
• The leader is a throughput and latency bottleneck. Sharding into many Raft groups (multi-raft) is how CockroachDB and TiKV scale writes horizontally.
• Distributed locks without fencing tokens are unsafe. Treat the lock as a performance hint and guard writes with a monotonic token the resource checks.
• If you are reaching for consensus per request, you probably do not need strong consistency at that layer. Push consensus down to metadata and coordination; let the data path use weaker guarantees where acceptable.

Further Reading

• In Search of an Understandable Consensus Algorithm (Raft paper): the primary Raft source; read the extended 18-page version for membership changes and log compaction, not just the conference short form.
• The Raft Visualization: interactive animations that are the fastest way to internalize leader election and log replication without reading code.
• Paxos Made Simple (Lamport, 2001): the readable 13-page single-decree Paxos derivation; start here before attempting the original “Part-Time Parliament” paper.
• Paxos Made Live (Chandra, Griesemer, Redstone, 2007): Google’s engineering diary of turning single-decree Paxos into Chubby; the best “theory to production” reading in this area.
• Jepsen: etcd 3.4.3 (Kingsbury, 2020): the canonical modern analysis of etcd and the definitive argument for fencing tokens over distributed locks.
• CockroachDB “Scaling Raft” (Darnell, 2015): the MultiRaft idea that enables per-range consensus at scale; essential reading for anyone building a distributed database.
• HotStuff (Yin et al., PODC 2019): the BFT protocol behind most production blockchain consensus; read if your threat model includes malicious participants.
• DDIA Chapter 9 (Kleppmann): the most readable textbook treatment of consistency, consensus, and total order broadcast; pairs well with this chapter.

Flashcards

References