Causality
Summary: A consistency model based on the “happened-before” relationship, providing a partial ordering of events in a distributed system.
Sources: chapter9
Last updated: 2026-04-17
Causality is a weaker but more efficient guarantee than linearizability. It ensures that events that are causally related (i.e., one happened before another) are seen in the same order on all replicas (source: chapter9, p. 339).
The Happened-Before Relationship
Causality defines a partial order of events (source: chapter9, p. 341).
- If event A happened before event B, then all nodes must see A before B (source: chapter9, p. 341).
- If two events A and B are not causally related (i.e., they are concurrent), then different nodes can see them in different orders (source: chapter9, p. 341).
In contrast, linearizability provides a total order: every operation is atomic and happens at a single point in time, allowing any two operations to be compared (source: chapter9, p. 341).
Capturing Causal Dependencies
To maintain causality, systems must track what happened before what (source: chapter9, p. 342).
- Sequence numbers: A total order that is consistent with causality can be generated using a single leader to increment a counter for each operation (source: chapter9, p. 344).
- Lamport Timestamps: A more scalable way to generate a total order that is consistent with causality without a single leader (source: chapter9, p. 345).
- Version Vectors: Used to detect concurrent writes (source: chapter9, p. 343).
Causal Consistency
Causal consistency is often considered a “middle ground”: it is stronger than eventual-consistency but doesn’t have the performance and availability costs of linearizability (source: chapter9, p. 342).