betaFeedback

WorksComputer Science

A Unifying Metatheorem on Weak-Memory Robustness

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 PP 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.

Introduction

Sequential Consistency (SC) is the standard view of communication in concurrency, whereby a thread’s modification of shared memory is immediately visible to the whole system [46]. This allows program executions to admit a simple, sequential representation, that reflects the mental model of most practitioners in concurrent programming. In practice, however, interthread communication is considerably more involved, owing to compiler optimizations as well as architectural features such as buffers, caches, and speculative execution. These features can cause threads to hold divergent views of the shared memory, and produce highly complex and counterintuitive weak behaviors. Memory models [6] are formal specifications of the behaviors that a program may exhibit in such a system, and have become standard in programming (e.g., for C/C++ [15], Java [48], Rust [67], OCaml [32], the Linux Kernel [8]) and hardware design (e.g., SPARC/x86-TSO [63], Arm [56]).

One desirable property of a program P executing under a memory model MMMM is robustness, which specifies that P does not exhibit any weak behaviors under MMMM [19, 64]. A robust program, thus, runs with the efficiency of the optimizations allowed by MMMM, while following the simple mental and reasoning model of SC. Robust programs further admit SC-based verification techniques, which are far more efficient and lightweight, as typically verification under weak memory is of much higher complexity [12, 42], or even undecidable [1, 12, 23].

Authors’ Contact Information: Giovanna Kobus Conrado, Aarhus University, Aarhus, Denmark, [email protected]; Stephan Spengler, Uppsala University, Uppsala, Sweden, [email protected]; Mohamed Faouzi Atig, Uppsala University, Uppsala, Sweden, [email protected]; Andreas Pavlogiannis, Aarhus University, Aarhus, Denmark, [email protected]. As such, algorithmically deciding whether a program is robust against a memory model has been studied extensively across many models. Case after case, the problem was proven to be decidable in PSPACE for TSO [18, 19], PSO [29], RMO [29], POWER [30], RA [44], and a C11-style model [50]. Analogous results for transactional models further imply a PSPACE bound for the RMW-free fragments of SRA and WRA [14]. At this point, it is natural to ask whether each case indeed requires individual treatment, or they all fall under the umbrella of a single, root argument. Is there a unifying theory for weak-memory robustness?

Our contributions. This paper answers this question affirmatively for a broad class of memory models. Our starting point is Kater [37], which observes that most popular memory models are expressible in Kozen’s Kleene Algebra with Tests (KAT) [40]. We show that KAT-definability suffices to decide the robustness question uniformly and, complexity-wise, optimally, under a natural prefix-closedness condition. We summarize here our main contributions, while we refer to the coming sections for formal definitions and proofs.

We consider program executions represented as standard execution graphs [13, 45] G=⟨E,sb,rf,mb⟩G = \langle E, \mathrm{sb}, \mathrm{rf}, \mathrm{mb} \rangle, where EE is a set of events comprising the execution, sb represents the execution order of each thread, rf is a reads-from relation pairing reading events with the writes they observe, and mb represents the order in which writes modify the shared memory. Our primary result is a unifying metatheorem for weak-memory robustness, which we have also formalized in Lean1.

Theorem 1.1. Given any concurrent program P and any prefix-closed memory model MM defined in KAT, deciding whether P is robust against MM is in PSPACE.

Prefix-closedness is the natural property that the execution of any program can be constructed incrementally as the program runs, and is satisfied by most common memory models. Theorem 1.1 unifies the PSPACE robustness of nearly all prior work2, and extends the results for SRA and WRA from their RMW-free fragments to the full models. Moreover, it proves that robustness is in PSPACE for several new memory models, e.g., the full RC11 [45], the OCaml memory model [32], LRA [65], and PSI [58] (in its shared-memory realization with unary transactions)3. This closes all memory models that were left open in [44] (with PSI restricted to unary transactions). We further remark that robustness is at least as hard as state reachability under SC, against any memory model that can simulate SC (which is often easy, e.g., by utilizing CAS operations or memory fences [9]). In such cases, robustness becomes PSPACE-hard, and thus Theorem 1.1 is tight.

