Handling Complex Interference Compositionally: A Concurrent Garbage Collector Case Study

arXiv:2609.27392 · cs.LO · Submitted 2026-09-23 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Handling Complex Interference Compositionally".

Jane: Here's the gist of the paper. The Ben-Ari concurrent garbage collector algorithm prevents memory corruption by requiring specific ordering between mutator actions and collector marking, a requirement that cannot be easily captured by standard rely/guarantee conditions.

Tom: The Limitation of Traditional Verification Techniques Rely/guarantee is a well-known verification technique for reasoning about concurrent programs, but it fails for algorithms exhibiting strong interference, such as the Ben-Ari concurrent garbage collector where compositional rely and guarantee conditions are difficult to construct The difficulty arises because the complex interactions between components prevent the construction of compositional rely and guarantee conditions Non-blocking concurrent algorithms present the most challenging type to verify, as seen with Ben-Ari's algorithm where interference could cause memory in use to be incorrectly reclaimed by the Collector The Novel Proof Technique This paper investigates an approach for verifying the Ben-Ari algorithm that enables reasoning to be performed in a more compositional manner by reasoning that a given property holds for all instances of a particular variable and then instantiating the variable to the local variable required This results in identifying the core property required of a component, which reveals why reliance/guarantee does not work directly for some problems The technique allows strongly intertwined behavior to be separated without requiring ghost variables The Core Property Identification The abstract predicate used for the algorithm provides more than a simple bridge between components; it uncovers the core property that is required by the Collector, revealing a deeper insight into why the algorithm works correctly This approach helps reveal why rely/guarantee is insufficient for some algorithms The core property required of the Collector is identified through the can-be-marked property, which states that for every node that is marked and in the set s, if one of its children are unmarked, then there must be another path to that node via another node c The Verification Framework The paper introduces a theorem called Holds For All which allows reasoning about the local variables of another component without the need for shared auxiliary variables The general outline involves finding a suitable property p and a relation q such that if the guarantee of one component holds, and property p holds on σ, then a relation q holds over the two states and w This allows reasoning about the safe set of the Collector without actually referring to the safe set The Mutator is required to show that property p holding on σ implies a relation q holds between σ and σ' Mutator Proof Obligations The Mutator consists of two atomic operations, Change and MarkTbm, whose postconditions are defined to ensure safety The post-Change condition ensures that if a redirection occurred, the new target node is stored as tbm and that node was reachable from the roots in the original hp The post-MarkTbm condition ensures that after marking, either all-ok holds or the number of marked nodes has increased This guarantees that another round of marking will take place and the required nodes will be identified The alternation of Change and MarkTbm ensures that for any sequence of Mutator steps, either can-be-marked can be shown to hold at the end or the number of marked nodes would have increased The identification of the core property enables more efficient algorithms to potentially be designed, such as an alternative algorithm allowing the Mutator access to the consid set The approach provides deeper understanding into why Ben-Ari's algorithm works This method is useful for understanding further classic algorithms for which it is difficult to understand why they work The identification of the core property also provides insights into the nature of interference and why rely/guarantee is insufficient for some algorithms The proofs are currently being mechanised and will be completed for future work References

BA84: Mordechai Ben-Ari.

Jane: Algorithms for on-the-fly garbage collection.

Tom: ACM Transactions on Programming Languages and Systems, 6(3):333–344, 1984

Hav99: Klaus Havelund.

Title and authors: Tom: We're diving into "Handling Complex Interference Compositionally: A Concurrent Garbage Collector Case Study" now and looking at who wrote it. It’s by Nisansala P. Yatapanage from the School of Computing at the Australian National University.

Jane: That title tells you immediately that they are dealing with interference—those tricky interactions—and trying to handle them in a compositional way, which is a big deal for verification research right now.

Lu: It’s important to note that they're taking the Ben-Ari concurrent garbage collector as their case study because it’s known for having those strong interference issues that make standard verification techniques fail.

Meng: So they picked a specific problem, the Ben-Ari collector, to show why general tools don't work easily in this area. That feels like a very targeted research choice.

Tom: Right. They are basically saying that relying on rely and guarantee conditions is challenging for algorithms with strong interference because of these complex interactions between components.

Jane: And the authors are proposing a new technique to overcome that challenge by focusing on finding a core property required by the Collector itself, instead of trying to build those complicated conditions for every single part.

