Weak Memory Model Formalisms: Introduction and Survey
Roger C. Su, Robert J. Colvin · 2025
Read Weak Memory Model Formalisms: Introduction and Survey by Roger C. Su, Robert J. Colvin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-04115.txt.
Introduction
Roger Su and Robert Colvin survey the formal methods used to pin down weak memory models, in a paper from 2025. Modern chips and compilers may reorder memory steps, so the order a program lists is not the order others see. That gap makes shared-memory code hard to get right. Exact formal rules are the only firm base for proof.
The survey covers the two main styles of rule writing. One builds traces step by step, and the other states relations between memory events. A stripped-down chip model makes both styles concrete. The authors trace the field's history in hardware and theory. They also sum up what is known about the cost of checking such rules. The piece closes with open paths for tools that reason about low-level code.
Catalog record
| CREATOR | Roger C. Su, Robert J. Colvin |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 121 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-04115
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Weak Memory Model Formalisms: Introduction and Survey Thanks: August 10, 2026 CCS: General and reference Surveys and overviews CCS: Theory of computation Logic CCS: Theory of computation Semantics and reasoning CCS: Software and its engineering Correctness CCS: Software and its engineering Formal methods CCS: Software and its engineering Concurrent programming structures CCS: Computer systems organization Multicore architectures Roger C. Su, Robert J. Colvin Abstract . Memory consistency models define the order in which accesses to shared memory in a concurrent system may be observed to occur. Such models are a necessity since program order is not a reliable indicator of execution order , due to microarchitectural features or compiler transformations. Concurrent programming, already a challenging task, is thus made even harder when weak memory effects must be addressed. A rigorous specification of weak memory models is therefore essential to make this problem tractable for developers of safety- and security-critical, low-level software. In this paper we survey the field of formalisations of weak memory models, including their specification, their effects on execution, and tools and inference systems for reasoning about code. To assist the discussion we also provide an introduction to two styles of formal representation found commonly in the literature (using a much simplified version of Intel’s x86 as the example): a step-by-step construction of traces of the system ( operational semantics ); and with respect to relations between memory events ( axiomatic semantics ). The survey covers some long-standing hardware features that lead to observable weak behaviours, a description of historical developments in practice and in theory, an overview of computability and complexity results, and outlines current and future directions in the field. 1. Introduction Programmers of low-level concurrent systems code – e.g., operating systems or library data structures – need to address the behaviour of the target architecture; specifically, how communication occurs via accesses to shared memory. This is nontrivial, as architectures (single- or multi-core) do not guarantee to execute instructions in the order specified, and nor do compilers guarantee to maintain the order of the program statements in the generated code. This can add to the difficulties already associated with concurrency under the standard, sequential interpretation. For example, consider an Arm or RISC-V processor executing assembly corresponding to the following higher-level code, where one process writes data \mathtt{d} to a shared variable \mathtt{x} and then signals this change to a concurrent process (or processes) via a shared “ \mathtt{flag} ” variable. The reading process spins waiting for the flag to be set and then reads the data from \mathtt{x} into its local state (variable \mathtt{r} ). (1) \mathtt{x:=d\mathrel{;}flag:=1\hskip 10.4999pt\parallel\hskip 10.4999pt(\mathrel{\mathbf{while}}flag\neq 1\mathrel{\mathbf{do}}\{\})\mathrel{;}r:=x} The processor executing the first process can potentially execute the two instructions out of order, since, from the perspective of a single processor, the order is irrelevant to the final values of the two variables. As such, the flag may be set before \mathtt{d} is written to \mathtt{x} , and thus the second process may receive an unintended value. In fact, by the same justification, even if the first process performs its instructions in the order specified, the second processor may execute the load of \mathtt{x} before the loop is resolved (a type of speculative execution ), again resulting in an erroneous value for \mathtt{x} . To address this extra complication introduced by architectures and compiler optimisations, processor vendors and language designers define a “memory model”, a minimal set of constraints about the behaviour of interacting concurrent processes, typically with respect to the order of accesses of shared memory. If those constraints are too weak to enforce the logic of an algorithm, programmers may inject “fences” or related mechanisms that can restore the standard, sequential behaviour of a (segment of a) program. For instance, the use of release/acquire constraints is a well-known programming pattern for addressing weak memory model effects [ Gharachorloo et al. 1990 ] . A release fence, ‘ \mathtt{rel} ’, (in C, atomic_thread_fence(memory_order_release) ) can be injected into the first process of ( 1 ), \mathtt{x:=1\mathrel{;}\mathtt{rel}\mathrel{;}flag:=1} . In tandem with an acquire fence after the loop of the second process these ensure the intended value for \mathtt{x} will be read. However, excessive use of such mechanisms comes with performance penalties, which can be a significant issue for low-level systems code [ Ritson and Owens 2016 ] . Since the early days of multiprocessors (a system consisting of multiple processors) to the present age of multicore processors (each processor consisting of multiple cores), the literature on weak memory models has developed in academia, the commercial sector, and standardisation committees. The issue affects hardware designers, compiler writers, application programmers, and language designers [ Adve and Gharachorloo 1996 ; Adve and Boehm 2010 ] . As yet, no consensus on a particular formal representation has been settled upon, leaving programmers – in particular those requiring formal assurance for the code – with many choices. The company Arm has led the way in formalising their architecture and robustly investigating their design, including with publicly accessible tool support. Their formal model is validated on hardware through the use of thousands of small programs called “litmus tests”. However, the mechanisms for inferring properties of programs using their formalisation are complex, even for simple programs; as a result, many other representations have been considered. In this paper, we survey these diverse formalisms and tools that have been proposed for representing weak memory models. A formal specification of a memory model should preferably match the existing intuitions about processor behaviours and compiler optimisations. Furthermore, it should support an easy enumeration of the consequences: a guide that feeds into the software developers’ effort. Though this paper is primarily aimed at researchers with a background in formal methods, we consider the field from the perspective of a practitioner: • How to specify a memory model? (hardware designers; language designers); • How to understand the effect of a memory model on a program? (compiler writers; application programmers); and • How to formally verify that a program is correct under a particular memory model? (application programmers – specifically for secure or safety-critical systems). Each of these questions has many potential answers, depending on the level of microarchitectural detail vs. abstraction desired, level of tool support, and program properties under question. Scope and Limitations. In this survey we attempt to cover the majority of common formalisations of modern hardware and software weak memory models, with reference to historical developments where there are clear impacts on current practice. We are particularly focussed on formalisations that lead to tools and techniques for inferring properties of programs, i.e., from a developers perspective. We aim to trace the historical development of processor design from the 1960s, through theoretical developments in the 1990s and up to the present day, which includes regular contributions in major publishing venues and refinements of commercial specifications. As a result, we were unable to find a methodical sequence of search terms of the type used in a recent survey on programming language memory models [ Moiseenko et al. 2021 ] . Hence, we do not claim full coverage, but intend that the range of works surveyed is indicative of the state of the field. We do not specifically consider issues related to hardware or compiler construction: