Distributed Systems Coordination
Who is allowed to decide, and how does everyone else learn the decision without asking?
Who this mechanism is for: a developer who writes services, calls APIs and knows basic SQL, and who now has to run software on more than one machine. You do not need to know how consensus, replication or databases work inside. Every technical term is explained the first time it appears, and again in the glossary at the end. You do need to be willing to read some arithmetic: most claims here are small calculations.
The story we will follow
Ingrid Haugen is a backend engineer at Tixora, a company that sells tickets for concerts, football matches and festivals. At the heart of Tixora is SeatKV, a key-value store the company built itself. It holds the status of every seat ("seat A12 of show 881 is FREE, HELD or SOLD") and every shopping-cart hold. SeatKV runs on 12 storage machines (called nodes) in 3 racks, spread over 3 availability zones (separate buildings) of one cloud region in Frankfurt. The data is cut into 64 pieces (partitions), and every piece is stored on 3 nodes. A small separate cluster of 5 machines, the metadata cluster, stores the list of nodes, the map of which node holds which partition, and who the current leader of each partition is. A second region in Mumbai serves fans in Asia.
Tixora handles about 20 million seat operations per day. But when a famous tour goes on sale, hundreds of thousands of requests arrive in the first minute. That minute is when everything breaks.
Ingrid works with two colleagues. Babajide ("Jide") Adeyemi is the site-reliability engineer on call. He watches the dashboards and proposes quick fixes: "lower the timeout", "add nodes", "add retries". Carmen Reyes is the product lead. She asks the "why can't we just ...?" questions: "why can't we sell the same seat from Mumbai in 20 ms?", "why can't we never lose a sale?"
During the next on-sale season Ingrid will meet five problems, one at the start of each article. Each problem looks like a bug. Each is actually a consequence of one hard fact: machines that share nothing can only talk by messages, and a message that does not arrive tells you nothing about why. At the end of each article we go back and solve her problem.
The main idea of this whole mechanism:
How this mechanism is organized
- 1
No shared present
What is new when there is no shared memory, no shared clock, and no way to tell a dead machine from a slow one? Why do safety and liveness need different tools?
CaseA faster failure detector made it worse
- 2
Distribution of data
Given that data must live on several machines, who owns which bytes, and what does it cost to change the owner?
CaseA 28-hour move, and a partition that stayed hot
- 3
Deciding without observing
How do machines agree on a leader, a lock, a membership list or a snapshot when none of these can be observed directly?
Case12 seats sold twice, and the lock worked
- 4
Communication
How do machines talk across a network that may delay, duplicate or drop messages, and why do retries, fan-out and discovery cause outages?
CaseA 2-second page from 50 ms partitions
- 5
Putting it together
What does this whole mechanism forbid, what are the escapes, and where is the reasoning still weak?
CaseThe post-mortem: four problems side by side
After that: a summary, hands-on labs, interview questions and a glossary.
One request: do not skip the numbers. This mechanism quotes round-trip times, failure probabilities and message counts. The ratios between them decide which design is possible.
What do I do, and what does each option cost?
Can I see it myself?
A shorter timeout makes a failure detector wrong more often
Measure the false-suspicion rate of a heartbeat detector against its timeout ([The arithmetic worth carrying](/mechanisms/coordination/how-it-works/no-shared-present/the-arithmetic), [Failure detection: liveness is a relation, not an attribute](/mechanisms/co
SimulatePythonFan-out arithmetic and rebalancing time
Check two formulas from [The arithmetic worth carrying](/mechanisms/coordination/how-it-works/no-shared-present/the-arithmetic) and [State has mass](/mechanisms/coordination/how-it-works/distribution-of-data#the-arithmetic-everything-divides-by) with real numbers.
SimulatePython with NumPyWhy two majorities always intersect, and why a lock with a TTL is not enough
See quorum intersection and a stale lock holder ([Consensus: what it delivers and what it costs](/mechanisms/coordination/how-it-works/deciding-without-observing/consensus) and [Locks, leases and fences: why mutual exclusion is unavailable](/mechanisms/co
Simulate · Break itPythonFencing tokens versus a paused leader (about 30 minutes)
Claim to test: a lease alone leaks at the boundary, and a fence checked by the resource closes the gap (What coordination forbids, item 3).
Break itPythonEscrow removes coordination
Measure the message count of a global budget with and without escrow ([Coordination avoidance, which is where this article should end](/mechanisms/coordination/how-it-works/deciding-without-observing/coordination-avoidance)).
SimulatePythonFan-out tail and power-of-two-choices (about 45 minutes)
Claim to test: at N = 100 and per-shard p99, about 63% of requests contain a p99 event, and two random choices beat greedy choice on stale load information (see Scatter-gather and Service discovery).
SimulatePython with NumPyHedging: when it helps and when it does not (about 40 minutes)
Claim to test: hedging at p95 turns a 1-in-20 slow tail into about 1-in-400 if slowness is attempt-local, and does nothing if it is request-local (see Hedging).
SimulatePython
Can I reason about it under questioning?
Interview questions
Short questions on distributed coordination, such as failure detection, consensus and quorums, leases and fencing, split brain, partitioning and the costs of remote calls, each with an answer you could give aloud and a link to the full explanation.
Scenarios
Longer problems on distributed coordination, of the kind asked in senior interviews: each one estimated with numbers, diagnosed, and answered with its trade-offs.
The tensions this mechanism takes a position on. Each recurs across mechanisms.
Consistency vs. availability vs. latency
For example: quorums, replication modes.
Ordering vs. parallelism
Global order costs serialization; parallelism costs order.
Latency vs. throughput
For example: batching, group commit, micro-batch.
Coupling vs. coordination cost
For example: 2PC vs. sagas, schema contracts vs. schema-on-read.
Durability vs. acknowledgment latency
How much must be confirmed before you say "yes".
Ideas this mechanism meets that keep coming back, mechanism after mechanism.
Absence is not evidence
Absence of an event is not absence of a failure.
Variance costs more than volume
Variance costs more than volume.
Independence is assumed
Independence is assumed everywhere and is true almost nowhere.
Costs are conserved
Costs are conserved, never removed.
Fixed cost per operation
Fixed cost per operation implies a natural batch size.
Show all 16 principlesShow fewer
Designate one write
Atomicity over n items is atomicity over one designated item.
Coordination cannot be made cheaper
Coordination is the only thing you cannot make cheaper.
Local optimizations compose badly
Identical mechanisms at adjacent layers do not add up. They interfere.
Granularity mismatch
Granularity mismatch creates amplification.
The algebra decides
What can be skipped, pushed down, parallelized, merged or precomputed is determined by the algebra of the function, not the layout of the data.
Sound approximations
When exactness is too expensive, use a sound approximation.
Guarantees have scope
Atomicity is bounded by the shared commit substrate.
The end-to-end argument
Guarantees compose to the weakest link, and only endpoint guarantees are real.
Little's Law
Concurrency = Throughput × Latency.
Power laws and skew
Coordination scales with parties
Coordination cost scales with the number of parties who must agree, not with the volume of data.