Linearizability

Linearizability is a correctness condition for concurrent objects in distributed systems. It requires that each operation appears to take effect instantaneously at some point between its invocation and its response, and that the order of non-overlapping operations reflects real time.

Introduced by Maurice Herlihy and Jeannette Wing in 1990, linearizability is defined in terms of histories of method calls. A history is linearizable if there exists a legal sequential history with the same set of operations, in which every operation's linearization point lies between its invocation and response and non-overlapping operations respect real-time order.

Linearizability is stronger than sequential consistency, which only requires that the result be consistent with some sequential order but not that real-time order is preserved. As a safety property, linearizability is composable: if each object in a system is linearizable, the system as a whole is linearizable.

In practice, the linearization point may be at the invocation, the response, or somewhere in between, and may depend on implementation details. Proving linearizability often requires reasoning about concurrent executions and may involve modeling with abstract histories or linearization points.

Common linearizable data structures include atomic queues, stacks, and counters implemented with synchronization primitives such as compare-and-swap. Linearizability is a key criterion for correctness in databases and concurrent libraries, but it does not by itself guarantee progress or fault tolerance.

In distributed environments with failures or clock skew, achieving linearizability requires careful design, and developers may use techniques such as consensus protocols, versioned data, or bounded delays. Linearizability is distinct from casual consistency or eventual consistency.