Causal consistency

Causal consistency is one of the major memory consistency models. In concurrent programming, where concurrent processes are accessing a shared memory, a consistency model restricts which accesses are legal. This is useful for defining correct data structures in distributed shared memory or distributed transactions. Causal Consistency is “Available under Partition”, meaning that a process can read and write the memory (memory is Available) even while there is no functioning network connection (network is Partitioned) between processes; it is an asynchronous model. Contrast to strong consistency models, such as sequential consistency or linearizability, which cannot be both safe and live under partition, and are slow to respond because they require synchronisation. Causal consistency was proposed in 1990s as a weaker consistency model for shared memory models. Causal consistency is closely related to the concept of Causal Broadcast in communication protocols. In these models, a distributed execution is represented as a partial order, based on Lamport's happened before concept of potential causality. Causal consistency is a useful consistency model because it matches programmers' intuitions about time, is more available than strong consistency models, yet provides more useful guarantees than eventual consistency. For instance, in distributed databases, causal consistency supports the ordering of operations, in contrast to eventual consistency. Also, causal consistency helps with the development of abstract data types such as queues or counters. Since time and ordering are so fundamental to our intuition, it is hard
to reason about a system that does not enforce causal consistency. However, many distributed databases lack this guarantee, even ones that
provide serialisability. Spanner does guarantee causal consistency, but it also forces strong consistency, thus eschewing availability under partition. More available databases that ensure causal consistency include MongoDB
and AntidoteDB.

Causal consistency captures the potential causal relationships between operations, and guarantees that all processes observe causally related operations in a common order. In other words, all processes in the system agree on the order of the causally related operations. They may disagree on the order of operations that are causally unrelated. The Causal Consistency model is weaker than sequential consistency, which ensures that all processes observe all write operations in common order, whether causally related or not. However, causal consistency is stronger than PRAM consistency, which requires only the write operations that are done by a single process to be observed in common order by each other process. It follows that when a system is sequentially consistent, it is also causally consistent. Additionally, causal consistency implies PRAM consistency, but not vice versa.

The causal consistency model can be refined into four session guarantees. They can be summarised as follows:

Read Your Writes: If a process performs a write, the same process later observes the result of its write. Monotonic Reads: the set of writes observed (read) by a process is guaranteed to be monotonically non decreasing. Writes Follow Reads: if some process performs a read followed by a write, and another process observes the result of the write, then it can also observe the read (unless it has been overwritten). Monotonic Writes: If some process performs a write, followed some time later by another write, other processes will observe them in the same order. Transactional session guarantees for serialisability and snapshot isolation are presented by Daudjee and Salem.