Lu: They achieve this by reasoning about one property holding for all instances of a variable and then instantiating it into the local variable needed, which is how they make the reasoning more compositional.

Meng: I’m still curious about how much effort goes into defining that specific property that unlocks this deeper understanding. Is it just a clever trick?

Tom: It’s presented as more than just a trick; it's a method for separating strongly intertwined behavior without needing those ghost variables in the proof.

Jane: So, they are showing how you can achieve separation without relying on those extra variables that usually clutter the verification process.

Lu: The result is identifying this core property required of a component, which gives us a deeper understanding into why the original algorithm works correctly.

Meng: That’s valuable for us because understanding *why* something works helps you design better things from scratch, not just patch it up with verification tricks.

Tom: It shifts the focus from just proving safety to truly understanding the underlying requirements of correctness in concurrent systems.

Jane: And that's what makes this work; they are providing insights into both how the algorithm functions and why reliance and guarantee reasoning falls short for some cases.

The paper's summary: Tom: So, let's summarize what the paper is actually saying about the Ben-Ari concurrent garbage collector. It tackles the complexity of interference by proposing a new verification approach to verify it compositionally.

Jane: They are essentially showing that you can reason about these concurrent systems in a more compositional way by reasoning about properties for individual variables and then instantiating them locally.

Lu: This process leads directly to identifying the core property that the Collector needs, which is what they call the can-be-marked property.

Meng: Can you lay out what that can-be-marked property looks like again? I need something concrete to visualize this concept.

Jane: It states that if a node is marked and it's in set S, and one of its children is unmarked, then there must be another path to that node via some other node C.

Tom: So the core idea is maintaining connectivity or reachability through alternative paths even when marking is happening concurrently.

Lu: That property provides more than just a simple bridge between components; it uncovers what the Collector fundamentally requires from its parts to work safely.

Meng: It’s about finding a deeper requirement, not just checking if the final outcome matches our expectation. That's where the value is for us.

Jane: The paper shows that this property reveals why reliance and guarantee is insufficient for some algorithms by showing where those traditional conditions break down in the presence of interference.

Tom: So they are pinpointing exactly where those standard reasoning techniques fall short due to how strongly intertwined the behavior is between the components.

Lu: This allows them to separate that intertwined behavior without needing ghost variables, which is a significant methodological improvement for concurrency proofs.

The paper's improvements: Tom: Now let's look at what they propose as improvements over existing methods, specifically how this new approach works in practice. They introduce a theorem called Holds For All.

Jane: That theorem is key because it allows reasoning about the local variables of another component without needing those shared auxiliary variables that were used before.

Lu: The general outline involves finding a suitable property P and a relation Q such that if the guarantee of one component holds, and property P holds on sigma, then relation Q holds over two states and w.

Meng: So we're looking for a suitable property P and relation Q that links the guarantee state to the system state across different states. That sounds like a lot of bookkeeping.

Tom: It is bookkeeping, but it’s about making sure you don't actually have to refer to the safe set directly during reasoning.

Jane: The Mutator has to show that property P holding on sigma implies relation Q holds between sigma and sigma prime. That’s where the actual work happens for the Mutator part of the proof.

Lu: For example, the post-Change condition ensures that if a redirection happened, the new target node is stored as tbm and it was reachable from roots in the original heap state.

Meng: So we need to define those precise postconditions for Change and MarkTbm that guarantee safety based on what was just done.

Tom: And the post-MarkTbm condition ensures that after marking, either all-ok holds or the number of marked nodes has increased in a way that guarantees another round of marking will occur.

Jane: That’s a rigorous guarantee for the Collector's stability; it ensures progress toward identifying all required nodes.

Lu: The alternation between Change and MarkTbm ensures that for any sequence of Mutator steps, either the can-be-marked property can be shown to hold at the end, or the number of marked nodes would have increased.

Conclusion: Tom: So to wrap up this discussion on "Handling Complex Interference Compositionally: A Concurrent Garbage Collector Case Study," they've identified a core property for the Collector and a framework called Holds For All.

Jane: The implication is that we can reason about local variables of another component without needing shared auxiliary variables, making the verification much more compositional.

Lu: This method provides a deeper understanding of why the algorithm works and shows how to separate strongly intertwined behavior without requiring ghost variables in the proof.

Meng: For us, it means we have a better tool for understanding why this specific algorithm is stable, which is useful knowledge we can apply elsewhere in our research.

Lalam: I’m quite confident that this approach provides a deeper insight into the nature of interference and why rely and guarantee reasoning isn't sufficient for some algorithms.

