How do computers agree on anything when some of them crash?
Leslie Lamport explained consensus with a made-up Greek island parliament whose lawmakers kept wandering in and out, and Raft was invented just to be easier to understand.
▶ Start the storyComputers agree by voting, and by never needing everyone's vote. This is the problem: several machines must settle on one value, even though some of them may crash or be unreliable. Typical consensus algorithms make progress as long as a majority of servers is available, so a cluster of five can keep going even if two fail. If more servers fail, the cluster stops making progress, but it never returns a wrong result. And once a decision is made, it is final.
5 → 2
Databases use this to agree on which transactions to commit and in what order. Each server keeps a log of commands, and makes sure every machine applies the same commands in the same order, so all of them end in the same state.
The classic solution is Paxos, which Leslie Lamport submitted in 1989 and described through a made-up Greek island whose parliament had to function even though legislators wandered in and out of the chamber. It became a family of protocols, and it guarantees safety, though a famous result by Fischer, Lynch and Paterson shows no deterministic fault-tolerant protocol can guarantee progress in an .
Paxos was hard to grasp, so Diego Ongaro and John Ousterhout designed Raft to be easy to understand. A cluster elects one leader, who sends regular heartbeats. If the heartbeats stop, a follower becomes a and asks for votes; whoever wins a majority leads. The leader's log entries count as committed once half or more of the followers confirm them.
Quiz me
0/3
Recap
Consensus algorithms need only a majority to agree, so a cluster of five survives two crashes without ever returning a wrong answer.
💡 A trick to remember it · Majority rules, and the majority never forgets: five friends can lose two and still finish the vote.
Surprising fact · Paxos was explained through a fictional Greek island's parliament, and Raft was designed to be easier to understand.
Connects to
Sources (4)
No source, no claim. Every fact in this lesson (18 claims) cites at least one of these.