Linearizability and weaker consistency contracts

Prerequisites: Concurrent operations, invocation and response events, and partial orders.

Learning objectives

• Find or reject a legal linearization of a history.
• Distinguish linearizability from sequential and eventual consistency.
• Explain why per-object guarantees do not create multi-object transactions.

A consistency model specifies which observations concurrent clients may make. Linearizability asks whether every completed operation can be placed at one instant between its invocation and response so that the resulting total order obeys the object's sequential specification. If one operation finishes before another starts, that real-time order must be preserved. Overlapping operations can be ordered either way when their results permit it.

Consider a register initially 0. Client A writes 1 and receives success. Only afterward, client B begins a read and receives 0. This history is not linearizable: the completed write must precede the later read, so the read should return 1 if no intervening write exists. Now change the trace so B's read overlaps A's write. A result of 0 can be legal if the read is placed before the write; a result of 1 can be legal if placed after it. The precise intervals matter.

The sequential specification also matters. For a counter with atomic increment returning the new value, two overlapping increments from 0 must return 1 and 2 in some order. Both returning 1 cannot be explained by any legal serial execution. A system with individually linearizable read and write operations can still lose an update when clients implement increment as separate read-then-write calls. Atomicity belongs to the operation actually provided.

Sequential consistency requires a total order preserving each client's program order but does not impose all cross-client real-time constraints. Eventual consistency describes convergence under conditions such as no further updates and eventual delivery, but by itself gives little detail about intermediate reads or conflict resolution. Read-your-writes and monotonic reads are session guarantees that constrain particular observations without necessarily providing global linearizability.

Linearizability is compositional for independently specified objects: verifying each object's linearizable behavior supports reasoning about their composition at the operation level. It does not transform a sequence of operations on several objects into one atomic transaction. A transfer that separately debits A and credits B can expose an intermediate total even if each register operation is linearizable. Transactional atomicity and serializability address a different grouping.

Network partitions expose availability tradeoffs. If a read must reflect a completed write that its replica cannot learn about, immediately returning an arbitrary local value may violate linearizability. A protocol may need to wait, reject, or route the operation elsewhere. A timeout is an observation about waiting, not proof that the operation never took effect.

To test a claimed contract, record invocation times, response times, arguments, and results, including failures and ambiguous outcomes. Search for a legal sequential explanation under that contract. A history checker can find counterexamples, while passing a finite test cannot prove all executions correct. State the object semantics before interpreting the trace.

Practice problem

A register starts at 0. Write(7) runs from time 1 to 4. Read R runs from 2 to 3 and returns 0. Read S runs from 5 to 6 and returns 0. Analyze each read for linearizability and explain whether removing S makes the history legal. Then two clients implement increment as Read followed by Write(value+1), both read 0 and write 1. Explain why this does not disprove linearizability of the individual register operations.

Worked solution

R overlaps Write(7), so it can linearize before the write and legally return 0. S begins after the write completed, so it must follow that write and should return 7; returning 0 violates the register contract. Without S, place R before the write to obtain a legal history. In the increment example, a valid register order is Read 0, Read 0, Write 1, Write 1. Each read and write can be linearizable while the compound client operation loses one increment. Preventing that lost update requires an atomic increment, a compare-and-swap retry loop with suitable semantics, or a transaction that protects the whole read-modify-write sequence.

Check your understanding

Write(7) runs during times 1–4. Read R runs 2–3 and returns 0. Read S runs 5–6 and returns 0. The register began at 0. Which observation violates linearizability?

• R only.
• Neither, because replicas may always return old values.
• Both R and S.
• S only.

Explanation

R overlaps the write and can linearize before it. S begins after the write completed and must see 7 absent another write.

Two clients each read 0 from a linearizable register, then each writes 1. Which claim is justified?

• The register is necessarily not linearizable.
• Linearizability guarantees the final value 2.
• The sequence can be legal while the compound client increments lose an update.
• Synchronizing physical clocks would automatically make the increments atomic.

Explanation

Read 0, Read 0, Write 1, Write 1 is a valid register order. Atomic increment requires a stronger compound operation or protocol.

Primary reading

• Linearizability: A Correctness Condition for Concurrent Objects: Maurice Herlihy and Jeannette Wing

Open the study and save your work →