Consistency Trade offs · Linearizability

Key Question

If I build a system from linearizable components, is the whole system automatically linearizable?

Deep Dive

Yes — linearizability is compositional. This is one of its defining advantages over other consistency models. Compositionality means that if each individual object (register, queue, counter) in your system is linearizable, then any operation that touches multiple objects is also linearizable. You can reason about each object independently and combine them without worrying about unexpected interactions.

Formally: a history H is linearizable if and only if, for every object X in the system, the sub-history H|X (H restricted to operations on X) is linearizable. This is called the locality property.

Why does this matter? Consider a banking system with two registers: X (checking balance) and Y (savings balance). If each register is independently linearizable:

Client A: write X = X - 100    (withdraw $100 from checking)
Client B: read X, read Y       (check total balance)

Suppose X is initialized to 200, Y to 300. Client A withdraws 100 from X (X=100). Assume X is linearizable. Client B reads X=100 and Y=300. Since both X and Y are linearizable, the combined operation is also linearizable — B sees a consistent snapshot at some point in time. B’s total is 400.

But now consider the SAME scenario under sequential consistency:

Client A: [write X=100]
Client B:                    [read X=100] [read Y=300]

Under sequential consistency, each object individually is sequentially consistent. However, the COMPOSITION of sequentially consistent objects is NOT necessarily sequentially consistent! Here’s why:

Client A: write X=100    (at time 10:00)
Client B: write Y=200    (at time 10:01)
Client C: read X=100, read Y=200  (at time 10:02)
Client D: read Y=200, read X=100  (at time 10:02)

Both C and D see consistent values for X and Y individually. So far so good. But a client E could observe:

Client E: read X=100, read Y=300

How is this possible? Under sequential consistency, operations from each client appear in program order, but there’s no real-time requirement. The interleaving could be: (write Y=200 appears after read Y=300 for E). Each individual object is consistent, but the system as a whole produces a non-sensical result.

This CANNOT happen with linearizability. Because linearizability respects real time: if write X=100 completes before E reads Y, then E must see X >= 100. The real-time ordering prevents absurd interleavings.

Let’s see this with a concrete ASCII diagram. A violation under sequential consistency (but NOT linearizability):

Time ────────────────────────────────────────────────>
X ops:  [A writes 100]          [C reads 100]
Y ops:                           [B writes 200]
Client E:                                          [reads X=100, Y=300]

Under sequential consistency, this is valid if there’s some total order that respects program order. But under linearizability, B’s write Y=200 completes at 10:01, and E reads Y at 10:02 — so Y must be >= 200 for E.

Compositionality of linearizability means you can design your system object-by-object and trust that the whole is correct. This is why linearizability is the standard for concurrent data structures in shared-memory systems (like Java’s java.util.concurrent package) — each class is independently linearizable, and they compose safely.

Check Your Understanding

Is sequential consistency compositional? Why or why not?
If register X is linearizable and register Y is linearizable, is a transfer operation (X = X - 100, Y = Y + 100) guaranteed to be atomic? If not, what could go wrong?
Why is compositionality important for building complex distributed systems?

The “So What?”

Compositionality is the reason linearizability is the default model for reasoning about concurrent data structures. It means you can build a distributed key-value store with linearizable support for each key independently, and clients can safely operate on multiple keys without the system producing impossible results. This is why systems like Spanner and ZooKeeper invest heavily in linearizability — the ability to compose operations safely is invaluable.

✏️ Exercises

Linearizability — Exercises

Exercise 1

A distributed system processes a write of X=7 at 10:00:00. The write completes (client receives ack) at 10:00:01. A read of X starts at 10:00:02 and returns X=0. Is this system linearizable? Explain why or why not.

Exercise 2

Register X and register Y are each individually linearizable. Client A transfers $50 from X to Y by doing: read X, write X−50, read Y, write Y+50. Client B reads X and Y concurrently. Is it guaranteed that Client B never sees a state where the money has vanished (e.g., X+Y decreased)? If not, describe a scenario where this could happen.

