Causal Consistency

Causal Consistency is formally defined via happens-before relations: an operation A causally precedes B if (1) A and B occur on the same process and A precedes B in that process’s execution, (2) B reads a value written by A, or (3) there exists a chain of such relations transitively linking A to B. Any pair of operations not connected by this relation is concurrent, and the system is free to apply/observe them in any order on different replicas without violating the model. This is what allows causal systems to remain available under partition (satisfying the AP side of CAP) while still ruling out anomalies like observing an effect before its cause.

Implementations diverge on how they encode and enforce dependency tracking. Explicit-dependency systems (e.g., COPS, Eiger) attach a dependency set or version vector to every write, forcing a replica to stall application of an incoming update until all of its listed dependencies are locally satisfied — effectively a per-key causal barrier. Broadcast-based systems instead rely on a causal broadcast primitive at the messaging layer, delivering messages to all nodes in an order consistent with causality (commonly implemented with per-sender sequence numbers plus a delivery buffer that holds back messages until their prerequisites arrive). Both approaches require metadata that grows with either the number of writers or the depth of the dependency chain, which is why most production systems adopt causal consistency with convergent conflict handling (CCCH) — layering a CRDT or last-writer-wins merge function on top to resolve concurrent writes deterministically once delivered.

The critical edge case is the causal cut problem: a replica must never expose a state that includes an effect without also including its cause, even transiently. This forces careful handling of read-only transactions spanning multiple shards — a naive implementation can return a causally inconsistent snapshot if shard A has applied a dependent write but shard B has not yet received it. Systems solve this with mechanisms like explicit checkpoints (COPS’s dependency-check reads) or global stable snapshots gated by a watermark, both of which reintroduce latency proportional to the slowest causally-relevant replica, eroding some of the availability benefit the model is meant to provide.

• Session guarantees (monotonic reads, monotonic writes, read-your-writes, writes-follow-reads) are typically implemented as client-side special cases of causal consistency scoped to a single session, rather than the full cross-client causal graph.
• Causal consistency is proven to be the strongest model achievable while remaining available under partition (per the CAP-adjacent impossibility results), making it the theoretical ceiling for systems that cannot tolerate linearizability’s coordination cost.
• Garbage collecting dependency metadata is non-trivial: unbounded causal histories require either explicit pruning via stable snapshots or bounding via version vectors with fixed-size summaries, trading precision for memory.

Architecturally, choosing causal consistency shifts complexity from the storage engine into the client library or a dependency-tracking sidecar, since the guarantee is fundamentally about visibility ordering rather than storage layout. This makes it attractive for multi-region social-graph and collaborative-editing workloads where strict global ordering is unnecessary, but it demands rigorous testing — violations are silent and only manifest as subtle causality inversions under specific interleavings, making it a prime candidate for deterministic simulation testing rather than ad hoc integration tests.