Causal Consistency

Causal consistency is the consistency model that orders operations related by potential causality — Lamport’s happens-before relation — while leaving concurrent (causally-unrelated) operations free to be observed in different orders by different replicas. If one operation could have influenced another, every replica must agree they happened in that order; if two operations are independent, replicas may disagree about which came first. It was first defined for shared memory by Ahamad, Neiger, Burns, Kohli and Hutto in “Causal Memory: Definitions, Implementation and Programming” (Distributed Computing, 1995). Its central importance is a sharp theoretical result: causal consistency (in its real-time-respecting form) is the strongest consistency model that a system can provide while remaining always available under network partitions — proved by Mahajan, Alvisi and Dahlin (Consistency, Availability, and Convergence, UTCS TR-11-22, 2011). Everything weaker than causal — Eventual Consistency, per-key sequential — throws away ordering it did not have to; everything stronger — Sequential Consistency, Linearizability — forces a global order that a partition can make impossible to serve.

Mental Model

The right way to think about causal consistency is as a partial order made visible. In a distributed store there is no global clock and no single agreed timeline, so the only orderings that mean anything are the ones that could carry information: a write you read before issuing your own write, a message you received before you replied. These form a directed acyclic graph — the happens-before graph — and causal consistency is the promise that no reader ever sees the graph out of order. If operation a is an ancestor of operation b in that graph, then any replica that has made b’s effect visible has already made a’s effect visible. Operations with no path between them — concurrent operations — carry no information about each other, so replicas are permitted to apply them in whatever order is convenient. This is precisely what buys availability: two unrelated writes can be accepted and replicated in parallel with no coordination, because agreeing on their relative order would be busy-work that no client can detect.

flowchart TD
    A["put(photo)<br/>Client 1"] --> B["put(album → photo ref)<br/>Client 1"]
    B --> C["get(album) = ref<br/>Client 2"]
    C --> D["comment('nice pic!')<br/>Client 2"]
    X["put(status = 'away')<br/>Client 3"]

    A -. "must be visible<br/>before" .-> B
    B -. "gets-from" .-> C

    subgraph concurrent [" "]
      X
    end

    classDef causal fill:#e8f0ff,stroke:#3b6;
    classDef indep fill:#fff0e8,stroke:#b63;
    class A,B,C,D causal;
    class X indep;

What it shows and the insight to take: the blue chain is a causal thread — the photo is written, then referenced in the album, then that reference is read, then commented on. Causal consistency guarantees that any replica showing the comment already shows the album reference, which already shows the photo: you can never see “nice pic!” attached to a photo that appears not to exist. The orange node (an unrelated status update on Client 3) has no edge into or out of the chain — it is concurrent with everything in blue, so different replicas may legitimately order it before or after any blue operation. The insight: causal consistency is not “one timeline everyone agrees on”; it is “every timeline is a valid linear extension of the same partial order.”

The Happens-Before Order That Causal Consistency Enforces

Causal consistency is defined relative to a causality relation, so it cannot be understood without pinning down what “causally related” means. The relation is Lamport’s potential causality, written ⤳ (leads-to), and for a read/write data store it is generated by exactly three rules, stated crisply in the COPS paper (Lloyd, Freedman, Kaminsky, Andersen, SOSP 2011, §3):

1. Execution thread. If a and b are two operations in a single thread of execution, then a ⤳ b if operation a happens before operation b. (Program order within one client is causal.)
2. Gets-from. If a is a write (put) and b is a read (get) that returns the value written by a, then a ⤳ b. (Reading a value makes you causally aware of the write that produced it.)
3. Transitivity. For operations a, b, and c, if a ⤳ b and b ⤳ c, then a ⤳ c. (Causality composes.)

These rules establish causality within a client’s own thread and across clients wherever they exchanged information through the store. Crucially, the model assumes all communication flows through the data store — clients do not have a private back-channel — so “gets-from” plus transitivity is how one client’s writes become causally visible to another. This is the same Happens-Before Relation Lamport introduced in 1978, and the machinery that tracks it at runtime is Vector Clocks (or their replicated-data cousin, Version Vectors): a vector clock can decide, for any two operations, whether one ⤳ the other or whether they are concurrent.

