linearizable

Linearizable is an adjective used to describe a concurrent object whose behavior satisfies the linearizability correctness condition. Linearizability requires that every operation on the object appears to take effect instantaneous at some point between its invocation and its response, and that the order of non-overlapping operations respects real time. In practice this means the system behaves as if there is a single, global order of operations that is consistent with the observed results.

Formally, an execution history is linearizable if there exists a sequential history of all operations that is valid for the object and preserves the real-time order of non-overlapping invocations. A linearizable history thus yields a legal sequential history that agrees with the actual timing of non-overlapping operations.

Linearizability implies sequential consistency; every linearizable history is sequentially consistent, but not every sequentially consistent history is linearizable. It is stronger than many other common models and, for multiple objects, is not the same as serializability, which concerns transactional guarantees rather than per-operation real-time ordering.

In practice, linearizability is achieved by identifying a linearization point for each operation and by designing algorithms (often lock-free or wait-free) that ensure those points exist in every execution. It is widely used in designing and reasoning about concurrent data structures such as stacks, queues, and maps, and in distributed systems where predictable, real-time-consistent behavior is required.

The concept was introduced by Herlihy and Wing in 1990 as a formal correctness condition for concurrent objects.