Consensus and Raft

Some decisions must be made exactly once. Which node is the leader? Who holds the lock? Is the username "sam" taken? If two nodes decide on their own, you get split brain: two leaders accepting conflicting writes, or two lock holders corrupting one file. Failure models explain why a single node cannot decide alone either. It may crash, or be paused without knowing it.

Consensus gets a group of nodes to agree on a value, even when some of them fail. Almost every system that offers linearizable operations on replicated data depends on it. Examples include etcd (and so every Kubernetes cluster), ZooKeeper, Consul, Kafka's KRaft controller, CockroachDB, TiDB and Spanner.

Concepts in this section

Read the pages in this order.

The problem and the limits

A consensus algorithm must guarantee three things. No two nodes decide differently. The decided value was proposed by some node. A node decides at most once. It must also make progress, so every live node eventually decides.

The first three are safety rules, which say nothing bad happens. The last is liveness, which says something good eventually happens.

In 1985, Fischer, Lynch and Paterson proved that no deterministic algorithm can guarantee termination in a fully asynchronous system, if even one node may crash. Real algorithms avoid this by using timeouts. They are always safe, and they make progress whenever the network behaves well for long enough.

Paxos, Multi-Paxos and Zab

Paxos came first. Lamport described it in "The Part-Time Parliament" and later in "Paxos Made Simple". Multi-Paxos runs many instances for a log and keeps a stable leader. Google's Chubby and Spanner use Paxos variants.

Raft is the one most new systems use, because it specifies the surrounding details: election rules, log repair, membership and snapshots.

Changing the cluster

Replacing a machine changes what "majority" means. If nodes switch to the new membership at different times, two leaders could win the same term. Raft fixes this with joint consensus, or by adding or removing one node at a time. etcd uses single-node changes and adds new members as non-voting learners until they catch up.

What consensus is used for

You rarely implement consensus. You use systems built on it.

• Kubernetes stores all cluster state in etcd. If etcd loses quorum, the control plane stops accepting changes, though running pods keep running. See Kubernetes core.
• Leader election. Each replica tries to create a key with a time-to-live. The one that succeeds runs the scheduled jobs.
• Consensus-backed databases. CockroachDB and TiKV run one Raft group per range of data. This is how consensus scales.

Common mistakes

• Writing your own consensus. It is a multi-year project, and it is hard to get right under failure.
• Using an even number of voters. Four voters tolerate the same failures as three.
• Storing hot application data in etcd. Its design targets small, critical, slowly changing data.

Key takeaways

• Consensus makes nodes agree on one value or one log, even with crashes.
• FLP says no algorithm can guarantee termination when the network is fully asynchronous. Practical systems use timeouts.
• Majorities overlap, so 2f + 1 nodes tolerate f failures.
• Raft is terms, randomized elections, log replication, and a leader whose log is the source of truth.
• Every write pays a majority round trip and a disk flush.

Further learning

Diego Ongaro's talk on Raft explains election and replication with animations.

Martin Kleppmann's lecture walks through Raft as pseudocode.

Raft consensus algorithm (visualization and paper)Raft is a consensus algorithm that is designed to be easy to understand.raft.github.io Paxos Made Simple (Lamport)paxos-simple.pdflamport.azurewebsites.net MIT 6.5840 Distributed Systems6.5840 Home Page: Spring 2026pdos.csail.mit.edu