Lune

POPL2023Top-tier venue

Kater: Automating Weak Memory Model Metatheory and Consistency Checking

Michalis Kokologiannakis, Ori Lahav, Viktor Vafeiadis

Abstract

The metatheory of axiomatic weak memory models covers questions like the correctness of compilation mappings from one model to another and the correctness of local program transformations according to a given model---topics usually requiring lengthy human investigation. We show that these questions can be solved by answering a more basic question: "Given two memory models, is one weaker than the other?" Moreover, for a wide class of axiomatic memory models, we show that this basic question can be reduced to a language inclusion problem between regular languages, which is decidable. Similarly, implementing an efficient check for whether an execution graph is consistent according to a given memory model has required non-trivial manual effort. Again, we show that such efficient checks can be derived automatically for a wide class of axiomatic memory models, and that incremental consistency checks can be incorporated in GenMC, a state-of-the-art model checker for concurrent programs. As a result, we get the first time- and space-efficient bounded verifier taking the axiomatic memory model as an input parameter.

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.

5 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

  • Optimal Reads-From Consistency Checking for C11-Style Memory Models cites Truly stateless, optimal dynamic partial order reduction
  • How Hard Is Weak-Memory Testing? cites Truly stateless, optimal dynamic partial order reduction
  • How Hard Is Weak-Memory Testing? cites Optimal Reads-From Consistency Checking for C11-Style Memory Models
  • Complexity of Consistency Testing for the Release-Acquire Semantics cites Optimal Reads-From Consistency Checking for C11-Style Memory Models
  • Complexity of Consistency Testing for the Release-Acquire Semantics cites How Hard Is Weak-Memory Testing?
  • Model Checking C/C++ with Mixed-Size Accesses cites Truly stateless, optimal dynamic partial order reduction
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers5

  1. 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
  2. How Hard Is Weak-Memory Testing?Soham Chakraborty, Shankara Narayanan Krishna, Umang Mathur, Andreas PavlogiannisPOPL 2024 · 10 citations
  3. Model Checking C/C++ with Mixed-Size AccessesIason Marmanis, Michalis Kokologiannakis, Viktor VafeiadisPOPL 2025 · 2 citations
  4. Extending the C/C++ Memory Model with Inline AssemblyPaulo Emílio de Vilhena, Ori Lahav, Viktor Vafeiadis, Azalea RaadOOPSLA 2024 · 1 citation
  5. Complexity of Consistency Testing for the Release-Acquire SemanticsR. Govind, S. Krishna, Sanchari Sil, B. SrivathsanFM 2026

Builds on2

  1. Truly stateless, optimal dynamic partial order reductionMichalis Kokologiannakis, Iason Marmanis, Vladimir Gladstein, Viktor VafeiadisPOPL 2022 · 46 citations
  2. Satisfiability modulo ordering consistency theory for multi-threaded program verificationFei He, Zhihang Sun, Hongyu FanPLDI 2021 · 26 citations

Related papers

  1. Model checking for a multi-execution memory modelEvgenii Moiseenko, Michalis Kokologiannakis, Viktor VafeiadisOOPSLA 2022 · 4 citations
  2. CAAT: consistency as a theoryThomas Haas, Roland Meyer, Hernán Ponce de LeónOOPSLA 2022 · 11 citations
  3. RAT-CAT-SAT: Model Checking Memory Consistency ModelsJan Grünke, Thomas Haas, Roland MeyerOOPSLA 2026
  4. RELINCHE: Automatically Checking Linearizability under Relaxed Memory ConsistencyPavel Golovin, Michalis Kokologiannakis, Viktor VafeiadisPOPL 2025 · 4 citations
  5. Decidable verification under a causally consistent shared memoryOri Lahav, Udi BokerPLDI 2020 · 30 citations
Dusk over the sea between two cliffs drawn in fine vertical lines