The question this answers
What does it mean for a distributed system to behave "as if there were only one copy"?
Linearizability for a set of operations on a single object: there exists an assignment of an effect point to each operation, lying within that operation's invocation-to-response interval, such that executing the operations in effect-point order is a legal sequential execution of the object, and any operation that completed before another began is ordered first. It is a per-object guarantee — linearizability of two objects individually does not linearize operations across them.
Everything below is bought to hold this sentence. "Strongly consistent" with no scope attached is a slogan, not a guarantee — read what it actually covers, and what it explicitly does not.
A node can never verify linearizability locally; it has no view of other clients' intervals. A replica serving a read knows only its own state, which is why a linearizable read requires either reading through a leader that has confirmed it still holds leadership, or reading a quorum and repairing before returning. "I am the leader and my data is current" is exactly the inference that fails. See Fencing Tokens: Making the Stale Actor Safe, Not Just Unlikely.
A node knows its own state and the messages that arrived. Everything else is inference from evidence that was already stale. "B has not replied in five seconds" is knowledge; "B is down" is a decision — and usually the bug.
The interval is the whole idea
The mistake almost everyone makes first is treating an operation as an instant. It is not. A write is invoked at one time and responds at another, and anything can happen in between — including the entire lifetime of another client's read. During that window, a read is permitted to return either the old value or the new one, and both are correct.
Linearizability asks a question about existence: is there some way to pick a single instant inside each operation's interval such that the whole history reads as a sensible sequential story? If such a placement exists, the history is linearizable. If no placement exists, it is not — and the counterexample is a proof, not an opinion.
Two consequences follow immediately and both surprise people. First, a read concurrent with a write may legally return the stale value — that is not a violation. Second, once *any* read has returned the new value, no later read may return the old one, even from a different client on a different node, because their intervals no longer overlap.
C2 overlaps the write and returns the old value — legal, because we may place the write's effect at t=4, after C2's effect at t=2. C3 also overlaps the write and returns the new value, which is legal because its effect point sits at 5.5, after 4. C4 begins after everything and returns 1. The single sequential story is: read(x)->0, write(x,1), read(x)->1, read(x)->1.
Non-linearizable: no placement can work
The classic violation has three operations and no clever placement rescues it. C2's read returns 1, which forces the write's effect point to be at or before t=4. C3's read begins at t=7 — strictly after C2 responded, so their intervals do not overlap and real-time order applies. C3 must therefore see everything C2 saw. It returns 0.
There is no assignment of effect points that produces a legal sequential history here. The value went backwards across two non-overlapping operations, and no amount of "the replica was lagging" changes the verdict — that explanation is the *cause*, not a defence. This is precisely the anomaly that read-from-any-replica produces, which is why serving reads from an asynchronous follower is not linearizable no matter how small the lag.
C2 returning 1 forces the write's effect point into [0, 4]. C3 is invoked at 7, after C2 responded at 4, so real-time order requires C3 to be ordered after C2 and therefore after the write. A legal sequential history would then have C3 return 1. It returned 0. No placement of effect points repairs this, so the history is not linearizable.
What it costs, and where the cost actually lands
Linearizability is not free and the price is not primarily latency. A linearizable read cannot be served from a node that might be behind, so it requires one of: reading through a leader that has *confirmed* it is still leader (a round trip, or a lease with a bounded clock assumption), reading a quorum and repairing before responding, or reading from a node holding a valid read lease. Every one of these is a dependency on other nodes for a read.
That dependency is the real cost: a linearizable operation cannot complete while the node handling it is cut off from the rest of the system. This is the exact statement CAP formalises, and it is why linearizability and availability-under-partition are the pair that cannot both be had. See CAP: What the Theorem Actually Says.
Linearizability also composes in one very useful way and fails to compose in another. It is *composable across objects* in the formal sense — if each object is individually linearizable, the whole system is linearizable — but that guarantee is about each object separately, and it gives you nothing about an operation spanning two objects. For that you need transactions, and specifically strict serializability. See Serializability vs Linearizability: Two Different Properties.
- A leader read is linearizable only if the leader confirms leadership at read time or holds a valid lease — otherwise a partitioned-away leader serves stale reads confidently.
- A quorum read is linearizable only if it repairs a partially-completed write before returning; otherwise a later read can observe the older value.
- Compare-and-set, unique-id allocation, distributed locks and fencing tokens all require linearizability. Nothing weaker suffices.
- Per-object linearizability says nothing about multi-object atomicity, and this gap is where most "we have strong consistency" designs break.
Key points
- An operation is an interval, not a point; linearizability asks whether effect points can be placed inside those intervals to yield a legal sequential history.
- A read concurrent with a write may legally return the old value; once any read returns the new value, no later non-overlapping read may return the old one.
- The real-time constraint is what distinguishes linearizability from sequential consistency.
- It is a per-object property. It gives you nothing about atomicity across two objects.
- The cost is a dependency on other nodes for every operation — which is exactly why it cannot survive a partition on the minority side.
The chain, answered
Every field here is required, which is why no lesson in this domain can recommend a design without naming what an operator sees when it fails, what survives the partition, what repairs it afterwards, and the simpler thing to consider first.
- • Record the history: each operation's invocation time, response time and result.
- • Search for an assignment of effect points, one per operation, within each operation's interval.
- • Require the resulting order to be a legal sequential execution for the object's type.
- • Require that if operation A responded before operation B was invoked, A precedes B in the order.
- • If such an assignment exists the history is linearizable; a single history with no valid assignment disproves the guarantee for the system.
- • A read is served by a replica that has not yet applied a completed write.
- • A leader that has been partitioned away serves reads believing it is still current.
- • A quorum read observes a partially-completed write and returns without repairing it, letting a later read see the older value.
- • A read lease outlives its validity because clocks disagreed about when it expired.
- • The operation spans two objects and per-object linearizability provides nothing.
- • Stale leader reads: after a network blip, the demoted leader continues answering reads for several seconds with pre-partition data. The operator sees no errors, and clients see values regress. This is the failure that makes leader reads without leadership confirmation unsafe.
- • Lost update through compare-and-set on a non-linearizable store: two clients both read the old value, both write, and one update disappears. Observed as a counter that undercounts, or an inventory that oversells, under load only.
- • Read-path regression: an operator moves reads to replicas for capacity and silently downgrades the model. The symptom is intermittent anomalies with no error rate, appearing weeks after the change.
- • Availability loss on the minority side: after making reads linearizable via quorum, the minority side of a partition returns errors for reads that used to succeed. This is correct behaviour and reads as an outage.
- • Lease-expiry violation under clock skew: a node holds a read lease it believes is valid while the cluster has already moved on, serving stale linearizable-looking reads. Observed as a narrow window of impossible values around failovers.
- • Every linearizable operation requires communication with, or a valid lease from, enough of the system to rule out a more recent state elsewhere.
- • That communication is on the critical path of reads as well as writes — which is what makes linearizable reads expensive in a way people do not expect.
- • Across regions the cost is bounded below by the round-trip time. There is no implementation that avoids this. See The One Number You Cannot Optimise.
- • On the majority side of a partition, linearizable operations continue normally.
- • On the minority side, they must block or fail. A system that keeps answering there is not linearizable, whatever it claims.
- • During a leader change, there is a window where no operation can be linearizable, so the system is unavailable rather than incorrect — which is the correct trade for this guarantee.
- • Detect: run a linearizability checker against recorded histories under fault injection. This is the only way to know rather than believe. See Chaos Engineering Is Not Randomly Breaking Production.
- • Contain: fence stale leaders at the storage layer so a demoted node cannot serve reads it believes are current. See Fencing Tokens: Making the Stale Actor Safe, Not Just Unlikely.
- • Recover: after a partition, the minority side resumes as soon as it can reach a quorum; no data reconciliation is needed because nothing incorrect was served.
- • Reconcile: nothing to reconcile — that is the point of paying for this model. The reconciliation work you avoid is the return on the coordination you paid.
- • Verify: assert the invariant that required linearizability (uniqueness, no oversell, no double-spend) continuously, since it is the observable consequence.
- • Whether each read confirmed leadership or read a quorum, versus being served locally — this is the difference between the guarantee and its absence.
- • Read-lease age at the moment of service, and how close it runs to expiry.
- • Rate of failed operations attributable to loss of quorum, which should rise during partitions and is the visible price of the model.
- • Results of continuous history checking under injected faults, rather than during steady state where every model looks correct.
- • Invariant-violation counters for the specific property linearizability was bought to protect.
- • Compare-and-set, distributed locks, leader election, fencing tokens and unique-id allocation — none of which are correct on a weaker model.
- • Any invariant that must never be violated even momentarily: no oversell, no double-spend, no duplicate identity.
- • Coordination primitives that other systems will build on, where a rare violation propagates into every dependent system.
- • Read-heavy paths where a few hundred milliseconds of staleness is genuinely harmless — you are paying coordination on every read for nothing.
- • Cross-region operations, where the round trip is felt by users and the guarantee is rarely what the feature needs.
- • Systems that must accept writes during a partition, which linearizability forbids on the minority side by construction.
- • Multi-object invariants, where per-object linearizability does not deliver what the team believes it does and the money is wasted.
- • Session guarantees, which fix the user-visible symptoms at a fraction of the cost. See Session Guarantees: The Underrated Middle Ground.
- • Causal consistency, the strongest model compatible with staying available under partition. See Causal Consistency: Never Show an Effect Before Its Cause.
- • Bounded staleness, where a replica refuses to answer if it is more than X behind — much cheaper and adequate for many "must be fresh" requirements.
- • Restructure the operation to be commutative so ordering stops mattering. See CRDTs: Deterministic Merge, Not Correct Merge and Coordination Avoidance: Restructuring the Problem Instead of Paying for It.
- • Strict serializability if the requirement actually spans multiple objects — linearizability alone will not deliver it. See Serializability vs Linearizability: Two Different Properties.
Is there a legal placement of effect points?
Linearizable: placing each operation's effect point at the times shown yields the sequential history C2:read→0 C1:write(1) C3:read→1 , which is legal for a register and respects every real-time ordering in the history.
What people believe, and what is true
Linearizability means reads always return the latest value.
A read concurrent with a write may legally return either value. The constraint applies to operations that do not overlap in real time.
Reading from the leader is linearizable.
Only if the leader confirms it is still leader, or holds a valid lease. A partitioned-away leader is the canonical source of non-linearizable reads and reports no error while doing it.
Linearizability gives us atomic multi-key operations.
It is a single-object property. Two individually linearizable keys give you nothing about an operation touching both — that requires transactions.
Linearizability is the same as serializability.
Different properties on different axes. One is about real-time order of single operations; the other is about transactions being equivalent to some serial order. See Serializability vs Linearizability: Two Different Properties.
Go deeper
Only the levels this lesson can honestly fill — a missing level is a claim nobody had.
Overview
The system behaves as if there were one copy and every operation happened at a single instant inside its own duration, in real-time order.
Practical
Use it where an invariant must never be momentarily violated: locks, uniqueness, compare-and-set. Make sure your reads actually get it — leader reads need leadership confirmation or a lease, quorum reads need synchronous repair — and expect the minority side of a partition to become unavailable, because that is the guarantee working.
Advanced
Linearizability is a *local* property in Herlihy and Wing's sense: a system is linearizable if and only if each object is, which is what makes it composable and what makes it useless for cross-object invariants. It is also the model that makes a concurrent object indistinguishable from a sequential one, which is why it is the correctness condition for concurrent data structures generally, not just distributed ones. That is the connection to the single-machine memory model — see concLinks memory-model and atomics-are-not-magic.
Internals
Checking linearizability of a recorded history is NP-complete in general, because the search is over placements of effect points. Practical checkers (Knossos, Porcupine, Jepsen's tooling) exploit the fact that real histories are mostly sequential, pruning with a "linearize the earliest completable operation" search plus memoisation of visited states. This matters operationally: you cannot check linearizability at runtime, only offline over recorded histories, which is why fault injection with history recording is the standard verification path. See Fault Injection: The Catalogue, and Which Faults Are Hard and Distributed Debugging: The Question Ladder.
Apply it
- 🔧 Given a history where a write is invoked at t=0 and never responds (the client crashed), determine whether the remaining reads can still be linearized, and explain why a pending operation is treated differently from a completed one.
- 💬 Draw a history with one write and two reads that is not linearizable, and prove no effect-point placement works.
- 💬 Is a read served by the leader linearizable? Under exactly what condition?
- 💬 Your key-value store is linearizable per key. A colleague wants to use it to atomically move an item between two lists. What do you tell them?