Linearizability

Linearizability is the strongest single-object consistency model. It requires that every operation appear to take effect at some single instant between the moment it was invoked and the moment it returned, and that this instant respect real time: if one operation finishes before another begins, the second must see the first.

The practical meaning is that the system behaves as though there were one copy of the data, processing operations one at a time. A reader never sees a value that has already been superseded, and two observers never disagree about the order in which things happened. This is what most people assume a database does, which is why the guarantee is usually noticed only when it is absent.

It is also the consistency used in the formal statement of the CAP result — Gilbert and Lynch’s proof used atomic, or linearizable, consistency, as Abadi’s paper restates. That detail matters when reading CAP arguments, because weaker models are not what the theorem constrains.

The cost is coordination. Producing a single real-time order across replicas requires them to communicate before answering, which adds latency on every operation and makes the system unavailable whenever the necessary replicas cannot be reached. That is the trade-off that PACELC describes as present all the time, not only during a partition.

Two distinctions prevent common confusion. Linearizability is about single objects; serializability is about transactions over multiple objects, and neither implies the other. And it is a property of the observable history, which means it can be tested by examining operation traces rather than by inspecting the implementation — the approach Jepsen takes.

Where the weaker models sit relative to this one, and when the coordination is worth paying for, is worked through in Replication, Consistency, and Time.