Linearizability

The most critical property. If operation A completes before operation B begins in real time, then A must appear to have taken effect before B in the system's linearizable history. This preserves the causal order observed by clients.

• Example: If a write of value X=5 finishes at time t1, and a subsequent read starting at t2 (where t2 > t1) reads X, it must see 5 or a later value, never the previous value.
• This property is stricter than causal consistency, which only preserves causally related orders.

Each operation is atomic and appears to occur at a single, instantaneous point on a global timeline. This point lies somewhere between the operation's invocation and response events.

• This creates a total order of all operations across the entire system.
• It is the defining characteristic that differentiates linearizability from weaker models like sequential consistency, which only requires a total order per process.
• In a multi-agent system, this guarantees that all agents observe a consistent, interleaved sequence of actions.

Linearizability provides external consistency or strict serializability. The system's observable behavior is equivalent to a single-copy system where operations are executed one at a time, in an order consistent with real-time.

• This is the strongest consistency guarantee commonly used in practice, stronger than serializability alone.
• It simplifies reasoning for developers because the system behaves as if there is only one, non-replicated server.
• It is a safety property, ensuring nothing incorrect happens, as opposed to a liveness property.

A system is linearizable if and only if each individual object within the system is linearizable. This locality property is powerful for system design.

• It allows engineers to reason about and verify consistency on a per-object basis.
• A system can mix linearizable and non-linearizable objects.
• This property does not hold for other models like sequential consistency, where the consistency of the whole system does not guarantee the consistency of its parts.

A linearizable system must allow progress for operations that are not contending for the same resource. A slow or failed replica should not indefinitely block operations on unrelated data.

• This is a key distinction from transactional models like strict two-phase locking (2PL), which can lead to cascading aborts or deadlocks.
• However, concurrent operations on the same object are ordered, and one may have to wait for the other to establish its linearization point.
• This property is related to wait-freedom and lock-freedom in concurrent algorithm design.

Under the CAP theorem, linearizability is a Consistency (C) guarantee. In the presence of a network partition, a linearizable system must choose between:

• Maintaining Linearizability (C): Sacrificing Availability (A) by returning an error for requests that cannot be guaranteed to be consistent.
• Maintaining Availability (A): Sacrificing linearizability, potentially falling back to a weaker model like eventual consistency.
• This makes linearizable systems CP systems (Consistent and Partition-tolerant). Implementing them at scale requires sophisticated coordination protocols like Paxos or Raft.

A family of consistency models where any read operation on a data item returns a value corresponding to the result of the most recent write operation, as perceived by all nodes in the system. Linearizability and Sequential Consistency are the two most prominent strong models.

• Linearizability adds a real-time constraint, requiring operations to appear instantaneous at a point between their invocation and response.
• Sequential Consistency only requires that all processes see operations in some sequential order that respects each process's program order, but not necessarily real-time order.

A strong consistency model where the result of any execution is the same as if the operations of all processes were executed in some sequential order, and the operations of each individual process appear in this sequence in the order specified by its program. Unlike Linearizability, it does not preserve the real-time ordering of operations across different processes. This is a fundamental model for reasoning about parallel and distributed program correctness.

A weaker consistency model that guarantees causally related operations are seen by all processes in the same order, while allowing concurrent (non-causally related) operations to be seen in different orders. It is stronger than Eventual Consistency but weaker than Sequential Consistency. It is defined by the happens-before relationship and is often implemented using mechanisms like Vector Clocks to track causal dependencies.

A weak consistency model that guarantees if no new updates are made to a given data item, all accesses will eventually return the last updated value. It provides high availability and partition tolerance at the cost of temporary inconsistency. It is the base guarantee for many globally distributed databases (e.g., DNS, Apache Cassandra). This model sits at the opposite end of the spectrum from Linearizability, as formalized by the CAP Theorem.

A communication primitive, also known as Total Order Broadcast, that guarantees all correct processes in a distributed system deliver the same set of messages in the same total order. It is a fundamental building block for implementing Linearizability and State Machine Replication. Protocols like Paxos and Raft provide implementations of atomic broadcast, ensuring all replicas process commands identically to maintain a linearizable state.

A fundamental technique for implementing a fault-tolerant service by replicating a deterministic state machine across multiple nodes. Linearizability is achieved by ensuring all replicas start from the same state and process the same sequence of client commands in the same total order, typically via Atomic Broadcast. This is the core mechanism behind systems like etcd and Consul, providing strongly consistent, fault-tolerant coordination.