This clickable map (adapted from Bailis, Davidson, Fekete et al and Viotti & Vukolic) shows the relationships between common consistency models for concurrent systems. Arrows show the relationship between consistency models. For instance, strict serializable implies both serializability and linearizability, linearizability implies sequential consistency, and so on. Colors show how available each model is, for a distributed system on an asynchronous network.
Consistency in Non-Transactional Distributed Storage Systems.pdf
Jepsen analyses the safety properties of distributed systems–most notably, identifying violations of consistency models. But what are consistency models? What phenomena do they allow? What kind of consistency does a given program really need?
In this reference guide, we provide basic definitions, intuitive explanations, and theoretical underpinnings of various consistency models for engineers and academics alike.
Distributed systems are a type of concurrent system, and much of the literature on concurrency control applies directly to distributed systems. Indeed, most of the concepts we’re going to discuss were originally formulated for single-node concurrent systems. There are, however, some important differences in availability and performance.
Systems have a logical state which changes over time. For instance, a simple system could be a single integer variable, with states like 0, 3, and 42. A mutex has only two states: locked or unlocked. The states of a key-value store might be maps of keys to values, for instance: {cat: 1, dog: 1}, or {cat: 4}.
A process1 is a logically single-threaded program which performs computation and runs operations. Processes are never asynchronous—we model asynchronous computation via independent processes. We say “logically single-threaded” to emphasize that while a process can only do one thing at a time, its implementation may be spread across multiple threads, operating system processes, or even physical nodes—just so long as those components provide the illusion of a coherent singlethreaded program.
An operation is a transition from state to state. For instance, a single-variable system might have operations like read and write, which get and set the value of that variable, respectively. A counter might have operations like increments, decrements, and reads. An SQL store might have operations like selects and updates.
In theory, we could give every state transition a unique name. A lock has exactly two transition: lock and unlock. An integer register has an infinite number of reads and writes: read-the-value-1, read-the-value-2, …, and write-1, write-2, ….
To make this more tractable, we break up these transitions into functions like read, write, cas, increment, etc., and values that parameterize those functions. In a single register system, a write of 1 could be written: