What Linearizability Actually Guarantees
Linearizability is a consistency model that applies to a single object — in distributed systems literature, that object is usually called a register, a single key-value pair. The defining property, from the original paper, is that each operation appears to take effect instantaneously at some point between its invocation and its response. Practically, this means a linearizable system behaves as if there were only one copy of the data and every operation applied to it atomically.
This is not the same as saying all operations are ordered globally ahead of time. Concurrent operations may interleave in any way, but the system must produce results that are consistent with some sequential order. That order must respect the real-time precedence of operations: if operation A completes before operation B starts, B cannot appear before A in the sequential history.
Valid and Invalid Histories
Consider three clients reading and writing a register that starts at 0. Client A reads 0; client B reads 0 while client C writes 1; client A then reads 1; client B reads 1. This sequence is linearizable because each read can be assigned a point between its start and completion where the write it observed actually happened. The reads of 0 occurred before the write took effect; the reads of 1 occurred after.
Now modify the last step: client B reads 0 instead of 1, even though client A already read 1 earlier and that read completed before B's read began. Since A's read of 1 means the write of 1 must have already occurred, B's later read of 0 contradicts the required ordering. A weaker system might produce such a history, but a linearizable one cannot. There is no way to arrange the operations into a sequence where the write of 1 happens before A's read and also after B's read.
A Subtler Violation
Some non-linearizable histories are harder to spot. Consider a case where client A reads 0, client B writes 1, client A writes 0, and then client B reads 1. Looks plausible at first glance, but the ordering constraints conflict.
Client A's read of 0 tells us that A's read happened before B's write of 1 — if it had happened after, A would have read 1. Since A's second operation (the write of 0) starts after A's first read ends, that write also happens after B's write. Therefore, after A writes 0, the register logically holds 0. B's later read of 1 is then impossible to reconcile with any sequential ordering of these events. Even though the two writes are concurrent, the read results impose an order between them, and that order makes the final read invalid.
The Formal Definition
A formal statement of linearizability helps clarify these examples. Give each operation e a start time start(e) and an end time end(e). A history H is a set of operations with a strong partial order based on real time: operation e precedes operation f if end(e) occurs before start(f). Operations not related by this order are concurrent.
In the diagrams above, H is the observed history — the overlapping rectangles. A sequential history is one where the order is a total order, meaning no operations are concurrent.
H is linearizable if it is equivalent to some sequential history S, and the partial order defined by H is a subset of the total order defined by S. In other words, the real-time precedence of operations must be preserved in the sequential history. S is the linearization of H — the bottom timeline in the diagrams, where each operation is applied atomically at an instant.
Linearizability vs. Serializability
The two models are frequently conflated, but they address different concerns:
- Serializability is a multi-object property for transactions. It guarantees that a set of operations spanning multiple objects executes as if they were a single atomic transaction — no partial effects, no intermixing of sub-operations.
- Linearizability is a single-object property. It concerns the observed order of operations on one register, as demonstrated throughout this article.
For a broader taxonomy of consistency models, the Jepsen project maintains a useful reference, and Kyle Kingsbury's work on linearizability checking — including the Knossos checker and analyses of real systems such as etcd — provides practical grounding for these theoretical concepts.
