We just hit a fundamental mathematical wall: it is now proven impossible to fully verify certain high-performance concurrent programs.
April 16, 2026
Original Paper
On the Decidability of Verification under Release/Acquire
arXiv · 2604.13683
The Takeaway
A seven-year-old open question in computer science has been settled, and the news isn't good for verification engineers. This paper proves that 'reachability'—knowing if a program can hit an error state—is undecidable in certain common memory models. This means we can never build a perfect tool to guarantee that complex, multi-threaded code is bug-free. It establishes a hard limit on our ability to secure and verify the high-performance software that runs our world. For practitioners, this means moving from 'perfect verification' to 'probabilistic risk management' is now a mathematical necessity. It defines a permanent boundary for the field of software safety.
From the abstract
The verification of concurrent programs under weak-memory models is a burgeoning effort, owing to the increasing adoption of weak memory in concurrent software and hardware. Release/Acquire has become the standard model for high-performance concurrent programming, adopted by common mainstream languages and computer architectures. In a surprising result, Abdulla et al. (PLDI'19) proved that reachability in this model is undecidable when programs have access to atomic Read-Modify-Write (RMW) opera