Strong Consistency

Imagine you're designing a system where multiple users can simultaneously bid on an auction item. User A places a bid of $100 from New York. At almost the same instant, User B places a bid of $105 from Tokyo. Which bid wins? When each user refreshes their screen, what should they see?

In a world of distributed systems—where data is replicated across continents for availability and performance—answering this seemingly simple question becomes extraordinarily complex. Without strong guarantees, User A might see their $100 bid as the current highest, while User B simultaneously sees $105 as the highest. Worse, a third user might see an older bid of $95 as the current highest.

This is where linearizability enters the picture. It's the strongest practical consistency model in distributed systems, providing a guarantee that makes a distributed system appear to behave as if there's only a single copy of the data, with all operations happening atomically at some point in time.

Linearizability (also known as atomic consistency or strong consistency) is a consistency model that provides the strongest guarantee about how operations on shared data appear to clients. At its core, linearizability makes a powerful promise:

Once a write operation completes, all subsequent reads (from any client, on any replica) will return that written value or a more recent value. The system behaves as if there is only one copy of the data, and all operations are atomic.

This might sound straightforward, but in a distributed system where data exists on multiple machines across the globe, achieving this guarantee is remarkably challenging and comes with significant trade-offs.

The Formal Definition

Formally, a system is linearizable if:

1. Each operation appears to take effect atomically at some instant between its invocation and response.
2. This instant is called the linearization point — the logical moment when the operation "happens."
3. The order of these linearization points must be consistent with the real-time order of non-overlapping operations.

In simpler terms: if operation A completes before operation B starts (in real time), then A must appear to have happened before B in the total order. However, if A and B overlap in time, the system can order them in either way—as long as it picks one order consistently.

A Concrete Example

Consider a simple key-value store with operations:

• write(x, v) — writes value v to key x
• read(x) — reads the current value of key x

Let's trace through a scenario with three clients:

In this example:

• Client A's write linearizes at T3
• Client B's read overlaps with A's write, so it could return either 0 or 1—but once it returns 1, all subsequent reads must return 1 or later values
• Client C's read, starting after A's write completes, must return 1 (or a more recent value)

The key insight: linearizability ensures that once you observe a value, you can never "go back in time" and see an older value.

The concept of linearization points is central to understanding and proving linearizability. Every operation in a linearizable system has a linearization point—a specific instant in time when the operation "logically takes effect."

Properties of Linearization Points

1. Between invocation and response: The linearization point must occur after the operation is invoked and before the response is returned to the client.

2. Atomic: All effects of the operation happen instantaneously at this point. There's no intermediate state.

3. Ordered: Linearization points of all operations form a total order that respects:

   • The real-time order of non-overlapping operations
   • The sequential semantics of the data structure

Visualizing Linearization Points

The Challenge of Overlapping Operations

When operations overlap in time, the system has flexibility in ordering their linearization points. However, this flexibility comes with constraints:

Legal orderings must be consistent with sequential semantics. If a read overlaps with a write, the read can see either the old or new value. But once any read returns the new value, all subsequent reads must also return the new value (or an even newer one).

This is what distinguishes linearizability from weaker models. Consider this scenario:

Understanding linearizability requires comparing it with other consistency models. Each model makes different trade-offs between strength of guarantees and system performance/availability.

The Consistency Spectrum

Consistency models form a spectrum from strongest to weakest:

Linearizability vs. Sequential Consistency

The distinction between these two is subtle but crucial:

Sequential Consistency requires that all processes see the same order of operations, and this order respects the program order within each process. However, it says nothing about real-time ordering between processes.

Linearizability adds the real-time constraint: if operation A completes before B starts (in wall-clock time), then A must appear before B in the global order.

Example of the difference:

Process 1: write(x, 1)  [completes at T1]
Process 2: read(x)      [starts at T2 where T2 > T1]

Sequentially Consistent: read(x) could return 0 (if ordered before write)
Linearizable: read(x) MUST return 1 (write completed before read started)

This real-time guarantee makes linearizability much stronger—and much more expensive to implement.

Linearizability vs. Serializability

These terms are often confused because they sound similar and relate to ordering guarantees:

Serializability is a property of transactions (groups of operations). It guarantees that the outcome of executing concurrent transactions is equivalent to some serial (one-at-a-time) execution.

Linearizability is a property of single operations on single objects. It guarantees that each operation appears atomic.

They operate at different levels:

• Linearizability: per-object, per-operation
• Serializability: per-transaction (possibly spanning multiple objects)

Strict Serializability combines both: transactions appear to execute in some serial order that respects real-time ordering. This is what systems like Google Spanner provide.

Linearizability isn't an academic curiosity—it's essential for implementing many real-world systems correctly. Without linearizability, certain applications become impossible or extremely difficult to build correctly.

