Chapter 9: Consistency

Introduction

The introduction contrasts database consistency with the multiple meanings of consistency in distributed systems and previews the chapter’s topics.

• Database and distributed consistency: Distinguish database consistency—a transaction moving between states valid under application-level constraints—from the multiple interpretations of consistency in distributed systems, where components can fail and messages can be delayed, reordered, or lost.
  Why it matters: The distinction explains why this chapter examines more than one consistency model.
• Chapter consistency topics: Describe the chapter’s stated plan to explore consistency models and scenarios in which they arise, including linearizability, eventual consistency, and the CAP conjecture and theorem.
  Why it matters: This preview gives you a map of the questions the chapter will address.

Key terms: consistency, transaction, valid state, application-level constraints, consistency models, linearizability, eventual consistency, CAP conjecture and theorem

9.1 Consistency models

This section models operations and system histories so that consistency can be defined as satisfying a specific set of valid histories.

• Processes and operation boundaries: Describe a process as a sequential series of operations on objects, with each operation beginning at invocation and ending at completion. Explain that processes can operate concurrently even though each process waits for an operation’s response before issuing its next one.
  Why it matters: These boundaries make it possible to reason precisely about overlapping operations.
• Histories of concurrent operations: Explain that a system history records invocation and completion events in their real-time order, including the overlap between operations from different processes.
  Why it matters: A history is the evidence that a consistency model classifies.
• Model-specific consistency guarantees: Explain that a consistency model defines which histories are valid and that a system meets the model only if all its possible histories are valid under it. Distinguish violating a particular model’s guarantees from violating consistency as a concept.
  Why it matters: It makes claims about a system’s consistency testable and specific.

Key terms: process, object, operation, invocation, completion, history, invocation event, completion event, concurrent structure, consistency model

9.1.1 Common consistency models

The section connects application-specific correctness to consistency models: engineers choose acceptable histories, while common models provide established guarantees with different virtues and limitations.

• Application-specific consistency choices: Explain that engineers decide which system behaviors and histories are acceptable for their application, and that common, well-defined consistency models offer different guarantees with different virtues and limitations.
  Why it matters: A consistency model is useful only in relation to the behavior an application needs or can tolerate.

Key terms: correctness, consistency models, histories, virtues and limitations

9.1.2 Virtues and limitations

This section explains how consistency models relate by the histories they allow and why choosing a stronger or weaker model trades availability and latency against predictable behavior.

• Consistency model strength hierarchy: Explain that consistency models can be disjoint, overlap, or have a subset relationship, and that a model allowing fewer valid histories is stronger than one allowing more.
  Why it matters: The histories a model permits determine which outcomes an application must be prepared to handle.
• Consistency choice tradeoffs: Explain why stronger consistency can make behavior easier for developers to reason about but requires more coordination, reducing availability and increasing latency; weaker consistency reverses those pressures while exposing more effects of distribution.
  Why it matters: Choosing a consistency level means balancing predictable behavior against availability and response time.
• Surprising register read: Describe the example in which a process writes 10 to a register initially holding 0 but subsequently reads 0, and explain that whether this is correct depends on the promised consistency model: linearizability requires the most recent value, whereas eventual consistency can permit an intermittent older value.
  Why it matters: The same read can be an error under one contract and an allowed outcome under another.

Key terms: consistency models, valid histories, subset, superset, stronger, weaker, developer experience, coordination, availability, latency

9.2 Linearizability

Introduces linearizability as a strong consistency model that gives replicated objects a real-time recency guarantee and makes replication transparent.

• Recency and replication transparency: Explain that linearizability, also called atomic consistency, guarantees that once an operation completes, subsequent operations witness its effects. Describe how this makes a replicated distributed system behave like a nonreplicated, nondistributed one.
  Why it matters: This is the central promise that linearizability makes to users of a replicated system.
• Per-object real-time semantics: Describe linearizability as a real-time guarantee about individual operations on individual objects, defined according to the semantics of each object type. Note that queue and stack are the upcoming examples of different object types.
  Why it matters: The object's type determines what behavior a linearizable execution must preserve.

Key terms: linearizability, atomic consistency, recency guarantee, replication transparency, real-time guarantee, single operations, single objects, object type, queue, stack

9.2.1 Queue and stack

The section defines correct queue and stack behavior through operation traces, then explains how linearizability carries those object semantics into a distributed setting.

• Queue and stack ordering: Distinguish a queue’s first-in, first-out behavior from a stack’s first-in, last-out behavior using insert and remove operations. Describe why inserting a then b means removing a then b from a queue, but b then a from a stack.
  Why it matters: The same sequence of removals can be correct for one object type and incorrect for another.