We prove Theorem 1.1 by showing that non-robust programs always contain a regular set of weak executions that can be represented efficiently. This follows the high-level approach of Courcelle’s celebrated work on MSO for graphs [26]; however, Courcelle’s theorem gives a much larger, non-elementary complexity bound. To arrive at PSPACE, we first prove that SC-consistent executions have bounded pathwidth. This, together with the prefix-closedness of MM, implies that non-robust programs always exhibit weak executions of bounded pathwidth. Thus, the search for a witness reduces to searching for a bounded-pathwidth execution of P that is MM-consistent and SC-inconsistent. To perform this search, we define an algebra of graph operations, so that a finite sequence of such operations represents the path decomposition of an execution. We then develop dedicated automata for verifying that such an execution constitutes a robustness violation witness, i.e., that it is (i) valid for P, (ii) MM-consistent, and (iii) SC-inconsistent. Crucially, we ensure that each automaton transition can be verified in polynomial space, leading to our PSPACE bound.

Our automata-theoretic treatment further implies that robustness is always efficiently monitorable in a dynamic setting, e.g., in the spirit of the tool Sober for TSO [20], or the recent Rsan for a C11-style model [49]. Thus, although such tools rest on clever insights and memory-model specific optimizations to be efficient, their existence also follows from a unifying algorithmic principle.

Although the prefix-closedness condition of Theorem 1.1 is satisfied by most common memory models, it is not universal. E.g., the, KAT-definable, Relaxed model is not prefix-closed. It is, thus, natural to ask whether this condition is necessary. We prove that it cannot be dropped, in general.

Theorem 1.2. Robustness against Relaxed is undecidable, already over programs with two threads and four memory locations.

Finally, we implement the algorithm behind Theorem 1.1 in a prototype tool RoboKAT, which is parametric on the memory model. We use RoboKAT to check robustness against nine memory models, including RC11, OCaml, SRA and PSI, for which, to our knowledge, no sound and complete robustness checker existed. Although its generality comes at a natural performance cost compared to model-specific tools, RoboKAT gives the correct verdict on each of 180 litmus test/model pairs within seconds, and finds all known violations in the Rocker benchmarks [44].

Preliminaries

In this section, we fix notation and recall automata, introduce execution graphs, programs, and memory models, and define robustness, the main subject of this work.

Background

General notation. Given an integer ii, we let [i]={1,…,i}[i] = \{1, \ldots, i\}. For a binary relation RR, we write R?R^{?}, R+R^{+}, R∗R^{*}, and R−1R^{-1} for its reflexive, transitive, and reflexive-transitive closures and its inverse, respectively. We denote by R1;R2R_{1}; R_{2} the composition of R1R_{1} and R2R_{2}. We write irr⁡(R)\operatorname{irr}(R), acy⁡(R)\operatorname{acy}(R), and emp⁡(R)\operatorname{emp}(R) to indicate that RR is irreflexive, acyclic, and empty, respectively. We occasionally call ⟨e1,e2⟩∈R\langle e_{1}, e_{2}\rangle\in R an edge, written e1→Re2e_{1} \xrightarrow{R} e_{2}. Given a set SS, we write [S][S] for the identity relation on SS. A binary relation RR is a successor relation on a finite set XX if it is the transitive reduction of some total order on XX.

Labeled transition systems. A labeled transition system (LTS) is a tuple T=⟨Q,Σ,Δ,init⁡⟩\mathcal{T} = \langle Q, \Sigma, \Delta, \operatorname{init}\rangle, where (i) QQ is a finite set of states, (ii) Σ\Sigma is a finite alphabet, (iii) Δ⊆Q×(Σ∪{ϵ})×Q\Delta\subseteq Q \times(\Sigma\cup\{\epsilon\}) \times Q is a transition relation, and (iv) init⁡∈Q\operatorname{init} \in Q is the initial state. We write p→αqp \xrightarrow{\alpha} q for ⟨p,α,q⟩∈Δ\langle p, \alpha, q\rangle\in\Delta, and call the transition silent if α=ϵ\alpha= \epsilon. For a transition δ=⟨p,α,q⟩\delta= \langle p, \alpha, q\rangle, we let src⁡(δ)=p\operatorname{src}(\delta) = p, tgt⁡(δ)=q\operatorname{tgt}(\delta) = q, and lab⁡(δ)=α\operatorname{lab}(\delta) = \alpha. A run of T\mathcal{T} is a sequence init⁡→α1p1→α2⋯→αnpn\operatorname{init} \xrightarrow{\alpha_{1}} p_{1} \xrightarrow{\alpha_{2}} \cdots\xrightarrow{\alpha_{n}} p_{n} of transitions starting at init. The language L(T)⊆Σ∗\mathcal{L}(\mathcal{T}) \subseteq\Sigma^{*} contains every word α1α2⋯αn\alpha_{1}\alpha_{2}\cdots\alpha_{n} that induces a run of T\mathcal{T}. The size of T\mathcal{T} is ∣T∣=∣Q∣+∣Δ∣|\mathcal{T}| = |Q| + |\Delta|.

