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
Quorum overlap makes a read meet the latest write; linearizability asks for more. 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. The write finished before the read started, so the write must come first and the read must return 1. Place the write instant before the read instant and every answer makes sense. That order 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's private order. The guarantee is a promise about what clients can observe. Scope: 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.
Start with the call and return times. Then place one instant inside each window.
Each operation takes effect once inside its window, and the history must read as one real-time order.
Lesson, quiz and flashcard text written for this dataset and revised in the P25 source pass.
2 · Watch
به انگلیسیTake it off screen
Where it sits
Learn first
Optional connections
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.