💻 computer science

An automata-based approach for synchronizable mailbox communication

This paper establishes that determining whether a finite-state mailbox communication system is synchronizable under round-based semantics without size limitations is PSPACE-complete, achieved through a novel automata-based approach that also refines the complexity of related questions.

Original authors: Romain Delpy, Anca Muscholl, Grégoire Sutre

Published 2026-05-27

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Romain Delpy, Anca Muscholl, Grégoire Sutre

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 a bustling office building where employees (processes) need to coordinate their work. They don't talk face-to-face; instead, they leave notes in mailboxes. This is the world of mailbox communication.

In this paper, the authors tackle a tricky problem: How do we know if a group of computer programs talking through mailboxes is actually following a logical, orderly schedule, or if they are just chaotically shouting over each other?

Here is a breakdown of their findings using simple analogies.

The Setup: The Office Mailroom

In many computer systems, processes talk to each other in two main ways:

Peer-to-Peer: Like two people passing a note directly through a window. If Person A sends a note to Person B, it goes straight into B's hand.
Mailbox: Like a real office. Everyone has a single inbox. If Person A, Person C, and Person D all send notes to Person B, they all pile up in B's single mailbox in the order they arrived.

The authors focus on the Mailbox system because it's common in modern programming languages (like Rust or Erlang).

The "Round-Based" Rule

The paper studies a specific rule called "Round-Based Communication." Imagine a game of "Telephone" played in rounds:

Phase 1 (Send): Everyone writes their notes and drops them in the mailboxes. No one is allowed to read yet.
Phase 2 (Receive): Everyone opens their mailbox and reads the notes they received. No one is allowed to write new notes yet.

If a system can be rearranged to always follow this "All Send, Then All Receive" pattern, the authors call it Synchronizable.

The Big Question

The researchers asked: "Given a chaotic set of computer programs, can we efficiently figure out if they could be rearranged to follow these neat rounds, even if the rounds get huge?"

Previous studies had to guess a maximum size for these rounds (e.g., "No round can have more than 100 notes"). The authors removed this limit, asking what happens if a round can be infinitely long.

The Solution: The "Magic Checklist"

The authors developed a new method using automata (think of these as sophisticated flowcharts or checklists).

Instead of trying to simulate every possible chaotic scenario (which would take forever), their method looks at the skeleton of the communication. They treat the messages like beads on a string. They check if the string can be cut into neat chunks (rounds) where every "send" bead is followed eventually by its matching "receive" bead, without any weird loops or contradictions.

They proved that:

It is solvable: You can determine if a system is synchronizable.
It is efficient (relatively): The problem belongs to a complexity class called Pspace-complete.
- Analogy: Imagine a puzzle that is hard to solve, but you don't need a supercomputer the size of a planet to solve it. A standard, powerful computer can solve it, provided you give it enough memory (space) to keep track of the steps. It's not "impossible," but it's not "trivial" either.

Key Findings in Plain English

The "Round Size" Myth: Previous work worried that if rounds got too big, the math would break. The authors showed that even if the rounds are massive (exponentially large), the problem is still solvable with the same level of difficulty.
The "Mailbox vs. Direct" Confusion: They found that just because a system works well with direct hand-offs (Peer-to-Peer), it doesn't mean it works well with mailboxes. A system might look orderly in one setup but become a chaotic mess in the other. They provided a way to check if a Peer-to-Peer system can be safely "translated" to a Mailbox system.
The "Fixed Number" Trick: If you know exactly how many people are in the office (a fixed number of processes), the problem becomes much easier (solvable in "Ptime"), almost like a simple checklist.

Why Does This Matter?

In the world of software, "bugs" often happen because messages get mixed up or arrive in the wrong order. This paper gives developers and verification tools a mathematical guarantee.

If you have a complex system of programs talking via mailboxes, this paper provides the recipe to prove:

"Yes, this system is safe and follows a logical order."
"No, this system has a hidden chaos that cannot be fixed by just reordering the messages."

The Bottom Line

The authors built a new automated traffic cop for computer programs. This cop can look at a chaotic stream of messages and decide, with high mathematical certainty, whether the traffic can be organized into neat, orderly rounds. They proved that while this job is challenging, it is definitely within the reach of modern computers, and they did it without needing to guess how big the traffic jams might get.

Technical Summary: An Automata-Based Approach for Synchronizable Mailbox Communication

Problem Statement
The paper investigates finite-state communicating systems (CFMs) operating under mailbox semantics, where each process possesses a single FIFO buffer (mailbox) multiplexing messages from all other processes. This contrasts with the standard peer-to-peer (p2p) semantics where each channel has a dedicated buffer. The authors focus on round-based communication, specifically sr-rounds (send-then-receive rounds), where processes execute a sequence of sends followed by a sequence of receives within a single round.