Critical Use Cases Requiring Linearizability

1. Distributed Locking

Distributed locks coordinate access to shared resources across multiple processes. Without linearizability, two processes could simultaneously believe they hold the lock:

Process A: acquireLock() returns SUCCESS
Process B: acquireLock() returns SUCCESS  // DISASTER!

If the lock service isn't linearizable, both processes might see a state where the lock is available, leading to concurrent access to the protected resource.

2. Leader Election

In systems with a single leader (databases, message queues, coordination services), exactly one node must be elected leader at any time. Non-linearizable systems can result in a "split-brain" scenario:

Node A: checkLeader() returns 'A is leader'
Node B: checkLeader() returns 'B is leader'  // SPLIT-BRAIN!

Both nodes believe they're the leader, potentially causing data corruption as both accept writes.

3. Unique Constraint Enforcement

Enforcing uniqueness (usernames, email addresses, transaction IDs) requires linearizability. Consider username registration:

4. Compare-and-Swap (CAS) Operations

Many distributed algorithms rely on atomic compare-and-swap:

cas(key, expectedValue, newValue)

This operation should atomically: read the current value, compare it to the expected value, and only write the new value if they match. Without linearizability, the "read" portion might see stale data, breaking the atomicity guarantee.

5. Financial Systems

Bank transfers, trading systems, and payment processing require linearizability to prevent:

• Double-spending
• Lost transactions
• Inconsistent balances across systems

Achieving linearizability in a distributed system requires careful design. There are several fundamental approaches, each with different trade-offs:

Approach 1: Single Leader (Synchronous Replication)

The simplest approach: route all reads and writes through a single node.

How it works:

1. All writes go to the leader
2. Leader applies write synchronously (possibly waiting for replicas)
3. Leader responds to client
4. All reads also go to the leader

Trade-offs:

• ✅ Simple to implement and reason about
• ❌ Leader is a single point of failure
• ❌ All traffic goes through one node (bottleneck)
• ❌ Latency equals round-trip to leader + processing

Approach 2: Consensus Protocols

Consensus protocols (Paxos, Raft, Viewstamped Replication) achieve linearizability through coordinated agreement among a quorum of nodes.

How it works:

1. Client sends request to a replica (often the leader)
2. Leader proposes the operation to all replicas
3. Wait for a quorum (majority) to acknowledge
4. Operation is committed and response sent to client

Why it's linearizable:

• Any two quorums must overlap by at least one node
• This overlap ensures information propagates correctly
• No operation can commit unless a majority agrees
• Reads can be linearizable by going through the same process or using "linearizable leases"

Approach 3: Linearizable Quorum Reads

In quorum-based systems, achieving linearizable reads is subtle. Simply reading from a quorum is not sufficient—you might read from a quorum that hasn't yet seen the latest write.

Techniques for linearizable reads:

1. Read through consensus: Route reads through the same consensus protocol as writes
2. Lease-based reads: Leader holds a lease; reads are valid while lease is active
3. Read repair with quorum intersection: Read from quorum, write any newer values back

Each technique has latency implications:

• Consensus reads: ~2 round trips
• Lease reads: 1 round trip (to leader), but adds complexity
• Quorum reads with repair: Variable, depending on conflicts

Claiming linearizability is easy; proving it is hard. How do we verify that a system actually provides linearizable operations?

The Linearizability Checker

Given a history of operations (invocations and responses with timestamps), we check if there exists a valid linearization:

1. Collect all operations with their start and end times
2. Try to find an ordering of linearization points such that:
   • Each point falls between invocation and response
   • The sequential execution with this ordering is valid
   • Non-overlapping operations respect real-time order

The challenge: This is an NP-complete problem in general. Checking linearizability of arbitrary histories is computationally hard.

Practical Testing Approaches

1. Jepsen Testing Framework

Jepsen is the industry-standard tool for testing distributed systems' consistency claims:

• Runs operations concurrently against the system
• Introduces failures (network partitions, node crashes)
• Records complete history of operations
• Uses linearizability checkers (Knossos, Elle) to verify histories
• Has uncovered bugs in Redis, MongoDB, CockroachDB, etcd, and many others

2. WGL Algorithm

The Wing & Gong algorithm provides a practical approach:

• Constructs a graph where nodes are operations
• Edges represent ordering constraints
• Checks for cycles (cycles = not linearizable)
• Optimized for common patterns

3. Formal Verification

For critical systems, formal methods can prove linearizability:

• TLA+ specifications
• Model checking with bounded state spaces
• Theorem proving (Coq, Isabelle)

We've explored linearizability—the gold standard of distributed systems consistency. Let's consolidate the key concepts:

What's Next:

Now that we understand what linearizability guarantees, the next page explores the implementation costs—what it takes to build a linearizable system and why these costs make linearizability impractical for many use cases.