Linearizability

Linearizability is the strongest single-object consistency model: it requires that every operation on a shared object appear to take effect instantaneously at some single point — its linearization point — that falls between the operation’s invocation and its response, and that this apparent instantaneous order be consistent with the real-time order of non-overlapping operations. It was defined precisely by Maurice Herlihy and Jeannette Wing in “Linearizability: A Correctness Condition for Concurrent Objects” (ACM Transactions on Programming Languages and Systems, Vol. 12, No. 3, July 1990, pp. 463–492) as a generalization of Lamport’s earlier notions of atomic registers to arbitrary abstract data types (Herlihy & Wing 1990). Its defining sentence: linearizability “provides the illusion that each operation applied by concurrent processes takes effect instantaneously at some point between its invocation and its response.” Two properties make it the model of choice for coordination systems: it is local (composable) — a system is linearizable if and only if each of its objects is — and it is nonblocking — a pending invocation of a total operation is never forced to wait. This note develops the formal history model, the exact L1/L2 conditions, the locality and nonblocking theorems, and the razor-sharp distinction from Sequential Consistency (which drops the real-time requirement) and from Serializability (which is a multi-object transaction property).

Mental Model — the “single point in time” illusion

The intuition every practitioner should carry: a linearizable object behaves exactly as if it lived on a single machine, protected by a single global lock, servicing one operation at a time. Concurrency is an illusion the object maintains — internally it may replicate, pipeline, and batch, but externally each operation looks atomic and appears to happen at one indivisible instant somewhere inside the wall-clock window during which the caller was waiting for a response.

sequenceDiagram
    participant A as Process A
    participant O as Object (register x, init 0)
    participant B as Process B
    A->>O: invoke write(x,1)
    Note over O: linearization point ●<br/>(x becomes 1 here)
    O-->>A: ok
    B->>O: invoke read(x)
    O-->>B: returns 1
    Note over A,B: write(1) finished in real time<br/>BEFORE read began, so read MUST see 1

What it shows and the insight to take: each operation occupies a real-time interval (invocation to response), but linearizability collapses it to a point (●) inside that interval. The order of those points must (a) be a legal sequential execution of the object’s specification, and (b) respect real time — if A’s write completes before B’s read even starts, the write’s point precedes the read’s point, so B is guaranteed to observe the write. The whole content of linearizability is that second clause: real-time order between non-overlapping operations is preserved. Drop it and you have the weaker Sequential Consistency.

The formal model — histories, invocations, responses

Herlihy and Wing model an execution as a history H: “a finite sequence of operation invocation and response events” (Herlihy & Wing 1990, §2.1). Each invocation is written ⟨x op(args) A⟩ — object x, operation op, arguments, process A — and each response ⟨x term(res) A⟩, where term is a termination condition (Ok for normal return). A response matches an invocation when their object and process names agree. An invocation with no following matching response is pending.

Several derived notions do the work:

• complete(H) — the maximal subsequence of H consisting only of invocations and their matching responses. Pending invocations are dropped; they may or may not have “happened.”
• Process subhistory H|P — the subsequence of events with process name P. Because a real process issues one operation, waits for its response, then issues the next, every H|P is sequential. A history in which every process subhistory is sequential is well-formed; all histories considered are well-formed.
• Object subhistory H|x — the events touching object x. These are generally not sequential (multiple processes hit one object concurrently).
• Sequential history — one where the first event is an invocation and every invocation is immediately followed by its matching response. A sequential history is legal if each object subhistory obeys that object’s sequential specification (the ordinary single-threaded semantics — e.g. a FIFO queue dequeues items in enqueue order).
• Equivalence — histories H and H' are equivalent when H|P = H'|P for every process P. Equivalence means “every process saw the same thing,” regardless of how operations across processes interleaved.

The real-time order <_H

The crux. A history H “induces an irreflexive partial order <_H on operations” (Herlihy & Wing 1990, §2.2):

e₀ <_H e₁ if res(e₀) precedes inv(e₁) in H.

In words: operation e₀ precedes e₁ in real time exactly when e₀ finished (its response appeared) before e₁ started (its invocation appeared). Operations whose intervals overlap are unrelated by <_H and are called concurrent. If H is already sequential, <_H is a total order — nothing overlaps.

