Why three nodes, or five, and almost never four?
Ask anyone who runs etcd or ZooKeeper how many nodes the cluster has and the answer is usually three or five. Four looks safer, yet it survives no more failures than three. The reason is the whole idea of consensus.
A storage system keeps its partition map, which server owns each partition, on five nodes, A to E. Every change is a command such as p7 → s4, and order matters: p7 → s4 then p7 → s9 leaves partition 7 on s9, the reverse leaves it on s4. So all five must apply the same commands in the same order, and a command, once decided and acted on, must never change, even if the nodes that decided it crash a second later. Meanwhile any node may be down, and messages get delayed or lost. Agreeing under those conditions is the consensus problem.
The obvious shortcuts each break one of those conditions. Letting the newest timestamp win trusts clocks that drift, and leaves no moment when the answer is final. Waiting for every node halts all changes the moment one crashes, the price Two-phase commit accepts for a different job. And letting one primary decide only moves the question to who replaces it, the failover trap from Replication & read replicas.
Any two majorities share a node
The way out is to decide by majority: a command is decided once more than half of the nodes have accepted it in the round that proposed it, three of the five. It is enough because any two majorities of the same five nodes overlap, since 3 + 3 is more than 5. Whatever a later majority is asked, at least one of its members was in the majority that accepted the earlier decision, and a protocol uses that shared member to stop the later majority from contradicting it.
To survive f crashed nodes, a cluster needs 2f + 1: three nodes survive one failure, five survive two. That answers the opening question. Four nodes need three for a majority, so they too survive one failure, with one more machine that can fail and one more acknowledgement to wait for. And a network split of two against two leaves neither half a majority, where an odd-sized cluster split in two always leaves one side with a majority.
Agree on a log, not on a value
The nodes do not vote on the map itself. They agree on a replicated log, a numbered list of commands that every node ends up holding in the same order, and each node applies the entries, strictly in order, to its own copy of the map. Same start, same deterministic commands, same order, same result: this is state machine replication.
The protocols you are likely to meet, Raft among them, give the log to a leader that orders the commands. A rebalancer sends p7 → s4 to A, the leader:
- A appends the command to its own log as entry 42 and writes it to disk.
- A sends entry 42 to B, C, D and E.
- B and C write it to their own disks and acknowledge. D is slow and E is down.
- A now holds entry 42, an entry from its own current term, on three of five nodes counting itself: the entry is committed.
- A applies entry 42 to its map and answers the rebalancer; its next message tells the followers to apply it too.
Diagram components: Application Service, Coordination Service, Coordination Service, Coordination Service, Coordination Service, Coordination Service.
Three copies on disk, the leader's included, are a majority, so A does not wait for D or E. They catch up later.
Terms: how an old leader finds out
The leader sends heartbeats when it has nothing to replicate. Now a network fault cuts A and B off from C, D and E. C stops hearing heartbeats and, after a randomised election timeout, stands as a candidate. Leadership is numbered in terms: A led term 4, so C starts term 5 and asks for votes. Each node votes at most once per term, and C wins with three, its own, D's and E's. Because two majorities overlap, no term can have two leaders. Random timeouts make split votes rare; when one happens, nobody wins and a new term starts.
A knows none of this. It still leads term 4 in its own eyes and keeps accepting commands, but A and B are two of five, so none of those entries commits and none of those clients is told it succeeded. Every message carries its sender's term, and a node that has seen term 5 rejects anything stamped 4. When the network heals, A hears from term 5, steps down and becomes a follower, and the new leader's log overwrites its uncommitted entries. No acknowledged write is lost, because none of them was acknowledged.
Diagram components: Coordination Service, Coordination Service, Coordination Service, Coordination Service, Coordination Service.
A still leads term 4 but reaches only B, so its entries never commit. C won term 5 with three votes; when the link returns, A steps down.
Why must C hold everything committed before the split? A node refuses its vote to a candidate whose log is less up to date than its own: whose last entry has an older term, or the same term and a lower index. A committed entry sits on a majority, C needed a majority of votes, and the two overlap, so a candidate missing the entry could not have won.
Reads hide the same trap. An old leader answering from its own copy can return a value the new majority has already replaced, so a system that promises up-to-date reads typically has the leader check with a majority that it still leads before it answers.
What a commit costs
Each commit costs a round trip from the leader to enough followers for a majority, plus a disk flush on each of them. Spread five nodes over three regions, two, two and one, to survive losing any one, and no region holds a majority, so every commit waits for a cross-region round trip, often tens of milliseconds. Every write also passes through the leader, so more nodes buy failures survived, not write capacity: five nodes wait for three copies where three wait for two. Systems that need more write throughput run many consensus groups side by side, as CockroachDB does with one Raft group per range of keys.
Where the guarantee ends
Consensus decides nothing without a majority. With three of five nodes down or cut off, the cluster refuses writes, and the minority side of a partition stops on purpose: it is the consistent side of the choice laid out in Consistency models: strong vs eventual (CAP). Even with a majority up, repeated failed elections can stall it; the core protocols of Raft and Paxos need timeouts only to make progress, not to stay safe.
The protocols also assume that a node either follows them or stops. Surviving f nodes that send corrupt or malicious messages takes a Byzantine fault tolerant protocol and, in the usual designs, 3f + 1 nodes. And the agreement ends at the cluster's edge: a client that took a lock and then paused can still write to a database the cluster has never heard of, and Distributed locks & leader election shows the fencing token that stops it.
Back to three or five
You will rarely implement any of this. etcd, which holds Kubernetes' cluster state, and Consul's servers run Raft; ZooKeeper runs its own protocol, ZAB; Paxos, from Leslie Lamport, is the older family, and Raft was designed to be easier to understand. What you do decide is the opening question.
The Distributed Lock Service challenge asks it in its own words: guarantee consistency under network partitions. Put the locks in a store that commits by majority, the etcd or CockroachDB component, give it three members if surviving one failure is enough or five for two, and write on the Grid what a client cut off with the minority gets: an error or a timeout, never a lock. The leases, watches and fencing around it are walked through in Coordination services: small state, leases & watches.