When it comes to implementing distributed systems, there are a whole variety of consistency models to choose from. Going through papers on system implementations of varying degrees of consistency guarantees (e.g.Spanner or Bayou), I found myself mixing up strictly different terms and models. To prevent further confusion, I thought it would be a good idea to cover some key terminologies here.

What is Consistency?

There are myriads of different consistency guarantees, but what is consistency in the context of distributed systems in the first place? Different definitions may exist, but I found the following the clearest: consistency is a test on the execution of operations¹ (WLOG, let’s limit the type of operations to read() and write(v) for the sake of simplicity): if the test for a consistency condition \(C\) passes on execution \(e\), we say \(e\) is $C$-consistent.

We can also define hierarchies between different consistency semantics: \(C_s\) is stronger than \(C_w\) if and only if the set of executions accepted by \(C_s\) is a subset of the set of executions accepted by \(C_w\). (\(E_{C_s}\subset E_{C_w}\)) If neither of them is stronger, than the two are incomparable.

Causal Consistency

Using Lamport’s happened-before relation, we can define a consistency semantic. As the CAC paper states, an execution is causally consistent if \(\exists\) a DAG \(G\), a happens-before graph defined by the precedes partial ordering (\(\succ_G\)), satisfies the following check:

• Serial ordering at each node: If \(v\) and \(v^{\prime}\) are vertices corresponding to operations by the same node, \(v.startTime < v^{\prime}.startTime \Leftrightarrow v\prec_G v^{\prime}\).
• Read returns the latest preceding concurrent writes. Note that this doesn’t place any restrictions on the ordering of each of the concurrent writes.

The second point essentially separates consistency from conflict resolution, as in the responsibility of resolving order between the concurrent writes is passed to the individual nodes. So there is no guarantee of a total ordering in an execution that is causally consistent; as long as the partial ordering defined by a happened-before relation is satisfied, different nodes may observe different permutations of a valid execution.

Real-time-causal Consistency (RTC)

We could also add a real-time requirement to the consistency test regarding the happened-before graph above. An execution \(e\) is RTC consistent if the HB graph satisfies this additional property:

• \(\forall u, v: u.endTime < v.startTime \Rightarrow v \nprec_G u\)

Sequential Consistency (Lamport)

Unlike causal consistency, sequential consistency constrains the execution to be in some total order, and the resulting execution should be consistent with the order of operations on each individual nodes.

More Topics to Cover

• Linearizability
• External consistency (Gifford)
• Serializability

Further Readings

• Consistency Models (Jepsen)
• Linearizability: A Correctness Condition for Concurrent Objects (Herilhy)
• Consistency, Availability and Convergence (Marajan et al.)