Consistency Trade offs · Linearizability

Key Question

At what exact moment does a write or read “take effect” in a linearizable system?

Deep Dive

Every operation in a linearizable system has a linearization point — a single instant in time between the operation’s invocation and response when it appears to take effect atomically. This is the “magic moment” when the operation becomes visible to all subsequent operations. Identifying these points is crucial for understanding and debugging distributed systems.

Write to a Distributed Register

Consider a register replicated across 3 nodes (R1, R2, R3) with a write quorum of 2 (w=2). Client A wants to write X=42.

Client A: [--- send(42) to R1,R2,R3 ---|---- ack from R2,R3 ----]
                   ^                        ^
            invokes write              response received
                          
R1: ---[store]---[ack]--->  (Node 1 stores, responds)
R2: ---[store]---[ack]--->  (Node 2 stores, responds)
R3: ---[store]---[ack]--->

The linearization point occurs when the second acknowledgment arrives (since w=2). At this exact moment, the value X=42 is “officially” written. Why the second ack? Because before it, only one node acknowledged — a concurrent read could talk to the other two nodes and miss the value. After the second ack, at least one node in any read quorum (if read quorum overlaps with write quorum) will have the value.

But wait — what if the write quorum doesn’t overlap with the read quorum? Then linearizability is impossible. The requirement for linearizability is that read quorums and write quorums must intersect. With 3 nodes, if w=2 and r=2, they always intersect (2+2 > 3).

Read from a Distributed Register

For a read, the linearization point depends on the implementation:

Read from majority — linearization point is when the majority responds. The read assembles the most recent value from the responses.
Read with condition check — if the read checks a version number, the linearization point is when it validates that no newer version exists.
Single-replica read — linearization point is when the response is returned, BUT this is only safe if the write quorum guarantees the chosen replica has the latest value.

Client B: [--- read request ---|---- receive latest from R2,R3 ----]
              ^                         ^
         invokes read             response received
                         
Linearization point for the value returned: when the read assembled
its response from the quorum (the moment it picked the latest version).

Compare-and-Swap (CAS)

The linearization point of a CAS operation is the exact moment the CAS succeeds or fails. There is no ambiguity:

CAS(X, expected=42, new=99)
                   
Time:  [-- invoke CAS on 3 replicas --|--- success: X was 42 ---]
                                        ^
                                   Linearization point

If X was 42, the CAS linearizes at the instant the majority acknowledges the update. If X was not 42, it linearizes at the instant the majority confirms no change occurred.

The Overlap Rule

An important consequence: if operation A linearizes before operation B invokes, then B must see A’s effect:

A:   [---|================|----]
         LP_A
              B:      [---|============|----]
                        LP_B must be after LP_A

If A’s linearization point falls within B’s invocation-response interval, A and B CONCURRENT — either order is valid.

Check Your Understanding

With 5 replicas, w=3, r=3, what is the earliest possible linearization point for a write?
Can a read that contacts only one replica be linearizable? If so, under what conditions?
Two concurrent writes both write to the same register. How does the system decide which one linearizes first?

The “So What?”

Understanding linearization points helps you debug consistency issues in production. If a read returns stale data, the question is: “Did this read’s linearization point occur before or after the write’s linearization point?” Draw the timeline. If the read’s linearization point is after the write’s, and you still see stale data, the system is not linearizable — you’ve found a bug, and it’s time to check quorum intersection or clock skew.

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