Linearizability, also called atomic consistency, makes a replicated distributed system behave like a single, nonreplicated system. Once an operation completes, every later operation observes its effect. section 9.2
The mental model is a sequential history of operations on one object. A concurrent execution is linearizable when its results match some sequential history, while preserving the real-time order of operations that did not overlap. The guarantee is defined per object type, so the permitted ordering follows that object’s semantics. section 9.2.2 section 9.2
Queue, stack, and stale replica
For a queue, inserting a and then b must make successive removals return a and then b; a stack must return b and then a. Across multiple replicas, if process B increments a counter and process A subsequently reads it, A must see the increment rather than a stale replica value. section 9.2.1 section 9.2.2
Linearizability distinguishes two related claims:
- A linearizable history has an equivalent sequential ordering that preserves nonconcurrent real-time order. section 9.2.2
- A linearizable system guarantees that every possible history satisfies those conditions. section 9.2.2
- The strong recency guarantee improves reasoning about applications but can reduce availability and increase latency, especially during network partitions. section 9.5 section 9.4.2
Table 9.1 Valid and invalid traces of a queue
| Valid |
Invalid |
|
|
|
Compare valid and invalid queue traces to see how linearizability preserves object-specific sequential semantics. section 9.2.1
