Linearizability

Herlihy, M. P., & Wing, J. M. (1990). Linearizability: A Correctness Condition for Concurrent Objects. ACM Transactions on Programming Languages and Systems, 12(3), 463-492.

Type

Journal article

Intellectual base

Primary research

Year

1990

DOI

10.1145/78969.78972

Link

https://doi.org/10.1145/78969.78972

Cited from

computer_science

Cited by

4 citations across 4 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Concurrency
  • Interleaving-safe invariants and atomicity boundaries
• Consistency Model
  • It does not say what the state is; it says which interleavings of reads and writes count as legal observations, and therefore what observers may assume about one another's view.

    This sourceDefines linearizability as the strongest single-object consistency condition requiring a real-time-consistent total order.

• Fault Tolerance
  • Listed in the references but not attached to a specific claim.
• Transaction
  • Failure mode: exactly-once is assumed without ensuring idempotence or deduplication, leading to duplicate charges, double-bookings, and lost retries

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:9f6f519c74eb · see in the full table