💻 computer science

Completeness of Logical Atomicity for Linearizability in Concurrent Separation Logic

This paper resolves an open question in the Iris separation logic framework by proving the completeness of logical atomicity for linearizability, demonstrating that any linearizable data structure can be assigned a logically atomic specification and thereby enabling the mechanized integration of various linearizability proof techniques.

Original authors: Zichen Zhang, Simon Oddershede Gregersen, Joseph Tassarotti

Published 2026-07-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zichen Zhang, Simon Oddershede Gregersen, Joseph Tassarotti

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a chaotic, high-speed bank with thousands of tellers working at once. In the real world, we want to be sure that even though everyone is moving fast and overlapping, the money doesn't disappear or get duplicated. In the world of computer science, this "safety guarantee" is called linearizability. It's like saying, "Even though you saw two people grab the same account at the same time, if you rewind the tape, there was a single, perfect moment where one finished and the other started, just like a line at a coffee shop."

For a long time, computer scientists had two different ways to prove this safety.

The Old Way: The "Black Box" Inspector
One way was to act like a detective looking at the whole history of the bank. You'd watch every single transaction, try to find the exact split-second (the "linearization point") where each teller did their magic, and prove that if you rearranged them in that order, the math still worked. This is linearizability. It's great for proving the bank is safe, but it's a nightmare to use when you want to build new things on top of the bank. It's like trying to build a house by constantly re-checking the foundation's blueprints every time you lay a brick. It's too heavy and clunky for the next step.

The New Way: The "Magic Wand"
The other way, used by a fancy logic system called Iris, is called logical atomicity. Instead of looking at the whole history, this approach gives the programmer a "magic wand" (a logical rule). It says, "Trust me, this operation happened all at once, so you can treat it like a single, instant step." This makes building new apps much easier because you don't have to worry about the messy details of how the magic happened, just that it did.

The Big Question: Is the Magic Wand Enough?
Here is the puzzle this paper solves: We knew that if you had the "Magic Wand" (logical atomicity), you could prove the bank was safe (linearizability). That was like saying, "If you have a magic wand, you can definitely build a safe house."

But the reverse question was a mystery: If we already know the bank is safe (linearizable), can we always find a Magic Wand for it?
Some people worried that maybe some banks were so complex that no Magic Wand existed, even if they were perfectly safe. They thought the Magic Wand might be missing some rules, making it "too weak" to describe every possible safe bank.

The Breakthrough: Yes, the Wand Exists!
This paper proves, with absolute mathematical certainty (it's a theorem, not just a guess or a simulation), that yes, you can always find a Magic Wand for any safe bank.

The authors, Zichen Zhang, Simon Oddershede Gregersen, and Joseph Tassarotti, showed that if a data structure (like a queue or a list) is linearizable, you can always derive a logically atomic specification for it. They didn't just suggest this; they built a machine-checked proof using a tool called the Rocq Prover to verify every single step.

How Did They Do It? (The Time Travelers and The Helpers)
To prove this, they had to solve two tricky problems:

The Future Problem: Sometimes, you don't know when a transaction is "done" until you see what happens later. It's like a teller saying, "I'll finish this transaction once the next person walks in." This is called "future-dependent linearization." To solve this, they used prophecy variables. Think of these as time-traveling crystal balls. At the start of the program, the crystal ball predicts the entire future history of the bank. This lets the proof "know" exactly when to snap its fingers (apply the magic) for every transaction, even the ones that depend on the future.
The Helping Problem: Sometimes, one teller helps another finish their work. In the old way, you had to prove exactly who helped whom at a specific physical moment. But the authors showed that you can use a shared notebook (an invariant). When a transaction starts, you write a "promise" in the notebook. When the transaction finishes, you look at the notebook, find all the promises that are now ready to be kept, and snap your fingers for all of them at once. This is called helping. It means one physical step can logically "finish" multiple operations.

What This Means for You
The paper doesn't just say "we did it." It actually demonstrated this power by taking three different, complex ways of proving safety that existed outside of the Iris logic system and translating them into the Magic Wand style.

They proved the Herlihy-Wing queue (a famous, tricky bank line) is safe using three different methods: "aspect-oriented" proofs, "forward simulation," and "meta-configuration tracking."
They proved the Baskets Queue is safe.
They even took a proof for the Folly MPMC queue (a high-performance bank line used by Meta) that was already proven to be safe in a different way, and used their new "bridge" to turn it into a Magic Wand proof.

The Bottom Line
This paper closes a huge gap in computer science. It proves that the "Magic Wand" (logical atomicity) is not a limited tool; it is complete. If a concurrent data structure is safe, the Magic Wand can describe it. You don't have to choose between a complex history check and a simple magic rule; you can use the complex history check to prove safety, and then automatically get the simple magic rule for free.

The authors have made all their code and proofs available on GitHub, so anyone can check their work. They didn't just suggest this might be true; they proved it, turning a long-standing open question into a settled fact.

Technical Summary: Completeness of Logical Atomicity for Linearizability in Concurrent Separation Logic

Problem Statement
Linearizability is the standard correctness condition for concurrent data structures, guaranteeing that operations appear to take effect atomically at some instant between their invocation and response. While extensive formal methods exist to prove linearizability, concurrent separation logics (CSL) like Iris have historically favored "logical atomicity" as a specification style. Logical atomicity internalizes the concept of atomicity within the logic's reasoning rules, allowing clients to reason about operations as if they were physically atomic, particularly regarding invariant access.

Prior work established a soundness theorem: if a data structure satisfies a logically atomic specification in Iris, it is linearizable. However, the converse remained an open question: Is every linearizable data structure guaranteed to admit a logically atomic specification? Without this completeness property, it was unclear whether the logic was "missing" rules or if proving logical atomicity for complex structures (e.g., those with future-dependent linearization points) required ad-hoc, non-compositional techniques that could not be generalized. Furthermore, there was no formal mechanism to transport linearizability proofs derived via external techniques (outside the logic) into logically atomic specifications within Iris.

Methodology
The authors prove a completeness theorem for Iris, demonstrating that for any linearizable data structure, a corresponding logically atomic triple can be derived. The proof relies on three core technical mechanisms:

Prophecy Variables: To address the challenge of future-dependent linearization points (where the linearization point of an operation depends on future events), the proof employs prophecy variables. These allow the proof to "predict" the complete trace of call and return events at the time of object creation. This enables the extraction of a consistent set of linearization points from the linearizability assumption without needing to retroactively adjust them as the trace extends.
Helping and Shared Invariants: To bridge the gap between abstract linearization points (events in a trace) and concrete physical steps (program execution), the authors utilize a "helping" technique. They maintain an invariant that stores "atomic update" (AU) assertions for all in-flight operations. When an operation emits a Call or Return event, the proof gathers and fires the AUs for all pending operations whose linearization points precede that event. This allows a single physical step to logically linearize multiple operations.
Wrapper Construction: The proof is constructed for a "wrapped" version of the data structure. The init and op methods are instrumented with wrappers that allocate prophecy variables and ghost tags. These wrappers record the call and return events, allowing the proof to correlate the physical execution with the prophesied trace.

The authors also establish a connection between logical atomicity and contextual refinement. They prove that if a program $e$ refines a program $e'$ (where $e'$ satisfies a logically atomic specification), then $e$ also satisfies a logically atomic specification. This allows the transport of logical atomicity across refinement chains.