• Object correctness and linearizability: Explain that correct behavior is defined for each object type in a single-process, single-object setting, and that linearizability preserves those semantics when multiple processes interact with multiple copies of the object.
  Why it matters: Linearizability needs an object-specific definition of correct behavior to preserve.

Key terms: queue, stack, FIFO, FILO, enqueue, dequeue, correctness, object type, single-process, single-object setting, linearizability

9.2.2 Formal definition of linearizability

Defines linearizability for an operation history, illustrates a violation caused by replication lag, and distinguishes a linearizable history from a system-wide guarantee.

• Sequential and concurrent histories: Distinguish a sequential history, in which each invocation is immediately followed by its completion, from a concurrent history, in which operations can interleave.
  Why it matters: This distinction makes clear what kind of ordering a linearizable concurrent history must be able to match.
• Two conditions for linearizability: Explain that a history is linearizable when an equivalent sequential history exists that yields the same results and preserves the real-time order of nonconcurrent operations. Describe the implication that an operation invoked after another completes must see the completed operation’s effects.
  Why it matters: These two conditions provide the test for whether observed operations could have behaved like a single sequential execution.
• Stale counter read: Explain why the illustrated replicated increment-only counter history is not linearizable: a read after the second increment returns 1 rather than 2, exposing replication lag.
  Why it matters: The counter gives a concrete example of how a stale replica can violate real-time ordering.
• History versus system guarantee: Distinguish the claim that one particular history is linearizable from the claim that a system is linearizable, which requires every possible history of that system to be linearizable.
  Why it matters: One successful execution does not establish a guarantee about all executions of a replicated system.

Key terms: history, sequential, concurrent, invocation, completion, linearizability, sequential equivalence, real-time ordering, nonconcurrent operations, replicated, distributed, increment-only counter

9.3 Eventual consistency

This section introduces eventual consistency as a weak model that guarantees eventual convergence, then points to the Amazon shopping cart as a practical example.

• Eventual convergence guarantee: Explain that eventual consistency is one of the weakest consistency models and guarantees that all nodes will eventually reach the same state, not that they have the same state immediately.
  Why it matters: The convergence guarantee is the starting point for understanding what eventual consistency does and does not promise.
• DynamoDB term and cart example: State that Werner Vogels popularized the term eventual consistency to describe Amazon DynamoDB’s consistency model, and that the Amazon shopping cart is introduced as an example for exploring its practical implications.
  Why it matters: The shopping cart gives the abstract convergence guarantee a practical setting.

Key terms: eventual consistency, convergence guarantee, Werner Vogels, Amazon DynamoDB, Amazon shopping cart

9.3.1 The shopping cart

A shopping-cart example shows how a network partition creates conflicting replicas and why an eventual-consistency policy must choose which user actions to preserve.

• Shopping cart replica conflict: Trace how two identical carts diverge during a network partition: both start with A, one client removes A and adds B, and another adds C to the other replica. Explain why restoring communication requires conflict resolution.
  Why it matters: The example makes the conflict behind eventual consistency concrete.
• Additions over removals policy: Explain Amazon's choice to retain added cart items over removed ones when resolving conflicts. Describe its tradeoff: added items do not vanish, but removed items may reappear, creating a potentially surprising user experience.
  Why it matters: A conflict-resolution rule determines which surprises users may encounter.

Key terms: replicas, network partition, conflict, consistent state, retain items added, removed items resurrect, availability

9.3.2 Variants of eventual consistency

Defines basic and strong eventual consistency by their shared delivery guarantee and different convergence guarantees.

• Basic eventual consistency guarantees: Explain that basic eventual consistency eventually delivers an update from one nonfaulty replica to every other nonfaulty replica, and that replicas eventually reach the same state after updates stop. State that it does not constrain behavior during continuous updates or the values reads may return before convergence.
  Why it matters: These limits clarify what basic eventual consistency does—and does not—promise a reader.
• Strong eventual consistency guarantees: Explain that strong eventual consistency shares basic eventual consistency’s eventual-delivery guarantee but requires any two replicas that have received the same set of updates to be in the same state. Distinguish this from basic consistency’s guarantee of convergence after updates stop.
  Why it matters: The distinction identifies the stronger condition under which replicas must agree.

Key terms: basic eventual consistency, eventual delivery, weak convergence, strong eventual consistency, strong convergence

9.3.3 Implementation

This section explains how replicas reconcile concurrent updates under eventual consistency, contrasting application-specific rules with operation-based and state-based CRDTs.

