Linearizability and Checking a History
Linearizability says every operation appears to take effect at one instant between its call and its return, so a replicated store can be reasoned about as a single object. Whether a recorded history satisfies it is a decidable question, and the check is expensive.
What a learner can do afterwards
- Decide whether a short recorded history is linearizable and give the ordering or the conflict
- Say how linearizability differs from serializability and from a weaker consistency model
- Explain why the client-observed history, not the server's internal order, is what gets checked
1 · Read
Every operation has a call, when you invoke it, and a return, when you get the answer. Linearizability says each operation appears to take effect at one single instant between its call and its return. The whole history then reads as if the operations ran one after another on a single object.
A write of x = 1 starts and finishes. Then a read of x starts and returns 1. Place the write instant before the read instant and every answer makes sense. That order, write then read, is the single-object explanation.
To check a history, slide each instant inside its own call to return window until every read returns the latest write placed before it. Real-time order is law: an operation that finished before another started must come first, while overlapping operations may sit in either order. If no placement explains some read, that read is the conflict.
Judge only what clients saw: call and return times, never the server private order. Note the scope too: linearizability covers one object and honors real-time order. Serializability covers many objects inside transactions but ignores real-time gaps, while weaker models allow stale reads.
Each operation takes effect once inside its window, and the history must read as one real-time order.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.