Tom: It moves us toward designing more efficient algorithms by revealing exactly what is required to maintain correctness, like the can-be-marked property.

Jane: This paper is useful because it provides a new way to see why these specific concurrent systems are stable and where they might fail under interference.

Lu: We get better tools for understanding the nature of interference itself, which helps us design new systems that are inherently more robust against those kinds of interactions.

Meng: I still have to consider the implementation cost, but conceptually, isolating the core requirement is a powerful idea for future verification work.

Nisansala P. Yatapanage

School of Computing, The Australian National University

cs.LO

Submitted: 2026-09-23

Updated: 2026-10-29

Comments: To be published in the 12th International Symposium on Dependable Software Engineering Theories, Tools and Applications (SETTA 2026)

License: http://creativecommons.org/licenses/by-nc-sa/4.0/

Importance score: 81/100

The gist: The Ben-Ari concurrent garbage collector algorithm prevents memory corruption by requiring specific ordering between mutator actions and collector marking…

Key concepts

Rely/Guarantee Limitation
Standard rely/guarantee conditions are insufficient for algorithms with strong interference, like the Ben-Ari collector. The complex interactions between components prevent building simple, compositional rules that capture the necessary ordering between mutator actions and collector marking, leading to verification gaps.
Core Property Identification
The paper uncovers a fundamental property needed by the Collector: 'can-be-marked.' This property dictates that if a marked node has an unmarked child, there must be another path to it through another node. Identifying this core requirement reveals why simpler verification techniques fail and provides insight into the algorithm's correctness.
Holds For All Theorem
This theorem enables reasoning about the local variables of one component without needing shared auxiliary variables or ghost variables. It allows a property to be reasoned about for all instances of a variable, enabling a more compositional approach to verifying components in concurrent systems.
Postconditions for Mutator Operations
The paper defines specific postconditions for Mutator operations like Change and MarkTbm. These conditions directly enforce safety properties, such as ensuring that after marking, either 'all-ok' holds or the number of marked nodes has increased, guaranteeing progress in the marking process.

Terminology

Summary

The Ben-Ari concurrent garbage collector algorithm prevents memory corruption by requiring specific ordering between mutator actions and collector marking, a requirement that cannot be easily captured by standard rely/guarantee conditions. p. 1

Where the paper says it

In [JY19], Ben-Ari’s concurrent garbage collector is specified with rely/guarantee, but it is concluded that there is no way of specifying suitable rely and guarantee conditions without breaking compositionality. The Ben-Ari algorithm allows both the Mutator and the Collector to run at the same time without corrupting the memory.

The Limitation of Traditional Verification Techniques

Rely/guarantee is a well-known verification technique for reasoning about concurrent programs, but it fails for algorithms exhibiting strong interference, such as the Ben-Ari concurrent garbage collector where compositional rely and guarantee conditions are difficult to construct The difficulty arises because the complex interactions between components prevent the construction of compositional rely and guarantee conditions Non-blocking concurrent algorithms present the most challenging type to verify, as seen with Ben-Ari's algorithm where interference could cause memory in use to be incorrectly reclaimed by the Collector

The Novel Proof Technique

This paper investigates an approach for verifying the Ben-Ari algorithm that enables reasoning to be performed in a more compositional manner by reasoning that a given property holds for all instances of a particular variable and then instantiating the variable to the local variable required This results in identifying the core property required of a component, which reveals why reliance/guarantee does not work directly for some problems The technique allows strongly intertwined behavior to be separated without requiring ghost variables

The Core Property Identification

The abstract predicate used for the algorithm provides more than a simple bridge between components; it uncovers the core property that is required by the Collector, revealing a deeper insight into why the algorithm works correctly This approach helps reveal why rely/guarantee is insufficient for some algorithms The core property required of the Collector is identified through the can-be-marked property, which states that for every node that is marked and in the set s, if one of its children are unmarked, then there must be another path to that node via another node c

The Verification Framework

The paper introduces a theorem called Holds For All which allows reasoning about the local variables of another component without the need for shared auxiliary variables The general outline involves finding a suitable property p and a relation q such that if the guarantee of one component holds, and property p holds on σ, then a relation q holds over the two states and w This allows reasoning about the safe set of the Collector without actually referring to the safe set The Mutator is required to show that property p holding on σ implies a relation q holds between σ and σ'

Mutator Proof Obligations

