Strict linearizability
Strict linearizability adds a crash deadline to linearizability: an interrupted operation takes effect before its caller crashes or has no effect.
In the original model, a crashed process stops permanently and shared objects do not fail. Successful calls still respect their invocation-response intervals; the extra boundary concerns calls interrupted by a crash. [1]
A strict completion can insert a pending call's response before the crash or discard that call, while preserving the resulting real-time order. This rules out a previously ineffective write first becoming effective after its caller's crash. [2]
Durable linearizability uses full-system crashes and new abstract threads in later eras. It preserves completed calls but can allow a pending call to take effect in a later era. The crash deadline is therefore an additional restriction, not another name for durability. [3]
The condition constrains the abstract operation history, not every recovery instruction. It does not supply the caller with a lost return value or a method for deciding which interrupted call took effect. [1] [2]
A history-level deadline is not a timestamp for implementation writes. The persistent-set literature distinguishes apparent limited effect from strict limited effect (SLE), which additionally constrains a set operation's key write relative to a crash. SLE is a separate set-specific condition, not a synonym. [5]
Relations
Limitations
Citations
- Aguilera and Frolund. Strict Linearizability and the Power of Aborting. HPL-2003-241 (2003), sections 1-3.6.
- Berryhill, Golab and Tripunitara. Robust Shared Objects for Non-Volatile Main Memory. OPODIS 2015, section 4, Definition 2.
- Izraelevitz, Mendes and Scott. Linearizability of Persistent Memory Objects Under a Full-System-Crash Failure Model. DISC 2016, sections 1-2 and 3.3.
- Coccimiglio, Brown and Ravi. The Fence Complexity of Persistent Sets (2023), expanded manuscript, section 5.
Further reading
Sources & caveats
- Primary-source synthesis of the crash boundary, not strict serializability or a storage-device persistence-ordering model.
- The 2003 report is the original primary text hosted on a mirror; sections 2 and 3.6 specify its failure model and formal definition.
- The linked article's two-read example is a finite constructed history, not a cluster run, hardware test or implementation correctness proof.