How do five servers agree on anything when any of them can crash and the network can drop messages? This page explains quorums, Raft and Paxos from first principles, with diagrams and a small simulation.
A consensus algorithm lets a group of machines agree on a single value, or a sequence of values, even though some of them crash and messages are delayed or lost. Agreeing on a sequence gives you a replicated log, and if every server applies the same log of commands to the same deterministic state machine, every server ends up in the same state. This is state machine replication, the basis of fault-tolerant coordination services such as etcd, ZooKeeper and Consul, and of the metadata layers inside Kafka (KRaft), CockroachDB, TiDB and many others.
The algorithms on this page tolerate crash failures (a node stops or restarts), not Byzantine failures (a node lies). With 2f + 1 servers, they keep working as long as a majority of f + 1 is up: three servers survive one failure, five survive two.
Without consensus, replicated systems face split brain: a network partition leaves two halves each believing it is in charge, both accept writes, and the data diverges irreparably. Consensus prevents this with majority quorums. Any two majorities of the same group overlap in at least one server, so two leaders cannot both be confirmed for the same term, and a committed value is always known to someone in any future majority.
The FLP result (Fischer, Lynch and Paterson, 1985) proves that no deterministic algorithm can guarantee consensus in a fully asynchronous network with even one crash. Practical algorithms sidestep it by always being safe (never returning conflicting answers) and being live (making progress) only when the network behaves well enough for timeouts to work.
Raft (Ongaro and Ousterhout, 2014) was designed to be understandable. Time is divided into numbered terms. Each term has at most one leader. Every server starts as a follower and expects regular heartbeats from a leader. If it hears nothing for a randomised election timeout (often 150–300 ms), it increments its term, becomes a candidate, votes for itself and sends RequestVote to everyone else. A server grants at most one vote per term, and only to a candidate whose log is at least as up to date as its own. A candidate with votes from a majority becomes leader. Randomised timeouts make split votes rare, and if one happens the candidates simply time out and try again. Any server that sees a message with a higher term immediately reverts to follower.
Clients send commands to the leader. The leader appends each command to its log with the current term and sends AppendEntries to followers, including the index and term of the preceding entry. A follower rejects the request if its log does not contain that preceding entry; the leader then backs up and resends earlier entries until the logs match. This log matching check guarantees that if two logs agree on an entry's index and term, they agree on everything before it.
Once an entry from the current term is stored on a majority, the leader marks it committed, applies it to its state machine, replies to the client and tells followers the new commit index. In the diagram, entry 5 exists on three of five servers, so it is committed even though two followers lag. Because voters refuse candidates with less complete logs, any future leader must hold every committed entry: this is Raft's leader completeness property.
Paxos (Lamport, 1998; restated plainly in Paxos Made Simple, 2001) is the older algorithm and the one most correctness proofs build on. In basic Paxos, which decides a single value, a proposer picks a unique ballot number n and sends Prepare(n). Each acceptor promises to ignore ballots lower than n and reports any value it has already accepted. If a majority promise, the proposer must adopt the highest-numbered value reported (or may choose its own if none) and sends Accept(n, v). When a majority accept, v is chosen. The rule that a proposer must adopt a previously accepted value is what makes a chosen value permanent.
Multi-Paxos runs this for every slot in a log and, with a stable leader, skips phase 1 for subsequent slots, which makes its message pattern in the steady state very similar to Raft's. Raft can be seen as a particular, fully specified Multi-Paxos with a stronger leader and stricter rules about log contents.
The simulation below models only leader election: randomised timeouts, terms and one vote per term. It is for intuition, not production use.
import random
class Node:
def __init__(self, nid, peers):
self.id, self.peers = nid, peers
self.term, self.voted_for, self.state = 0, None, "follower"
self.reset_timer()
def reset_timer(self):
self.timer = random.randint(150, 300) # ms until election
def request_vote(self, term, candidate):
if term > self.term: # newer term: step down, clear vote
self.term, self.voted_for, self.state = term, None, "follower"
if term == self.term and self.voted_for in (None, candidate):
self.voted_for = candidate
self.reset_timer()
return True
return False
def run(n=5, alive=None, seed=1):
random.seed(seed)
nodes = {i: Node(i, None) for i in range(n)}
alive = set(alive if alive is not None else nodes)
for t in range(0, 3000, 10): # 10 ms ticks
for node in (nodes[i] for i in sorted(alive)):
if node.state == "leader":
for j in alive - {node.id}: # heartbeats suppress elections
nodes[j].reset_timer()
continue
node.timer -= 10
if node.timer <= 0:
node.term += 1; node.state = "candidate"; node.voted_for = node.id
votes = 1 + sum(nodes[j].request_vote(node.term, node.id) for j in alive - {node.id})
print(f"t={t}ms node {node.id} term {node.term}: {votes}/{n} votes")
if votes > n // 2:
node.state = "leader"
return node.id, node.term
node.reset_timer()
return None, None
print("leader:", run()) # all 5 up
print("leader:", run(alive=[0, 1, 2])) # 3 of 5: still a majority
print("leader:", run(alive=[0, 1])) # 2 of 5: no leader can be electedWith five or three live nodes, the first node to time out wins a majority. With two of five, every candidate gets two votes, never three, and the cluster correctly refuses to elect a leader. That refusal is the safety property in action: a minority partition stays unavailable instead of diverging.
| Protocol | Fault model | Leader | Understandability | Used in |
|---|---|---|---|---|
| Raft | Crash, 2f+1 nodes | Strong, required | Designed for it, full spec | etcd, Consul, CockroachDB, TiKV, Kafka KRaft |
| Multi-Paxos | Crash, 2f+1 nodes | Optimisation | Hard; many details left open | Google Chubby and Spanner |
| ZAB | Crash, 2f+1 nodes | Strong | Moderate | Apache ZooKeeper |
| PBFT and descendants | Byzantine, 3f+1 nodes | Rotating primary | Hard | Permissioned blockchains |