Consistency in Distributed Systems

Imagine a banking system where you transfer $1,000 from your savings account to your checking account. You execute the transfer, receive a confirmation, and then immediately check your checking account balance—only to find the $1,000 hasn't arrived. You panic. Is it lost? No—it's simply that you're reading from a different database node that hasn't received the update yet.

This scenario illustrates one of the most fundamental challenges in distributed systems: consistency. When data is replicated across multiple machines, ensuring that all nodes reflect the same state at the same time becomes extraordinarily difficult—and in some cases, mathematically impossible without sacrificing other properties.

Consistency, in the context of the CAP theorem, is the guarantee that every read receives the most recent write. It's the promise that a distributed system behaves as if it were a single machine with a single copy of the data.

The term "consistency" is notoriously overloaded in computer science. Before we can discuss CAP theorem consistency, we must disambiguate it from other uses:

ACID Consistency (Database Transactions): In traditional database theory, consistency means that transactions bring the database from one valid state to another, respecting all defined integrity constraints (foreign keys, unique constraints, check constraints). This is a local property—it applies to a single database instance.

CAP Consistency (Distributed Systems): In distributed systems, consistency refers to data agreement across nodes. Specifically, it guarantees that all nodes in the distributed system see the same data at the same time. If you write a value and immediately read it from any node, you get the value you just wrote.

Eventual Consistency: A weaker form where, if no new updates are made, all nodes will eventually converge to the same value—but there's no guarantee about when.

The Formal Definition:

In CAP theorem terms, a system provides consistency if and only if:

1. All reads return the most recently completed write's value
2. Once a write completes, all subsequent reads see that write
3. There is a total order of operations that all nodes agree upon

This is equivalent to what theoreticians call linearizability—the strongest form of consistency guarantee in distributed computing.

Linearizability is the consistency model that CAP theorem refers to as 'C'. It's the formally rigorous definition of what it means for a distributed system to behave like a single-copy system.

Definition: A system is linearizable if:

1. Each operation appears to take effect instantaneously at some point between its invocation and response
2. There exists a total ordering of all operations that is consistent with real-time ordering
3. Each read returns the value of the most recent write in this total order

The Key Insight: Linearizability creates the illusion that there is only one copy of the data, and all operations act on it atomically. Even though data may be replicated across many nodes, the system behaves as if reads and writes happen at a single point.

Understanding Linearization Points:

Every operation in a linearizable system has a linearization point—the instant when it conceptually takes effect. This point must:

• Fall between the operation's start and end time
• Respect real-time ordering: if operation A completes before B starts, A's linearization point must precede B's
• Create a consistent total order when all operations are arranged by their linearization points

The beauty and challenge of linearizability is that the system doesn't need to explicitly timestamp operations. It just needs to behave as if such points exist.

While linearizability is the strongest consistency model, it's not the only one. In practice, systems operate across a spectrum of consistency guarantees, each with different properties, performance characteristics, and use cases.

Understanding this spectrum is crucial because:

1. Stronger consistency is more expensive (latency, availability, throughput)
2. Many applications can tolerate weaker consistency
3. Choosing the right consistency level is a critical architectural decision

Sequential Consistency:

Slightly weaker than linearizability. All operations appear in some sequential order that all processes agree on, but this order doesn't have to respect real-time. A read might return a value from the 'future' in real-time, as long as the sequential order is maintained.

Causal Consistency:

