In a causally consistent data store, how does a write's set of causal dependencies get determined, and what rule must the store enforce before it lets a replica expose that write to readers?

## How a write's dependencies are determined A write's causal dependencies are determined mechanically from the causal history of the client that issued it, not by any global mechanism. Concretely, when a client issues write W, its **causal context** is the union of: - everything the client previously read — reading a value creates a **read-from** dependency on whichever write produced it; - plus everything the same client previously wrote in program order; - plus, transitively, everything those earlier writes themselves depended on. In practice a system doesn't need to attach the full transitive closure to every write. A well-known optimization, used by **COPS**, is to track only the **nearest** dependencies (the writes a client directly read or issued most recently for each key), because each of those writes already carries its own dependency list, so satisfying the nearest dependency transitively satisfies everything further back in the chain. This keeps per-write metadata bounded by roughly the number of distinct keys a client's session has touched recently rather than growing with the entire system history. ## Why the check is needed at all This mechanism exists because replication in a causally consistent store is asynchronous and multi-path: writes propagate between replicas over independent network links (or via gossip), and nothing about the network guarantees they arrive in the order they were issued. Without an explicit dependency check, a replica could apply a 'reply' write before the 'original post' write it depends on simply because it arrived over a faster link. The rule that fixes this — satisfying the **causal cut** — says: before a replica makes an incoming write visible to any local reader, it must first confirm every write named in that write's dependency set is already present and visible locally. If any dependency is missing, the replica cannot expose the write yet — it must hold it in a pending buffer and re-check as further writes arrive, applying it only once its dependencies are locally satisfied. ## The trade-off The trade-off here is metadata and latency against ordering correctness. But the cost is real on each approach: | Approach | Why it appeals | What it costs | |---|---|---| | Explicit per-write dependency lists, as in **COPS** | attractive because they're precise, and let a replica check locally, without consulting a remote coordinator, whether it's safe to expose a write — exactly what keeps causal consistency compatible with high availability under partitions | every write now carries extra bytes of dependency metadata, and that metadata has to be garbage-collected once dependencies are known to be satisfied everywhere, itself a nontrivial distributed problem | | Coarser alternatives exist — e.g., treating an entire client session's causal history as a single opaque token rather than fine-grained per-key dependencies | in exchange, simpler and cheaper tracking | reducing bookkeeping precision, and sometimes causing a write to wait on dependencies it doesn't really need | ## The production failure mode The most visible production failure mode is **dependency stalling**: a write sits in a replica's pending buffer, invisible to readers, because one of its dependencies hasn't arrived — perhaps the source replica is slow, a link is congested, or a partition has cut off the path the dependency needed. This shows up as uneven, hard-to-predict write visibility lag: two writes issued moments apart by the same client can become visible on a remote replica at very different times depending on how quickly each one's dependencies propagate. In systems with **hot** keys many clients depend on (a popular post, a frequently-read config value), dependency chains can also grow large enough that tracking and checking them becomes a measurable per-write cost — sometimes called **dependency explosion**. ## Where it shows up A concrete real-world illustration is the **COPS** system (Clusters of Order-Preserving Servers), from Lloyd et al.'s 2011 paper, explicitly built to demonstrate that this per-write, nearest-dependency tracking approach could deliver causal consistency across geo-replicated data centers while keeping metadata overhead and latency low, in contrast to naively tracking the full transitive history of every write.