Causal Consistency

Imagine two friends chatting on a social network. Alice posts "I got the job!" and then adds "Starting Monday." Bob, on a distant data center, should always see Alice's first post before the second — cause must precede effect. Yet Alice can also be writing at the exact same moment that Carol posts "Congrats!" on an unrelated topic, and those two updates have no causal link at all.

Causal consistency is the formal rule that captures this intuition: if write $A$ causally influences write $B$ (because the author of $B$ had already seen $A$), then every node in the system must deliver $A$ before $B$. Writes that are causally independent — concurrent, in the language of distributed systems — are free to arrive in any order.

This makes causal consistency the strongest consistency model that a distributed system can guarantee while remaining always available and partition-tolerant — the sweet spot that stronger models like linearizability must sacrifice during network failures. Lamport's seminal 1978 paper introduced the happens-before relation $\to$ and the vector clocks that track it, giving us the machinery to enforce causality without a global clock.

The demo below shows three nodes (A, B, C) exchanging writes. Each write carries a vector clock — a small array that records how many writes each node has seen. When a node receives a message it checks: are all the writes this message depends on already present? If yes, it delivers immediately; if not, it holds the message until the dependencies arrive.

<!-- {{c_html_intro}} -->
<div class="hint">{{hint_para}}</div>
<div class="nodes-row" id="nodesRow"></div>
<div class="controls">
  <label for="fromSel">{{label_from}}</label>
  <select id="fromSel"></select>
  <label for="msgInput">{{label_msg}}</label>
  <input id="msgInput" type="text" placeholder="{{placeholder_msg}}" maxlength="30" />
  <button id="sendBtn" type="button">{{btn_send}}</button>
  <button id="resetBtn" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="logPanel" class="log-panel">
  <div class="log-title">{{log_title}}</div>
  <div id="logBody"></div>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #1a1a2e; }
.hint { font-size: .85rem; color: #444; margin-bottom: .8rem; line-height: 1.5; }
.nodes-row { display: flex; gap: 10px; margin-bottom: .8rem; flex-wrap: wrap; }
.node-card {
  flex: 1; min-width: 140px; border: 1.5px solid #cdd9e3;
  border-radius: 10px; padding: 8px 10px; background: #f0f4f8;
}
.node-name { font-weight: 700; font-size: .95rem; margin-bottom: 4px; }
.vc-row { font-size: .75rem; color: #555; margin-bottom: 4px; font-family: ui-monospace, monospace; }
.inbox { font-size: .8rem; min-height: 28px; }
.inbox-item {
  display: inline-block; margin: 2px 3px 2px 0; padding: 2px 7px;
  border-radius: 12px; font-size: .78rem; font-weight: 600;
}
.delivered { background: #d4edda; color: #155724; border: 1px solid #b2dfc5; }
.pending  { background: #fff3cd; color: #856404; border: 1px solid #ffeaa7; }
.controls { display: flex; gap: 8px; flex-wrap: wrap; align-items: center; margin-bottom: .8rem; }
.controls label { font-size: .82rem; color: #444; }
select, input[type=text] {
  padding: .3rem .5rem; border: 1px solid #adb1b8; border-radius: 7px;
  font-size: .85rem; background: #fff;
}
input[type=text] { min-width: 120px; }
button {
  font: 600 13px system-ui; padding: .35rem .8rem;
  border: 1px solid #1d3557; background: #1d3557;
  color: #fff; border-radius: 7px; cursor: pointer;
}
button.ghost { background: #fff; color: #1d3557; }
.log-panel { border: 1px solid #dde3ea; border-radius: 8px; padding: 8px; max-height: 140px; overflow-y: auto; }
.log-title { font-size: .78rem; font-weight: 700; color: #666; margin-bottom: 4px; }
.log-entry { font-size: .78rem; color: #333; padding: 2px 0; border-bottom: 1px solid #f0f0f0; }
.log-entry.causal { color: #155724; }
.log-entry.held   { color: #856404; }
.log-entry.recv   { color: #0c5460; }

// Code not found

Try sending writes in different orders. Notice that causally related writes always arrive in the right order on every node, but concurrent writes (ones with no causal link) may arrive in different orders at different nodes — and that is perfectly correct behavior under causal consistency.

The consistency hierarchy for distributed systems forms a precise ladder:

• Eventual consistency (weakest): every node will eventually converge on the same value, but reads may return stale or out-of-order data at any time.
• Causal consistency: if $A \to B$ (A happens-before B), every node delivers $A$ before $B$. Concurrent writes are unordered. This is achievable with full availability even across partitions.
• Sequential consistency: all nodes observe the same global ordering of all writes — but that ordering need not match real time, and it requires coordination that blocks during failures.
• Linearizability (strongest): every operation appears to take effect at a single instant on a global timeline. Achievable only with quorum-based consensus, which sacrifices availability under partition.

The key theorem, a consequence of the CAP theorem (Brewer, 2000), is that causal consistency is the strongest model in the hierarchy that can be implemented with genuine availability — meaning every non-failed node always answers reads and writes without waiting for any other node.

Tracking causality precisely requires vector clocks: each node $i$ maintains a vector $V$ where $V[j]$ counts the writes from node $j$ that node $i$ has seen. A write from node $i$ is tagged with the current vector; a recipient holds it until its own vector satisfies the tag's dependencies component by component. The metadata overhead is $O(n)$ per message for $n$ nodes, and efficient variants (dotted version vectors, interval tree clocks) reduce this in practice.

Unlike P vs NP, causal consistency is a solved problem in the sense that we know exactly what is and is not achievable: the boundary is sharp, the implementation is known, and real systems (CockroachDB, MongoDB, Cosmos DB) ship it today.

Causal consistency shows up wherever ordering matters but global coordination is too expensive:

• Social networks and feeds: a reply must always appear after the post it answers, even when read from a replica on the other side of the planet.
• Collaborative editing: in systems like Google Docs, an edit that deletes a word must be seen by everyone after the edit that inserted it, or the document becomes incoherent.
• Shopping carts: adding an item and then applying a discount coupon — two causally related writes — must arrive in that order at every replica, or the coupon silently fails.
• Distributed databases: systems like Dynamo and Cosmos DB offer causal consistency as an explicit dial the developer can turn up from eventual consistency, paying a small latency premium for the ordering guarantee.
• Real-time multiplayer games: a player's "shoot" event must always be processed after the "spawn" event that made the target exist, even across geographically distributed servers.

In each case the contract is the same: causally linked operations must be delivered in order; concurrent operations can race freely. That simple rule eliminates a vast class of anomalies while keeping the system fully available.

Causal consistency draws the sharpest possible line in distributed systems: it preserves the intuitive rule that cause precedes effect, everywhere and always, without requiring any node to wait for any other during normal operation. That makes it the strongest consistency guarantee a truly available system can offer.

Vector clocks are the elegantly simple mechanism that makes it work — each write carries a snapshot of the causal past, and recipients wait only for exactly the dependencies they need. The rest of the system runs free.

The next time a distributed application behaves strangely — a reply appearing before the post, a delete reverting an edit — ask whether its consistency model respects causality. If not, it is probably time to move one step up the ladder.