💻 computer science

Distributive Laws for Parallel Composition in Rely-Guarantee Concurrency

This paper develops and formalizes distributive laws for parallel composition within a rely-guarantee concurrency framework by establishing them in an abstract synchronous atomic algebra and demonstrating how restricting command forms enables stronger equality laws for algebraic reasoning.

Original authors: Ian J. Hayes, Larissa A. Meinicke

Published 2026-07-21

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Ian J. Hayes, Larissa A. Meinicke

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

=== DRAFT ===
Imagine you are trying to choreograph a massive dance troupe where hundreds of dancers move simultaneously on a single stage. In the world of computer science, this is the challenge of concurrent programming: getting multiple computer programs (threads) to run at the same time without tripping over each other. The problem is that if one dancer grabs a prop, another might need it, or they might accidentally step on each other's toes, causing the whole show to crash. To solve this, computer scientists use a set of rules called Rely-Guarantee. Think of "Rely" as a dancer's promise: "I promise I will only move if the other dancers stay within this specific zone." Think of "Guarantee" as a dancer's commitment: "I promise that whatever I do, I won't step outside this zone." By writing these promises down, you can prove that the whole troupe will perform correctly, even if you don't know exactly when each dancer will move.

Now, imagine you are the director trying to simplify the choreography. You have a complex routine where a dancer makes a promise (a "guarantee") and then does two things at once (parallel composition). You want to know: Can I split that promise and give a copy of it to each of the two smaller routines? In mathematics, this is called a distributive law. It's like asking if you can hand out a single rule to two different groups and get the same result as if you had given the rule to the whole group at once. This paper dives deep into the algebra of these promises to figure out exactly when you can split them up and when you absolutely cannot.

The Paper's Big Discovery

In this paper, Ian J. Hayes and Larissa A. Meinicke act like algebraic detectives, hunting for the specific conditions under which these "promises" (guarantees) can be distributed across parallel tasks. They are working within a formal system called Concurrent Refinement Algebra, which is a fancy way of saying they are building a mathematical toolbox to prove that computer programs work correctly.

Their main finding is a bit like a "Goldilocks" rule for splitting promises. They prove that if a promise has a very specific property—being "idempotent" with respect to parallel composition—then you can distribute a "Guarantee" command over parallel composition (splitting a promise across two simultaneous tasks). In plain English, this means the promise must be self-similar; if you take the promise and run it alongside itself, it doesn't change the nature of the promise.

The authors show that for a standard Guarantee command (where a thread promises to keep its interference within a certain boundary), this condition holds true. Therefore, they prove the following equality:

Guarantee(Promise) + (Task A || Task B) = (Guarantee(Promise) + Task A) || (Guarantee(Promise) + Task B)

This is a powerful tool. It means that if you have a complex program where a thread makes a promise while doing two things at once, you can mathematically break that down into two smaller, simpler programs, each carrying the same promise. This makes it much easier to verify that large, complicated software systems are safe.

What They Rule Out

However, the paper is very careful to tell us what doesn't work. The authors explicitly argue against the idea that this same trick works for Rely conditions. A "Rely" is an assumption a thread makes about what the environment (the other threads) will do.

They prove that you cannot simply split a "Rely" assumption across parallel tasks in the same way. If you have a thread that relies on the environment behaving a certain way, and that thread is running two tasks in parallel, you cannot just give a copy of that reliance to each task. Why? Because the "Rely" on the left side of the equation is an assumption about the entire environment of the combined group. But if you split it, the "Rely" on the right side would only be an assumption about the interference from the other specific task, which is a much weaker and different condition.

The paper shows that the equation:

Rely(Condition) + (Task A || Task B) = (Rely(Condition) + Task A) || (Rely(Condition) + Task B)
is false in general.

