Consensus Algorithms Aren't About Agreement

When people hear "consensus algorithm", they imagine nodes voting on a decision — a democratic process where everyone agrees. That mental model is wrong and leads to wrong conclusions about what consensus does, what it costs, and when you need it. Consensus is not about agreement. It is about total order — ensuring that every node processes the same operations in the same sequence, even when messages are delayed, nodes crash, and networks partition. The distinction is everything.

What consensus actually solves

The consensus problem, formally:

Given a set of processes that may propose values, designate one of them as the chosen value, such that:

1. Safety (agreement): at most one value is chosen.
2. Liveness (validity): a proposed value can eventually be chosen.
3. Termination: a value is eventually chosen (if the system is healthy).

The key insight: the "value" is not a vote. It is an operation. In a replicated state machine, every consensus decision is "apply this log entry at this position." The total order of these decisions is what makes the state machines consistent. Without total order, two nodes might apply the same operations in different sequences and diverge.

Node A: [op1] [op2] [op3] [op4]
Node B: [op1] [op2] [op3] [op4]
Node C: [op1] [op2] [op3] [op4]
 
All nodes see the same sequence → state machines converge

If the sequence differs — even by one operation — the state machines diverge, and there is no algorithm to reconcile them without additional coordination. Consensus is the mechanism that prevents this divergence.

Raft: consensus made legible

Raft (2014) was designed explicitly for understandability. Its decomposition into three sub-problems makes the mechanics clear:

Leader election

One node is the leader at any time. The leader accepts all client writes and replicates them to followers. If the leader fails, a new leader is elected.

state transitions:
 
follower → candidate → leader
   ↑          |
   |          ↓
   └──── follower (when leader appears)

The election protocol:

1. A follower's election timeout fires (150–300ms random).
2. It increments its term (a monotonically increasing logical clock) and becomes a candidate.
3. It votes for itself and requests votes from peers.
4. A node votes for the first candidate it hears from in a given term (one vote per term).
5. A candidate with a majority becomes leader.

The term is the mechanism that prevents split-brain. Two leaders in the same term is impossible — a node can only vote once per term, and a majority requires a majority of votes. If two candidates split the vote, neither wins, the term expires, and a new election starts with a higher term.

Log replication

The leader receives client requests, appends them to its log, and replicates log entries to followers:

client → leader: "SET x = 5"
leader log: [op1][op2][SET x=5]
              ↓ replicate
follower A log: [op1][op2][SET x=5]
follower B log: [op1][op2][SET x=5]
              ↓ commit (majority acknowledged)
leader: "SET x = 5 is committed"

An entry is committed when a majority of nodes have replicated it. The leader then applies the entry to its state machine and responds to the client. Followers apply entries as they are committed.

The log matching property ensures total order: if two logs contain an entry with the same index and term, all preceding entries are identical. This is enforced by the leader rejecting follower AppendEntries RPCs when the follower's log diverges from the leader's.

Safety: the invariants that make it work

Raft's safety depends on two invariants:

1. Election restriction: a candidate's log must be at least as up-to-date as any other node's log in that term. A node only grants a vote if the candidate's last log entry is more recent. This ensures the elected leader has all committed entries.

2. Leader completeness: if a log entry is committed in a given term, it will be present in the logs of the leaders for all higher-numbered terms. This prevents a stale leader from overwriting committed entries after a network partition.

These invariants are what make Raft safe — they guarantee that committed entries are never lost, even across leader changes and network partitions.

The cost of consensus

Consensus is expensive because it requires synchronous replication — every operation must be acknowledged by a majority before it is committed:

write path:
1. client → leader                    (1 RTT)
2. leader → majority followers        (1 RTT)
3. majority → leader                  (1 RTT)
4. leader → client                    (confirmation)
 
total: 2–3 RTTs for every write

At 1ms RTT between nodes, that's 2–3ms per write — before any application logic. At 10ms RTT (cross-datacenter), it's 20–30ms. This is why consensus systems are deployed in a single datacenter or with low-latency links between nodes.

The throughput ceiling is also real: the leader serializes all writes, so write throughput is bounded by the leader's capacity. Multi-raft (sharding the state machine across multiple consensus groups) is the standard solution, but it adds coordination overhead for cross-shard operations.

What consensus does not do

Three common misconceptions:

1. Consensus does not make your system "available." CAP theorem says a consensus system is CP — it sacrifices availability during a partition. If a majority of nodes are unreachable, the system stops accepting writes. This is the correct behavior for a consistent system, but it is not availability.

2. Consensus does not make reads consistent by default. A follower may serve stale reads because it hasn't applied the latest committed entry. Linearizable reads require either reading from the leader (which adds a load on the leader) or a read index protocol (the leader confirms its leadership before responding, adding one RTT).

3. Consensus does not prevent application-level divergence. If two operations commute (at x = x + 1 and y = y + 1), consensus ensures they execute in the same order — but the application might not care about the order. Consensus is overkill for commutative operations; last-writer-wins or CRDTs may be sufficient.

When you need it (and when you don't)

You need consensus when:

• Your system must be linearizable (every read sees the most recent write).
• You are implementing a replicated state machine (distributed lock, configuration store, distributed database).
• Correctness depends on total order — not just eventual consistency, but immediate, visible consistency.

You don't need consensus when:

• Eventual consistency is acceptable — caching, counters, analytics.
• Operations commute — increments, set additions, CRDTs.
• You can tolerate stale reads — read replicas, CDN caches.

etcd, Consul, and ZooKeeper use consensus for configuration and coordination. CockroachDB and YugabyteDB use consensus per-shard for distributed transactions. Kafka uses Raft for controller quorum and KRaft for metadata replication. In every case, the system uses consensus because correctness requires total order, not because "agreement is nice."