Linearizability

Linearizability is the strongest consistency guarantee for a single piece of data. The system acts as if there were one copy. Every operation takes effect at one instant between the moment the client sent it and the moment the client got the reply.

The big idea

Think of a whiteboard in a shared office. Once someone writes a number on it, everyone who looks afterwards sees that number. Nobody sees an old number after the new one has been written.

The whiteboard analogy breaks when the copies live in different places. A replica in Virginia and a replica in Oregon can hold different values for a few milliseconds. Linearizability is the promise that users never see that gap.

Two rules make it up:

• Once a write completes, every read that starts after that moment sees it, or a newer value.
• Once any reader has seen a new value, no later reader may see the old one, even on another replica.

The second rule is the one people forget. It ties the order of operations to real time, across all clients.

Walking through it

Register x starts at 0 on three replicas. Client A writes x = 1. The write completes at t=10 ms. Here is what linearizability allows.

t=0    A: write x=1 sent to R1
t=10   A: write x=1 completes (ack)
t=20   B: read x from R3 -> 0    NOT allowed, started after t=10
t=50   B: read x from R2 -> 1    allowed
t=60   B: read x from R3 -> 0    NOT allowed, B already saw 1

The read at t=20 must return 1, because the write finished at t=10. The read at t=60 is also wrong, because a newer value was already seen at t=50.

Sequential consistency is weaker. It only needs everyone to agree on one order of operations. That order does not have to match real time, so the read at t=20 could return 0 and still be allowed.

You need linearizability for leader election, distributed locks, unique usernames, and inventory. In each case, a stale read leads to a wrong decision.

Common mistakes

• Thinking "fresh enough" is linearizable. It is a strict rule tied to real time, not a loose "usually up to date".
• Assuming a quorum read is always linearizable. Overlapping quorums make stale reads rare, but racing writes can still show new-then-old without extra care.
• Reading from a follower and assuming the leader's guarantee applies. A follower can lag behind the leader.

Check yourself

1. A write completed at t=10 ms. A read starts at t=20 ms on a different replica. Must it see the write? Yes. Under linearizability, any read that starts after a completed write must return that value or a newer one.
2. Why does sequential consistency allow the t=20 read to return 0? It only requires one agreed order. "B reads 0, then A writes 1" is a valid order that ignores real time.

Key takeaways

• Linearizability makes a replicated value behave like one copy.
• A completed write must be visible to every read that starts afterwards.
• Once a new value is seen, older values cannot reappear for any reader.
• Sequential consistency keeps one agreed order but ignores real time.
• Leader election, locks, uniqueness and inventory all need this guarantee.

Further learning

Next, see how this guarantee fits with the network failures in CAP and PACELC.

Martin Kleppmann's Cambridge lecture defines linearizability with timeline diagrams and shows where quorum reads still break it.