What is causal consistency in distributed systems?

Consistency

We know that the system stores the most recently updated data on a single computer. However, data is shared and replicated across many computing nodes in a distributed system.

Consistency is a property of the distributed system which ensures that every node or replica has the same view of data at a given time, irrespective of which client has updated the data. Strong consistency would mean that the distributed system converges on a single value, and the client always reads the latest data.

Consistency models

A consistency model is a contract between a distributed system and the applications that run on it. This model is a set of guarantees made by the distributed system. There are various consistency models employed by different distributed systems such as linearizability, serializability, causal consistency, and eventual consistency. We’ll be talking about causal consistency in this shot.

Causal consistency

Causal consistency is a weak form of consistency that preserves the order of causally related operations. A happens-before relationship between operations captures causality. You can refer to this shot to recall what we mean by the happens-before relationship in distributed systems. This means all processes must see potentially causally related operations in the same order.

In other words, if a happens before b, then a must execute before b on all replicas. All other concurrent operations may be seen in different orders.

A key difference between causal consistency and sequential consistency is that causal consistency does not require a total order.

Causal consistency implies that reads are fresh only with respect to the writes that they are causally dependent on. Moreover, only causally-related writes are ordered by all replicas in the same way. Concurrent writes can be committed in different orders.

Example

In the following example, we have a distributed system consisting of four different processes: P1, P2, P3, and P4.

There are a number of operations happening at every process. W(Y,A) means that the value of object Y is being written as A. R(Y) means that the value of object Y is being read.

At first glance, the following sequence of operations might seem causally consistent, but they are not.

Having read C, P3 must continue to read C or some newer value (perhaps B), but can’t go back to A. That’s because W(Y,C) was conditional upon W(Y,A) having finished.

If P3 had read B on its second read, we could say that this system guaranteed causal consistency. That’s because W(Y,B) and W(Y,C) are not causally related. Instead, they are concurrent.