PRAM (Pipelined RAM) Consistency
Writes performed by a single process are seen by all other processes in the order they were issued, but writes from different processes may be seen in different orders by different processes. Strictly weaker than processor and causal consistency; incomparable to cache consistency; strictly stronger than slow 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
- Processor Consistency (PC) — Processor consistency is strictly stronger than PRAM consistency (Goodman 1989; Steinke & Nutt 2004).
- Causal Consistency — Causal memory is strictly stronger than PRAM consistency (Steinke & Nutt 2004).
- Strictly stronger than
- Slow Consistency — Slow consistency is strictly weaker than PRAM consistency (Hutto & Ahamad 1990; Steinke & Nutt 2004).
- Read-Your-Writes (Session Guarantee) (RYW) — Brzezinski et al. (2003) proved PRAM consistency holds iff a system provides read-your-writes, monotonic reads and monotonic writes (Viotti & Vukolić 2016, Eq. 20). PRAM is the conjunction of the three, so it implies read-your-writes while the converse fails: read-your-writes is strictly weaker than PRAM.
- Monotonic Reads (Session Guarantee) (MR) — Brzezinski et al. (2003) proved PRAM = read-your-writes ∧ monotonic reads ∧ monotonic writes (Viotti & Vukolić 2016, Eq. 20). PRAM implies monotonic reads while the converse fails, so monotonic reads is strictly weaker than PRAM.
- Monotonic Writes (Session Guarantee) (MW) — Brzezinski et al. (2003) proved PRAM = read-your-writes ∧ monotonic reads ∧ monotonic writes (Viotti & Vukolić 2016, Eq. 20). PRAM implies monotonic writes while the converse fails, so monotonic writes is strictly weaker than PRAM.
- Incomparable with
- Cache Coherence — PRAM and cache consistency are incomparable: PRAM orders a process's own writes globally but not per-location, cache consistency the converse (Goodman 1989; Steinke & Nutt 2004).
References
- Richard J. Lipton, Jonathan S. Sandberg. PRAM: A Scalable Shared Memory. Technical Report CS-TR-180-88, Princeton University, 1988.
- 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