Linearizability

Linearizability

Illustration of a linearizable process

Linearizability is a consistency model for concurrent computing systems. It is a correctness condition for concurrent data structures that ensures that operations appear to occur instantaneously at some point between their invocation and their response. This property is crucial for reasoning about the behavior of concurrent systems and ensuring that they behave in a predictable manner.

Definition

Linearizability is defined in terms of atomic operations on shared data structures. An operation is said to be linearizable if it can be ordered in a sequence that respects the real-time ordering of operations and each operation appears to take effect instantaneously at some point between its invocation and its completion.

In a linearizable system, each operation on a shared object appears to take effect at a single, indivisible point in time, even though the operation may actually take some time to execute. This point is called the "linearization point."

Importance in Concurrent Systems

Linearizability is important in concurrent systems because it provides a simple and intuitive way to reason about the behavior of concurrent operations. It allows developers to think about operations as if they were executed in a sequential order, even though they are actually executed concurrently.

This property is particularly useful in distributed systems, where operations may be executed on different nodes and need to be coordinated to ensure consistency. Linearizability provides a strong guarantee that helps in building reliable and predictable distributed applications.

Linearizability vs. Sequential Consistency

Linearizability is often compared to sequential consistency, another consistency model for concurrent systems. While both models ensure that operations appear to occur in a specific order, linearizability is a stronger condition because it respects the real-time ordering of operations.

Sequential consistency only requires that the result of any execution is the same as if the operations of all the processes were executed in some sequential order, but it does not require that this order respects the real-time order of operations. Linearizability, on the other hand, requires that the order of operations respects the real-time order, making it a stricter and more intuitive model.

Applications

Linearizability is used in the design of concurrent data structures such as queues, stacks, and hash tables. It is also used in the implementation of distributed databases and transactional memory systems.

By ensuring that operations on these data structures are linearizable, developers can guarantee that the system behaves in a predictable and reliable manner, even in the presence of concurrent operations.

Related pages

• Consistency model
• Concurrent computing
• Distributed system
• Sequential consistency
• Atomic operation