Word automata. A word automaton is a tuple A=⟨Q,Σ,Δ,init⁡,QF⟩\mathcal{A} = \langle Q, \Sigma, \Delta, \operatorname{init}, Q_{F}\rangle, where ⟨Q,Σ,Δ,init⁡⟩\langle Q, \Sigma, \Delta, \operatorname{init}\rangle is an LTS and QF⊆QQ_{F} \subseteq Q is a set of accepting states. We call a word α1α2…αn\alpha_{1}\alpha_{2}\ldots\alpha_{n} of A\mathcal{A} if it induces a run in A\mathcal{A} ending in QFQ_{F}. A\mathcal{A} is deterministic if Δ\Delta is a function with no silent transitions.

Execution Graphs

Program domains. We consider concurrent programs consisting of a finite set of threads Tid⁡\operatorname{Tid}. Each thread executes events, and communicates with others through a finite set Loc⁡\operatorname{Loc} of shared locations that store values from a finite set Val⁡\operatorname{Val}. Events further carry an annotation from a finite set Ann⁡\operatorname{Ann}.

Labels and events. A label is a read ra(t,x,v)r_a(t,x,v), a write wa(t,x,v)w_a(t,x,v), a read-modify-write (RMW) rmwa(t,x,vr,vw)rmw_a(t,x,v_r,v_w), or a fence fa(t)f_a(t), where t∈Tidt \in\mathrm{Tid} is a thread, x∈Locx \in\mathrm{Loc} is a location, vv, vrv_r, vw∈Valv_w \in\mathrm{Val} are values, and a∈Anna \in\mathrm{Ann} is an annotation (e.g., an access mode, such as rlx in RC11). We let Lab be the set of labels. An event e=⟨id,lab⟩e = \langle\mathrm{id}, \mathrm{lab} \rangle consists of an identifier id∈N\mathrm{id} \in\mathbb{N} and a label lab∈Lab\mathrm{lab} \in\mathrm{Lab}, and E is the set of events. We write lab(e)\mathrm{lab}(e), tid(e)\mathrm{tid}(e), opr(e)∈{r,w,rmw,f}\mathrm{opr}(e) \in\{r,w,rmw,f\}, and ann(e)\mathrm{ann}(e) for the label, thread, operation, and annotation of ee, and loc(e)\mathrm{loc}(e), valr(e)\mathrm{val}_r(e), and valw(e)\mathrm{val}_w(e) for its location and the values it reads and writes, when defined (e.g., a fence has no location and no value). We use the same notation for labels. We identify events with their labels when identifiers are irrelevant (e.g., wa(t,x,v)w_a(t,x,v)), and may further omit components that are irrelevant or clear from the context (e.g., w(x)w(x) or facqf_{\mathrm{acq}}). We let R, W, RMW, and F be the sets of read, write, RMW, and fence events, respectively, and use the same names for the corresponding sets of labels. For X⊆EX \subseteq E or X⊆LabX \subseteq\mathrm{Lab}, t∈Tidt \in\mathrm{Tid}, and x∈Locx \in\mathrm{Loc}, we let XtX^t and XxX_x be the elements of XX of thread tt and of location xx, respectively.