Exercise 3

A system provides non-linearizable behavior to the general case. However, all operations from a single client appear linearizable to that client. Is this possible? Explain how the system might achieve this (or why it’s impossible).

Exercise 4

Google Spanner provides strict serializability. Describe how TrueTime (GPS + atomic clocks) is used to:

Assign commit timestamps to transactions
Guarantee that a read that starts after a write commits will see the write’s effects
Handle clock uncertainty (the ε interval)

👁️ View Solutions

Linearizability — Solutions

Solution 1

No, this system is not linearizable.

The write completes (response received) at 10:00:01. The read starts (invokes) at 10:00:02 — a full second after the write completed. Since the read’s invocation is after the write’s response, real-time order requires the write to appear before the read. The write’s linearization point must be at or before 10:00:01, and the read’s linearization point must be at or after 10:00:02. Therefore, the read MUST see X=7 (or a newer value). Returning X=0 violates linearizability.

The only exception would be if the system had clock skew that placed the read “before” the write in real time, but the problem states the absolute times are accurate. The system is broken.

Solution 2

No, it’s not guaranteed. While each register (X and Y) is individually linearizable, the transfer operation involves four separate operations on two registers. There is no atomicity across the multi-step transfer.

Here’s the problematic scenario:

Client A: read X (gets 100), write X=50 (linearizes)
Client B: read X (gets 50), read Y (gets 0 — transfer hasn’t updated Y yet)
Client A: read Y (gets 0), write Y=50 (linearizes)

Client B sees X=50, Y=0 for a total of 50 — the money “disappeared” from B’s perspective. Both X and Y are individually linearizable, but the transfer as a whole is not atomic.

This is why real banking systems use transactions — they need serializability (or strict serializability) to make multi-step operations atomic. Or they use a single register approach (e.g., a ledger that tracks all accounts in one data structure).

Solution 3

Yes, this is possible — this is essentially what session guarantees (like read-your-writes) provide.

A system can be globally non-linearizable but present a linearizable view to each individual client. How?

Sticky sessions: Route a client to the same replica for all its operations. That replica maintains a consistent ordering, and the client never interacts with other replicas to observe inconsistency.
Client-side versioning: The client includes its last-seen timestamp/version with every request. The server ensures the response is at least as recent as that version.
Session tokens: The server issues a session token after each write. The client presents this token with reads, and the server uses it to route or coordinate the read to a replica that has seen the write.

This is how systems like Amazon DynamoDB (with consistent reads) and Apache Cassandra (with read-your-writes consistency) work. The system as a whole may not be linearizable for all clients, but each individual client experiences a linearizable view of their own data.

Solution 4

Spanner uses TrueTime to provide strict serializability through the following mechanism:

Assigning commit timestamps:

When a transaction commits, Spanner assigns it a timestamp s that is guaranteed to be greater than the current TrueTime value.
TrueTime returns an interval [earliest, latest] rather than a single time point. The commit timestamp is set to latest (or later) of the leader’s TrueTime interval at commit time.
This ensures no future transaction can be assigned an earlier timestamp.

Guaranteeing reads see writes:

A read transaction is assigned a timestamp s_read.
The read waits until TT.now().earliest > s_read (the “commit wait”) before returning.
This ensures that all transactions with timestamps <= s_read are fully committed and visible.
Any write that committed before the read started will have a timestamp < s_read, and the read wait guarantees the write’s effects are visible.

Handling clock uncertainty (ε):

TrueTime returns [now - ε, now + ε] — the true time is somewhere in this interval.
Spanner never assumes a precise time; it always uses the worst-case bound.
ε is typically 1-7ms (GPS) or higher (non-GPS data centers).
The commit wait ensures the read’s earliest time exceeds the write’s latest time, closing the window of uncertainty.

This is how Spanner achieves external consistency (equivalent to strict serializability) across globally distributed data centers without a centralized clock.