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:
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.
