Linearizability vs Sequential Consistency, in depth: histories, real-time order, a working checker, composability, cost, and where real systems land

Histories: the thing both models judge

A consistency model is a rule about histories. A history records, for each operation, which process issued it, the operation and its result, when it was invoked and when the response came back. Two operations are concurrent if their intervals overlap; otherwise one finished before the other started, and real time orders them.

Both models answer the same question about a history: can the operations be arranged in a single sequence that is legal for the object, meaning every read returns the value of the most recent write before it in the sequence? They differ in which orderings of the history the sequence is required to keep.

• Sequential consistency (Lamport, 1979): there is a legal sequence that keeps each process's own operations in the order that process issued them. Operations of different processes may be reordered freely, even if one finished long before the other began.
• Linearizability (Herlihy and Wing, 1990): there is a legal sequence that keeps real-time order: if operation a returned before operation b was invoked, a comes before b, whichever processes issued them. An equivalent picture is that each operation takes effect at one instant, its linearization point, somewhere between its invocation and its response.

Because operations from one process never overlap, real-time order includes program order, so every linearizable history is sequentially consistent. The reverse is false, and the gap is exactly the histories where a process sees something older than what another process had already seen or written, with no overlap to excuse it.

Worked examples

Stale read. P1 writes x = 1 and gets an acknowledgement. Afterwards, P2 reads x and gets 0. Sequential consistency accepts this: put P2's read before P1's write. Linearizability rejects it: the write returned before the read began, so the read must follow it and must return 1. This is exactly what a replica that lags the leader produces.

New then old. In the diagram, P1's write is slow and overlaps both reads. P2 reads 1, and after P2's read has returned, P3 reads 0. Each read alone is fine, since a read concurrent with a write may return either value. But linearizability requires one instant for the write: P2 seeing 1 means the write took effect before P2's read returned, so P3's later read must also see 1. Sequential consistency places P3's read before the write and accepts it. This is the signature of reads served by different replicas at different lag.

A checker you can run

For small histories you can check both models by brute force: try every permutation of the operations, keep those that respect the required ordering, and test whether any of them is legal. Real checkers such as Knossos and Porcupine prune this search aggressively, but the definitions are the same.

from itertools import permutations

# op = (process, kind, obj, value, invoke_time, response_time); registers start at 0
def legal(seq):
    state = {}
    for _, kind, obj, val, _, _ in seq:
        if kind == "w":
            state[obj] = val
        elif state.get(obj, 0) != val:
            return False
    return True

def check(history, model):
    before = []
    for a in history:
        for b in history:
            if a is b:
                continue
            if model == "linearizable" and a[5] < b[4]:
                before.append((a, b))   # a returned before b was invoked
            if model == "sequential" and a[0] == b[0] and a[4] < b[4]:
                before.append((a, b))   # same process, program order
    for seq in permutations(history):
        pos = {op: i for i, op in enumerate(seq)}
        if all(pos[a] < pos[b] for a, b in before) and legal(seq):
            return True
    return False

stale = [("P1", "w", "x", 1, 0, 1), ("P2", "r", "x", 0, 2, 3)]
new_then_old = [("P1", "w", "x", 1, 0, 10), ("P2", "r", "x", 1, 2, 3),
                ("P3", "r", "x", 0, 4, 5)]
for h in (stale, new_then_old):
    print(check(h, "sequential"), check(h, "linearizable"))   # True False, twice

Running it prints True and False for both histories: sequentially consistent, not linearizable. The search is factorial, so keep test histories to a handful of operations, or use a real checker. What Jepsen taught us explains how histories are recorded from real clusters under faults and fed to such checkers.

Composability: the property that decides designs

Herlihy and Wing proved that linearizability is local: if each object in a system is linearizable on its own, the whole system is linearizable. You can build a linearizable service from independently linearizable pieces, such as separate partitions each run by its own consensus group, and reason about them one at a time.

Sequential consistency is not local. Take two registers x and y, both starting at 0. P1 writes x = 1 then reads y and gets 0. P2 writes y = 1 then reads x and gets 0.

h = [("P1", "w", "x", 1, 0, 1), ("P1", "r", "y", 0, 2, 3),
     ("P2", "w", "y", 1, 0, 1), ("P2", "r", "x", 0, 2, 3)]
only_x = [o for o in h if o[2] == "x"]
only_y = [o for o in h if o[2] == "y"]
print(check(only_x, "sequential"), check(only_y, "sequential"), check(h, "sequential"))
# True True False