Causal consistency then makes one demand: a read must return a value consistent with ⤳. Formally (COPS §3.1, following Ahamad et al.), it must appear that the operation writing the value a read returns occurs after all operations that causally precede it. Concurrent operations — where neither a ⤳ b nor b ⤳ a — are deliberately unordered; the model says nothing about which a given replica applies first, and different replicas may choose differently.

A worked example straight from COPS (Figure 2) makes the boundary precise. Three clients operate through a replica:

• Client 1: put(x,1) → put(y,2) → put(x,3)
• Client 2: get(y)=2 → put(x,4)
• Client 3: get(x)=4 → put(z,5)

By the execution-thread rule, get(y)=2 ⤳ put(x,4). By gets-from, put(y,2) ⤳ get(y)=2. By transitivity, put(y,2) ⤳ put(x,4), and continuing, put(y,2) ⤳ put(x,4) ⤳ put(z,5). Therefore any replica that exposes z=5 must already expose x=4 and y=2. If Client 3, having just read get(x)=4, then issued get(x) and got back 1, causal consistency would be violated — it would have gone backward across a causally-ordered pair. But note what is not constrained: put(x,3) was written by Client 1 and read by no one before its thread ended, so it is concurrent with put(x,4); two replicas may forever disagree about whether the final value of x is 3 or 4. That freedom is the whole point.

Causal+ : Adding Convergent Conflict Handling

Plain causal consistency has a gap that shows up exactly at those concurrent writes. Because it refuses to order put(x,3) against put(x,4), one replica may settle on x=3 and another on x=4 forever — the replicas are each internally causally consistent but permanently divergent. COPS closes this with causal+ consistency (“causal consistency with convergent conflict handling”), the model it actually implements. The + adds one property: convergent conflict handling, which requires that all replicas resolve conflicting concurrent writes to the same value using a handler function h that is associative and commutative, so that replicas applying the conflicting writes in different orders still arrive at the same result (COPS §3). The simplest such handler is last-writer-wins (the Thomas write rule): tag each write with a timestamp and declare the higher one the winner. Richer handlers merge — e.g. keeping both values as siblings for the application to reconcile, the approach CRDTs and Dynamo take. The result is a store that is causally correct and never permanently diverges — “conflict-free” and “always-progressing,” in COPS’s words.

The COPS paper places causal+ on an explicit spectrum of consistency models, stronger on the left (its Figure 3):

Linearizability > Sequential > Causal+ > Causal > FIFO (PRAM) / Per-Key Sequential > Eventual

The bolded top two — Linearizability and Sequential Consistency — are provably incompatible with what COPS calls an ALPS system: one that is simultaneously Available, Low-latency, Partition-tolerant, and Scalable. Causal+ is the strongest model the paper finds achievable under those four constraints, which is why its title exhorts readers to “don’t settle for eventual.”

Why Causal Is the Strongest Model Available Under Partition

The claim that causal consistency is the ceiling for a partition-tolerant, always-available system is not folklore — it is a theorem. Mahajan, Alvisi and Dahlin’s Consistency, Availability, and Convergence (CAC) states a tight bound (their §1):

“No consistency stronger than real time causal (RTC) consistency … can be provided in an always-available, one-way convergent system” — and, complementarily, “RTC can be provided in an always-available, one-way convergent system.”

Every term is load-bearing, and the paper defines each. An always-available system is one where “for any workload, all reads and writes can complete regardless of which messages are lost and which nodes can communicate” — the strongest form of availability, the one a CAP-availability advocate wants. One-way convergent means “if node p can receive from node q, then eventually p’s state reflects updates known to q” — a liveness property capturing the anti-entropy behavior of systems like Bayou and Dynamo (see Anti-Entropy and Read Repair). Real-time causal (RTC) consistency is causal consistency plus a real-time constraint the paper calls CC3, “time doesn’t travel backward”: if operation u finishes in real time before operation v starts, then v may not be ordered before u. RTC layers CC3 atop the two ordinary causal checks — CC1 (“serial ordering at each node,” i.e. program order) and CC2 (“a read returns the latest preceding write”). Mahajan et al. observe that RTC “is not a new semantics”: most systems claiming to enforce causal consistency actually enforce the stronger RTC, since it would be bizarre for a practical implementation to order a later real-time operation before an earlier one.

