Linearizability

Linearizability is one of the strongest Consistency Models used in Concurrent Programming and Distributed Systems. It was first introduced by Maurice Herlihy and Jeannette Wing in their seminal 1990 paper. The model provides a guarantee that operations on a shared object appear to take effect instantaneously at some point between their invocation and their response. This creates the illusion that the system consists of a single copy of the data, even if it is physically distributed across multiple nodes.

A key characteristic of Linearizability is that it is a local property: if every object in a system is individually linearizable, then the entire system is linearizable. This distinguishes it from other models like Sequential Consistency, which is not local. Furthermore, Linearizability respects the real-time ordering of operations. If an operation A finishes before operation B starts, A must appear to occur before B in the linearized history. This property is crucial for building predictable Distributed Algorithms.

In the context of the CAP Theorem, Linearizability corresponds to the 'C' or Consistency component. Achieving this level of consistency in a distributed environment often requires the implementation of Consensus Algorithms such as Paxos or Raft. Many modern databases and coordination services, such as Etcd and Apache ZooKeeper, offer linearizable operations to ensure data integrity. For a deeper technical dive, refer to the original Herlihy and Wing research or the consistency model analysis provided by Jepsen.

• Strict Serializability
• Eventual Consistency
• Atomic Operations
• Distributed Shared Memory