Linearizability
Linearizability is a correctness condition for concurrent objects. It says each operation appears to take effect instantaneously at some single point, called its linearization point, between the moment the operation is invoked and the moment it returns.
This gives concurrent code an intuitive feel. Even though operations overlap in time, you can pretend they happened one at a time in some sequence that matches the order they really occurred. If operation A finished before operation B started, then A must appear before B in that sequence.
Two properties define it:
- Real time order Non overlapping operations keep their actual time order.
- Atomic effect Each operation seems to happen at one indivisible instant, never half done.
Linearizability is a local property. If every individual object in a system is linearizable, the whole system is, which makes it a powerful building block. It is also stronger than sequential consistency because it adds the real time constraint that sequential consistency lacks.
For a queue, linearizability means that if an enqueue completes before a dequeue begins, the dequeue cannot miss that value. It is the gold standard correctness guarantee for lock free data structures, though it can cost performance compared with weaker guarantees.
Key idea
Linearizability makes each operation appear to occur atomically at one instant within its real time interval, giving concurrent objects a simple sequential story.