Each register alone is sequentially consistent: put the read before the write. Together they are not: P1's write precedes P1's read of y, which must precede P2's write of y, which precedes P2's read of x, which must precede P1's write of x, a cycle. So two independently sequentially consistent stores do not make a sequentially consistent system, and every cross-object invariant needs its own argument.

This history is also the classic store-buffer litmus test for CPUs, and x86 processors allow it: their memory model, TSO, lets a store sit in a core's store buffer while a later load to a different address goes ahead. Multicore memory is not sequentially consistent by default. Languages restore it on request: C++ seq_cst atomics and Java volatile fields make data-race-free programs behave sequentially consistently, at the cost of fences.

Why real time matters in practice

Real-time order sounds like a theoretical nicety until processes talk to each other outside the store. A user saves a document and the server replies OK; the user sends a colleague a link; the colleague's request goes to another replica and shows the old version. Under sequential consistency nothing went wrong, because the store does not know about the link. Under linearizability this cannot happen.

The same gap breaks coordination. A lock service that is only sequentially consistent can let a client acquire a lock that another client already holds, as observed through a stale replica. Leader election, uniqueness checks such as username registration, and compare-and-set on configuration all need linearizability, or a fencing mechanism that tolerates its absence. Clocks in distributed systems explains why timestamps alone cannot recover real-time order across machines.

The cost of real time

Sequential consistency lets one side be cheap. If all writes go through a single ordered log, a replica can answer reads locally from whatever prefix of the log it has applied, as long as each client never moves backwards: reads are fast and possibly stale. Linearizability forbids that, because a local replica cannot know whether a write elsewhere has already completed. Attiya and Welch showed that in a system with bounded message delays, a sequentially consistent register can make either reads or writes purely local, but not both, while a linearizable register cannot make either one local.

Under a network partition, neither model can keep both sides answering every request, but linearizability is the stricter one: a minority side cannot serve even a read without risking staleness. In consensus systems the usual techniques for linearizable reads are routing reads through the log, the ReadIndex approach in which the leader confirms it is still leader with a heartbeat round before answering, and leader leases, which skip the round but depend on bounded clock drift. Raft in depth covers these mechanisms.

Where real systems land

The pattern is consistent: writes are usually ordered by one leader or one consensus group, and the read path decides which model you actually get. Cassandra's per-partition Paxos is explained in Cassandra lightweight transactions.

Worked design: choosing per operation

Consider a configuration service built on a Raft-based store, used by a fleet of 2,000 application servers. Three kinds of operation run against it. Feature flags are read by every server on every request and change a few times a day. A deployment controller uses compare-and-set on a version key to make sure only one rollout runs at a time. And an operator who flips a flag expects the dashboard, served by another node, to show the new value at once.

Making every flag read linearizable would push thousands of reads per second through the leader's ReadIndex round, for no benefit: a server that sees a flag a few hundred milliseconds late is harmless, as long as it never flips back to an older value. Those reads can go to followers, with each client pinned to one replica so its view only moves forward. That is sequential consistency per client, and it is cheap. The deployment controller's compare-and-set must be linearizable, which it is because it goes through the log, and so must the controller's read of the current version before deciding to act. The operator's dashboard read should use the linearizable path too, because the operator's own acknowledgement and the dashboard are linked through a person, outside the store. Writing down this decision per operation is the whole skill.

Failure modes

• Follower reads behind a load balancer: a linearizable store becomes sequentially consistent, or weaker, when reads spread across replicas. Check the client configuration, not just the server.
• Stale leader: a deposed leader that has not noticed answers reads from its old state. ReadIndex or lease checks prevent it; leases fail if clocks drift past their bound.
• Client caches: a cache in front of a linearizable store silently downgrades every read it serves.
• Retries with unknown outcomes: a timed-out write may or may not have happened. Treat it as concurrent with everything after it, and make it idempotent.
• Session tricks mistaken for linearizability: read-your-writes and monotonic reads per client do not prevent another client from seeing older data.

What to do next

1. List the operations in your system whose correctness depends on real-time order: locks, leader election, uniqueness and compare-and-set.
2. For each store you use, find the documented guarantee for reads and writes separately, and which client settings change it.
3. Check whether any replica, cache or load balancer serves reads outside the consistent read path.
4. Run the checker above on hand-written histories for the anomalies you care about until the definitions are second nature.
5. Record real histories under faults with a Jepsen-style test and check them with Knossos or Porcupine.
6. Where you accept sequential consistency, document the stale-read window and add fencing to anything that coordinates.