Linearizability

The intuition: one instant inside the interval

Imagine three programs hammering a single shared variable x over a network. One writes 1, another writes 2, a third reads. Each of those operations is not instantaneous — it has a call (the moment the client sends the request) and a return (the moment it gets a response). In between, the request is in flight, queued, replicated, maybe waiting on a lock. The operations overlap in real time. So what is the "right" answer the read should see?

Linearizability gives a beautifully simple answer. Pretend each operation happened atomically at a single instant — its linearization point — somewhere between its call and its return. If you can pick one such instant per operation so that (1) the resulting sequential order is a legal history for the object, and (2) the order never contradicts real time (if op A returned before op B was called, A's point comes before B's point), then the execution is linearizable. The system behaves as if there is a single copy of the data and every operation touches it one at a time, even though under the hood there may be five replicas and a consensus protocol.

The mental model worth keeping: every overlapping interval bar collapses down to a single dot on the timeline, and those dots line up into one consistent story. A read returns the value written by the most recent write that linearized before it. There is no "stale" read once a write has completed — that is the whole point.

The precise definition and a little history

Linearizability was formalized by Maurice Herlihy and Jeannette Wing in their 1990 paper "Linearizability: A Correctness Condition for Concurrent Objects" (ACM TOPLAS). Their setting was shared-memory multiprocessors, not networks, but the definition is identical for distributed registers.

A history is the sequence of invocation and response events for a set of concurrent operations. A history is linearizable if it can be extended (by adding responses for any pending operations, and discarding the rest) to a history H' such that:

• Sequential legality. H' is equivalent to some legal sequential history S — meaning if you replay the operations of S one at a time against the object's specification, every return value is correct.
• Real-time order is preserved. If operation a finishes (returns) before operation b begins (is invoked) in the original history, then a precedes b in S.

Operations whose intervals overlap may be ordered either way — concurrency gives you freedom. The real-time rule only constrains operations that don't overlap. The existence of a linearization point per operation is an equivalent, more operational way to state the same condition.

Linearizability vs sequential vs serializability vs causal

These four consistency models are constantly confused. They live on different axes: scope (single object vs multi-object transactions) and ordering strength (real-time, program order, or just causal).

	Linearizability	Sequential consistency	Serializability	Strict serializability	Causal consistency
Scope	Single object	Single object	Multi-object transactions	Multi-object transactions	Single or multi-object
Ordering constraint	Real-time total order	Some total order respecting each process's program order	Some serial order (no real-time)	Serial order + real-time	Respects causality (happens-before) only
Respects wall-clock real time?	Yes	No	No	Yes	No
Composable / local?	Yes	No	No	No	Yes
Available under partition? (CAP)	No (CP)	No	No	No	Yes (AP)
Coined by	Herlihy & Wing, 1990	Lamport, 1979	Eswaran et al., 1976	Papadimitriou, 1979	Ahamad et al., 1995
Canonical example	etcd, ZooKeeper, a CAS register	Hardware memory models	Classic SQL isolation (SERIALIZABLE)	Google Spanner	COPS, Bayou, Dynamo-style stores

Three things to take away. First, linearizability and serializability are orthogonal: one is about real-time order of single operations, the other about serial equivalence of multi-operation transactions. Their conjunction is strict serializability, the gold standard Spanner targets. Second, sequential consistency is strictly weaker than linearizability — it allows a process to read a value that was overwritten in real time, as long as no single process observes its own operations out of program order. Third, causal consistency is the strongest model that stays available under partitions; everything stronger is forced to choose CP.

Why linearizability composes (the locality property)

Herlihy and Wing proved that linearizability is local: a history over a set of objects is linearizable if and only if each object's sub-history is linearizable on its own. This is also called the composability property, and it is a big deal.

It means you can build a linearizable system out of independently linearizable components without inventing any cross-object coordination. If your key-value store makes each key linearizable, the whole store is linearizable. Serializability has no such luck: you can have two databases that are each serializable, yet a transaction touching both can produce a non-serializable global schedule, because serializability allows reordering that ignores real time and so the two local orders can disagree.