There is, however, a special exception. If you combine a "Rely" and a "Guarantee" into a single command (specifically, if the Guarantee is strong enough to satisfy the Rely, meaning the thread's promises are stricter than its assumptions), then you can distribute that combined command. This is like saying, "If I promise to stay in my lane (Guarantee) and I assume everyone else stays in their lane (Rely), and my promise is strong enough to cover everyone's behavior, then I can split this rule up."

How Sure Are They?

The authors are not just guessing or running simulations; they have mathematically proved these laws. They developed a rigorous algebraic theory and formalized all their proofs using a computer tool called Isabelle/HOL. This is a system that checks every single step of a mathematical proof to ensure there are no logical gaps. So, when they say a law holds, it is a proven fact within their mathematical framework. When they say a law fails, they have a proof that it cannot be true.

The "Pseudo-Atomic" Twist

To get these results, the authors had to invent a new category of commands they call "pseudo-atomic". Imagine a command that usually acts like a single, indivisible step (atomic), but sometimes has a tiny bit of "failure" attached to it. They found that even these slightly messy, "pseudo-atomic" commands follow the same distributive rules as the clean ones, provided they meet the same self-similarity condition. This extends their findings to a wider range of real-world programming scenarios where things might not be perfectly clean.

The Bottom Line

This paper provides the mathematical "glue" that allows computer scientists to break down complex, multi-threaded programs into smaller, manageable pieces without losing track of the safety rules. It tells us exactly when we can split a promise across parallel tasks (we can, if it's a Guarantee) and when we must keep the assumption whole (we must, if it's a Rely). By proving these rules with the help of a computer, the authors have given developers a reliable way to build safer, more complex concurrent software, ensuring that the digital dance troupe never steps on its own toes.

Technical Summary: Distributive Laws for Parallel Composition in Rely-Guarantee Concurrency

Problem Statement
The rely/guarantee approach is a established method for reasoning about the correctness of shared-memory concurrent programs by decomposing interference assumptions (rely) and commitments (guarantee) into compositional properties. While distributive laws are fundamental for the algebraic manipulation of programs in mathematics and Hoare logic, their application to concurrent programs within a rely/guarantee framework is complex. Specifically, there is a need for a rigorous algebraic theory to determine when and how guarantee and rely conditions can be distributed over parallel composition. Previous work established distributive laws for sequential composition and iteration, but extending these to parallel composition ( $c_1 \parallel c_2$ ) presents challenges. Notably, while guarantee conditions distribute over parallel composition, rely conditions generally do not, due to the differing scopes of interference assumptions (global environment vs. specific thread interactions). The paper addresses the gap in developing a unified algebraic framework to derive precise distributive laws for parallel composition involving rely and guarantee commands.

Methodology
The authors develop a theory based on a Concurrent Refinement Algebra (CRA), structured using weak quantales and weak biquantales augmented with tests and atomic commands. The methodology proceeds in three main stages:

Abstract Algebraic Foundation: The theory is first developed in a highly abstract "synchronous atomic algebra." Commands are modeled as elements of a complete distributive lattice with operations for sequential composition ( $;$ ), parallel composition ( $\parallel$ ), and weak conjunction ( $\sqcap$ ). The framework distinguishes between atomic commands (indivisible transitions) and pseudo-atomic commands (commands that may abort, represented as $a \lor b; \top$ ).
Derivation of General Distributive Laws: The authors investigate the conditions under which an iteration of an atomic command, $a^\omega$ $a^{ω}$ , distributes over parallel composition. They prove that the equality $a^\omega \sqcap (c_1 \parallel c_2) = (a^\omega \sqcap c_1) \parallel (a^\omega \sqcap c_2)$ $a^{ω} ⊓ (c_{1} ∥ c_{2}) = (a^{ω} ⊓ c_{1}) ∥ (a^{ω} ⊓ c_{2})$ holds if and only if the atomic command is idempotent with respect to parallel composition ( $a = a \parallel a$ $a = a ∥ a$ ). This proof utilizes:
- Finite approximations: Analyzing commands up to a finite length $i$ .
- Limit closure: Proving that infinite iterations of atomic commands are limit-closed (equal to the infimum of their finite approximations).
- Super-compactness: Assuming the lattice of commands is "super-algebraic," allowing arbitrary commands to be decomposed into choices of super-compact (deterministic, non-aborting) commands.
Application to Rely/Guarantee: The abstract results are instantiated in an Aczel algebra, where commands are defined via program transitions ( $\pi$ $π$ ) and environment transitions ( $\epsilon$ $ϵ$ ).
- Guarantee commands ( $\text{guar}_\pi g$ ) are defined as the infinite iteration of $(\pi g \lor \epsilon \text{univ})$ .
- Rely commands ( $\text{rely } r$ ) are defined as the infinite iteration of $(\pi \text{univ} \lor \epsilon r \lor \epsilon \bar{r}; \top)$ .
- The authors analyze the condition $a = a \parallel a$ for these specific command forms to determine validity.

Key Contributions and Results

General Distributive Law for Atomic Iterations: The paper establishes that for an atomic command $a$ , the distribution law $a^\omega \sqcap (c_1 \parallel c_2) = (a^\omega \sqcap c_1) \parallel (a^\omega \sqcap c_2)$ holds if and only if $a = a \parallel a$ .
Validity of Guarantee Distribution: By showing that the basis command for a guarantee, $\pi g \lor \epsilon \text{univ}$ , satisfies the idempotency condition (since $g \subseteq \text{univ}$ ), the authors prove the equality:
$\text{guar}_\pi g \sqcap (c_1 \parallel c_2) = (\text{guar}_\pi g \sqcap c_1) \parallel (\text{guar}_\pi g \sqcap c_2)$
This confirms that guarantee conditions can be distributed over parallel composition.
Invalidity of Pure Rely Distribution: The authors demonstrate that the basis command for a rely, $\pi \text{univ} \lor \epsilon r \lor \epsilon \bar{r}; \top$ , does not satisfy the idempotency condition (unless $r$ is universal). Consequently, the general distributive law for relies over parallel composition does not hold:
$\text{rely } r \sqcap (c_1 \parallel c_2) \neq (\text{rely } r \sqcap c_1) \parallel (\text{rely } r \sqcap c_2)$
This is attributed to the fact that a rely on the left assumes interference from the entire environment, whereas the relies on the right only account for interference from the other thread in the pair.
Composite Distribution (Evolve Invariant): The paper derives a stronger equality for composite commands where a rely and guarantee are combined, specifically the "evolve invariant" command ( $\text{evolve } r \equiv \text{rely } r \sqcap \text{guar}_\pi r$ ). If $g \subseteq r$ , the following equality holds:
$\text{rely } r \sqcap \text{guar}_\pi g \sqcap (c_1 \parallel c_2) = (\text{rely } r \sqcap \text{guar}_\pi g \sqcap c_1) \parallel (\text{rely } r \sqcap \text{guar}_\pi g \sqcap c_2)$
This is valid because the guarantee condition ensures the rely condition is met across the parallel composition.
Pseudo-Atomic Commands: The theory is extended to handle pseudo-atomic commands (commands that may abort), showing that similar distributive properties hold under specific conditions regarding the aborting components.

Significance and Claims
The paper claims to provide the first algebraic derivation of distributive laws for parallel composition specifically tailored to rely/guarantee concurrency. By formalizing the theory in Isabelle/HOL, the authors ensure the correctness of the lemmas and proofs presented.

The significance lies in enabling stepwise algebraic development of concurrent programs. The ability to distribute guarantee conditions over parallel composition allows developers to reason about complex concurrent systems by decomposing them into components with local guarantees, simplifying verification. The paper explicitly notes that while the most general laws are refinements (one-directional), restricting the form of the command (e.g., using guarantees or specific rely/guarantee combinations) yields stronger equality laws. This work bridges the gap between abstract algebraic structures (quantales) and practical concurrency reasoning (rely/guarantee), offering a rigorous foundation for manipulating concurrent specifications. The authors do not claim to solve all concurrency verification problems but rather provide essential algebraic tools for the specific domain of rely/guarantee reasoning.