Strong consistency models

What "Consistent" Really Means

Network partitions are not a question of if but when. Switches, NICs, host hardware, operating systems, disks, virtualization layers, and language runtimes—not to mention the program semantics themselves—all conspire to delay, drop, duplicate, or reorder our messages. In such an uncertain world, it's natural to want our software to maintain some semblance of intuitive correctness. But what, precisely, does "the right thing" mean in a distributed context?

A useful way to frame the question is to think of a system as a state plus a set of operations that transform that state. As the system runs, it moves through a sequence of states via a history of operations.

Consider the simplest case: a single variable, where the operations are reads and writes to that variable. In a sequential program, our intuition is clear. If we write a, read, read, then write b, subsequent reads should return b until the value changes again.

We call such a structure a register. A read returns the most recently written value, and that model feels so natural it seems like the only possibility. But it is not. A variable could theoretically return any value—a, d, or the moon. We would call such a system incorrect, simply because the observed history violates our intuitive model of how variables work.

This gives us a working definition of correctness: given rules that relate operations and state, the history of operations in a system must always follow those rules. We call those rules a consistency model.

Consistency models can be arbitrarily strict or loose. "A read returns the value from two writes ago, plus three, except when the value is four, in which case the read may return either cat or dog" is—technically—a consistency model. So is "every read always returns zero." The easiest model to satisfy is "no rules at all," since every system trivially conforms to it.

Formally, consistency models are sets of all allowed histories of operations. An execution that produces a history in that set is consistent. One that doesn't is inconsistent. If every possible execution of a system falls within the allowed set, the system satisfies the model. For real systems to be predictable, we need them to satisfy "intuitively correct" models.

Concurrency Breaks the Simple Picture

Concurrent programs introduce a complication: multiple logical threads of control ("processes") may operate against the same register. Since operations from different processes can interleave in more than one order, the single-process invariant—that a read returns the most recent write that came before it in the program text—no longer holds from the perspective of a single process. One process may write a and later read b, written by another process. That is not a violation of correctness; it is a sign that the register has become a place of coordination between processes, allowing them to share state.

The key insight is that a logical thread or process is really a constraint over allowed histories: operations belonging to the same process must occur in that process's order. Concurrency is therefore not an arbitrary free-for-all, but a partial order over operations.

Yet even this relaxed model breaks down once we account for the physical reality of distance.

Distance Introduces Ambiguity

In almost every real system, processes are not co-located with each other or with memory. A CPU is physically far from its DIMMs; a process in one datacenter is potentially thousands of kilometers from the databases it reads and writes. Information cannot travel faster than the speed of light, so operations cannot be instantaneous. A write takes time to reach the authoritative state, and the acknowledgment takes time to return.

Since messages travel at variable speeds, the true time an operation takes effect is ambiguous. A read invoked when the value is a might complete after a write of b has already arrived, returning b. Using invocation or completion time as the "true time" of an operation fails symmetrically. If a read arrives before a concurrent write, it returns the stale value while the current state is already b.

Any system where operations take time must therefore relax its consistency model to accommodate such ambiguous orderings. The question becomes: must we allow all orderings, or can we still impose some bounds on when operations take effect?

Linearizability: One Instant, One State

Even in a timed world, there are hard limits. No message travels faster than light, so no operation can take effect before invocation. Likewise, an operation cannot take effect after its completion is acknowledged, since that acknowledgment would have to travel back in time.

If we further assume there is a single global state, and that operations on it occur atomically, we get a powerful rule: each operation appears to take effect atomically at some point between its invocation and completion.

That model is linearizability. Although operations are concurrent and take time, the system behaves as if each one takes effect at a single, well-defined instant in a global linear order.

The "single global state" need not correspond to a single machine, and operations need not literally be atomic at the hardware level. A linearizable system can comprise smaller coordinating processes—which are themselves linearizable—each built from even smaller coordinating parts. What matters is the external history: it must look as though operations were sequentially applied to a single, atomic state.

Linearizability has immediate and consequential properties:

• No stale reads. Once a write completes, every subsequently invoked read must see that write (or a later value).
• No non-monotonic reads. It is impossible to read a new value and then an older one.
• Safe state mutation. Operations like compare-and-set can be used as building blocks for mutexes, semaphores, channels, counters, and arbitrary shared data structures, because each operation takes effect atomically.

These guarantees make linearizable systems relatively easy to reason about, which is why so many concurrent programming constructs are built on them. Variables in JavaScript are (independently) linearizable, as are volatile variables in Java, atoms in Clojure, and individual processes in Erlang. Mutexes and semaphores in most languages are linearizable too. Strong assumptions yield strong guarantees.

Sequential Consistency: Relaxing Time, Preserving Order