The deep reason this bound is causal and not something stronger is subtle and is the paper’s real contribution: without a convergence requirement, there exist artificial semantics strictly stronger than causal that are still always-available — for instance, a gossip system that refuses to send a message unless its sequence number is divisible by 100 is “technically stronger than causal consistency and still always available; yet … feels artificial.” Convergence — the demand that connected nodes actually share their writes — is what rules these degenerate strengthenings out and makes causal the genuine ceiling. This reframes the folk claim “causal is the best you can do under a partition” into a precise statement: among semantics that are always available AND actually converge, none beats real-time causal. This is the escape hatch that CAP Theorem and PACELC Theorem point at: when you must stay available under partition, causal+ is the strongest contract on offer.

Implementing Causal Consistency: Tracking Dependencies

Enforcing causality at runtime means the store must, for every write, know what that write depends on and refuse to expose it until those dependencies are already visible locally. There are two broad implementation families.

Log exchange with version/vector clocks (the older approach). Systems like Bayou and earlier causal stores write all operations at a logical replica into a single serialized log, tag entries with a version vector, and ship logs between replicas; a receiving replica replays entries in an order that respects the vectors, establishing potential causality and detecting concurrency. COPS’s critique (§3.4) is that this “inhibits replica scalability, as it relies on a single serialization point in each replica to establish ordering” — either causal dependencies are limited to keys on one node, or a single node must commit-order every operation in the cluster. This is why Vector Clocks carried per-client grow without bound in a wide-open multi-client system, a real cost discussed under Failure Modes below.

Explicit per-key dependency metadata (the scalable approach, COPS). COPS spreads a datacenter’s keyspace across many nodes and attaches to each stored value a key_version and an explicit list of dependencies — the (key, version) pairs that causally precede it. Client libraries accumulate the set of versions a client has read or written; when the client issues a put, that set becomes the new write’s dependency list. Within the local datacenter, operations execute in a linearizable order, so local causal order is free. When a write is replicated to a remote datacenter, the receiving datacenter, before committing the incoming version, issues dependency checks — it asks the nodes responsible for each dependency whether that (key, version) is already present locally, and blocks the commit until they all say yes. Only then does the value become visible, guaranteeing no reader in that datacenter ever sees an effect before its cause. The extended variant, COPS-GT, adds get transactions — a lock-free, non-blocking way to read a causally-consistent snapshot of multiple keys in at most two rounds — because single-key causal consistency does not by itself give a consistent multi-key read.

Failure Modes and Common Misunderstandings

“Causal means fresh.” No. Causal consistency says nothing about recency. A read may return arbitrarily stale data and still be perfectly causal, as long as it does not contradict something the same client already saw. A client that has never observed a newer write is entitled to keep reading an old value indefinitely. If you need “the latest committed value,” you need Linearizability, and you have left the always-available regime.

Concurrent-write conflicts do not vanish — they are relocated. Plain causal consistency leaves concurrent writes unordered, which means the application (or a causal+ conflict handler) must resolve them. Last-writer-wins silently discards one write and is only safe with well-synchronized clocks (a dangerous assumption — see Conflict Resolution and Last-Writer-Wins); merge handlers preserve both but push complexity onto the application; CRDTs make the merge automatic and correct but constrain what data types you may use.

Metadata cost and the throughput cliff. Tracking full causal dependencies is expensive. Naïve dependency lists or per-client vector clocks grow with the number of writers and the length of causal chains, inflating both storage and the network cost of replication. Worse, a body of follow-on work (notably Bailis et al.’s “bolt-on causal consistency” and Ajoux/Bronson/Lloyd/Kumar’s later Facebook study) found that under write-heavy, skewed workloads the dependency-checking traffic can dominate and cause throughput to collapse — the very reason large systems often deploy plain Eventual Consistency with Session Guarantees for Consistency instead of full causal.

Uncertain

Verify: (1) the exact attribution and 1995 date of the original causal memory definition to Ahamad, Neiger, Burns, Kohli and Hutto — this was confirmed via the COPS reference list and encyclopedic sources, but the primary paper (Distributed Computing 9(1):37–49) was not fetched during this task; (2) the specific “throughput cliff / dependency-checking dominates” finding attributed to bolt-on causal consistency and the Facebook follow-up — this rests on memory and secondary summary, not a primary read this session. To resolve: fetch the Ahamad 1995 paper and the Bailis SIGMOD 2013 “Bolt-on Causal Consistency” paper directly. Reason: primary PDFs not retrieved this session. #uncertain

