Relaxed Memory Model Zoo

Ordering relationships

Strictly weaker than

• Sequential Consistency (SC) — Causal memory is strictly weaker than sequential consistency (Ahamad et al. 1995; Steinke & Nutt 2004).

Strictly stronger than

• Weak Causal Consistency (CC) — Bouajjani et al., POPL 2017, §4 and Fig. 1: CM and CCv 'are both strictly stronger than CC'. Witness: Fig. 2 history (2c) — pa: wr(x,1) || pb: wr(x,2); rd(x)▷1; rd(x)▷2 — is CC but neither CM nor CCv, since pb revises its ordering of the two writes after already having read one of them.
• PRAM (Pipelined RAM) Consistency — Causal memory is strictly stronger than PRAM consistency (Steinke & Nutt 2004).
• Writes-Follow-Reads (Session Guarantee) (WFR) — Brzezinski, Sobaniec & Wawrzyniak (PDP 2004) show that causal consistency requires all four session guarantees — read-your-writes, monotonic reads, monotonic writes and writes-follow-reads. Their data-centric models are the classical shared-memory taxonomy (atomic, sequential, causal, processor, PRAM, weak, release, scope, entry), so their causal consistency is causal memory, and this edge is correctly against the Causal node rather than CCv. Causal memory therefore implies writes-follow-reads while the converse fails — one session guarantee constrains far less than a per-site serialisation over the causal order — so writes-follow-reads is strictly weaker. Note this is an implication, not an equality: neither Brzezinski et al. nor Viotti & Vukolić state the converse here (see issue #11), and the earlier gloss 'causal = PRAM ∧ writes-follow-reads, Eq. 25' was wrong twice over — Eq. 25 is the definition of WritesFollowReads, not a theorem about causal consistency, and the sources assert only that causal consistency 'requires and includes them all'.

Incomparable with

• Causal Convergence (CCv) — Causal memory and causal convergence are incomparable (Perrin, Mostéfaoui & Jard, PPoPP 2016; Bouajjani et al., POPL 2017, §1 and Fig. 1). Both witnesses are in Bouajjani et al. Fig. 2. History (2a) — pa: wr(x,1); rd(x)▷2 || pb: wr(x,2); rd(x)▷1 — is CM but not CCv, because arbitration would have to place wr(x,2) both after and before wr(x,1) (Ex. 5). History (2b) — pa: wr(z,1); wr(x,1); wr(y,1) || pb: wr(x,2); rd(z)▷0; rd(y)▷1; rd(x)▷2 — is CCv but not CM: reading y=1 drags wr(z,1) into pb's causal past behind wr(x,2), which the earlier rd(z)▷0 contradicts (Ex. 6).
• Causal+ (Convergent Causal) Consistency — Causal+ = CCv ∧ StrongConvergence, and CCv is incomparable to causal memory, so the two are incomparable rather than ordered. This replaces a strictly_weaker edge that read the Viotti-Vukolić containment (Eq. 27) as being against causal memory; it is against CCv. Witnesses, both Bouajjani et al. POPL 2017 Fig. 2: history (2a) is CM but not CCv, hence not causal+; history (2b) is CCv and not CM, and reads each of x, y and z exactly once, so StrongConvergence (V-V Eq. 17, constraining only reads with equal visible-write sets) is vacuous on it — it is causal+ but not CM.
• Real-Time Causal Consistency (RTCausal) — RealTimeCausality = CCv ∧ RealTime, and CCv is incomparable to causal memory. This replaces a strictly_weaker edge that read the Viotti-Vukolić containment (Eq. 28) as being against causal memory; it is against CCv. Witnesses, both Bouajjani et al. POPL 2017 Fig. 2: history (2a) is CM but not CCv, hence not real-time causal; history (2b) is CCv and not CM, and admits a real-time schedule — pa's writes all completing before pb starts — whose arbitration order (pa's writes before wr(x,2)) extends rb, so RealTime (V-V Eq. 9, rb ⊆ ar) holds. RealTime constrains arbitration only, not visibility, so rd(z)▷0 may still miss wr(z,1): it is real-time causal but not CM.
• 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).