Distributed Coordination

You run a nightly billing job on three servers for redundancy. At midnight, all three start running it, and every customer is charged three times.

You need exactly one server to do the work. That sounds trivial — pick one — and it is one of the genuinely hard problems in distributed systems, because the machines must agree while being unable to reliably tell whether each other are alive.

That agreement problem is consensus, and coordination systems exist to solve it once so you do not have to solve it repeatedly and badly.

What needs coordinating

The same primitive underlies several familiar problems:

• Leader election — exactly one node performs a role.
• Distributed locks — only one process touches a resource at a time.
• Configuration — all nodes read the same settings and learn about changes.
• Service discovery — nodes find each other as membership changes.
• Membership — everyone agrees on who is currently in the cluster.

Each reduces to: get a group of unreliable machines to agree on one value.

Why it is hard

The obstacle is the ambiguity from the failure detection lesson. When node A cannot reach node B, A cannot tell whether B crashed, is slow, or is fine behind a broken network.

That produces the failure that makes coordination dangerous:

Split brain. The network partitions. Nodes on each side conclude the others are dead and elect their own leader. Two leaders now accept writes, and the data diverges. Reconciling afterwards ranges from painful to impossible.

Which is why real algorithms are built on majorities.

Quorums: why a majority is the answer

The rule is elegant. Require agreement from more than half the nodes for any decision.

Two majorities of the same set must share at least one member — you cannot form two majorities from five nodes without overlap. That shared member cannot agree to two conflicting things, so two leaders cannot both be elected.

The consequences are worth internalising:

• A cluster of 5 tolerates 2 failures. With 3 remaining you still have a majority.
• Even numbers waste a node. A cluster of 4 also tolerates only 1 failure, because 3 of 4 is the majority threshold — same as 3 of 5's 2-failure tolerance would suggest is achievable with fewer machines. This is why coordination clusters are always odd: 3, 5, 7.
• You lose availability rather than correctness. If a partition leaves no side with a majority, nobody makes progress. That is a deliberate CP choice from the CAP lesson — refuse to act rather than risk two leaders.

Consensus algorithms

Paxos proved consensus was possible and is notoriously difficult to understand and implement.

Raft was designed for understandability and is what most modern systems use. It works in a way you can hold in your head:

1. Nodes start as followers.
2. A follower that hears nothing from a leader becomes a candidate and requests votes.
3. A candidate receiving votes from a majority becomes leader.
4. The leader sends regular heartbeats; all writes go through it and are replicated to followers.
5. If the leader goes silent, the cycle repeats with a new term number.

The term number is what makes it safe. It increases with each election, and nodes reject messages from an older term. A leader that was partitioned away and returns finds its term is stale and steps down — automatic protection against split brain.

Distributed locks, and the trap

The obvious way to ensure one worker runs the billing job:

const acquired = await lock.acquire('billing-job', { ttl: 60_000 });
if (!acquired) return;
await runBilling();
await lock.release('billing-job');

The TTL exists so a crashed holder does not block forever. It also introduces the flaw.

Worker A acquires the lock and starts. It then pauses — garbage collection, a slow disk, CPU starvation — for 70 seconds. The 60-second TTL expires. Worker B acquires the lock and starts billing. Worker A wakes up, believing it still holds the lock, and continues billing.

Both are now running. The lock did exactly what it promised and you still have two writers.

Fencing tokens

The fix, and the part almost everyone omits.

The lock service returns a monotonically increasing number with each grant. Every write to the protected resource carries that token, and the resource rejects any token lower than the highest it has seen.

Worker A acquires -> token 33, pauses
Worker B acquires -> token 34, writes with 34
Worker A wakes    -> writes with 33 -> REJECTED (34 already seen)

The stale worker is fenced out by the storage layer itself, not by trusting it to behave. This is the same idea as Raft's term numbers, and the same reason the failure detection lesson insisted on fencing after failover.

Coordination services

ZooKeeper is the long-standing option: a hierarchical namespace with ephemeral nodes that vanish when a client disconnects, which makes leader election and membership natural.

etcd is a key-value store using Raft, and is what Kubernetes stores all cluster state in.

Consul adds service discovery and health checking.

All are CP: during a partition, the minority side stops serving rather than risking divergence.

Avoiding coordination entirely

The best coordination is none, and this is the answer interviewers appreciate most.

Partition the work. Instead of electing one leader for the billing job, shard customers across workers by id. Each worker owns its slice; no agreement needed. This is the single most effective technique.

Make operations idempotent. If running the job twice is harmless, exclusive execution stops mattering.

Use atomic database operations. A conditional update decides the winner without a separate lock service.

Use CRDTs. Data structures that merge deterministically need no agreement at all.

Coordination is expensive — it costs round trips, availability during partitions, and operational burden. Every design that removes the need for it is worth more than a design that implements it well.

Check your understanding

Common mistakes

Locks without fencing tokens. The most common serious error, and the one that silently corrupts data.

Even-numbered clusters. Four nodes tolerate the same single failure as three, at higher cost.

Putting coordination in the request path. Consensus needs round trips to a majority. Doing it per request adds latency to everything.

Using ZooKeeper as a database. It is designed for small, rarely-changing coordination data, not application state.

Assuming a released lock means work finished. The holder may have crashed mid-operation. Design for partial completion.

Practice

Key takeaways

• Coordination problems — leader election, locks, configuration, membership — all reduce to agreeing on one value among unreliable machines.
• Majorities prevent split brain, because two majorities must overlap. Use odd-sized clusters; even numbers buy no extra fault tolerance.
• Coordination systems are CP: during a partition the minority stops making progress rather than risking two leaders.
• Raft is the practical algorithm to know, and its term numbers are what force a returning stale leader to step down.
• A distributed lock is a lease, not a mutex — a paused holder plus TTL expiry means two workers can run simultaneously.
• Fencing tokens are the fix: the resource rejects writes carrying a stale token.
• Avoiding coordination beats implementing it — partition the work, make operations idempotent, use atomic conditional writes.

Further reading

• Leslie Lamport, "The Part-Time Parliament" (ACM TOCS, 1998) and "Paxos Made Simple" (2001).
• Diego Ongaro and John Ousterhout, "In Search of an Understandable Consensus Algorithm" (USENIX ATC 2014) — Raft.
• Martin Kleppmann, "How to do distributed locking" (2016) — the fencing-token argument in full.
• Mike Burrows, "The Chubby Lock Service for Loosely-Coupled Distributed Systems" (OSDI 2006).
• Pat Helland, "Life Beyond Distributed Transactions: An Apostate's Opinion" (CIDR 2007) — designing to avoid coordination.