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.
Related¶
- Instantiates: Shared-State Consistency Contract Design — occupies the strong end of the contract's guarantee spectrum.
- Consumes: Leader-Based Replication or a consensus group to realize the single total order.
- Sibling mechanisms: Quorum Read/Write Protocol · Sequential-Consistency Trace Protocol · Causal-Consistency Protocol · Bounded-Staleness Read Policy · Leader-Based Replication · Lease and Fencing-Token Protocol
Editorial Notes¶
Form Classification¶
Form family: Control, Automation & Runtime
Rationale: The executable protocol orders live reads and writes so every read reflects the latest completed write in real-time order.
Nearest alternative: Protocol, Workflow & Routine — Operations exchange messages by protocol, but runtime consistency enforcement is the operative mechanism.
Review outcome: Adjudicated after independent review; high confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Single lineage
Present-day reach: Specialized
Rationale: Linearizability was formalized in distributed computing as a real-time consistency condition for concurrent objects and shared storage.
Review outcome: Independent reviewer agreement; high confidence.
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] Seth Gilbert and Nancy Lynch. "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services". SIGACT News 33(2), 51–59 (2002). Under a network partition, an atomic or linearizable service cannot also guarantee a response to every request. registry ↩ Show verification details
Supported in partVerified against the publisher's abstract
The abstract proves consistency, availability and partition tolerance cannot all hold, supporting the core impossibility but not the operational step that the minority side stops serving.
“It is impossible to achieve all three.”