Distributed Consensus: Raft, Terms and the CAP Theorem

Why agreeing on one value is hard

A single database server never has to argue with itself. A cluster of five does. Every server keeps its own append-only log of commands, and consensus is the guarantee that all correct servers execute the same commands, in the same order, even though the network between them can delay, drop or reorder any message and any node can crash without warning. Formally, a consensus protocol must satisfy three properties: agreement (no two correct nodes decide differently), validity (the decided value was actually proposed by someone) and termination (every correct node eventually decides). The 1985 FLP impossibility result proved that no deterministic algorithm can guarantee all three in a purely asynchronous network — real systems dodge this with timeouts and randomisation, trading a theoretical guarantee for one that works in practice almost all the time.

Raft: one leader, one log, one term at a time

Raft, designed by Ongaro and Ousterhout in 2014, was explicitly built to be easier to reason about than the earlier Paxos protocol, while giving the same safety guarantees. Every server is in one of three states — follower, candidate, or leader — and time is divided into monotonically increasing terms, each with at most one leader. All client commands flow through the current leader, which appends them to its own log and then replicates them to followers via AppendEntries remote calls, tagged with the term in which they were written.

Leader election with randomised timeouts

Followers expect a periodic heartbeat from the leader. If none arrives before a randomised election timeout elapses (commonly 150-300ms), the follower assumes the leader is gone, bumps the term number, becomes a candidate, votes for itself, and asks every peer for a vote:

grant_vote(candidate) =
  candidate.term  >= self.currentTerm
  AND self.votedFor in {null, candidate.id}
  AND candidate.log is at least as up-to-date as self.log

// a candidate that wins a majority becomes leader for that term
// and immediately sends heartbeats to suppress further elections

Randomising the timeout is the whole trick: if every follower waited an identical interval they would all start elections at once and split the vote forever. With randomised timeouts, one follower almost always fires first and collects a majority before anyone else even notices the leader is gone. A term acts as a logical clock — any message carrying a stale term number is rejected outright, which is what prevents an old, temporarily-partitioned leader from corrupting the log once it reconnects.

Log replication and the commit rule

An entry becomes committed, and safe to apply to the state machine, only once the leader has confirmed it is stored on a majority of servers — for a five-node cluster, that means the leader plus two followers. This single rule is what makes Raft tolerate ⌊(n-1)/2⌋ failures: a five-node cluster survives two simultaneous crashes because any two majorities of three out of five servers must overlap in at least one node, so a newly elected leader can never "forget" a value that a previous majority already committed.

The CAP theorem: pick two, but P isn't really optional

Eric Brewer's CAP theorem states that a distributed data store can provide at most two of Consistency (every read sees the latest write), Availability (every request gets a response) and Partition tolerance (the system keeps functioning when the network splits). Because real networks do partition, giving up P is not a serious option, so the practical choice collapses to CP versus AP. Raft and Paxos are CP: during a partition, the minority side refuses to accept writes rather than risk two leaders committing conflicting values — a deliberate sacrifice of availability to keep every acknowledged write durable and correct.

Crash faults versus Byzantine faults

Raft assumes crash-stop failures: a bad node simply goes silent, it never sends corrupted or contradictory messages. That assumption is what lets 2f+1 replicas tolerate f failures. Byzantine fault tolerance drops that assumption entirely and assumes a faulty node can behave arbitrarily, including actively lying to different peers — which requires 3f+1 replicas plus cryptographic signing to tolerate the same f faults, and is why BFT protocols like PBFT and HotStuff are reserved for blockchains and other adversarial environments rather than ordinary internal infrastructure like etcd or Kafka's KRaft metadata layer.

Frequently asked questions

Try it live

Every term, heartbeat and election above runs live in Distributed Consensus. Kill a leader, partition the network, and watch a new leader get elected — or watch the minority side stall — entirely in your browser.