Lune

OOPSLA2022Top-tier venue

Model checking for a multi-execution memory model

Evgenii Moiseenko, Michalis Kokologiannakis, Viktor Vafeiadis

Abstract

Multi-execution memory models, such as Promising and Weakestmo, are an advanced class of weak memory consistency models that justify certain outcomes of a concurrent program by considering multiple candidate executions collectively. While this key characteristic allows them to support effective compilation to hardware models and a wide range of compiler optimizations, it makes reasoning about them substantially more difficult. In particular, we observe that Promising and Weakestmo inhibit effective model checking because they allow some suprisingly weak behaviors that cannot be generated by examining one execution at a time.

We therefore introduce Weakestmo2, a strengthening of Weakestmo by constraining its multi-execution nature, while preserving the important properties of Weakestmo: DRF theorems, compilation to hardware models, and correctness of local program transformations. Our strengthening rules out a class of surprisingly weak program behaviors, which we attempt to characterize with the help of two novel properties: load buffering race freedom and certification locality. In addition, we develop WMC, a model checker for Weakestmo2 with performance close to that of the best tools for per-execution models.

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.

1 top-tier paper has 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

  • Relaxed Memory Concurrency Re-executed cites HMC: Model Checking for Hardware Memory Models
  • Relaxed Memory Concurrency Re-executed cites Promising 2.0: global optimizations in relaxed memory concurrency
  • Relaxed Memory Concurrency Re-executed cites Pomsets with preconditions: a simple model of relaxed memory
  • Relaxed Memory Concurrency Re-executed cites The leaky semicolon: compositional semantic dependencies for relaxed-memory concurrency
  • VSync: push-button verification and optimization for synchronization primitives on weak memory models cites HMC: Model Checking for Hardware Memory Models
  • The leaky semicolon: compositional semantic dependencies for relaxed-memory concurrency cites Promising 2.0: global optimizations in relaxed memory concurrency
  • The leaky semicolon: compositional semantic dependencies for relaxed-memory concurrency cites Pomsets with preconditions: a simple model of relaxed memory
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Relaxed Memory Concurrency Re-executedEvgenii Moiseenko, Matteo Meluzzi, Innokentii Meleshchenko, Ivan Kabashnyi et al.POPL 2025 · 2 citations

Builds on5

  1. Promising 2.0: global optimizations in relaxed memory concurrencySung-Hwan Lee, Minki Cho, Anton Podkopaev, Soham Chakraborty et al.PLDI 2020 · 48 citations
  2. VSync: push-button verification and optimization for synchronization primitives on weak memory modelsJonas Oberhauser, Rafael Lourenco de Lima Chehab, Diogo Behrens, Ming Fu et al.ASPLOS 2021 · 40 citations
  3. HMC: Model Checking for Hardware Memory ModelsMichalis Kokologiannakis, Viktor VafeiadisASPLOS 2020 · 29 citations
  4. Pomsets with preconditions: a simple model of relaxed memoryRadha Jagadeesan, Alan Jeffrey, James RielyOOPSLA 2020 · 28 citations
  5. The leaky semicolon: compositional semantic dependencies for relaxed-memory concurrencyAlan Jeffrey, James Riely, Mark Batty, Simon Cooksey et al.POPL 2022 · 21 citations

Related papers

  1. Verifying optimizations of concurrent programs in the promising semanticsJunpeng Zha, Hongjin Liang, Xinyu FengPLDI 2022 · 5 citations
  2. Kater: Automating Weak Memory Model Metatheory and Consistency CheckingMichalis Kokologiannakis, Ori Lahav, Viktor VafeiadisPOPL 2023 · 15 citations
  3. Sequential reasoning for optimizing compilers under weak memory concurrencyMinki Cho, Sung-Hwan Lee, Dongjae Lee, Chung-Kil Hur et al.PLDI 2022 · 11 citations
  4. 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
  5. Modular data-race-freedom guarantees in the promising semanticsMinki Cho, Sung-Hwan Lee, Chung-Kil Hur, Ori LahavPLDI 2021 · 14 citations
Dusk over the sea between two cliffs drawn in fine vertical lines