The problem hiding under everything: agreement
By now you know the hard part of a distributed system: there is no shared clock, no shared memory, messages take unpredictable time and can vanish, and machines can suffer partial failure — some die while others keep running, and nobody is sure which. Almost every interesting distributed task, once you peel it back, turns out to be one deceptively simple question dressed up in different clothes: can a set of machines all agree on a single value, even though they can only whisper to each other through an unreliable network? That question is called consensus.
Think of a board of directors scattered across the world who can only communicate by mailing letters — letters that sometimes arrive late, sometimes arrive out of order, and sometimes get lost entirely. They must all settle on exactly one decision: "the meeting is on Tuesday." It is not enough for each to pick a day; they must pick the same day, never change their mind once committed, and end up matching even though no two of them ever spoke at the same instant. Consensus is that protocol — a recipe for turning many separate opinions into one decision that everyone honours.
We need three properties from any honest consensus protocol. Agreement: no two correct machines decide different values. Validity: the value decided must be one that some machine actually proposed (you cannot agree on garbage nobody suggested). Termination: every correct machine eventually decides, rather than waiting forever. Holding all three at once, over a lossy network full of failures, is far harder than it sounds — and there is a famous, sobering reason why.
Why agreement is genuinely hard
The trouble is that you can never tell a slow machine apart from a dead one. When you mail a letter and no reply comes back, did the recipient crash, or is the reply simply still in the mail? Over an asynchronous network you cannot distinguish "crashed" from "slow" — this is one of the fallacies of distributed computing (latency is not zero, the network is not reliable). A theorem known as FLP makes this precise: with even one machine that might crash, no consensus protocol can guarantee it always terminates in a fully asynchronous system. There is always some unlucky timing of messages that stalls it.
Practical consensus protocols — Paxos and the more teachable Raft — get their work done by first solving a smaller problem you already met in guide 4's world of coordination: leader election. Instead of everyone arguing with everyone (which is chaos), the machines first elect a single leader. The leader proposes values; the others, called followers, simply vote to accept or reject. As long as a strict majority of machines agree, the value is decided. Routing every decision through one leader, backed by a majority vote, turns the tangled all-to-all problem into something tractable.
Why insist on a majority — more than half — rather than, say, any two machines? Because any two majorities of the same group must overlap in at least one machine. That overlap is the secret glue: it guarantees that a new decision cannot be made by a group that is unaware of the previous one, since at least one machine is in both groups and remembers. Majority voting is how a distributed system stays consistent across crashes and elections without ever needing the shared memory it does not have.
The CAP theorem: a choice you cannot avoid
Now suppose your service is spread across machines on two sides of an ocean, and the undersea cable between them is cut. The two halves can each still talk to their own users, but they cannot talk to each other. This is a network partition — the system has split into islands that can no longer exchange messages. A customer on the west coast writes a new value; a customer on the east coast reads. What should happen? The CAP theorem says that during a partition you face an unavoidable choice, and it is worth seeing exactly why.
CAP names three things you might want: Consistency (every read sees the most recent write — all machines show the same value), Availability (every request gets an answer, never an error or a hang), and Partition tolerance (the system keeps working even when the network splits). The theorem's real content is sharper than the popular slogan "pick two of three." Partitions are a fact of networks, not an option you can switch off — so P is not really negotiable. The honest statement is: when a partition happens, you must choose between C and A. You cannot have both at once.
Walk the cut-cable example through. To stay consistent, each isolated half must refuse any request it cannot safely answer — the west coast cannot accept the write if it cannot confirm the east coast will see it, so it returns an error. That sacrifices availability. To stay available, each half answers anyway from its own local copy — but now the west coast has the new value while the east coast serves the old one, and the two disagree. That sacrifices consistency. There is no third door: with the cable cut, you either say "no" (consistent but unavailable) or risk "stale" (available but inconsistent).
Fault tolerance through replication
Why go to all this trouble? Because the whole point of a distributed system is to keep working when individual machines do not. A single server is a single point of failure: when it dies, your service dies with it. The cure is replication — keeping copies of the same data on several machines so that the failure of any one is survivable. If you store three copies of your data, two machines can be on fire and the third still serves every read. This is fault tolerance built from cheap, unreliable parts, the same spirit as RAID mirroring a disk, but spread across whole computers.
But replication immediately drags consensus back in, because copies that are allowed to drift apart are worse than useless — a reader who lands on the wrong copy gets a wrong answer. The standard cure is state-machine replication: treat every replica as an identical machine that starts in the same state and applies the exact same sequence of updates in the exact same order. If they all begin equal and all process the same operations in the same order, they stay equal forever. The only hard part is agreeing on that order across the network — which is precisely consensus, run once per update.
Ordering and consensus are quietly the same family of problem, which is why guide 4's logical clocks and the happened-before relation matter here: they give every replica a consistent way to reason about the order of events without a shared clock. Putting it together, a fault-tolerant service usually looks like this: a small group of replicas, one elected leader, every update funnelled through consensus so all replicas apply it in the same order, and a majority required to commit — so the service survives any minority of crashes and never forgets a committed decision.
Putting it together: a committed write, step by step
Let us trace a single write through a replicated, consensus-backed service of five machines. Five is a common choice because a majority is three, so the system tolerates two simultaneous failures and still makes progress. Watch how leader election, majority voting, and replication all click together into one mechanism.
- A client sends "set X = 7" to the leader. (If the client guessed wrong and reached a follower, it is told who the current leader is and redirects.)
- The leader appends the update to its own log as "proposed, not yet committed," then mails the proposal to all four followers.
- Each follower that receives it appends the same entry to its own log, in the same position, and replies "acknowledged" to the leader.
- Once the leader has heard back from a majority — itself plus two others, three in total — the write is committed. A majority can never be undone by a future majority, because the two must overlap in a machine that remembers this entry.
- The leader tells the followers "entry committed," they apply it to their copy of X, and the leader answers the client "done." Even if the leader now crashes, the new leader elected from the survivors already has this entry in a majority of logs, so it is never lost.
Client Leader (L) Followers (F1..F4) | | | |---- set X = 7 ------->| | | |-- propose(X=7) -------->| (append to log) | |<------- ack ------------| | | ... wait for a | | | MAJORITY (3 of 5) ... | | | [committed!] | | |-- commit(X=7) --------->| (apply X=7) |<------ done ----------| | 5 machines -> majority = 3 -> tolerates 2 failures
And there is the whole rung in one motion. There is no shared clock or memory, so the machines coordinate purely by passing messages; messages can be slow or lost, so we never trust a single reply and always demand a majority; machines can suffer partial failure, so we keep replicas and elect a new leader when the old one goes quiet; and when the network itself partitions, CAP forces us to consciously choose whether this service answers with possibly-stale data or refuses until it can be sure. Distributed systems are not magic — they are careful agreement, built one honest message at a time.