9 Consistency

 

This chapter covers

  • Consistency
  • Linearizability
  • Eventual consistency
  • The CAP conjecture and theorem

In database systems, consistency has one interpretation: A transaction transitions the database from one consistent state to another consistent state. In distributed systems, however, consistency has multiple interpretations, each captured as a consistency model.

9.1 Consistency models

To focus our attention on consistency, in this chapter, we reason about a distributed system as a collection of concurrent processes operating on a collection of objects: A process is a sequence of operations on objects. The object’s type defines the set of possible values and the set of possible operations to create and manipulate object instances. An operation is not instantaneous; instead, an operation is delineated by its invocation and completion. We model an operation on an object as an invocation and a completion pair:

Operation = Invocation • Completion

Processes are strictly sequential, that is, each process issues a sequence of operations to objects, alternately issuing an invocation and then waiting to receive the associated response (see Figure 9.1).

Figure 9.1 A process is a sequence of steps, that is, a sequence of operations on objects. An operation is delineated by its invocation and completion.

9.1.1 Common consistency models

9.1.2 Virtues and limitations

9.2 Linearizability

9.2.1 Queue and stack

9.2.2 Formal definition of linearizability

9.3 Eventual consistency

9.3.1 The shopping cart

9.3.2 Variants of eventual consistency

9.3.3 Implementation

9.4 The CAP conjecture and CAP theorem

9.4.1 History

9.4.2 Conjecture versus theorem

9.4.3 The CAP Theorem

9.5 Summary