Linearizability also has a second structural virtue: it is a non-blocking property. A pending invocation of a total operation (one that is always defined, like a read or a write) never has to wait for another pending operation to complete in order to be linearized. Contrast this with serializability, where a transaction may have to block to avoid a non-serializable interleaving. Non-blocking-ness is what lets linearizable objects be implemented with wait-free or lock-free algorithms.

The cost: coordination, latency, and CAP

Linearizability is not free. To guarantee that a read sees the latest completed write, the system must establish a single agreed-upon order — and agreeing requires communication. Concretely:

• Every write needs a quorum round-trip. In a consensus-based system with replication factor 5, a write isn't safe to acknowledge until a majority (3 nodes) has durably accepted it. That is at least one network round-trip to the slowest of the majority — typically a few milliseconds within a datacenter, tens to hundreds across regions.
• Reads cost coordination too. A naive read from one replica can be stale. A linearizable read must either go through the leader, confirm leadership with a quorum, or use a lease — so reads are no longer "free local lookups."
• The CAP tie-in. Gilbert and Lynch's 2002 proof of the CAP theorem is, precisely, a proof that linearizability and availability are incompatible under a network partition. When the network splits, a linearizable system on the minority side must stop answering (sacrifice availability) rather than risk a stale read. Linearizable systems are therefore CP: they choose Consistency and forfeit Availability when Partitions happen.
• Latency even without partitions. The PACELC framework extends CAP: else (in normal operation) you still trade latency for consistency. Linearizable systems are PC/EC — they pay latency for consistency always, not just during partitions.

How real systems provide linearizability

There are three workhorse techniques, often combined:

• Single-leader replication. Funnel every operation through one node that imposes a total order, then replicate. ZooKeeper (via Zab) and etcd (via Raft) do this. The leader is the linearization authority; followers serve only after catching up or via leader-confirmed reads.
• Consensus protocols. Raft, Multi-Paxos, and Zab make a quorum agree on each command's position in the log before it commits. Because a majority must acknowledge and any two majorities overlap, no committed write can be lost or reordered — exactly the invariant linearizability needs. Spanner adds TrueTime to make the order respect real time across continents.
• Compare-and-swap registers. The simplest linearizable object is a hardware (or distributed) CAS register: CAS(expected, new) atomically swaps the value only if it currently equals expected. Each CAS has an obvious linearization point — the instant the atomic instruction executes. Lock-free data structures are built by composing CAS operations, each linearizable on its own.

The common thread: a single point of serialization (a leader, a consensus log slot, or an atomic instruction) furnishes the linearization point for free.

JavaScript: checking whether a history is linearizable

Here is a brute-force linearizability checker for a read/write register. It tries every order in which the still-pending operations could linearize, replaying each candidate against the register spec while enforcing real-time precedence. This is the famous "Wing & Gong" style checker — exponential in the worst case (the general problem is NP-complete), but exact and clear.

// Each op: { proc, type: 'write'|'read', val, call, ret }
// call/ret are integer timestamps on a single real-time line.

function isLinearizable(history, initial = 0) {
  // A candidate total order must respect real time: if a.ret < b.call, a before b.
  // We search by repeatedly choosing a "minimal" op (one whose call is <= the
  // earliest unfinished return) to linearize next, replaying it against state.

  function search(remaining, state) {
    if (remaining.length === 0) return true;

    // The earliest return among remaining: nothing called after it may go first.
    const minRet = Math.min(...remaining.map(o => o.ret));

    for (const op of remaining) {
      // Real-time rule: op can be next only if it could have linearized
      // before everything that must come after it — i.e. its call is not
      // strictly after some other op that already had to finish first.
      if (op.call > minRet) continue;            // someone must precede op

      let nextState = state;
      if (op.type === 'write') {
        nextState = op.val;                       // write takes effect
      } else {
        if (op.val !== state) continue;           // read must match current state
      }

      const rest = remaining.filter(o => o !== op);
      if (search(rest, nextState)) return true;   // this choice works
    }
    return false;                                  // no legal next op
  }

  return search(history.slice(), initial);
}