Execution graphs. Under weak memory, program executions are often represented as execution graphs [45], also called candidate executions [13]. An execution graph is a tuple G=⟨E,sb,rf,mb⟩G = \langle E,\mathrm{sb},\mathrm{rf},\mathrm{mb}\rangle, where E⊆EE \subseteq\mathcal{E} is a finite set of events, and sb, rf, and mb are binary relations over EE that are well-formed, in the following sense.

  • The sequenced-before relation sb records the order in which events are issued by each thread, by relating each event to its immediate successor. Formally, sb is well-formed if it is the union of successor relations on EtE^t, one per t∈Tidt \in\mathrm{Tid}.

  • The reads-from relation rf relates each read/RMW event to the write/RMW event it reads from. Formally, rf is well-formed if rf⊆⋃x∈Loc(Wx∪RMWx)×(Rx∪RMWx)\mathrm{rf} \subseteq\bigcup_{x \in\mathrm{Loc}} (W_x \cup\mathrm{RMW}_x) \times(R_x \cup\mathrm{RMW}_x), rf−1\mathrm{rf}^{-1} is a function with domain E∩(R∪RMW)E \cap(R \cup\mathrm{RMW}), and valw(e1)=valr(e2)\mathrm{val}_w(e_1) = \mathrm{val}_r(e_2) for each e1rfe2e_1 \mathrel{\mathrm{rf}} e_2.

  • The modifies-before relation mb orders the writes/RMWs on each location. Formally, mb is well-formed if it is the union of successor relations on Ex∩(W∪RMW)E_x \cap(W \cup\mathrm{RMW}), one per x∈Locx \in\mathrm{Loc}.

