Linearizability and Sequential Consistency
Linearizability says every operation appears to take effect at one instant between its call and its return, and that instant respects real time across threads. Sequential consistency is weaker: each thread's operations stay in program order and there is some single global order, but it doesn't have to match wall-clock time. Linearizability composes across objects; sequential consistency does not.
What linearizability really says
Pick any concurrent execution. For each operation, draw a horizontal bar from the moment the call started to the moment it returned. The execution is linearizable if a single point can be placed inside each bar so that:
- The points form a total order.
- If bar A finished before bar B started in real time, A's point comes before B's.
- Reading the operations in point order produces a valid sequential history of the object.
That is it. The point is the linearization point. For an AtomicLong.incrementAndGet, the point is the successful CAS. For a ConcurrentHashMap.put, the point is when the new entry becomes visible to subsequent reads.
A linearizable history looks like this. Each operation is a horizontal bar from call to return. Inside each bar sits one linearization point (the dot). The dots, read left to right, give the global order, and bars that finished before others started have their dots in the right order:
real time --> 0 5 10 15 20 25 30 35 40 45
Thread A: [==== write(x,1) ====]
* LP@t=5
Thread B: [==== read(x)=1 ====]
* LP@t=22
Thread C: [==== write(x,2) ====]
* LP@t=39
LPs in real-time order: write(x,1)@5 > read(x)=1@22 > write(x,2)@39
Why "real time" The real-time part is what makes the model useful to clients. A client knows when its own call returned and when its next call started. If a write returned at 10:00:01 and a read began at 10:00:02, the client expects to see that write. Linearizability is the model that delivers exactly that promise.
What non-linearizability looks like
Take the Accounts example from the code: totalBalance() reads a then b without a lock. A transfer(50) call slips between the two reads, so the reader sees the pre-transfer a (= 100) and the post-transfer b (= 150) and returns 250. The real total was 200 the whole time. There is no point inside the reader's interval where placing the LP would yield 250.
real time --> 0 5 10 15 20 25 30 35 40 45
Reader: [============== totalBalance() returns 250 =============]
^ reads a=100 @t=2 ^ reads b=150 @t=40
Writer: [==== transfer(50) ====]
* LP@t=22 (a -= 50, b += 50)
Sum a+b over time: 200 ============== 200 ====== 200 ====== 200
t=0..22 t=22..end
(100+100) (50+150)
before LP after LP
The reader's bar spans the writer's bar. The actual sum was 200 at every instant inside the reader's interval (100+100 before the LP, 50+150 after). 250 was never a real value.
The reader's bar spans the writer's bar. The actual sum was 200 at every instant inside the reader's interval (100+100 before the LP, 50+150 after). 250 was never a real value. The read is non-linearizable because no valid LP exists for it.
Sequential consistency is weaker
Two short rules:
- Linearizable: the moment a write call returns, everyone can see it.
- Sequentially consistent: everyone eventually agrees on what order things happened. But "the write returned" does not mean "everyone can see it yet."
The clearest analogy is text messaging.
A user hits send at 10:00:01. The phone shows "sent" instantly. The recipient's phone shows the message at 10:00:08, after the server pushed it. For 7 seconds the sender's phone says "sent" while the recipient's phone shows nothing. After 10:00:08 both phones see the same chat in the same order.
Sender phone: send at 10:00:01 ---- Y sent -------------------->
|
| message in flight
v
Recipient: . . . . . . . . . . message arrives at 10:00:08
----------->
Wall clock: 10:00:01 10:00:04 10:00:08
That gap is sequential consistency. The order both phones agree on (the first message, then the next) is consistent. The wall-clock visibility is not.
If the same chat were linearizable, the "sent" checkmark would not appear until the recipient's phone had the message. The sender would wait the 7 seconds. Slower, but the checkmark would mean what it says.
Sequential consistency is cheaper everywhere: replicated databases, CPU store buffers, eventual-consistency caches. The system buffers, batches, replicates, and returns without confirming. The catch: the moment wall-clock time enters the reasoning ("my write returned, so the read I just started must see it"), SC will betray it.
Why it matters: composition
Here is the property that makes linearizability the one to pick:
If every individual piece of a system is linearizable, the whole system is linearizable.
Build with linearizable Lego, the result is linearizable. Reason about each piece in isolation, and that reasoning still holds when the pieces are wired together.
Sequential consistency does not have this property. Two SC pieces wired together can produce behavior no single SC system could ever show.
Intuition: SC lets each piece pretend "the world held still while I ran my operations." Each piece is consistent with its own paused-world story. Wire two pieces together, and each piece's paused world is different. Combined behaviors emerge that no single paused world allows.
Concrete picture. Imagine two whiteboards, each with a "first come, first served" stamp queue. Each whiteboard is internally consistent: anyone looking at one whiteboard sees a clean queue order. But the two whiteboards do not share a clock. So a person stamping both whiteboards in their own order can land in positions that no global clock would allow:
Alice stamps board P, then stamps board Q.
Bob stamps board Q, then stamps board P.
Each board's view (internally consistent):
Board P: Bob first, then Alice. < P's local order
Board Q: Bob first, then Alice. < Q's local order
But Alice's program order says she stamped P before she stamped Q.
Bob's program order says he stamped Q before he stamped P.
No single global clock can satisfy all four constraints at once.
Each board is SC. The combined system is not. There is no single global story consistent with both boards plus the program order of both people.
The practical consequence: when stitching components together, prefer linearizable per component over SC. Pick Zookeeper (linearizable) over Redis (not) for coordination. Pick AtomicReference (linearizable) over a pair of volatile fields (each SC alone, not as a pair) for shared state. When in doubt, go linearizable, especially anywhere two components have to agree on what happened.
The composition trap
Most correctness bugs in concurrent code come from composing primitives that are individually correct but whose combination breaks an invariant. A volatile field for a and a volatile field for b does not give an atomic snapshot of (a, b). Either one atomic that holds the pair, or a lock that brackets both updates and the read, is required.
When to actually pay for it
Linearizability has a price: in an asynchronous system with possible failures, linearizable operations need at least one round trip to a leader or a quorum. That sets a floor on latency that local-replica reads can beat.
Pay the price when:
- A leader election needs to return the same answer to two observers in the same wall-clock window. (etcd, ZooKeeper.)
- A distributed lock acquire must reflect every prior release. (Compare-and-set in Redis with Redlock is famously not enough.)
- An idempotency check must see every prior recorded request id.
Skip it when monotonic reads, read-your-writes, or causal consistency suffice. Most user-facing reads are in this bucket.
Practical mental tools
- For each shared object, can the linearization point be named? If not, linearizability is probably absent.
- For each invariant that spans two objects, what mechanism makes the combined operation appear at one instant? If the answer is "two locks," there's almost certainly a bug.
- When picking a backing store, look up its consistency model in the docs. If the docs are vague or the word "linearizable" doesn't appear, assume it is not.
Primitives by language
- AtomicReference.compareAndSet (linearizable on the reference)
- AtomicLong.incrementAndGet (linearizable)
- ConcurrentHashMap.putIfAbsent (linearizable)
Implementations
Two account balances. The invariant: the total stays constant under transfers. A snapshot reads each balance independently, so a transfer that happens between the two reads can produce a sum that never existed at any real instant. The composition of two correct single-variable reads is not a correct snapshot.
1 class Accounts {
2 volatile long a = 100;
3 volatile long b = 100;
4 // Invariant: a + b stays at 200 under transfer().
5
6 synchronized void transfer(long amount) {
7 a -= amount;
8 b += amount;
9 }
10
11 // NOT linearizable: the two reads happen at different instants.
12 long totalBalance() { return a + b; }
13 }
14
15 // Witness trace:
16 // t1: reader calls totalBalance(), reads a = 100
17 // t2: writer calls transfer(50), a becomes 50, b becomes 150, returns
18 // t3: reader reads b = 150, totalBalance returns 100 + 150 = 250
19 // 250 was never the real total at any instant during [t1, t3].
20 // Real values were always 200. The read pair has no single
21 // linearization point that fits between t1 and t3 with sum = 250.Bracket the read with the same lock that brackets the writes. Now the snapshot happens inside one critical section, so it has a single linearization point and always returns a value that existed at some real instant.
1 class Accounts {
2 long a = 100;
3 long b = 100;
4
5 synchronized void transfer(long amount) {
6 a -= amount;
7 b += amount;
8 }
9
10 // Linearizable: the read pair happens inside one critical section.
11 synchronized long totalBalance() {
12 return a + b;
13 }
14 }
15
16 // Every totalBalance() returns a value that was the real sum at the
17 // moment the lock was held. Every transfer() has a single linearization
18 // point (when it commits inside the synchronized block). The history
19 // of operations always matches some real-time order.A write-buffered store: writes go into a per-thread buffer and flush asynchronously. Each thread sees its own writes in program order, and there is one global flush order, so it is sequentially consistent. But a writer's response can return before the value is visible to readers, so real-time ordering breaks.
1 // Pseudocode for the model. Real systems that look like this:
2 // - eventually consistent caches
3 // - replicated DBs that ack on local commit and replicate async
4
5 class WriteBufferedRegister {
6 long visible = 0;
7 long buffered = 0; // last write, not yet flushed
8
9 synchronized void write(long v) { buffered = v; /* return now */ }
10 synchronized long read() { return visible; }
11
12 // Background flush: visible = buffered (eventually)
13 }
14
15 // Trace: write(1) returns at t=10. read() at t=11 returns 0 (not flushed yet).
16 // Real-time order says read should see 1. It doesn't. Not linearizable.
17 // It can still be sequentially consistent if every thread's reads
18 // respect program order and there's one global linearization. Many
19 // systems sacrifice linearizability for latency and live with this.Key points
- •Linearizability: each operation has a single 'effect point' that lies between its invocation and its response, and the order of effect points is consistent with real time.
- •Sequential consistency: there exists some interleaving of all operations that respects each thread's program order, but the interleaving does not have to match real time.
- •Linearizability is composable: if every object is linearizable, the system is linearizable. Sequential consistency is not.
- •Java volatile reads and writes on a single variable are linearizable; combining multiple volatiles or doing read-modify-write is not. Use java.util.concurrent.atomic for linearizable RMW.
- •Redis is not linearizable by default. etcd, ZooKeeper, and DynamoDB conditional writes are.
- •Linearizability has a real cost: in an async system with failures, linearizable reads cannot achieve sub-RTT latency (Attiya and Welch, 1994).
Follow-up questions
▸If linearizability is just sequential consistency plus a real-time constraint, why does the real-time part matter so much?
▸Is volatile in Java linearizable?
▸Is Redis linearizable?
▸Why do people say linearizability is expensive?
Gotchas
- !Composing two sequentially consistent objects can give a non-SC system. Composing two linearizable objects always gives a linearizable system.
- !A linearizable register is what most papers mean by 'atomic register.' The terms are interchangeable in the literature.
- !Don't conflate linearizability with serializability. Linearizability is about single-object real-time order. Serializability is about multi-operation transactions.
- !A snapshot read across two unrelated linearizable objects is not itself linearizable. A transaction or a globally-ordered log is required for that.
Common pitfalls
- Reaching for 'just use volatile' on multi-field invariants. Volatile gives per-field SC, not multi-field linearizability.
- Assuming that because every operation uses a lock, the whole system is linearizable. It is, only if there is one lock.
- Designing for linearizability when customers don't need it. Many features are fine with monotonic reads or read-your-writes, both much cheaper.
APIs worth memorising
- java.util.concurrent.atomic (linearizable RMW)
- etcd Txn (linearizable compare-and-swap)
- ZooKeeper sync() (forces a linearizable read by syncing with the leader)
Coordination services (etcd, ZooKeeper, Consul) are linearizable so that 'is the leader still leader' returns a real-time-correct answer. Distributed locks rely on this. Most user-facing data stores deliberately weaken to causal or eventual consistency to get latency and availability; they pay the cost in subtle bugs that only show up under load.