• Concurrent update reconciliation: Explain why eventual consistency requires conflict resolution when clients update replicas independently, and distinguish application-specific reconciliation from algorithmic reconciliation using CRDTs.
  Why it matters: Reconciliation determines how independently updated replicas can arrive at a shared state.
• Operation-based CRDT convergence: Describe how operation-based CRDTs replicate individual operations and the conditions that make replicas converge.
  Why it matters: Sending operations works only when their delivery and application preserve convergence.
• State-based CRDT convergence: Describe how state-based CRDTs replicate and merge entire states, including the properties required of the merge function and the grow-only set example.
  Why it matters: The merge rules explain how replicas can converge after receiving state from one another.

Key terms: eventual consistency, application-specific reconciliation, algorithmic reconciliation, conflict-free replicated data types, CRDTs, operation-based CRDTs, commutative CRDTs, operations, commutative, state-based CRDTs

9.4 Consistency, availability, and partition tolerance

Introduces CAP as a framework for discussing precisely defined tradeoffs in replicated distributed systems and warns that it is often misunderstood.

• CAP framework and scope: Explain that CAP concerns tradeoffs among specific definitions of consistency, availability, and partition tolerance in replicated, distributed systems, rather than loose uses of those words.
  Why it matters: Keeping the definitions precise helps prevent a common misunderstanding of CAP.

Key terms: CAP, consistency, availability, partition tolerance, replicated, distributed systems

9.4.1 History

This section traces CAP from Brewer’s conjecture to a formally proved theorem and explains why inevitable network partitions make “pick two out of three” misleading.

• CAP conjecture and theorem: Distinguish Brewer’s 2000 CAP conjecture from Gilbert and Lynch’s 2002 CAP theorem: Brewer proposed that a distributed system cannot simultaneously achieve consistency, availability, and partition tolerance, while Gilbert and Lynch supplied a formal proof of their interpretation.
  Why it matters: The distinction keeps an informal claim and a formally proved result from being treated as identical.
• Partition-time CAP choice: Explain why the original “pick two out of three” framing is misleading: realistic systems must account for inevitable network partitions, so partition tolerance is not an optional choice; when a partition occurs, the choice is between consistency and availability, yielding CP or AP systems.
  Why it matters: This framing identifies the tradeoff CAP asks you to consider during a network partition.

Key terms: CAP conjecture, CAP theorem, consistency, availability, partition tolerance, pick two out of three, network partitions, CP, AP

9.4.2 Conjecture vs. theorem

This section gives the informal meanings of consistency, availability, and network partitions used to discuss the CAP conjecture and theorem.

• Consistency and availability guarantees: Distinguish consistency as a safety property from availability as a liveness property in the section’s informal definitions. Explain that a consistent read may fail but, if successful, reflects the most recent write; an available read eventually succeeds but may return an older value.
  Why it matters: These definitions clarify what each CAP guarantee requires of a read.
• Network partition failure mode: Describe a network partition as a failure that divides nodes into segments and loses messages sent between segments. Explain that CAP’s consistency-or-availability choice concerns replicated systems under partitioning, while the conjecture and theorem are based on different interpretations not specified further here.
  Why it matters: The partition is the failure condition under which the section frames CAP’s choice.

Key terms: consistency, availability, safety property, liveness property, network partition, replicated system, conjecture, theorem

9.4.3 CAP theorem

This section presents Gilbert and Lynch’s CAP theorem through its system model and contradiction proof, then explains why the theorem should not be used as a blanket design argument.

• Partitioned system model: Describe the assumptions of Gilbert and Lynch’s example: three nodes communicate over an asynchronous network without clocks, while a permanent partition prevents N1 and N2 from communicating even though C can contact both.
  Why it matters: The impossibility result depends on the model’s specific assumptions.
• CAP contradiction proof: Trace the proof by contradiction: assume the partitioned system can remain both consistent and available, then show that an acknowledged write of v1 at N1 followed by a read at N2 returns the old value v0 because the update cannot cross the partition.
  Why it matters: The write-and-read sequence makes the conflict between the assumed properties observable.
• Limits of CAP arguments: Distinguish Brewer’s intuitive, practical conjecture from Gilbert and Lynch’s formal theorem, and explain why the theorem’s model may not settle a particular engineering decision. Describe both its value in highlighting tradeoffs and the risk of using “CAP” to end discussion instead of naming more precise tradeoffs.
  Why it matters: A theorem is useful only when its assumptions fit the system and question being discussed.

Key terms: system model, asynchronous network, permanent network partition, C, N1, N2, proof by contradiction, consistency, availability, partition tolerance

9.5 Summary

The chapter summary contrasts consistency guarantees and their tradeoffs, from linearizability and eventual consistency to the limits imposed by network partitions.