Linearizability
Summary: A strong consistency model that provides a recency guarantee, making a multi-node system appear as if there were only a single copy of the data.
Sources: chapter9
Last updated: 2026-04-17
Linearizability (also known as atomic consistency, strong consistency, or external consistency) is one of the strongest consistency models in distributed systems (source: chapter9, p. 324). Its goal is to make a system appear as if there is only a single copy of the data, and all operations on it are atomic (source: chapter9, p. 324).
The Recency Guarantee
In a linearizable system, once any client successfully completes a write, all subsequent reads (from any client) must return the new value (source: chapter9, p. 324). It is essentially a “recency guarantee.”
Linearizability vs. Serializability
It is important to distinguish linearizability from serializability:
- Serializability: An isolation property of transactions that ensures they behave as if they had executed in some sequential order. It doesn’t guarantee which order (source: chapter9, p. 329).
- Linearizability: A recency guarantee on reads and writes of an individual object. It ensures that the system behaves as if there were only one copy of the data (source: chapter9, p. 329).
A system that provides both is said to have strict serializability or strong one-copy serializability (source: chapter9, p. 329).
Use Cases
- Locking and Leader Election: In single-leader replication, nodes must agree on who the leader is. This lock must be linearizable to avoid split-brain (source: chapter9, p. 330).
- Uniqueness Constraints: Ensuring a username or email is unique requires a linearizable operation (like compare-and-set) (source: chapter9, p. 330).
- Cross-Channel Timing Dependencies: If a system has multiple communication channels (e.g., a database and a message queue), non-linearizability can lead to race conditions (source: chapter9, p. 331).
Implementation
- Single-leader replication: Potentially linearizable if reads are also sent to the leader or synchronously updated followers (source: chapter9, p. 333).
- Consensus algorithms: Linearizable by design (e.g., ZooKeeper, etcd) (source: chapter9, p. 333).
- Multi-leader replication: Generally not linearizable (source: chapter9, p. 333).
- Leaderless replication: Usually not linearizable, even with strict quorum (), because of variable network delays and clock skew (source: chapter9, p. 334).
The Cost
Linearizability is slow and can impact availability. According to the cap-theorem, if you require linearizability and a network partition occurs, some nodes must become unavailable (source: chapter9, p. 336).