References

  1. [1]Parosh Aziz Abdulla, Jatin Arora, Mohamed Faouzi Atig, and Shankaranarayanan Krishna. Verification of programs under the release-acquire semantics. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2019, page 1117–1132, New York, NY, USA, 2019. Association for Computing Machinery. doi:10.1145/3314221.3314649.DOI
  2. [2]Parosh Aziz Abdulla, Mohamed Faouzi Atig, and Tuan-Phong Ngo. The Best of Both Worlds: Trading Efficiency and Optimality in Fence Insertion for TSO. In Jan Vitek, editor, Programming Languages and Systems, volume 9032, pages 308–332. Springer Berlin Heidelberg, Berlin, Heidelberg, 2015. URL: http://link.springer.com/10.1007/978-3-662-46669-8_13, doi:10.1007/978-3-662-46669-8_13.DOI
  3. [3]S. V. Adve and Mark D. Hill. A Unified Formalization of Four Shared-Memory Models. IEEE Trans. Parallel Distrib. Syst., 4(6):613–624, June 1993. doi:10.1109/71.242161.DOI
  4. [4]Sarita V. Adve and Mark D. Hill. Weak Ordering—a new definition. In Proceedings of the 17th Annual International Symposium on Computer Architecture, ISCA ’90, page 2–14, New York, NY, USA, 1990. Association for Computing Machinery. doi:10.1145/325164.325100.DOI
  5. [5]C. Aiswarya, Pascal Baumann, Prakash Saivasan, Lia Schütze, and Georg Zetzsche. Bounded Treewidth, Multiple Context-Free Grammars, and Downward Closures. Proceedings of the ACM on Programming Languages, 10(POPL):2142–2173, January 2026. URL: https://dl.acm.org/doi/10.1145/3776716, doi:10.1145/3776716.DOI
  6. [6]Jade Alglave. A formal hierarchy of weak memory models. Formal Methods in System Design, 41(2):178–210, October 2012. doi:10.1007/s10703-012-0161-5.DOI
  7. [7]Jade Alglave, Daniel Kroening, Vincent Nimal, and Daniel Poetzl. Don’t sit on the fence: A static analysis approach to automatic fence insertion. ACM Trans. Program. Lang. Syst., 39(2), May 2017. doi:10.1145/2994593.DOI
  8. [8]Jade Alglave, Luc Maranget, Paul E. McKenney, Andrea Parri, and Alan Stern. Frightening Small Children and Disconcerting Grown-ups: Concurrency in the Linux Kernel. In Proceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS ’18, pages 405–418, New York, NY, USA, March 2018. Association for Computing Machinery. doi:10.1145/3173162.3177156.DOI
  9. [9]Jade Alglave, Luc Maranget, Susmit Sarkar, and Peter Sewell. Weak Memory Models. In Tayssir Touili, Byron Cook, and Paul Jackson, editors, Computer Aided Verification, pages 258–272, Berlin, Heidelberg, 2010. Springer. doi:10.1007/978-3-642-14295-6_25.DOI
  10. [10]Jade Alglave, Luc Maranget, and Michael Tautschnig. Herding cats: Modelling, simulation, testing, and data mining for weak memory. ACM Trans. Program. Lang. Syst., 36(2), July 2014. doi:10.1145/2627752.DOI
  11. [11]Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, USA, 1st edition, 2009.
  12. [12]Mohamed Faouzi Atig, Ahmed Bouajjani, Sebastian Burckhardt, and Mardanl Musuvathi. On the verification problem for weak memory models. In Proceedings of the 37th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’10, pages 7–18, New York, NY, USA, January 2010. Association for Computing Machinery. doi:10.1145/1706299.1706303.DOI
  13. [13]Mark Batty, Scott Owens, Susmit Sarkar, Peter Sewell, and Tjark Weber. Mathematizing C++ concurrency. In Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’11, pages 55–66, New York, NY, USA, January 2011. Association for Computing Machinery. URL: https://dl.acm.org/doi/10.1145/1926385.1926394, doi:10.1145/1926385.1926394.DOI
  14. [14]Sidi Mohamed Beillahi, Ahmed Bouajjani, and Constantin Enea. Robustness against transactional causal consistency. In International Conference on Concurrency Theory, 2019. URL: https://api.semanticscholar.org/CorpusID:195750509.
  15. [15]Hans-J. Boehm and Sarita V. Adve. Foundations of the C++ concurrency memory model. In Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’08, pages 68–78, New York, NY, USA, June 2008. Association for Computing Machinery. URL: https://dl.acm.org/doi/10.1145/1375581.1375591, doi:10.1145/1375581.1375591.DOI
  16. [16]Hans-J. Boehm, Olivier Giroux, and Viktor Vafeiadis. P0982R1: Weaken release sequences. ISO/IEC JTC1/SC22/WG21 paper, November 2018. URL: https://wg21.link/p0982r1.
  17. [17]Benedikt Bolig, Cinzia Di Giusto, Alain Finkel, Laetitia Laversa, Etienne Lozes, and Amrita Suresh. A Unifying Framework for Deciding Synchronizability. LIPIcs, Volume 203, CONCUR 2021, 203:14:1–14:18, 2021. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2021.14, doi:10.4230/LIPIcs.CONCUR.2021.14.
  18. [18]Ahmed Bouajjani, Egor Devenetc, and Roland Meyer. Checking and Enforcing Robustness against TSO. In Matthias Felleisen and Philippa Gardner, editors, Programming Languages and Systems, pages 533–553, Berlin, Heidelberg, 2013. Springer. doi:10.1007/978-3-642-37036-6_29.DOI
  19. [19]Ahmed Bouajjani, Roland Meyer, and Eike Möhlmann. Deciding robustness against total store ordering. In Proceedings of the 38th International Conference on Automata, Languages and Programming - Volume Part II, ICALP’11, page 428–440, Berlin, Heidelberg, 2011. Springer-Verlag.DOI
  20. [20]Sebastian Burckhardt and Madanlal Musuvathi. Effective Program Verification for Relaxed Memory Models. In Aarti Gupta and Sharad Malik, editors, Computer Aided Verification, pages 107–120, Berlin, Heidelberg, 2008. Springer. doi:10.1007/978-3-540-70545-1_12.DOI
  21. [21]Soham Chakraborty, Shankara Narayanan Krishna, Umang Mathur, and Andreas Pavlogiannis. How Hard Is Weak-Memory Testing? Proceedings of the ACM on Programming Languages, 8(POPL):66:1978–66:2009, January 2024. URL: https://dl.acm.org/doi/10.1145/3632908, doi:10.1145/3632908.DOI
  22. [22]Giovanna Kobus Conrado and Andreas Pavlogiannis. An MSO Framework for Weak-Memory Verification and Robustness. In Ana Sokolova and Patrick Totzke, editors, 37th International Conference on Concurrency Theory (CONCUR 2026), volume 391 of Leibniz International Proceedings in Informatics (LIPIcs), pages 25:1–25:23, Dagstuhl, Germany, 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2026.25, doi:10.4230/LIPIcs.CONCUR.2026.25.DOI
  23. [23]Giovanna Kobus Conrado and Andreas Pavlogiannis. On the decidability of verification under release/acquire, 2026. URL: https://arxiv.org/abs/2604.13683, arXiv:2604.13683.
  24. [24]B. Courcelle. The monadic second-order logic of graphs iii : tree-decompositions, minors and complexity issues. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, 26(3):257–286, 1992. URL: http://eudml.org/doc/92418.DOI
  25. [25]Bruno Courcelle. The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Information and Computation, 85(1):12–75, 1990. URL: https://www.sciencedirect.com/science/article/pii/089054019900043H, doi:10.1016/0890-5401(90)90043-H.DOI
  26. [26]Bruno Courcelle and Joost Engelfriet. Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2012.
  27. [27]Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer Publishing Company, Incorporated, 1st edition, 2015.
  28. [28]Aiswarya Cyriac, Paul Gastin, and K. Narayan Kumar. MSO Decidability of Multi-Pushdown Systems via Split-Width. In David Hutchison, Takeo Kanade, Josef Kittler, Jon M. Kleinberg, Friedemann Mattern, John C. Mitchell, Moni Naor, Oscar Nierstrasz, C. Pandu Rangan, Bernhard Steffen, Madhu Sudan, Demetri Terzopoulos, Doug Tygar, Moshe Y. Vardi, Gerhard Weikum, Maciej Koutny, and Irek Ulidowski, editors, CONCUR 2012 – Concurrency Theory, volume 7454, pages 547–561. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. doi:10.1007/978-3-642-32940-1_38.DOI
  29. [29]Egor Devenetc. Robustness against Relaxed Memory Models. doctoral thesis, Technische Universität Kaiserslautern, 2015. URL: https://nbn-resolving.de/urn:nbn:de:hbz:386-kluedo-40743.
  30. [30]Egor Devenetc and Roland Meyer. Robustness against power is pspace-complete. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming, pages 158–170, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg.
  31. [31]Cinzia Di Giusto, Davide Ferré, Laetitia Laversa, and Etienne Lozes. A Partial Order View of Message-Passing Communication Models. Proceedings of the ACM on Programming Languages, 7(POPL):55:1601–55:1627, January 2023. URL: https://dl.acm.org/doi/10.1145/3571248, doi:10.1145/3571248.DOI
  32. [32]Stephen Dolan, K. Sivaramakrishnan, and Anil Madhavapeddy. Bounding data races in space and time. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 242–255, Philadelphia PA USA, June 2018. ACM. doi:10.1145/3192366.3192421.
  33. [33]Alain Finkel and Etienne Lozes. Synchronizability of Communicating Finite State Machines is not Decidable. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 122:1–122:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.122, doi:10.4230/LIPIcs.ICALP.2017.122.DOI
  34. [34]Kouros Gharachorloo, Sarita V. Adve, Anoop Gupta, John L. Hennessy, and Mark D. Hill. Programming for different memory consistency models. Journal of Parallel and Distributed Computing, 15(4):399–407, 1992. URL: https://www.sciencedirect.com/science/article/pii/074373159290052O, doi:10.1016/0743-7315(92)90052-O.
  35. [35]G.J. Holzmann. The model checker spin. IEEE Transactions on Software Engineering, 23(5):279–295, 1997. doi: 10.1109/32.588521.DOI
  36. [36]Michalis Kokologiannakis, Ori Lahav, Konstantinos Sagonas, and Viktor Vafeiadis. Effective stateless model checking for c/c++ concurrency. Proc. ACM Program. Lang., 2(POPL), December 2017. doi: 10.1145/3158105.DOI
  37. [37]Michalis Kokologiannakis, Ori Lahav, and Viktor Vafeiadis. Kater: Automating Weak Memory Model Metatheory and Consistency Checking. Reproduction package for article: "Kater: Automating Weak Memory Metatheory and Consistency Checking", 7(POPL):19:544–19:572, January 2023. URL: https://dl.acm.org/doi/10.1145/3571212, doi: 10.1145/3571212.DOI
  38. [38]Michalis Kokologiannakis, Azalea Raad, and Viktor Vafeiadis. Model checking for weakly consistent libraries. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2019, page 96–110, New York, NY, USA, 2019. Association for Computing Machinery. doi:10.1145/3314221.3314609.DOI
  39. [39]Dexter Kozen. Lower bounds for natural proof systems. In 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), pages 254–266, 1977. doi:10.1109/SFCS.1977.16.DOI
  40. [40]Dexter Kozen. Kleene algebra with tests. ACM Trans. Program. Lang. Syst., 19(3):427–443, May 1997. doi:10.1145/256167.256195.DOI
  41. [41]Dexter Kozen. Automata on guarded strings and applications. Technical report, USA, 2001.
  42. [42]Ori Lahav and Udi Boker. What’s Decidable About Causally Consistent Shared Memory? ACM Transactions on Programming Languages and Systems, 44(2):1–55, June 2022. doi:10.1145/3505273.DOI
  43. [43]Ori Lahav, Nick Giannarakis, and Viktor Vafeiadis. Taming release-acquire consistency. SIGPLAN Not., 51(1):649–662, January 2016. doi:10.1145/2914770.2837643.DOI
  44. [44]Ori Lahav and Roy Margalit. Robustness against release/acquire semantics. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2019, page 126–141, New York, NY, USA, 2019. Association for Computing Machinery. doi:10.1145/3314221.3314604.DOI
  45. [45]Ori Lahav, Viktor Vafeiadis, Jeehoon Kang, Chung-Kil Hur, and Derek Dreyer. Repairing sequential consistency in C/C++11. In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2017, pages 618–632, New York, NY, USA, June 2017. Association for Computing Machinery. doi:10.1145/3062341.3062352.DOI
  46. [46]Lamport. How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs. IEEE Transactions on Computers, C-28(9):690–691, September 1979. doi:10.1109/TC.1979.1675439.DOI
  47. [47]P. Madhusudan and Gennaro Parlato. The tree width of auxiliary storage. ACM SIGPLAN Notices, 46(1):283–294, January 2011. URL: https://dl.acm.org/doi/10.1145/1925844.1926419, doi:10.1145/1925844.1926419.DOI
  48. [48]Jeremy Manson, William Pugh, and Sarita V. Adve. The Java memory model. In Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’05, pages 378–391, New York, NY, USA, January 2005. Association for Computing Machinery. URL: https://dl.acm.org/doi/10.1145/1040305.1040336, doi:10.1145/1040305.1040336.DOI
  49. [49]Roy Margalit, Michalis Kokologiannakis, Shachar Itzhaky, and Ori Lahav. Dynamic robustness verification against weak memory. Proc. ACM Program. Lang., 9(PLDI), June 2025. doi:10.1145/3792277.DOI
  50. [50]Roy Margalit and Ori Lahav. Verifying observational robustness against a c11-style memory model. Proc. ACM Program. Lang., 5(POPL), January 2021. doi:10.1145/3434285.DOI
  51. [51]OCaml Labs. Memory model for OCaml (hard formalisation). https://github.com/ocamllabs/ocaml-memory-model, 2017. herdtools7 formalisation of the Multicore OCaml memory model. Accessed: 2026-11-12.
  52. [52]Peizhao Ou and Brian Demsky. Automo: automatic inference of memory order parameters for c/c++11. In Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2015, page 221–240, New York, NY, USA, 2015. Association for Computing Machinery. doi:10.1145/2814270.2814286.DOI
  53. [53]Scott Owens. Reasoning about the implementation of concurrency abstractions on x86-tso. In Proceedings of the 24th European Conference on Object-Oriented Programming, ECOOP’10, page 478–503, Berlin, Heidelberg, 2010. Springer-Verlag.
  54. [54]Anton Podkopaev, Ori Lahav, and Viktor Vafeiadis. Bridging the gap between programming languages and hardware weak memory models. Proc. ACM Program. Lang., 3(POPL), January 2019. doi:10.1145/3290382.DOI
  55. [55]Emil L. Post. A variant of a recursively unsolvable problem. Bulletin of the American Mathematical Society, 52:264–268, 1946. URL: https://api.semanticscholar.org/CorpusID:122948861.DOI
  56. [56]Christopher Pulte, Shaked Flur, Will Deacon, Jon French, Susmit Sarkar, and Peter Sewell. Simplifying arm concurrency: multicopy-atomic axiomatic and operational models for armv8. Proc. ACM Program. Lang., 2(POPL), December 2017. doi:10.1145/3158107.DOI
  57. [57]Azalea Raad, Michalis Kokologiannakis, Viktor Vafeiadis, and Conrad Watt. A Formal Account of the Wasm 3.0 Concurrency Model. Proceedings of the ACM on Programming Languages, 10(OOPSLA2):333:515–333:543, October 2026. URL: https://dl.acm.org/doi/10.1145/3839465, doi:10.1145/3839465.DOI
  58. [58]Azalea Raad, Ori Lahav, and Viktor Vafeiadis. On parallel snapshot isolation and release/acquire consistency. In Amal Ahmed, editor, Programming Languages and Systems, pages 940–967, Cham, 2018. Springer International Publishing.DOI
  59. [59]Sebastian Reimers, Dennis Sprokholt, Martin Fink, Theofilos Augustis, Simon Kammermeier, Rodrigo C. O. Rocha, Tom Spink, Redha Gouicem, Soham Chakraborty, and Pramod Bhattotia. Arancini: A hybrid binary translator for weak memory model architectures. In Proceedings of the 31st ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2, ASPLOS ’26, page 157–174, New York, NY, USA, 2026. Association for Computing Machinery. doi:10.1145/3779212.3790127.DOI
  60. [60]RISC-V Foundation. The RISC-V Instruction Set Manual, Volume I: Unprivileged ISA, December 2019. Document Version 20191213.
  61. [61]Neil Robertson and Paul D Seymour. Graph minors. i. excluding a forest. Journal of Combinatorial Theory, Series B, 35(1):39–61, 1983.DOI
  62. [62]Susmit Sarkar, Kayvan Memarian, Scott Owens, Mark Batty, Peter Sewell, Luc Maranget, Jade Alglave, and Derek Williams. Synchronising c/c++ and power. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’12, page 311–322, New York, NY, USA, 2012. Association for Computing Machinery. doi:10.1145/2254064.2254102.DOI
  63. [63]Peter Sewell, Susmit Sarkar, Scott Owens, Francesco Zappa Nardelli, and Magnus O. Myreen. X86-TSO: A rigorous and usable programmer’s model for x86 multiprocessors. Communications of the ACM, 53(7):89–97, July 2010. doi:10.1145/1785414.1785443.DOI
  64. [64]Dennis Shasha and Marc Snir. Efficient and correct execution of parallel programs that share memory. ACM Transactions on Programming Languages and Systems, 10(2):282–312, April 1988. URL: https://dl.acm.org/doi/10.1145/42190.42277, doi:10.1145/42190.42277.DOI
  65. [65]Abhishek Kr Singh and Ori Lahav. Decidable verification under localized release-acquire concurrency. In Tools and Algorithms for the Construction and Analysis of Systems: 30th International Conference, TACAS 2024, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2024, Luxembourg City, Luxembourg, April 6–11, 2024, Proceedings, Part III, page 235–254, Berlin, Heidelberg, 2024. Springer-Verlag. doi:10.1007/978-3-031-57256-2_12.DOI
  66. [66]A. P. Sistla and E. M. Clarke. The complexity of propositional linear temporal logics. J. ACM, 32(3):733–749, July 1985. doi:10.1145/3828.3837.DOI
  67. [67]The Rust Project Developers. The Rustonomicon: Atomics. https://doc.rust-lang.org/nomicon/atomics.html. Accessed November 2026.
  68. [68]Salvatore La Torre, Parthasarathy Madhusudan, and Gennaro Parlato. A robust class of context-sensitive languages. In Proceedings of the 22nd Annual IEEE Symposium on Logic in Computer Science, LICS ’07, page 161–170, USA, 2007. IEEE Computer Society. doi:10.1109/LICS.2007.9.DOI

Paper details

vlnc:W_g6hyg4sa
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude AI, ChatGPT

View statement
Looking for related papers…
Contents