Causal consistency does not compose across independent objects for free. A single-key causal store does not guarantee a causally-consistent multi-object read; that is exactly the gap COPS-GT’s get-transactions exist to fill. Reading two related keys with two separate causal reads can still catch them mid-update.

Alternatives and When to Choose Them

Compared with its neighbors on the hierarchy, causal consistency occupies a deliberate middle. Sequential Consistency and Linearizability give a single global order (sequential) or a real-time-respecting one (linearizable), which application programmers find easiest to reason about — but both are unavailable under partition and require cross-node coordination (consensus, Read and Write Quorums) on the write path, so they cost latency even in the absence of failures (PACELC Theorem’s “else” cost). Choose them when correctness demands a global truth (account balances, unique-constraint enforcement) and you can tolerate unavailability during partitions.

Eventual Consistency sits just below causal: it promises only that replicas converge if writes stop, ordering nothing along the way. It is cheaper (no dependency tracking) and simpler, and when paired with Session Guarantees for Consistency it recovers the single-client comfort (read-your-writes, monotonic reads) that covers most user-facing needs — which is why it, not full causal, is the industry default for Dynamo-style stores. Choose plain eventual (plus session guarantees) when the causal-metadata cost is not worth it and per-client comfort suffices; choose causal(+) when cross-client causality matters — comment-after-post, reply-after-message, reference-after-target — and reordering would be visibly wrong to users.

CRDTs are orthogonal and complementary: they solve the convergence half (the + in causal+) with commutative, associative, idempotent merges, and are frequently layered under a causal-delivery layer to build causal+ stores.

Production Notes

Causal(+) consistency graduated from theory to production largely through the COPS lineage and social-network infrastructure. COPS itself (2011) demonstrated sub-millisecond operations with throughput comparable to weaker systems while scaling across many nodes per datacenter. Its successor Eiger extended causal+ to a column-family data model. At Facebook, the causal-consistency ideas informed real-world caching-consistency work (the “Existential Consistency” / χ measurements of TAO), which found that in practice the vast majority of reads already satisfy stronger-than-causal orderings, echoing the CAC observation that deployed “causal” systems usually deliver the stronger real-time-causal semantics. The recurring engineering lesson is the one under Failure Modes: causal consistency’s correctness is elegant, but its metadata is the hard part — production systems succeed by aggressively pruning dependency graphs (garbage-collecting dependencies once they are known globally applied) and by falling back to session guarantees over an eventually-consistent core when full causal tracking is too expensive. As of 2026, most widely-deployed NoSQL stores (Cassandra, DynamoDB, Riak) offer eventual consistency plus tunable quorums and session/read-your-writes options rather than full causal consistency, while MongoDB’s “causal consistency” sessions (since 3.6) are a mainstream example of the model shipped as an opt-in per-session guarantee.

Uncertain

Verify: the specific production claims about Eiger, Facebook’s TAO “existential consistency” measurements, and MongoDB offering causal-consistency sessions since version 3.6. These are stated from background knowledge, not from primary sources fetched this session. To resolve: fetch the Eiger (NSDI 2013), Facebook “Existential Consistency” (SOSP 2015), and MongoDB documentation directly. Reason: primary sources not consulted this session for these deployment facts. #uncertain

See Also

• Happens-Before Relation — Lamport’s partial causal order; the relation causal consistency is defined against
• Vector Clocks — the mechanism that detects concurrency vs causality at runtime; how dependencies are tracked
• Version Vectors — the replicated-data variant used to track object update lineage across replicas
• Eventual Consistency — the weaker, cheaper neighbor just below causal on the hierarchy
• Sequential Consistency — the stronger neighbor above; a single global order, but unavailable under partition
• Linearizability — the strongest single-object model; real-time order preserved
• CRDTs Basics — supplies the convergent conflict handling (the + in causal+)
• Session Guarantees for Consistency — read-your-writes and monotonic reads; the per-client subset of causality
• CAP Theorem — why availability under partition forces a weaker-than-linearizable model
• PACELC Theorem — the else-latency cost that also pushes systems toward causal/eventual
• Conflict Resolution and Last-Writer-Wins — the danger of clock-based tie-breaking for concurrent writes
• Anti-Entropy and Read Repair — the convergence substrate under one-way-convergent causal systems
• The Consistency Model Hierarchy — where causal+ sits in the full lattice
• Distributed Systems MOC — parent map (§3 Consistency Models)