This partial order is the entire distinctive content of linearizability. It is a “real-time” order because it is read off the physical clock times of invocations and responses — not from any logical happens-before (Happens-Before Relation) or program order.

The definition — L1 and L2

A history H is linearizable if it can be extended (by appending zero or more response events) to some history H' such that:

• L1: complete(H') is equivalent to some legal sequential history S, and
• L2: <_H ⊆ <_S.

S is called a linearization of H. Unpacking the two clauses (Herlihy & Wing 1990, §2.2):

• Extending H to H' captures that some pending invocations may already have taken effect even though their responses have not yet reached the caller — we are allowed to invent the responses they will eventually get. Then restricting to complete(H') throws away the pending invocations we decide never took effect.
• L1 says the operations can be arranged into a single sequential order S that is legal (obeys the object’s spec) and that each process agrees with (equivalence). This is the “everything looks atomic and one-at-a-time” clause.
• L2 says that sequential order S must contain the real-time order <_H: if e₀ really finished before e₁ started, then e₀ comes before e₁ in S too. This is the “respect real time” clause — and it is precisely what Sequential Consistency omits.

The definition is inherently nondeterministic: there may be many valid extensions H', and for each, many valid linearizations S. Linearizability only requires that at least one exists.

The linearization point is the informal name for where each operation sits in S — the single instant, somewhere in its interval, at which it “took effect.” Implementers reason in exactly these terms: to prove an algorithm linearizable, identify, for every operation, the concrete line of code (a compare-and-swap succeeding, a lock release, a log entry committing) that is its linearization point, and show those points always fall inside the operation’s interval and yield a legal order.

Worked examples — the FIFO queue histories

Herlihy and Wing’s queue examples make L1/L2 concrete. Write E(x) A for “process A enqueues x” and D(x) B for “process B dequeues x.”

Acceptable (H₁). A and B concurrently enqueue x and y; later B dequeues x, then A dequeues y. Because the two enqueues overlapped, <_H does not order them, so a linearization is free to place E(x) before E(y); then the FIFO spec makes D return x before y — legal. Linearizable. (Herlihy & Wing 1990, §2.3)

Not acceptable (H₂). A enqueues x and its response returns — the enqueue completes — and only then B enqueues y; yet a later dequeue returns y before x is ever dequeued. Here E(x) finished before E(y) started, so E(x) <_H E(y); L2 forces x ahead of y in every linearization; the FIFO spec then forces x to be dequeued first. Returning y first violates L2. Not linearizable — even though it would be sequentially consistent if the two enqueues were by the same process’s program order (they are not here; the point is that real-time order is violated).

Acceptable despite an early effect (H₃). A dequeue of x returns before x’s enqueue operation has returned. Because the enqueue is still pending, we may extend H with its response and place its linearization point before the dequeue: “the enqueue took effect before it completed.” Linearizable. This shows an operation’s linearization point can be anywhere in its interval — including before a concurrent operation that logically depends on it.

Never acceptable (H₄). y is enqueued once but dequeued twice. No legal sequential FIFO history does that, so no linearization exists under any ordering. Not linearizable — this is an object-semantics violation, independent of timing.

The lesson: L1 catches “the object did something impossible”; L2 catches “the object reordered operations that real time had already ordered.”

Locality — linearizability composes

Herlihy and Wing’s Theorem 1 is the property that makes linearizability uniquely valuable in systems built from many independent objects:

THEOREM 1. H is linearizable if and only if, for each object x, H|x is linearizable. (Herlihy & Wing 1990, §3.1)

A property that holds for a whole system whenever it holds for each object individually is called local. Linearizability is local; sequential consistency and serializability are not. The proof is a beautiful cycle-elimination argument: pick a linearization of each object’s subhistory, take < to be the transitive closure of the union of all the per-object orders <_x with the global real-time order <_H, and show < is a partial order (acyclic). The acyclicity argument works by choosing a hypothetical minimal cycle and showing that any two adjacent operations related by real-time order let you splice out a node to get a shorter cycle — a contradiction. Because < is acyclic, any total order extending it is a legal linearization of the whole system.

