Summary and key takeaways
The one constraint. No two machines share an observable present. Every fact one node holds about another is at least one one-way delay old, and the delay is unbounded. A slow node cannot be told from a dead one. All of this mechanism follows from this.
The one move. Stop trying to observe the property and define a checkable substitute that is an ordering claim, not a timing claim: "holder of the votes in term 7", "holder of epoch 4", "a cut no participant can tell from an instant", "acknowledged by a quorum". One data structure appears under eight names (term, epoch, generation, ballot, view, map version, fencing token, attempt ID): a monotonically increasing integer, agreed once by a quorum and stamped on everything.
The guiding sentence. Safety comes from intersection (no time). Liveness comes from timeouts (only time). Timeouts may change availability but must never be able to change correctness.
The story, in one line each (Tixora, SeatKV):
- A shorter timeout made failover constant and failed 40% of purchases, but sold nothing twice: timeouts only touch liveness.
- Adding nodes took 28 hours; a hot key could not be split; Mumbai read stale data. Fixes: throttled copy-catch-up-cutover, salting or replicating hot keys, follower reads at a timestamp.
- Twelve seats were sold twice because the seat store did not check a fencing token; membership grew 3 to 5 in one step; two sites need a witness.
- The seat map had a 2-second p99 because 40-way fan-out multiplies tails, and in a brownout storage nodes served pages nobody was waiting for; fixes were budgeted hedging, partial results, absolute propagated deadlines, and reject-and-correct discovery.
- The post-mortem showed four faces of one problem.
What this mechanism forbids (the independent items):
- Telling slow from dead.
- Deterministic consensus under asynchrony (FLP).
- Simultaneity.
- Mutual exclusion over a resource that does not check a token.
- A safe quorum over disputed membership, and majority availability in two symmetric domains.
- Write throughput from replication, and balance from balancing bytes.
- Splitting one hot key.
- Escaping
E[max of N]by restructuring, or hedging request-local slowness. - Bounding client staleness.
- A coordination-free non-monotonic invariant (CALM).
Items 1, 3, 5 and 10 are permanent. Item 2 is permanent but escaped in practice.
The four kinds of escape:
| Move | Instances | Costs |
|---|---|---|
| Replace timing with ordering | terms, epochs, fences, map versions, attempt IDs | a counter agreed once, a receiver that checks |
| Designate one event to mean n | committed log entry, ownership cutover, output commit | a single atomic point |
| Batch the coordination | leader, lease, in-band context, closed timestamps | failover window or clock-drift assumption |
| Restate the problem | CALM, escrow, UUIDs, partial results, geographic ownership | only when semantics permit; used last, though it is cheapest |
Three currencies. Resolution has exactly three currencies: waiting, wasted work, weakened semantics. There is no fourth; a design that seems to pay none has hidden one, usually weakened semantics.
Key numbers and formulas:
| Formula | Meaning |
|---|---|
P(slow) = 1 - (1 - p)^N | fan-out tail: N = 100 at p99 gives 63%; N = 40 gives 33% |
p^N | fan-out availability: 0.999^100 ≈ 90% |
L = λW | a propagated deadline caps W, therefore L: free admission control |
| hedge at p95 | 5% extra load; slow chance 0.05 becomes 0.05² = 0.0025 (1-in-400) if independent |
| quorum | N ≥ 2f+1; any two majorities intersect |
| light | about 10 µs per kilometre of round trip |
Rules to carry:
- A lease needs a fence. Order is cheaper to agree on than time.
- Membership is a quorum-defining set; discovery is a retryable cache.
- Keep the control plane off the data path and let the data plane fail static; control-plane load must scale with changes, not requests.
- Propagate absolute deadlines and make operations idempotent; retry policy is an overload question (retry budgets).
- Hedge only when the hedge rate is at the configured percentile; if it is higher, slowness is in the requests.
- Partial results are allowed only if the aggregation tolerates a missing input.
- Fan-out width and partition size pull in opposite directions: choose by whether queries touch one shard or all.
What stays unverified (each needs a test, alarm or drill): that every node holds the same membership; that the resource checks the fence on every write path; that tombstones outlive partitions; that clock drift stays within the lease assumption; that failures are as independent as 2f+1 assumes; that hedges are attempt-local; that "eventually" arrives; that the dedup window outlives the longest retry.
Claim typing. Permanent: FLP, quorum intersection, E[max of N], the lease boundary gap, unsplittable single key, CALM, the two-site result, the speed of light. Current practice: clock error bounds, partition-count defaults, EPaxos-class protocols, parallel replication apply. Economic: cross-AZ transfer prices, data residency, witness economics.
One sentence to keep: the cheapest round trip is the one your data model made unnecessary.