Causal Consistency
Causal memory: for each process, its own operations plus all writes known to it appear in a total order that respects Lamport's potential causality (writes as sends, reads as receives). Strictly weaker than SC; strictly stronger than PRAM; incomparable to processor and cache consistency.
Properties
Property vector author-extrapolated — set only where the model’s definition pins the cell down (unknown cells are omitted); cells citing a specific source are marked.
- Reasoning guarantees
- no Coherence
- Atomicity guarantees
- no Multicopy atomic
Ordering relationships
- Strictly weaker than
- Sequential Consistency (SC) — Causal memory is strictly weaker than sequential consistency (Ahamad et al. 1995; Steinke & Nutt 2004).
- Causal+ (Convergent Causal) Consistency — Causal+ = Causality ∧ StrongConvergence (Viotti & Vukolić 2016, Eq. 27; Lloyd et al., COPS, SOSP 2011). It adds strong convergence (all replicas that applied the same writes have equivalent state) on top of causal consistency, disallowing strictly more behaviours, so causal consistency is strictly weaker than causal+.
- Real-Time Causal Consistency (RTCausal) — RealTimeCausality = Causality ∧ RealTime (Viotti & Vukolić 2016, Eq. 28; Mahajan, Alvisi & Dahlin 2011). It adds the requirement that causally concurrent, real-time-non-overlapping writes be applied in real-time order, disallowing strictly more behaviours, so causal consistency is strictly weaker than real-time causal consistency.
- Strictly stronger than
- PRAM (Pipelined RAM) Consistency — Causal memory is strictly stronger than PRAM consistency (Steinke & Nutt 2004).
- Per-Object Causal Consistency (PO-Causal) — Burckhardt, Gotsman, Yang & Zawirski, POPL 2014, §7: (cross-object) causal consistency imposes the ordering axioms COCV/COCA, while per-object causal consistency imposes only the weaker per-object axioms POCV/POCA over the per-object happens-before order (Viotti & Vukolić 2016, §3.9). COCV/COCA disallow strictly more anomalies, so cross-object causal consistency is strictly stronger than per-object causal consistency.
- Writes-Follow-Reads (Session Guarantee) (WFR) — Brzezinski et al. (2004) proved causal consistency requires and includes all four session guarantees, i.e. causal = PRAM ∧ writes-follow-reads (Viotti & Vukolić 2016, §3.4, Eq. 25). Causal consistency therefore implies writes-follow-reads while the converse fails, so writes-follow-reads is strictly weaker than causal consistency.
- Incomparable with
- Processor Consistency (PC) — Processor and causal consistency are incomparable: each forbids a behaviour the other allows (Steinke & Nutt 2004).
- Cache Coherence — Causal and cache consistency are incomparable (Steinke & Nutt 2004).
References
- Mustaque Ahamad, Gil Neiger, James E. Burns, Prince Kohli, Phillip W. Hutto. Causal Memory: Definitions, Implementation, and Programming. Distributed Computing 9(1), 1995. doi:10.1007/BF01784241
- Robert C. Steinke, Gary J. Nutt. A Unified Theory of Shared Memory Consistency. Journal of the ACM 51(5), 2004. arxiv.org/abs/cs/0208027