Skip to content

Causal-Consistency Protocol

Consistency protocol — instantiates Shared-State Consistency Contract Design

Guarantees that reads respect cause and effect — if one operation could have influenced another, every observer sees them in that order — without paying for a global total order.

A Causal-Consistency Protocol makes the contract promise exactly one ordering property: causally related operations are seen by everyone in their causal order, while operations that are genuinely concurrent may be seen in any order. If a write B could have depended on write A (its author had already seen A), then no client will ever observe B without also observing A. Its distinguishing idea is that it enforces only the order cause-and-effect requires — the happens-before relation — which is strictly weaker and far cheaper than the single global total order linearizability demands, yet strong enough to eliminate the "reply before the message" class of anomalies.

Example

On a globally replicated discussion app, Amara posts "Has anyone tried the new API?" and Ben, seeing it, replies "Yes — much faster." A third user reading from a replica in another region must never see Ben's reply before Amara's question — a reply to a message that isn't there yet is nonsense. Causal consistency tracks that Ben's reply causally depends on Amara's post (Ben had read it), attaches that dependency to the reply, and holds the reply from being shown at any replica until the post it depends on is present there too. Two unrelated posts from different users, though, may appear in either order from region to region — the protocol spends ordering effort only where causality actually exists.

How it works

The distinctive move is that it tracks dependencies, not a clock tick. Each operation carries metadata — typically a version vector or a set of dependency tokens — recording the operations its author had already observed. A replica may apply an update (make it visible to local readers) only once all of that update's causal dependencies have themselves been applied; otherwise it buffers. Concurrent operations — neither in the other's dependency set — are unordered and may be applied in different orders at different replicas, which is precisely what keeps the protocol cheap and available under partition.

Tuning parameters

  • Dependency granularity — per-object vs. per-write vs. coarse "session" dependencies; finer tracking allows more concurrency but carries more metadata per operation.
  • Metadata form — full version vectors (exact, size grows with the number of actors) vs. explicit dependency lists (compact for few dependencies, unbounded for many).
  • Convergence pairing — causal order alone does not converge concurrent writes; pairing it with a merge or LWW rule ("causal+") decides the final value when two updates are concurrent.
  • Dependency GC — when to stop tracking a dependency as satisfied everywhere; aggressive collection saves space but risks exposing an update before its cause.

When it helps, and when it misleads

Its strength is killing the anomalies humans actually notice — out-of-order replies, an effect visible before its cause — while staying available and low-latency under partition, which linearizability cannot. Its honest limit is that causal consistency gives no total order, so two concurrent conflicting writes still need a separate convergence rule, and it does not enforce real-time recency — a client can read a causally-consistent but stale snapshot. The classic misuse is assuming "causal" implies "latest," then being surprised when a perfectly legal read returns old data.[1] The discipline is to pair the protocol with an explicit convergence rule for concurrent writes and to be clear that it orders causally-linked events, not wall-clock recency.

How it implements the components

  • visibility_and_order_relation — the protocol defines the visibility relation: an update becomes visible only after its causal predecessors, encoding happens-before as the order clients see.
  • client_observation_model — it fixes what a client may legally observe: any causally-consistent prefix of history, never an effect without its cause.

It defines the order but not the tokens that encode it — the timestamp/clock is Hybrid Logical Clock's and the per-actor counters are Version Vector's — nor the merge that settles concurrent writes, which is CRDT-Like State Merge's or Last-Write-Wins Register's.

References

[1] Happens-before — Lamport's partial order on events (a → b if a could causally influence b). Causal consistency is precisely the requirement that observers respect this partial order; it constrains neither the ordering of concurrent (incomparable) events nor real-time freshness. ↩