// Linearizable: W(1) and R overlap, R can linearize after the write.
console.log(isLinearizable([
  { proc: 'A', type: 'write', val: 1, call: 0, ret: 4 },
  { proc: 'B', type: 'read',  val: 1, call: 2, ret: 6 },
]));  // true

// NOT linearizable: the read starts (call 8) after the write of 2 already
// returned (ret 7), yet returns the stale value 1 written before it.
console.log(isLinearizable([
  { proc: 'A', type: 'write', val: 1, call: 0, ret: 3 },
  { proc: 'A', type: 'write', val: 2, call: 4, ret: 7 },
  { proc: 'B', type: 'read',  val: 1, call: 8, ret: 10 },
]));  // false

The key line is the real-time filter if (op.call > minRet) continue;. It refuses to linearize an operation before another operation that, by real time, was forced to happen first. Drop that line and you get a sequential-consistency checker instead — which is exactly why a stale-read history passes sequential consistency but fails linearizability.

Python: walking a read/write/CAS register history

This version handles compare-and-swap as well, and returns the witnessing linearization order when one exists, so you can see why a history is (or isn't) linearizable.

from itertools import permutations

# op = dict(proc=, type='write'|'read'|'cas', val=, expected=, call=, ret=)

def respects_real_time(order):
    # order is a list of ops; check no op appears before one that fully
    # preceded it in real time (prev.ret < later.call => prev must be earlier).
    for i, a in enumerate(order):
        for b in order[i + 1:]:
            if b['ret'] < a['call']:     # b finished before a even started
                return False              # yet b is placed after a -> illegal
    return True

def replay(order, initial=0):
    state = initial
    for op in order:
        if op['type'] == 'write':
            state = op['val']
        elif op['type'] == 'read':
            if op['val'] != state:
                return False
        elif op['type'] == 'cas':
            if state == op['expected']:
                state = op['val']         # swap succeeded
                if op.get('ok') is False:
                    return False
            else:
                if op.get('ok') is True:  # claimed success but couldn't swap
                    return False
    return True

def linearizable(history, initial=0):
    for order in permutations(history):
        if respects_real_time(order) and replay(list(order), initial):
            return list(order)            # a witnessing linearization
    return None

h = [
    dict(proc='A', type='write', val=1, call=0, ret=4),
    dict(proc='B', type='read',  val=1, call=2, ret=6),
    dict(proc='C', type='write', val=2, call=5, ret=9),
]
witness = linearizable(h)
print([f"{o['type']}({o.get('val')})" for o in witness] if witness else "NOT linearizable")
# -> ['write(1)', 'read(1)', 'write(2)']  (the only real-time-legal order that also replays)

Real checkers (Jepsen's Knossos and the faster Porcupine) prune this search aggressively with the Wing-and-Gong incremental algorithm and memoized partial states — but the semantics above are exactly what they enforce, and they are how distributed databases get caught returning stale reads.

Common misconceptions

• "Linearizable means serializable." No. Linearizability is about single operations on a single object plus real time; serializability is about transactions over many objects with no real-time requirement. A store can be linearizable per-key yet have no transactions at all. The combination is strict serializability.
• "It's just eventual consistency but faster." The opposite. Eventual consistency lets replicas disagree and converge later; linearizability forbids ever observing a stale value once a write has completed. They sit at opposite ends of the spectrum.
• "A read from any replica is fine if replication is fast." No amount of speed makes an unconfirmed local read linearizable — a slightly-behind follower can still return a value older than a write that already returned to its client. You need leader confirmation, a lease, or a quorum read.
• "Linearizability requires synchronized clocks." The definition uses real-time ordering, not timestamps. You only need to know that one operation returned before another was called — a fact established by the request/response handshake, not by wall clocks. (Spanner uses TrueTime to make this efficient across regions, but it is an optimization, not a requirement.)
• "It's about ordering writes." It's about both reads and writes. The hard cases are almost always reads: a read that returns a value no longer current is the classic linearizability violation.