Suppose we drop the requirement that an operation take effect inside its invocation-to-completion interval. We allow operations to take effect before invocation or after completion, so long as operations from any single process still take effect in that process's program order. This is sequential consistency.

Sequential consistency permits more histories than linearizability, yet it is still a useful—and familiar—model. A web upload service, for instance, may put a video into a processing queue and immediately return success. The video takes effect minutes later, once it's fully processed. To the user, the upload appears atomic but not instantaneous.

Layered caches often behave similarly. A post on a social network takes time to propagate through caching tiers; different users see it at different times. However, each user sees that poster's operations in order. A new post does not appear before an earlier one it logically follows, and once visible, a post does not disappear.

Linearizability and sequential consistency share a core assumption: expectations about order and value can be grounded in real things—time, and process causality. Distributed systems that want predictable behavior for concurrent readers and writers generally pick one of these models as their starting point. Everything weaker is a tradeoff, made either explicitly at the application level or implicitly by the architecture beneath it.

Causal Ordering, Without Total Order

Enforcing a total order on every operation from every process is stricter than many applications actually need. Causal consistency narrows the requirement: only operations that are causally related must be seen in a consistent order. For instance, a reply to a blog post should never appear before the post it replies to. If each operation explicitly declares its dependencies, the database can withhold an operation until all of its causal predecessors are visible.

This model is weaker than per-process ordering. Operations from the same process that share no causal link may execute in any relative order, which still prevents many of the most confusing anomalous behaviors without the overhead of a global sequence.

Serializability: Strong Order, Weak Time

Serializability demands that the history of operations be equivalent to some single atomic order, but it imposes no constraints based on when operations were invoked or completed. This makes the model both surprisingly weak and surprisingly strong at the same time.

Because serializability only requires some total order, it permits operations to be placed at arbitrary points in time—even outside their real execution windows. In a serializable system, a read x could logically occur before x was ever written, or a write could be delayed indefinitely into the future. For the program

x = 1
x = x + 1
puts x

under serializability, the output could be nil, 1, or 2, since the three operations may be ordered in any way.

What makes serializability strong is that it demands a total order, excluding many classes of interleavings. In the program

print x if x = 3
x = 1 if x = nil
x = 2 if x = 1
x = 3 if x = 2

there is only one possible order, regardless of how the code was written. The value of x will progress from nil to 3 and the final print will reliably output 3.

This lack of real-time bounds makes plain serializability impractical for many real applications. Most systems advertised as serializable actually provide strong serializability, which adds the time constraints of linearizability. Compounding the terminology problem, the SERIALIZABLE isolation level in many SQL databases does not mean serializability at all, but rather something like repeatable read or snapshot isolation.

The Cost of Stronger Ordering

Weak consistency models admit more histories than strong ones. That flexibility is not free: enforcing a stricter order requires coordination among participants. The CAP theorem formalizes this tension. In precise terms, it applies to:

1. Consistency, meaning linearizability (equivalent to a linearizable register).
2. Availability, requiring that every request to a non-failing node completes successfully, even during arbitrarily long partitions.
3. Partition tolerance, meaning the network can fail to deliver messages.

Since networks are never perfectly reliable, a purely CA system is unachievable in practice. All distributed systems on commodity hardware are either AP or CP.

The CAP theorem alone only rules out totally available linearizable systems. But other results extend this impossibility to any model stronger than a specific threshold, including sequential consistency, serializability, snapshot isolation, repeatable read, and cursor stability. Models that cannot be made fully available are marked in red in Peter Bailis’ Highly Available Transactions paper.

Once the definition of availability is relaxed, more consistency models become possible. Requiring only that a client always reaches the same server permits causal consistency, PRAM, and read-your-writes models. Demanding total availability drops us to the weakest tier: monotonic reads, read committed, and similar partial orders. These are the models implemented by stores like Riak and Cassandra, as well as low-isolation SQL settings. Their histories form a patchwork of partial orders rather than a single, linear timeline.

Picking a Model Per Use Case

Some algorithms are only safe under linearizability. A distributed lock service, for example, needs strict time boundaries; without them, a lock could be held "from the future" or "from the past." Many data structures, however, do not require this. Eventually consistent sets, lists, trees, and maps can be safely expressed as CRDTs even under weak consistency.

Stronger consistency models inherently require more messages to coordinate ordering, which can also raise latency. This trade-off explains why CPU memory models are not linearizable by default, and why geographically distributed systems running across datacenters with hundreds of milliseconds of latency make similar compromises.

In practice, most architectures are hybrid. Large volumes of data are written to eventually consistent stores like S3, Riak, or Cassandra, with a pointer to that data written linearizably to Postgres, Zookeeper, or Etcd. Some systems, including Cassandra and Riak, support multiple consistency levels internally, reducing the number of separate components. No single model is universally correct—choosing one depends on the availability, latency, and safety requirements of each piece of the system.