Causal Consistency

Causal consistency guarantees that operations which could have influenced one another are observed in that order by everyone, while operations that are genuinely concurrent may be observed in different orders by different readers.

Causal consistency prevents dependency inversions such as a reply appearing before the message it answers. It does not serialize concurrent decisions merely because their results matter to a user. Two buyers can independently act on the same apparent inventory unless another rule prevents that conflict. Preserving causal order and enforcing a business invariant are separate requirements.

The formal underpinning is Leslie Lamport’s 1978 happened before relation, which defines causality from what a system can actually know: one event precedes another if they occur in order within the same process, or if one is the sending of a message and the other its receipt, or by transitivity through those. Events not related in that way are concurrent — and the important part is that concurrency here is a structural fact about information flow, not a statement about wall-clock time.

That is also the model’s limit. The system can only track causality it can see. Two users who coordinate outside the system — one phones the other, who then makes an update — have created a real dependency that no message carries, so the system is free to order those operations either way. Causal consistency is therefore weaker than it can feel.

Causal consistency can be available during a partition when clients remain attached to replicas that have their causal dependencies: the availability classification is sticky available. A client that writes at A and moves to an isolated B before its write arrives cannot necessarily continue there without waiting or weakening its session guarantee. Session migration and failover therefore need dependency transfer or a wait or rejection path. This is a different availability contract from allowing every client to make progress at any reachable replica, and from the coordination needed for linearizability.

Where it sits among the other models, and what each one costs, is worked through in Replication, Consistency, and Time.

References

• Jepsen, Causal Consistency
• Leslie Lamport, Time, Clocks, and the Ordering of Events in a Distributed System (1978)