Why locality matters in practice: you can build, verify, and operate each linearizable object independently — a linearizable key x in one shard and a linearizable key y in another compose, with no global coordinator, into a system where operations across x and y still respect real time. As the paper puts it, “objects can be implemented and verified independently, and run-time scheduling can be completely decentralized.” This is exactly why linearizability is the contract etcd, ZooKeeper, and Spanner advertise: it lets clients reason about each key as if it were a single atomic variable, and lets independent keys be served by independent Raft or Paxos groups without breaking the guarantee.

Nonblocking — pending operations never have to wait

Theorem 2: a pending invocation of a total operation (one defined for every object state, like Enq on an unbounded queue) is never required to wait for another pending invocation to complete before it can be given a linearizable response (Herlihy & Wing 1990, §3.2). The proof: take any linearization S; because the operation is total, there is always a legal response you can append. Contrast this with serializability, which is “inherently a blocking property” — under two-phase locking a transaction may be forced to wait to preserve serializability even for a total operation. Two caveats: (1) partial operations legitimately block — Deq on an empty queue naturally waits for an Enq, and the spec models this by leaving Deq undefined on the empty queue; (2) a particular implementation may still block or deadlock — nonblocking is a property of the correctness condition, saying blocking is never forced by the definition itself.

Linearizability vs serializability — single object vs transactions

This distinction is the one most often muddled. Herlihy and Wing state it exactly: “Linearizability can be viewed as a special case of strict serializability where transactions are restricted to consist of a single operation applied to a single object” (Herlihy & Wing 1990, §3.3). Peter Bailis frames the same split from the database side (Bailis):

• Linearizability is “a guarantee about single operations on single objects.” It is a recency guarantee — once a write completes, later reads see it or something newer. It says nothing about grouping operations into transactions. It is essentially the “C” (consistency) of CAP Theorem.
• Serializability is “a guarantee about transactions, or groups of one or more operations over one or more objects” — it demands equivalence to some serial order but “does not — by itself — impose any real-time constraints.” See Serializability.
• Strict serializability = serializability + linearizability’s real-time order across whole transactions: transactions are equivalent to a serial execution and that serial order respects real time.

Property	Linearizability	Serializability	Strict serializability
Scope	single object, single op	multi-object transactions	multi-object transactions
Real-time order?	yes	no	yes
Composable (local)?	yes	no	no
Blocking?	nonblocking	inherently blocking	blocking

The crucial asymmetry: serializability is not local. Herlihy and Wing’s history H₈ has two queues p and q on which both processes operate; each object subhistory is (strictly) serializable, yet the combined history is not even serializable — the cross-object dependencies form a cycle invisible when you look at one object at a time. That is why serializable databases need global concurrency-control conventions (you cannot mix two-phase locking on one table with multiversion timestamping on another and expect global serializability), whereas linearizable objects just compose.

Where linearizability lives in the hierarchy

Linearizability sits at the top of the single-object consistency lattice (see The Consistency Model Hierarchy). Immediately below it is Sequential Consistency, which keeps the “single total order all processes agree on” but drops the real-time clause (L2). Below that, Causal Consistency keeps only causally-related order; below that, Eventual Consistency promises only convergence if writes stop. Jepsen’s map places it precisely: when “real-time ordering becomes irrelevant but uniform total ordering across processes remains necessary,” you drop from linearizability to sequential consistency; when you additionally need it “spanning multiple objects simultaneously,” you move up to strict serializability (Jepsen). One subtlety Jepsen flags: linearizability is a single-object model, but “the scope of ‘an object’ varies” — it might be one key, or an entire table treated atomically, but generally not spanning separate databases.

The cost — Attiya & Welch, why linearizability is strictly more expensive

Linearizability’s real-time requirement is not free. Hagit Attiya and Jennifer Welch, “Sequential Consistency versus Linearizability” (ACM TOCS 12(2), 1994), proved that when clocks are only approximately synchronized and message delay is uncertain by an amount u > 0, a linearizable implementation of a read/write register cannot make both reads and writes fast: the response time for reads is at least on the order of u/4 and for writes at least u/2 (search-surfaced result; Kleppmann’s talk summary). Sequential consistency, by contrast, lets you make either reads local or writes local (one of the two operations runs with no network wait). The intuition: to respect real time, a linearizable read must wait long enough to be sure it hasn’t missed a write that finished “just before” it in wall-clock time — and that waiting is bounded below by the network’s delay uncertainty. This is the concrete, quantified price of the L2 clause.

