Skip to content

Linearizable Read/Write Protocol

Read/write protocol — instantiates Shared-State Consistency Contract Design

Guarantees every read returns the most recent completed write, as if all operations ran one at a time on a single copy in real-time order.

Linearizable Read/Write Protocol pins the contract to the strongest single-object guarantee there is: every operation appears to take effect atomically at a single instant between its call and its return, and those instants form one total order consistent with real time. The practical promise is recency — once a write completes, every later read anywhere sees it or something newer; no read ever travels backward. What makes it this mechanism and not a weaker sibling is the real-time constraint: it orders reads, not just writes, so there is simply no legal execution in which a stale value is returned after a fresh one has been acknowledged. That promise is expensive, and the protocol pays for it by routing operations through a single agreed order (a consensus log or a leader with valid leases) rather than letting replicas answer independently.

Example

A cluster's control plane stores one fact that must never be wrong: who is the current primary. After a failover, every node reads that register to decide whether to accept writes. Under an eventually-consistent register, a lagging node could still read the old primary and a second node could also believe it is primary — split brain, double writes, corruption. A linearizable register forecloses this. The new primary's identity is committed through the coordination group; a read is served only after it is confirmed to reflect the latest committed entry (a leader read under lease, or a quorum read with a read-index barrier). A node that reads after the failover completes is guaranteed to see the new primary — never the stale one — so two nodes can never simultaneously believe they hold the role.

The cost shows up the moment the network splits: a minority-side node cannot get a fresh confirmation, so it must block or error rather than answer from a possibly-stale local copy. That refusal is the guarantee working as designed.

How it works

The distinguishing move is that reads are ordered, not merely writes. Every write is placed into a single total order (via consensus or a single leader), and every read is forced to observe the latest committed point in that order — by reading from the leader while its lease is provably valid, or by confirming with a quorum that no newer write has committed before returning. Weaker protocols let any replica answer a read locally; linearizability refuses, because a local answer cannot prove it is current. The whole design is the machinery that makes "current" provable at read time.

Tuning parameters

  • Read path — leader-lease read, quorum read-index, or full read-quorum. Leases give fast reads but lean on a clock-skew bound; quorum reads are slower but assumption-light.
  • Commit quorum / group size — larger groups tolerate more failures but raise write latency; this dial trades durability against speed.
  • Clock-bound assumption — how tightly you trust bounded skew (a TrueTime-style bound enables fast leased reads; distrusting clocks forces coordination on every read).
  • Object granularity — linearizability is per-object; deciding what counts as one linearizable unit trades reasoning simplicity against coordination scope.
  • Fencing on handover — whether stale leaders are fenced out (tokens) so a paused old leader cannot answer after its lease lapses.

When it helps, and when it misleads

Its strength is that it eliminates a whole class of anomalies for the object it covers: no staleness, no reordering, and semantics simple enough to reason about locally. For correctness-critical single facts — locks, leader election, unique allocation, a fencing counter — it is the right and often the only safe choice.

Its cost is exactly its guarantee: under a network partition it cannot be both available and linearizable, so the minority side must stop serving.[1] The classic misuse is reflexive over-coordination — teams ask for "strong consistency" for data where a session guarantee or bounded staleness would do, paying latency and availability for recency nobody needs. A subtler trap: linearizability is a single-object property and does not by itself give multi-object transactional isolation, so it is often confused with serializability. The discipline is to name the actual invariant first, and spend linearizability only where real-time recency of one object is genuinely required.

How it implements the components

  • consistency_guarantee_profile — declares the strongest point on the profile (linearizable / single-copy), the reference against which weaker siblings are defined.
  • operation_semantics_contract — fixes what success means: a completed write is immediately visible to every later read, and a read returns the latest completed write — no weaker outcome is legal.

It does not produce the concrete order-tracking artifact (visibility_and_order_relation) — that is Version Vector — nor tune the coordination/latency budget (coordination_latency_and_availability_budget), which is Quorum Read/Write Protocol; multi-object isolation belongs to Transaction Isolation.

Notes

Linearizability is not serializability: it constrains the order of single-object operations in real time, while serializability constrains the interleaving of multi-object transactions. A store can be linearizable per key yet allow transactional anomalies across keys. The two do compose in a useful way, though — unlike sequential consistency, linearizable objects remain linearizable when combined, which is what makes it a safe building block for higher-level protocols.

References

[1] CAP theorem — during a network partition a replicated system cannot be simultaneously available and linearizable (consistent); Gilbert & Lynch formalized Brewer's conjecture. This is why the minority side of a partition must block rather than return a possibly-stale read. ↩