The Mutator consists of two atomic operations, Change and MarkTbm, whose postconditions are defined to ensure safety The post-Change condition ensures that if a redirection occurred, the new target node is stored as tbm and that node was reachable from the roots in the original hp The post-MarkTbm condition ensures that after marking, either all-ok holds or the number of marked nodes has increased This guarantees that another round of marking will take place and the required nodes will be identified The alternation of Change and MarkTbm ensures that for any sequence of Mutator steps, either can-be-marked can be shown to hold at the end or the number of marked nodes would have increased

Conclusion and Implications

The identification of the core property enables more efficient algorithms to potentially be designed, such as an alternative algorithm allowing the Mutator access to the consid set The approach provides deeper understanding into why Ben-Ari's algorithm works This method is useful for understanding further classic algorithms for which it is difficult to understand why they work The identification of the core property also provides insights into the nature of interference and why rely/guarantee is insufficient for some algorithms The proofs are currently being mechanised and will be completed for future work

References

[BA84] Mordechai Ben-Ari. Algorithms for on-the-fly garbage collection. p. 3

Where the paper says it

4 The Complexity of Interference 3 Ben-Ari Concurrent Garbage Collector The Ben-Ari garbage collection algorithm [BA84] is a mark-and-sweep algorithm where the Collector runs concurrently with the Mutator, thus allowing lost memory to be reclaimed while a program is running. 2 shows the cycle of behaviour by the two components of the system: the Mutator which uses and loses memory and the Collector which must free the garbage.

ACM Transactions on Programming Languages and Systems, 6(3):333–344, 1984

[Hav99] Klaus Havelund. Mechanical verification of a garbage collector. p. 0

Where the paper says it

However, for some algorithms, devising suitable rely and guarantee conditions is challenging, due to the strong interference exhibited in these algorithms. The Ben-Ari concurrent garbage collector is an algorithm where the complex interactions between the components prevent the construction of compositional rely and guarantee conditions.

In International Parallel Processing Symposium, pages 1258–1283. p. 1
Where the paper says it

2 The Complexity of Interference which uses parallel threads to speed up the search for the first index of an array satisfying a given property p, and the parallel Sieve of Eratosthenes, which uses parallel threads to identify the set of prime numbers below a given maximum value. See [HJ18] for rely/guarantee developments of these problems.

Springer, 1999

[HJ18] I. J. Hayes and C. B. Jones. A guide to rely/guarantee thinking. p. 0

Where the paper says it

The Complexity of Interference: When Rely/Guarantee Does Not Work Nisansala P. Yatapanage School of Computing, The Australian National University Abstract.

In J. P. Bowen, Z. Liu, and Z. Zhang, editors, Engineering Trustworthy Software Systems, volume 11174 of LNCS, pages 1–38

[JH16] Cliff B. Jones and Ian J. p. 0

Where the paper says it

The algorithms which have been successfully verified using rely/guarantee fall into certain classes. The first group are the classic rely/guarantee examples, often used by Jones, the creator of rely/guarantee [Jon90].

Hayes. Possible values: Exploring a concept for concurrency. p. 1
Where the paper says it

For all of these approaches, it was concluded that rely and guarantee conditions could not be devised in a straightforward manner. In [JH16], in order to verify Simpson’s four-slot algorithm, a new notion, possible values was devised, to essentially describe the history of values held by a variable throughout the program execution.

Journal of Logical and Algebraic Methods in Programming, 85(5, Part 2):972–984, August 2016

[Jon90] C. B. Jones. Systematic Software Development using VDM. p. 6

Where the paper says it

Instead, the method shown in this paper reveals a deeper insight into why marking is needed. 2 Required Definitions From [JY19] Before proceeding, some preliminary definitions are required, taken directly from [JY19], presented using VDM syntax.

Prentice Hall International, second edition, 1990

[JY19] Cliff B. Jones and Nisansala Yatapanage. p. 0

Where the paper says it

The Complexity of Interference: When Rely/Guarantee Does Not Work Nisansala P. Yatapanage School of Computing, The Australian National University Abstract.

p. 0
Where the paper says it

The Complexity of Interference: When Rely/Guarantee Does Not Work Nisansala P. Yatapanage School of Computing, The Australian National University Abstract.

Investigating the limits of rely/guarantee relations based on a concurrent garbage collector example. p. 0
Where the paper says it