Uncertain

Verify: the exact constants (read ≥ u/4, write ≥ u/2) in the Attiya–Welch lower bound. Reason: these came from a search-result summary and a secondary talk write-up, not from reading the TOCS 1994 paper’s proof directly (the MIT PDF fetch 404’d during research). The qualitative result — linearizability strictly more expensive than sequential consistency under u > 0, both read and write Ω(u) — is well established; the precise fractions should be checked against the paper. #uncertain

Failure modes and common misunderstandings

• “Linearizable = serializable.” No. Different scope (single op vs transactions), different locality (local vs not), different blocking behavior. A store can be linearizable per key yet offer no multi-key transactions at all (etcd, DynamoDB with a strongly-consistent read on one key).
• “Linearizable = strongly consistent, so it must be slow globally.” Linearizability is about order, not latency, but the Attiya–Welch bound shows real-time order does impose a latency floor tied to delay uncertainty; and under CAP Theorem, a linearizable store must sacrifice availability during a partition. PACELC Theorem adds that even without partitions it pays latency for consistency.
• “A single leader makes reads automatically linearizable.” Only if reads actually go through the consensus path or a valid lease. A stale leader that lost an election but still answers reads can return stale data, violating linearizability — this is why systems use leader leases or read-index / quorum reads (see Read and Write Quorums, Raft).
• Linearization point drift under replication. In a replicated log, the linearization point of a write is when it commits to the log (a majority acknowledges), not when the client’s request arrived or when a follower applies it. Reads must observe committed state at least as new as any write that completed before the read began.
• Confusing it with Sequential Consistency. The single discriminating test: does the model preserve the order of operations that did not overlap in real time? Linearizability yes; sequential consistency no.

Alternatives and when to choose them

Choose linearizability when a client’s own perception of real time must be honored across processes: distributed locks, leader election, configuration that must be read-your-writes across clients, unique-ID/fencing tokens, “compare-and-set” registers. This is why Raft-backed stores (etcd, Consul) and ZooKeeper expose linearizable operations for coordination. Choose weaker models when you can: Sequential Consistency if you need a single agreed order but not real-time recency (classic shared-memory hardware, some caches); Causal Consistency when you need availability under partition but must still respect cause-and-effect (Vector Clocks/Hybrid Logical Clock track the order); Eventual Consistency and CRDTs Basics when availability and latency dominate and convergence-if-writes-stop suffices. The design rule from the Distributed Systems MOC: pick the weakest model the application tolerates — linearizability buys the strongest guarantees at the highest coordination cost.

Production notes

• etcd / ZooKeeper / Consul advertise linearizable reads and writes for the coordination keyspace precisely because locality lets many independent keys compose without a global lock, while the real-time guarantee lets clients treat a key as an atomic variable. etcd offers a “serializable” (non-linearizable, follower-local) read option as a faster, weaker alternative — a direct illustration of the Attiya–Welch trade-off.
• Spanner achieves external consistency — strict serializability, i.e. linearizability lifted to whole transactions — by using Google TrueTime commit-wait to bound clock uncertainty and order transactions by real time. See Spanner Distributed Transactions.
• Testing. Jepsen validates linearizability with the Knossos/Elle checkers, which search for a valid linearization of a recorded history — an NP-hard search in general, exactly the L1/L2 conditions above turned into a solver.

See Also

• Sequential Consistency — the model one rung down: same single total order, but the real-time clause (L2) is dropped, and it is not composable
• The Consistency Model Hierarchy — where linearizability sits at the top of the single-object lattice
• Causal Consistency — the strongest model still available under a network partition
• Serializability — the multi-object transaction analogue; linearizability is strict serializability restricted to one single-object operation
• CAP Theorem · PACELC Theorem — why a linearizable store gives up availability under partition, and pays latency otherwise
• Raft · Paxos High-Level · Read and Write Quorums — the machinery that implements linearizable operations over a replicated log
• Google TrueTime · Spanner Distributed Transactions — real-time bounding that lifts linearizability to global transactions (strict serializability)
• Distributed Systems MOC — parent map (§3 Consistency Models)
• Major System Designs MOC · System Architectures MOC — the systems and topologies that apply this model