Preserves the ordering of causally related operations. If operation A happens before operation B (and there's a causal relationship), then all nodes see A before B. Operations that aren't causally related can appear in any order.

Example: In a social media app, a reply must appear after the original post on all nodes. But two independent posts can appear in different orders on different nodes.

Session Guarantees (Read-Your-Writes, Monotonic Reads):

These are per-session guarantees that provide some consistency within a client's session without requiring global consistency:

• Read-Your-Writes: A client always sees its own updates. You post a message and immediately see it in your feed.
• Monotonic Reads: Once a client sees a value, it never sees an older one. If you saw 10 comments on a post, you'll never see only 8 later.
• Monotonic Writes: A client's writes are applied in the order issued.
• Writes Follow Reads: A write that follows a read will see that read's data.

Eventual Consistency:

The weakest practical guarantee. If updates stop, all replicas will eventually converge to the same value. No guarantee about when, and reads during updates may return any version.

Pitfall: 'Eventually' has no time bound. In theory, convergence could take seconds or hours. In practice, it's usually fast, but there are no guarantees.

Achieving linearizability in a distributed system is challenging because:

1. Network delays vary unpredictably — Messages between nodes take different amounts of time
2. Clocks are imperfect — There's no global clock all nodes can reference precisely
3. Nodes can fail — A node might crash in the middle of an operation

Despite these challenges, several techniques enable strong consistency:

The Quorum Approach in Detail:

Quorum-based systems are fundamental to understanding how consistency is achieved. The key insight is that if both reads and writes contact overlapping sets of nodes, consistency is guaranteed.

For a system with N nodes:

• W = number of nodes that must acknowledge a write
• R = number of nodes that must respond to a read

Quorum Condition: W + R > N

If this condition holds, every read quorum overlaps with every write quorum, so reads always see at least one node with the latest value.

Strong consistency doesn't come free. There are fundamental costs that cannot be engineered away—only traded against other properties:

Latency Cost: For linearizability, every operation must reach agreement across nodes. This means:

• Writes must wait for acknowledgments from W nodes
• Reads might need to contact R nodes and await responses
• In a geographically distributed system, cross-datacenter latency becomes the bottleneck

Example: A write that must synchronously replicate to a datacenter 100ms away adds at least 100ms to every write operation.

Throughput Cost:

Coordination limits parallelism. If all writes must be serialized through a single leader, that leader becomes a bottleneck. More nodes don't help throughput for writes—they may even hurt it due to coordination overhead.

Availability Cost:

This is the crux of CAP: during a network partition, you must choose between:

• Maintaining consistency: Reject operations that can't reach quorum (sacrifcing availability)
• Maintaining availability: Accept operations locally, risk inconsistency when the partition heals

Strong consistency systems are by design unavailable during partitions. This is not a bug—it's the mathematically proven trade-off that CAP describes.

Let's examine how production systems navigate consistency trade-offs:

Google Spanner: Achieves external consistency (stronger than linearizability!) using TrueTime—GPS clocks and atomic clocks synchronized across all datacenters. Transactions are committed with timestamps that reflect real-time ordering globally. The cost: significant infrastructure investment and latency (commits wait for clock uncertainty to pass).

Apache ZooKeeper: Provides linearizable writes and sequential consistency for reads. Used for coordination, configuration, and leader election. Sacrifices throughput for correctness—intended for small, critical data, not high-volume operations.

Amazon DynamoDB: Offers a choice: eventually consistent reads (default, cheaper, faster) or strongly consistent reads (costs more, higher latency). Applications choose per-read based on their needs.

Multi-Level Consistency Strategies:

Modern systems often use different consistency levels for different data types:

• User authentication data: Strong consistency (can't risk stale credentials)
• User profile data: Read-your-writes within session, eventual across sessions
• Social feed data: Eventual consistency (acceptable to miss a post briefly)
• Financial ledgers: Linearizable within transactions
• Analytics data: Eventual (correctness not required in real-time)

This polyglot consistency approach lets systems optimize each use case appropriately.

We've explored the 'C' in CAP theorem in depth. Let's consolidate the key insights:

What's Next:

Consistency is just one corner of the CAP triangle. In the next page, we'll explore Availability—the guarantee that every request receives a response. You'll learn how availability is defined, what it means for a system to be 'highly available,' and why maintaining availability during partitions forces you to sacrifice consistency.