However, for some algorithms, devising suitable rely and guarantee conditions is challenging, due to the strong interference exhibited in these algorithms. The Ben-Ari concurrent garbage collector is an algorithm where the complex interactions between the components prevent the construction of compositional rely and guarantee conditions.

Formal Aspects of Computing, 31:353–374, 2019

[NE00] Leonor Prensa Nieto and Javier Esparza. Verifying single and multi-mutator garbage collectors with Owicki-Gries in Isabelle/HOL. p. 0

Where the paper says it

The Ben-Ari concurrent garbage collector is an algorithm where the complex interactions between the components prevent the construction of compositional rely and guarantee conditions. This paper investigates an approach for verifying the Ben-Ari algorithm, which enables reasoning to be performed in a more compositional manner in cases where compositional reasoning would not otherwise be possible.

In MFCS 2000, volume 1893 of LNCS, pages 619–628. Springer, 2000

[OG76] S. S. Owicki and D. Gries. An axiomatic proof technique for parallel programs I. p. 0

Where the paper says it

Yatapanage School of Computing, The Australian National University Abstract. Rely/Guarantee is a well-known verification technique for reasoning about concurrent programs.

Acta Informatica, 6(4):319–340, 1976

[VP07] Viktor Vafeiadis and Matthew Parkinson. A marriage of rely/guarantee and separation logic. p. 1

Where the paper says it

Rely/guarantee is often combined with other logics, in particular separation logics, as with RGSep [VP07]. RGSep uses rely/guarantee for the shared parts of the memory and separation logic for the local parts.

In Luís Caires and Vascot Vasconcelos, editors, CONCUR 2007 – Concurrency Theory, volume 4703 of Lecture Notes in Computer Science, pages 256–271

[Yat24] Nisansala P. Yatapanage. Exploring the boundaries of rely/guarantee and links to linearisability. p. 3

Where the paper says it

A redirect changes a link to point to a different node. Nodes can be allocated by taking a new node from the Free set, and links can be removed.

In Ana Cavalcanti and James Baxter, editors, The Practice of Formal Methods: Essays in Honour of Cliff Jones, Part II, volume 14781 of Lecture Notes in Computer Science, pages 247–267

[ZCD+17] Yannick Zakowski, David Cachera, Delphine Demange, Gustavo Petri, David Pichardie, Suresh Jagannathan, and Jan Vitek. Verifying a concurrent garbage collector using a rely-guarantee methodology. p. 0

Where the paper says it

The Ben-Ari concurrent garbage collector is an algorithm where the complex interactions between the components prevent the construction of compositional rely and guarantee conditions. This paper investigates an approach for verifying the Ben-Ari algorithm, which enables reasoning to be performed in a more compositional manner in cases where compositional reasoning would not otherwise be possible.

In Mauricio Ayala-Rincón and César A.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved verification of concurrent garbage collectors by identifying a core property required of a component, thus enabling a deeper understanding about why the algorithm works correctly. This allows for more efficient design of algorithms by revealing what is required to maintain correctness, such as the can-be-marked property for the Collector.

  2. Development of an abstract set approach for reasoning about local variables without requiring ghost variables or detailed knowledge of another process's behavior. This technique enables verification where the rely condition of the Collector holds, which refers to the safe set, making it more compositional than previous methods like using a shared ghost variable tbm.

  3. Creation of formal postconditions for Mutator operations, such as post-Change and post-MarkTbm, that directly enforce the required safety properties on sets like can-be-marked. These conditions ensure that after the MarkTbm operation, in which tbm is marked, ideally, there would not be any more problem nodes, providing a rigorous guarantee for the Collector's stability.

Abstract

Rely/Guarantee is a well-known verification technique for reasoning about concurrent programs. However, for some algorithms, devising suitable rely and guarantee conditions is challenging, due to the strong interference exhibited in these algorithms. The Ben-Ari concurrent garbage collector is an algorithm where the complex interactions between the components prevent the construction of compositional rely and guarantee conditions. This paper investigates an approach for verifying the Ben-Ari algorithm, which enables reasoning to be performed in a more compositional manner in cases where compositional reasoning would not otherwise be possible. This is accomplished by reasoning that a given property holds for all instances of a particular variable and then instantiating the variable to the local variable required. As well as providing a reasoning approach which is more compositional, the result is the identification of the core property required of a component, thus enabling a deeper understanding about the reasons why the algorithm works correctly. This helps to reveal the reasons why the rely/guarantee approach does not work directly for some problems.

Related papers