The latency floor: one conservation law, four products
Why can reads and writes not both be local, and why do you pay for uncertainty rather than distance?
The governing arithmetic: one conservation law, four products
Take one object x, stored at two nodes A and B. Let d be the one-way delay between them.
Sequential consistency costs r + w ≥ d
The derivation needs two objects, which is itself a lesson. Suppose reads are local at A, writes are local at B, and both cost nothing. Now run the Dekker pattern (a classic two-variable test):
Client at A: write x = 1; then read y
Client at B: write y = 1; then read x (x and y start at 0)With no messages in flight, A's write to x has not reached B, and B's write to y has not reached A. So both reads return the old value 0. But no single total order of the four operations explains that. In any total order, one of the two writes comes before the other client's read, so that read must see 1. At least one of r or w must therefore carry a message, and their sum is bounded below by the delay.
Note what this means: sequential consistency's price is invisible in a single-object program. You only see it when two objects interact. That is the first hint that single-object linearizability (below) is the better primitive.
Linearizability costs uncertainty, not delay
Attiya and Welch proved bounds for read/write registers: read ≥ u/4 and write ≥ u/2, where u is the spread between the minimum and maximum message delay (u = d_max − d_min). The intuition is the whole point. An operation must be placed in real time relative to other operations. If a message took "somewhere between d_min and d_max" and you cannot tell whether it arrived before or after a local event, you must wait out the ambiguity.
This is the same quantity as the clock uncertainty ε of databases that assign commit timestamps from clocks (The unification and its price returns to it). Google Spanner pays ε on the write path, as a deliberate "commit wait". CockroachDB pays it on the read path, as occasional restarts of reads. The theorem says the same quantity is unavoidable for linearizable registers. The same physical limit appears a third time, with a different bill.
Four ways to buy a fixed total
Because the total is fixed and only the split is free, the products on the market are four solutions to one conservation law (the conserved-cost rule, as a theorem):
| How it is bought | Read cost | Write cost | What actually pays |
|---|---|---|---|
| Leader reads | a trip to the leader | quorum round trip | Geography and availability: one vantage point for everyone |
| Lease or read-index followers | local (with a lease) or one round trip (read-index) | quorum round trip | A clock assumption that nothing verifies, or the round trip you tried to avoid |
| Quorum reads (ABD) | majority round trip plus a write-back round | majority round trip | Two round trips, and a write on the read path |
| Local reads and writes | local | local | The total order itself: you gave up the model |
A lease is a time-limited promise: "for the next 10 s, I am the only one who may serve linearizable reads, and nobody else will accept writes without telling me." The follower holding a lease can answer reads locally. A read-index read asks the leader only for its current log position, then waits locally until it has applied up to that position. ABD is the classic algorithm for a register built from quorums: a read first collects values from a majority, then writes the winning value back to a majority before it returns.
The lease row is the sharpest example of cost relocation in this article: a lease buys read locality by substituting an unverifiable assumption for a message. The assumption is that clocks drift less than a stated bound. When drift exceeds the bound, correctness fails, and nothing reports it.