Key Contributions

Completeness Theorem: The paper provides the first completeness theorem for logical atomicity in Iris. It proves that any linearizable data structure (specifically for the HeapLang language) satisfies a logically atomic triple specification. This confirms that Iris is not "too weak" to express the atomicity of any linearizable structure.
Refinement Transport: The authors prove a theorem connecting contextual refinement to logical atomicity. This enables the derivation of logically atomic specifications for a data structure by proving it refines a coarse-grained, atomic implementation. This facilitates incremental verification through chains of refinements.
Embedding External Techniques: The paper demonstrates how to embed three distinct, external linearizability proof techniques into Iris to derive logically atomic specifications:
- Aspect-Oriented Proofs: Adapting Henzinger et al.'s method for queues.
- Forward Simulation with Commit Points: Adapting Bouajjani et al.'s technique for handling future dependencies.
- Meta-Configuration Tracking: Adapting Jayanti et al.'s universal technique for forward reasoning.
Mechanized Case Studies: The authors apply these embeddings to verify several challenging data structures:
- Herlihy-Wing Queue: Verified using all three external techniques, demonstrating that off-the-shelf linearizability proofs can be converted to logical atomicity without redeveloping proofs from scratch using prophecy variables.
- Baskets Queue: The first machine-checked proof of linearizability for this structure, utilizing forward simulation.
- Folly MPMC Queue: A high-performance queue from Meta's Folly library. The authors reuse a prior refinement proof (by Vindum et al.) to derive a logically atomic specification, bridging a gap where previous work could not access the result within a unary separation logic.

Results
All results have been mechanized in the Rocq Prover using the Iris framework. The proofs confirm that:

Linearizability implies the existence of a logically atomic specification.
Logical atomicity can be transported through refinement relations.
External linearizability proof methods (aspect-oriented, forward simulation, meta-configuration) can be formalized as meta-theorems in Iris to generate logical atomic triples.
The resulting specifications for the Herlihy-Wing and Baskets queues match the form of previously known logical atomic specifications but are derived via different, often shorter, proof paths.

Significance
The paper claims that this work resolves a fundamental theoretical gap in concurrent separation logic. By proving completeness, it establishes that logical atomicity is a robust and sufficient specification style for all linearizable data structures. Practically, it liberates developers from the burden of manually constructing complex logical atomic proofs involving prophecy variables and helping for every new data structure. Instead, they can leverage the vast array of existing linearizability proof techniques and automated tools, verify linearizability externally, and automatically "lift" that result into a logically atomic specification within Iris. This bridges the gap between the compositional reasoning benefits of logical atomicity and the mature ecosystem of linearizability verification tools.

Technical Summary: Completeness of Logical Atomicity for Linearizability in Concurrent Separation Logic

More like this