strict-linearizability · research · also Strictly linearizable

Strict linearizability

Strict linearizability adds a crash deadline to linearizability: an interrupted operation takes effect before its caller crashes or has no effect.

Related Observatory article: Read on hesela.com

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

related
Linearizability, Durable linearizability, Detectability, Crash consistency

Limitations

  • A safety property does not establish wait-freedom or a time limit for recovery. [1, 3]

Citations

  1. Aguilera and Frolund. Strict Linearizability and the Power of Aborting. HPL-2003-241 (2003), sections 1-3.6. (accessed 2026-11-20)
  2. Berryhill, Golab and Tripunitara. Robust Shared Objects for Non-Volatile Main Memory. OPODIS 2015, section 4, Definition 2. (accessed 2026-11-20)
  3. Izraelevitz, Mendes and Scott. Linearizability of Persistent Memory Objects Under a Full-System-Crash Failure Model. DISC 2016, sections 1-2 and 3.3. (accessed 2026-11-20)
  4. Coccimiglio, Brown and Ravi. The Fence Complexity of Persistent Sets (2023), expanded manuscript, section 5. (accessed 2026-11-20)

Further reading

  1. Hesela. Persistent memory: DAX is not a durable commit. (accessed 2026-11-20)
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.

JSON: /data/terms/strict-linearizability.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Strict linearizability. Hesela. 2026-11-20. https://hesela.dev/terms/strict-linearizability/