A system is defined as mb-synchronizable if every possible execution (trace) can be re-scheduled into an equivalent execution that is a sequence of such sr-rounds. The central problem addressed is determining whether a given CFM is mb-synchronizable. Previous work (e.g., [BEJQ18, GLL20, GLL23]) established decidability for this problem but often imposed fixed bounds on round sizes or relied on complex logical frameworks (like LCPDL or MSO logic) with high complexity bounds (e.g., Exptime). A significant gap remained regarding the precise complexity of mb-synchronizability without size restrictions on rounds, and the decidability of related verification problems (reachability, model-checking) in this unbounded setting.

Methodology
The authors propose a novel automata-based approach that avoids the high complexity of previous logical methods. The core of their technique relies on analyzing marked send sequences (ms-sequences).

Marked Send Sequences: The authors observe that for mb-synchronizable systems, the set of traces is not regular, but its projection onto send actions (annotated to distinguish matched vs. unmatched sends) is regular. They define an extended alphabet $\mathcal{S} \cup \overline{\mathcal{S}}$ where $\overline{\mathcal{S}}$ denotes unmatched sends.
R-Diamond LTS: They utilize the property of R-diamond labeled transition systems (LTS), where the order of receiving actions by distinct processes does not affect reachability. This allows them to construct automata that operate on ms-sequences rather than full traces, effectively "guessing" the structure of rounds.
Atomic Exchanges and Communication Graphs: To detect violations of synchronizability, the authors analyze atomic exchanges (sequences that cannot be decomposed into smaller exchanges). They introduce a communication graph $H_{mb}(u)$ for a sequence $u$ . A sequence is atomic if and only if this graph is strongly connected. They construct automata ( $B_p$ and $B_{all}$ ) to verify strong connectivity and the existence of specific paths (well-labelings) within these graphs, ensuring that the sequence corresponds to a valid, non-decomposable exchange.
Minimal Witnesses: The algorithm for checking mb-synchronizability searches for a minimal witness of non-synchronizability. This witness is an mb-viable trace $u = v \cdot r$ (where $r$ is a receive action) such that $v$ is mb-synchronizable, but $u$ is not. The existence of such a witness is characterized by the structure of atomic factors in $v$ and their causal ordering relative to $r$ .

Key Contributions and Results

Pspace-Completeness of mb-Synchronizability: The primary result (Theorem 5.15) establishes that checking whether a CFM is mb-synchronizable is Pspace-complete. This provides a tight complexity bound, improving upon previous Exptime upper bounds derived from logical characterizations.
Global-State Reachability: The paper proves that global-state reachability for mb-synchronizable CFMs is Pspace-complete (Theorem 3.6).
Model-Checking: The authors show that model-checking mb-synchronizable CFMs against a class of R-closed regular properties (properties invariant under the reordering of independent receive actions) is Pspace-complete (Theorem 4.3).
Mailbox-Similarity: They address the question of whether a p2p system can be simulated under mailbox semantics (mailbox-similarity). While undecidable in general, they prove it is Pspace-complete for mb-synchronizable CFMs (Theorem 4.10).
Fixed Process Count: A notable byproduct of the approach is that if the number of processes is fixed, all the above problems become solvable in Ptime (specifically Nlogspace).
k-Mb-Synchronizability: The paper extends the results to $k$ -mb-synchronizability (rounds bounded by size $k$ ), showing this problem is also Pspace-complete (Theorem 5.16), and addresses the existence of some $k$ for which a system is synchronizable (Theorem 5.17).

Significance and Claims
The paper claims that its automata-based approach offers a more direct and efficient method for reasoning about mailbox communication compared to previous logical approaches (MSO, LCPDL). By focusing on the projection of traces onto send actions and utilizing the structural properties of atomic exchanges, the authors achieve optimal complexity bounds (Pspace) for fundamental verification problems.

The authors emphasize that their definition of mb-synchronizability (without fixed round sizes) is practically relevant because, while bounds on round sizes can be inferred, they are often exponential in the number of processes, making fixed-size assumptions impractical. The paper also clarifies the relationship between their notion of synchronizability and other existing notions (weak synchronizability, send-synchronizability), demonstrating that these notions are incomparable and that their specific definition is necessary for the decidability of certain regular properties.

Finally, the authors suggest that their techniques are potentially easier to implement than previous approaches and could be adapted to dynamic settings, though they do not present a specific implementation or experimental evaluation in this work.