Lune

PLDI2020Top-tier venue

Decidable verification under a causally consistent shared memory

Ori Lahav, Udi Boker

Abstract

Causal consistency is one of the most fundamental and widely used consistency models weaker than sequential consistency. In this paper, we study the verification of safety properties for finite-state concurrent programs running under a causally consistent shared memory model. We establish the decidability of this problem for a standard model of causal consistency (called also "Causal Convergence" and "Strong-Release-Acquire"). Our proof proceeds by developing an alternative operational semantics, based on the notion of a thread potential, that is equivalent to the existing declarative semantics and constitutes a well-structured transition system. In particular, our result allows for the verification of a large family of programs in the Release/Acquire fragment of C/C++11 (RA). Indeed, while verification under RA was recently shown to be undecidable for general programs, since RA coincides with the model we study here for write/write-race-free programs, the decidability of verification under RA for this widely used class of programs follows from our result. The novel operational semantics may also be of independent use in the investigation of weakly consistent shared memory models and their verification.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

7 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Semantics of Remote Direct Memory Access: Operational and Declarative Models of RDMA on TSO Architectures cites Deciding reachability under persistent x86-TSO
  • Semantics of Remote Direct Memory Access: Operational and Declarative Models of RDMA on TSO Architectures cites Extending Intel-x86 consistency and persistency: formalising the semantics of Intel-x86 memory types and non-temporal stores
  • Extending Intel-x86 consistency and persistency: formalising the semantics of Intel-x86 memory types and non-temporal stores cites Deciding reachability under persistent x86-TSO
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers7

  1. Extending Intel-x86 consistency and persistency: formalising the semantics of Intel-x86 memory types and non-temporal storesAzalea Raad, Luc Maranget, Viktor VafeiadisPOPL 2022 · 24 citations
  2. Formal Verification of a Multiprocessor Hypervisor on Arm Relaxed Memory HardwareRunzhou Tao, Jianan Yao, Xupeng Li, Shih-Wei Li et al.SOSP 2021 · 24 citations
  3. Distributed causal memory: modular specification and verification in higher-order distributed separation logicLéon Gondelman, Simon Oddershede Gregersen, Abel Nieto, Amin Timany et al.POPL 2021 · 17 citations
  4. Deciding reachability under persistent x86-TSOParosh Aziz Abdulla, Mohamed Faouzi Atig, Ahmed Bouajjani, K. Narayan Kumar et al.POPL 2021 · 12 citations
  5. Semantics of Remote Direct Memory Access: Operational and Declarative Models of RDMA on TSO ArchitecturesGuillaume Ambal, Brijesh Dongol, Haggai Eran, Vasileios Klimis et al.OOPSLA 2024 · 11 citations

Builds on1

  1. Parameterized verification under TSO is PSPACE-completeParosh Aziz Abdulla, Mohamed Faouzi Atig, Rojin RezvanPOPL 2020 · 15 citations

Related papers

  1. Verifying observational robustness against a c11-style memory modelRoy David Margalit, Ori LahavPOPL 2021 · 22 citations
  2. RGSep under Release/Acquire ConsistencyEllen Arlt, Viktor VafeiadisOOPSLA 2026 · 1 citation
  3. Optimal Reads-From Consistency Checking for C11-Style Memory ModelsHünkar Can Tunç, Parosh Aziz Abdulla, Soham Chakraborty, Shankaranarayanan Krishna et al.PLDI 2023 · 12 citations
  4. How Hard Is Weak-Memory Testing?Soham Chakraborty, Shankara Narayanan Krishna, Umang Mathur, Andreas PavlogiannisPOPL 2024 · 10 citations
  5. Overcoming Memory Weakness with Unified Fairness - Systematic Verification of Liveness in Weak Memory ModelsParosh Aziz Abdulla, Mohamed Faouzi Atig, Adwait Godbole, Shankaranarayanan Krishna et al.CAV 2023 · 9 citations
Dusk over the sea between two cliffs drawn in fine vertical lines