Mechanized Metatheory of Forward Reasoning for End-to-End Linearizability Proofs
Zachary Kent, Ugur Y. Yavuz, Siddhartha Jayanti, Stephanie Balzer, Guy Blelloch · 2025
Read Mechanized Metatheory of Forward Reasoning for End-to-End Linearizability Proofs by Zachary Kent, Ugur Y. Yavuz, Siddhartha Jayanti, Stephanie Balzer, Guy Blelloch (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-2509-06872.txt.
Introduction
Proving concurrent data structures correct, with machine-checked certainty from start to finish, is advanced by Zachary Kent and four co-authors in a 2025 formal methods paper. Linearizability is the gold standard: every operation must appear to happen in an instant, even when operations overlap in time. A recent forward reasoning technique proves it soundly and completely, but its own foundations were not yet mechanized.
The authors formalize that technique in the Rocq proof assistant and mechanize proofs of its soundness and completeness. Shrinking the trusted base matters, because earlier end-to-end proofs leaned on unmechanized theory. As a case study, they produce a verified end-to-end linearizability proof for a simple concurrent register. The work turns a powerful paper method into one whose guarantees a computer has checked line by line.
Catalog record
| CREATOR | Zachary Kent, Ugur Y. Yavuz, Siddhartha Jayanti, Stephanie Balzer, Guy Blelloch |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 58 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-06872
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Mechanized Metatheory of Forward Reasoning for End-to-End Linearizability Proofs Zachary Kent, Ugur Y. Yavuz, Siddhartha Jayanti, Stephanie Balzer, Guy Blelloch Abstract In the past decade, many techniques have been developed to prove linearizability, the gold standard of correctness for concurrent data structures. Intuitively, linearizability requires that every operation on a concurrent data structure appears to take place instantaneously, even when interleaved with other operations. Most recently, Jayanti et al. presented the first sound and complete “forward reasoning” technique for proving linearizability that relates the behavior of a concurrent data structure to a reference atomic data structure as time moves forward. This technique can be used to produce machine-checked proofs of linearizability in TLA+/TLAPS. However, while Jayanti et al.’s approach is shown to be sound and complete, a mechanization of this important metatheoretic result is still outstanding. As a result, it is not possible to produce verified end-to-end proofs of linearizability. To reduce the size of this trusted computing base, we formalize this forward reasoning technique and mechanize proofs of its soundness and completeness in Rocq. As a case study, we use the approach to produce a verified end-to-end proof of linearizability for a simple concurrent register. Carnegie Mellon [email protected] Boston [email protected] Dartmouth [email protected] Carnegie Mellon [email protected] Carnegie Mellon [email protected] {CCSXML} ¡ccs2012¿ ¡concept¿ ¡concept_id¿10010147.10011777.10011778¡/concept_id¿ ¡concept_desc¿Computing methodologies Concurrent algorithms¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10003752.10003790.10002990¡/concept_id¿ ¡concept_desc¿Theory of computation Logic and verification¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡/ccs2012¿ ccs Computing methodologies Concurrent algorithms ccs Theory of computation Logic and verification keywords Concurrency, Verification † † runningauthor: Z. Kent, U. Y. Yavuz, S. Jayanti, S. Balzer, and G. Blelloch † † copyright: Zachary Kent, Ugur Y. Yavuz, Siddhartha Jayanti, Stephanie Balzer, and Guy Blelloch † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction Concurrent data structures are invaluable in modern shared-memory parallel computing. Due to scheduling asynchrony however, even deterministic concurrent algorithms have exponentially many possible executions, thereby making them notoriously difficult to design without subtle errors and race conditions. To ensure reliability of concurrent data structures, decades of work [ 11 ] has gone into designing techniques for proving linearizability [ 15 ] —the gold standard for correctness, which states that operations, which actually take place over intervals of time, must appear to take effect atomically. A significant goal of this line of work has been to design a simple, sound and complete verification technique for producing airtight, machine-verified proofs of linearizability. In 2024, Jayanti et al. [ 16 ] took an important stride towards achieving this goal by designing meta-configuration tracking —the first sound and complete forward reasoning proof technique for proving linearizability. This technique is easy to use, since it only requires the prover to reason forwards in time. Consonantly, it has immediate use in machine-verifying both theoretically difficult and practically relevant concurrent data structures. Meta-configuration tracking has been used to machine-verify algorithms that are infamous for being difficult to prove linearizable, such as the Herlihy-Wing queue [ 15 ] . Just as importantly, it has been used to machine-verify the correctness of concurrent data structures of considerable practical significance, such as the Jayanti-Tarjan union-find object [ 17 ] , which is used in Google’s open-source graph mining library to power “shared memory parallel clustering algorithms which scale to graphs with tens of billions of edges” [ 13 ] , and the fast, concurrent Parlay hash table [ 7 ] . While important algorithms have been machine-verified via meta-configuration tracking, the technique’s metatheory —i.e., proofs of soundness and completeness—remained un-mechanized. In this work, we ameliorate this situation by giving the first mechanization of meta-configuration tracking’s metatheory. Furthermore, we show that this enables end-to-end machine-verified proofs of linearizability by proving the correctness of a simple concurrent register algorithm. All our proofs are fully mechanized in Rocq. 1.1 Importance of machine-verifying concurrent data structures Due to scheduling asynchrony, even deterministic concurrent algorithms have exponentially many possible executions. The myriad possibilities make it nearly impossible to ensure race-free concurrent code through conventional unit testing, compelling machine-verification. The need for machine-verification is also bolstered by several practical examples of subtle races that have had disastrous consequences. A concurrency race in the power-grid was among the causes of the 2003 Northeast Blackout which effected over 50 million people across the United States and Canada [ 28 ] . NASA’s Mars Pathfinder repeatedly crashed due to a concurrency bug, nearly jeopardizing the entire mission which required years of preparation [ 18 ] . Race conditions in the Therac-25 radiation therapy machines caused radiation-poisoning, which eventually resulted in at least three deaths and several more injuries [ 24 ] . In short, fundamental algorithms are deployed in all sorts of systems, including those which are critical to the lives and well-being of people, thus motivating machine-verified rigor in proving subtle concurrent algorithms. The mechanization of the metatheory that we provide in this work enables such machine-verification guarantees of concurrent data structure correctness. 1.2 Challenges in proving linearizability and meta-configuration tracking Perhaps the most intuitive method for proving linearizability is forward simulation [ 20 ] . Linearizability is the condition that operations appear to take effect instantaneously at a point in time in its interval of execution, thus it is often proved by identifying these linearization points . If each linearization point can be identified, online, as it occurs in a run, then the proof of linearizability is made simple. In forward simulation, the prover keeps a copy of an atomic reference object and performs an induction over the steps of an arbitrary run of an algorithm using the implemented object, showing that its behavior is identical to that of the algorithm run with the atomic reference object if the reference object performs operations at the linearization points of the implemented object. While forward simulation is simple, it can only be used when linearization points can be identified and committed to online . Perhaps surprisingly, this turns out to be an important constraint. Only a small subset of linearizable algorithms, known as strong linearizable algorithms [ 12 ] , are amenable to this type of proof. The remaining algorithms exhibit future-dependent linearizability [ 11 ] , i.e., their linearization points depend on the future (since they cannot be identified online). Several proofs techniques for such algorithms require more complex reasoning, such as reasoning backwards in time [ 19 ] or prophesying the future [ 1 ] . In contrast, meta-configuration tracking provides a simple solution that essentially boils down to maintaining multiple forward simulations. The main observation of meta-configuration tracking is that at any point in time t , a future-dependently linearizable algorithm has not one, but several different sets of linearization points. Each set corresponds to a single forward simulation with an atomic reference object. As the future unfolds, some forward simulation will necessarily extend into the future, but determining which one is not possible online. In other words, it is not possible to commit to any single forward simulation in an online manner. Meta-configuration