Consistency Trade offs · Linearizability

Key Question

What does it mean for a distributed register to behave as if there’s only one copy, and all operations are instantaneous?

Deep Dive

Linearizability is the strongest single-object consistency model in distributed systems. It gives every client the illusion that there is exactly one copy of the data, and that every operation takes effect atomically at a single point in time. No client ever sees a “partial” or “stale” view of the world.

Formally, a history of operations is linearizable if:

There exists a total order of all completed operations that respects each operation’s real-time interval (its invocation and response).
The total order is consistent with the semantics of the object (e.g., a register returns the last written value).

Each operation has an invocation time (when the client sends the request) and a response time (when the client receives the reply). Between these two points, the operation is “in flight.” The linearization point is a single instant within that interval where the operation appears to take effect. Once a write linearizes at time T, every read that starts after T must return that value or a newer one.

Consider two clients operating on a shared register X initialized to 0:

          10:00:00          10:00:01          10:00:02
Client A: [---- write X=1 -----]
Client B:                         [---- read X=1 ----]

In a linearizable system, Client B’s read at 10:00:01.5 must see X=1 because the write linearized at (say) 10:00:00.5, and B’s read starts after that point. Now contrast with a non-linearizable system:

          10:00:00          10:00:01          10:00:02
Client A: [---- write X=1 -----]
Client B:                         [---- read X=0 ----]

Here B reads X=0 despite the write completing before B’s read began. This is a linearizability violation. The write appeared to take effect “after” B’s read, but the write’s response was at 10:00:01 and B’s invocation was at 10:00:01 — the write finished before the read started, so B MUST see X=1.

The recency guarantee is what makes linearizability useful: once a read returns value V, any subsequent read (by any client, that starts after the first read’s response) must return V or newer. This means that once you see a write, you can never “un-see” it.

Client A: [read X=1] --> knows X is at least 1
Client B:              [read X=?] --> must get 1 or 2, never 0
Time:     10:00:00     10:00:01     10:00:02

Linearizability is equivalent to requiring that:

Writes appear atomic (no partial writes).
Reads return the value of the most recent write relative to real time.
The system behaves as if there is a single, global copy of the data.

A simple test for linearizability: pick any two operations. If operation A completes before operation B begins, then A must appear before B in the total order. Operations that overlap in time can be ordered arbitrarily, as long as the order is consistent with the object’s semantics.

Check Your Understanding

Client A writes X=5 and gets a response at 10:00:00. Client B starts a read of X at 10:00:00.001. Is it guaranteed to see X=5 in a linearizable system? Why or why not?
Three clients operate on a register. Client A writes X=1. Client B writes X=2 (starting after A finishes). Client C reads X=2. If C then reads again, what values are possible?

The “So What?”

Linearizability is the “gold standard” for correctness in distributed systems. It’s the model we intuitively expect when we think about shared state — if I write data and you read it afterward, you should see my write. The cost is enormous: every operation must contact enough replicas to guarantee ordering, which means coordination, which means latency. Linearizability is the most expensive consistency model, and you should only use it when correctness trumps performance.

✏️ 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.