Lune

POPL2024Top-tier venue

How Hard Is Weak-Memory Testing?

Soham Chakraborty, Shankara Narayanan Krishna, Umang Mathur, Andreas Pavlogiannis

Abstract

Weak-memory models are standard formal specifications of concurrency across hardware, programming languages, and distributed systems. A fundamental computational problem is consistency testing: is the observed execution of a concurrent program in alignment with the specification of the underlying system? The problem has been studied extensively across Sequential Consistency (SC) and weak memory, and proven to be NP-complete when some aspect of the input (e.g., number of threads/memory locations) is unbounded. This unboundedness has left a natural question open: are there efficient parameterized algorithms for testing?

The main contribution of this paper is a deep hardness result for consistency testing under many popular weakmemory models: the problem remains NP-complete even in its bounded setting, where candidate executions contain a bounded number of threads, memory locations, and values. This hardness spreads across several Release-Acquire variants of C11, a popular variant of its Relaxed fragment, popular Causal Consistency models, and the POWER architecture. To our knowledge, this is the first result that fully exposes the hardness of weakmemory testing and proves that the problem admits no parameterization under standard input parameters. It also yields a computational separation of these models from SC, x86-TSO, PSO, and Relaxed, for which bounded consistency testing is either known (for SC), or shown here (for the rest), to be in polynomial time.

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.

6 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

  • The Complexity of Dynamic Data Race Prediction cites Fast, sound, and effectively complete dynamic race prediction
  • CSSTs: A Dynamic Data Structure for Partial Orders in Concurrent Execution Analysis cites The Complexity of Dynamic Data Race Prediction
  • CSSTs: A Dynamic Data Structure for Partial Orders in Concurrent Execution Analysis cites Fast, sound, and effectively complete dynamic race prediction
  • CSSTs: A Dynamic Data Structure for Partial Orders in Concurrent Execution Analysis cites C11Tester: a race detector for C/C++ atomics
  • Fixed Parameter Tractable Linearizability Monitoring cites The Complexity of Dynamic Data Race Prediction
  • Fixed Parameter Tractable Linearizability Monitoring cites Optimal prediction of synchronization-preserving races
  • Fixed Parameter Tractable Linearizability Monitoring cites Efficient Decrease-and-Conquer Linearizability Monitoring
  • Fixed Parameter Tractable Linearizability Monitoring cites The Complexity of Testing Message-Passing Concurrency
  • Optimal prediction of synchronization-preserving races cites The Complexity of Dynamic Data Race Prediction
  • Optimal prediction of synchronization-preserving races cites Fast, sound, and effectively complete dynamic race prediction
  • Efficient Decrease-and-Conquer Linearizability Monitoring cites The Complexity of Dynamic Data Race Prediction
  • Efficient Decrease-and-Conquer Linearizability Monitoring cites Fast, sound, and effectively complete dynamic race prediction
  • Efficient Decrease-and-Conquer Linearizability Monitoring cites Optimal prediction of synchronization-preserving races
  • Efficient Decrease-and-Conquer Linearizability Monitoring cites The Complexity of Testing Message-Passing Concurrency
  • The Complexity of Testing Message-Passing Concurrency cites Efficient Decrease-and-Conquer Linearizability Monitoring
  • Efficient Decrease-and-Conquer Linearizability Monitoring cites AWDIT: An Optimal Weak Database Isolation Tester
  • The Complexity of Testing Message-Passing Concurrency cites The Complexity of Dynamic Data Race Prediction
  • The Complexity of Testing Message-Passing Concurrency cites CSSTs: A Dynamic Data Structure for Partial Orders in Concurrent Execution Analysis
  • The Complexity of Testing Message-Passing Concurrency cites Truly stateless, optimal dynamic partial order reduction
  • The Complexity of Testing Message-Passing Concurrency cites Fast, sound, and effectively complete dynamic race prediction
  • The Complexity of Testing Message-Passing Concurrency cites C11Tester: a race detector for C/C++ atomics
  • The Complexity of Testing Message-Passing Concurrency cites Optimal prediction of synchronization-preserving races
  • The Complexity of Testing Message-Passing Concurrency cites AWDIT: An Optimal Weak Database Isolation Tester
  • AWDIT: An Optimal Weak Database Isolation Tester cites The Complexity of Dynamic Data Race Prediction
  • AWDIT: An Optimal Weak Database Isolation Tester cites CSSTs: A Dynamic Data Structure for Partial Orders in Concurrent Execution Analysis
  • AWDIT: An Optimal Weak Database Isolation Tester cites Fast, sound, and effectively complete dynamic race prediction
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers6

  1. CSSTs: A Dynamic Data Structure for Partial Orders in Concurrent Execution AnalysisHünkar Can Tunç, Ameya Prashant Deshmukh, Berk Çirisci, Constantin Enea et al.ASPLOS 2024 · 6 citations
  2. AWDIT: An Optimal Weak Database Isolation TesterLasse Møldrup, Andreas PavlogiannisPLDI 2025 · 5 citations
  3. Efficient Decrease-and-Conquer Linearizability MonitoringLee Zheng Han, Umang MathurOOPSLA 2025 · 2 citations
  4. The Complexity of Testing Message-Passing ConcurrencyZheng Shi, Lasse Møldrup, Umang Mathur, Andreas PavlogiannisPOPL 2026 · 2 citations
  5. Fixed Parameter Tractable Linearizability MonitoringLee Zheng Han, Umang MathurPLDI 2026

Builds on10

  1. Truly stateless, optimal dynamic partial order reductionMichalis Kokologiannakis, Iason Marmanis, Vladimir Gladstein, Viktor VafeiadisPOPL 2022 · 46 citations
  2. Fast, sound, and effectively complete dynamic race predictionAndreas PavlogiannisPOPL 2020 · 46 citations
  3. Optimal prediction of synchronization-preserving racesUmang Mathur, Andreas Pavlogiannis, Mahesh ViswanathanPOPL 2021 · 36 citations
  4. The Complexity of Dynamic Data Race PredictionUmang Mathur, Andreas Pavlogiannis, Mahesh ViswanathanLICS 2020 · 27 citations
  5. C11Tester: a race detector for C/C++ atomicsWeiyu Luo, Brian DemskyASPLOS 2021 · 26 citations

Related papers

  1. Complexity of Consistency Testing for the Release-Acquire SemanticsR. Govind, S. Krishna, Sanchari Sil, B. SrivathsanFM 2026
  2. 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
  3. Decidable verification under a causally consistent shared memoryOri Lahav, Udi BokerPLDI 2020 · 30 citations
  4. Verifying observational robustness against a c11-style memory modelRoy David Margalit, Ori LahavPOPL 2021 · 22 citations
  5. CAAT: consistency as a theoryThomas Haas, Roland Meyer, Hernán Ponce de LeónOOPSLA 2022 · 11 citations
Dusk over the sea between two cliffs drawn in fine vertical lines