A Unifying Metatheorem on Weak-Memory Robustness
Giovanna Kobus Conrado, Stephan Spengler, Mohamed Faouzi Atig, Andreas Pavlogiannis
cs.PL
Nov 17, 2026 · v1
cs.LO
TL;DR
The correctness of the unifying robustness metatheorem for KAT-definable memory models is formalized in Lean with a public repository; the PSPACE complexity bound is not formalized.
Abstract
Memory models specify the behaviors that concurrent programs may exhibit under compiler and hardware optimizations, which often deviate from Sequential Consistency (SC). Robustness is the property of a program P not exhibiting any weak behaviors when executing under a weak memory model MM, compared to SC. As such, the algorithmic problem of deciding whether $P$ is robust against MM has been studied extensively, and has been repeatedly shown to be in PSPACE for many memory models, such as TSO, PSO, and Release/Acquire. However, each model has required its own, dedicated proof, raising the natural question of whether robustness admits a unifying treatment across memory models. In this work, we answer this question affirmatively for a broad class of memory models definable in Kleene Algebra with Tests (KAT). We prove that robustness against any prefix-closed, KAT-definable memory model is in PSPACE. This metatheorem recovers nearly all prior PSPACE robustness results, and establishes PSPACE membership for several new models, including the full RC11 and the OCaml memory model. We have further formalized the correctness of our approach in Lean. On the other hand, we prove that robustness against the KAT-definable Relaxed model is undecidable, and thus prefix-closedness cannot be dropped, in general. Finally, we implement our algorithm in a prototype tool RoboKAT, and demonstrate its flexibility by checking robustness against nine memory models, several of which are not handled by prior work.
Problem
Deciding whether a concurrent program is robust against a weak memory model (it shows no behaviors beyond Sequential Consistency) has been proven in PSPACE separately for each model. The question is whether one uniform treatment covers many memory models.
Approach
Robustness is reduced to searching for non-robustness witnesses of bounded pathwidth when the memory model is prefix-closed. A graph algebra encodes execution graphs of bounded pathwidth as words. Automata over these words check well-formedness, conformance to the program, and consistency or inconsistency under KAT-definable memory models. The correctness argument is formalized in Lean, but the space-complexity part is not, because Mathlib does not support space complexity.
Results
Robustness against any prefix-closed KAT-definable memory model is in PSPACE. This recovers prior results and adds new ones, including full RC11 and the OCaml memory model. Robustness against the Relaxed model is undecidable, and a Spin-based prototype tool, RoboKAT, checks robustness against nine memory models.