9 Consistency
This chapter reframes consistency for distributed systems as a spectrum of formally defined consistency models that classify which histories of operations (invocations and completions over shared objects) are valid. A history captures real-time ordering and concurrency, and a system is consistent with respect to a model if all its possible histories satisfy that model’s predicate. Models relate by strength: stronger models admit fewer histories and are easier for developers to reason about, while weaker models admit more histories and expose more of the realities of distribution. Choosing among them is a trade-off: stronger consistency improves developer experience by hiding replication and concurrency quirks at the cost of coordination, availability, and latency; weaker consistency does the opposite, favoring availability and performance while tolerating anomalies that the application must handle.
Linearizability, one of the strongest models, provides a real-time recency guarantee: once an operation completes, all later operations see its effect. Formally, a concurrent history is linearizable if there exists an equivalent sequential history that preserves the real-time order of non-overlapping operations, defined per object type. Intuitively, it makes a replicated system behave like a single, non-replicated one, yielding replication transparency and predictable semantics for objects such as queues, stacks, or registers. Non-linearizable outcomes typically reveal replica lag or reordering under concurrency, producing stale reads. Achieving linearizability in practice requires coordination mechanisms (e.g., via consensus), which increase latency and reduce fault tolerance during partitions.
Eventual consistency sits near the other end of the spectrum and offers convergence rather than recency: if updates stop, all non-faulty replicas eventually agree. In basic eventual consistency, updates are eventually delivered and replicas converge after quiescence; strong eventual consistency additionally guarantees that replicas with the same set of updates are in the same state. Conflict resolution can be application-specific (e.g., favoring adds over removes in a shopping cart) or algorithmic via CRDTs, which ensure convergence using commutative operations (operation-based) or associative, commutative, idempotent merges (state-based). The chapter also clarifies CAP: under network partitions (which are inevitable), a replicated system must choose between availability and a specific notion of consistency. The original conjecture is intuitive but informal; the theorem is formal but narrow in assumptions, and both are often oversimplified. Practitioners should use precise, context-appropriate consistency and availability definitions rather than rely on blanket CP/AP labels.
A process is a sequence of steps, that is, a sequence of operations on objects. An operation is delineated by its invocation and completion.
A consistency model classifies histories as good (valid) histories and bad (invalid) histories.
Common consistency models and their relationship (Source: https://jepsen.io/consistency)
Disjoint, overlapping, and subsets
Consistency levels of Azure CosmosDB (https://learn.microsoft.com/en-us/azure/cosmos-db/consistency-levels)
Stronger versus weaker consistency models
Unexpected and unwanted surprises
Non-linearizable history of a replicated, distributed increment only counter
Eventual Consistent Shopping Cart
Eric Brewer, PODC Keynote “Towards Robust Distributed Systems”, 2000
Gilbert’s & Lynch’s System Model
Summary
- Consistency models allow developers to choose the guarantees that best align with their application’s requirements.
- Consistency models separate system histories (traces) into valid (correct) and invalid (incorrect) histories.
- Stronger consistency models improve the developer experience but reduce availability and increase latency, while weaker models prioritize availability and latency at the expense of developer experience.
- Linearizability, one of the strongest consistency models, ensures that operations on distributed and replicated systems appear as if the system were not distributed or replicated.
- Eventual consistency, one of the weakest models, guarantees that all replicas eventually converge to the same state, often requiring conflict resolution through application logic or algorithms like CRDTs.
- CAP describes the trade-offs between consistency, availability, and partition tolerance, demonstrating that systems must compromise on consistency or availability during network partitions.
- Brewer’s original interpretation of CAP is intuitive and practical, but it is not a theorem. Gilbert's and Lynch’s subsequent interpretation of CAP is a theorem but is neither intuitive nor practical.
FAQ
What is a consistency model in distributed systems?
A consistency model is a rule set (a predicate) that classifies which execution histories of a system are valid. It operates over sequences of invocation and completion events for operations on objects. A system is consistent with respect to a model if all of its possible histories are members of that model’s valid set.
What is a “history,” and how are operations represented?
A history is the real-time-ordered sequence of all operation events in a system. Each operation is modeled as two events: its invocation and its completion. Processes are sequential (they alternate invoke/complete), but operations from different processes may interleave in the global history.
What’s the difference between sequential and concurrent histories?
In a sequential history, every operation’s invocation is immediately followed by its completion—no interleaving. In a concurrent history, invocations and completions can interleave: one operation may be invoked before another earlier operation completes.
How do stronger and weaker consistency models relate?
Consistency models form a hierarchy via set inclusion over valid histories. A “stronger” model admits fewer valid histories (subset), offering tighter guarantees but requiring more coordination. A “weaker” model admits more histories (superset), exposing more effects of distribution while enabling higher availability and lower latency.
What does linearizability guarantee?
Linearizability (atomic consistency) provides a real-time recency guarantee: once an operation completes, all later operations observe its effect. It preserves single-object, single-operation semantics across replicas, making a replicated system behave like a single, non-replicated one (replication transparency).
How is linearizability defined formally?
- Sequential equivalence: There exists a sequential history equivalent to the concurrent history (same results).
- Real-time ordering: If one operation completes before another begins in real time, the sequential history respects that order.
Linearizability is defined per object type (e.g., queue vs. stack) to honor each type’s semantics.
What’s the difference between a linearizable history and a linearizable system?
A linearizable history is a single execution that admits an equivalent sequential ordering respecting real time. A linearizable system is one in which every possible history is linearizable—i.e., the system guarantees linearizability.
What is eventual consistency, and what are its variants?
Eventual consistency provides convergence: replicas that keep receiving updates eventually reach the same state.
- Basic eventual consistency: (1) Eventual delivery (updates on non-faulty replicas are eventually delivered to all non-faulty replicas), and (2) Weak convergence (after updates stop, replicas eventually agree).
- Strong eventual consistency: (1) Eventual delivery, and (2) Strong convergence (any two replicas that have received the same set of updates are in the same state).
How are conflicts handled under eventual consistency?
Two common approaches:
- Application-specific reconciliation: The app defines rules (e.g., “add-wins” in a shopping cart) to resolve divergent updates.
- Algorithmic reconciliation with CRDTs: Data types designed so replicas converge automatically. Operation-based CRDTs require no lost operations, exactly-once effective application, and a commutative apply function. State-based CRDTs require a merge function that is associative, commutative, and idempotent.
What does the CAP framework actually say, and how are the conjecture and theorem different?
CAP characterizes trade-offs among Consistency, Availability, and Partition Tolerance in replicated systems. In the presence of partitions (assumed possible), a system must choose between consistency and availability.
Differences:
- Conjecture (Brewer, 2000): Intuitive formulation (e.g., single-copy serializability, timely response by some node, temporary partitions).
- Theorem (Gilbert & Lynch, 2002): Formal proof under an asynchronous model with permanent partitions, defining consistency as linearizability of a read/write register and availability as eventual response by any node.
“Pick 2 of 3” is misleading because partition tolerance is not optional in realistic systems.
Think Distributed Systems ebook for free
