Abstract
Communicating finite-state machines (CFMs) are a Turing powerful model of asynchronous message-passing distributed systems. In weakly synchronous systems, processes communicate through phases in which messages are first sent and then received, for each process. Such systems enjoy a limited form of synchronization, and for some communication models, this restriction is enough to make the reachability problem decidable. In particular, we explore the intriguing case of p2p (FIFO) communication, for which the reachability problem is known to be undecidable for four processes, but decidable for two. We show that the configuration reachability problem for weakly synchronous systems of three processes is undecidable. This result is heavily inspired by our study on the treewidth of the Message Sequence Charts (MSCs) that might be generated by such systems. In this sense, the main contribution of this work is a weakly synchronous system with three processes that generates MSCs of arbitrarily large treewidth.
Introduction: The Reachability Problem
In distributed computing, modeling processes as Communicating Finite-State Machines (CFMs) allows for the formal analysis of asynchronous message-passing. A central challenge is the reachability problem: determining if a system can transition from an initial state to a specific target configuration. This problem is fundamental for verifying protocol safety and correctness.
While reachability for general CFMs is undecidable, researchers have sought constraints that make verification feasible. One such constraint is weak synchrony, where communication occurs in phases: each process must complete its "send" operations before beginning its "receive" operations within a phase. For point-to-point (p2p) FIFO communication, previous work established that reachability is decidable for two machines but undecidable for four. This paper addresses the critical gap: the case of three machines.
Methods: Simulating Complexity
The authors prove that three machines are sufficient for Turing power using two primary theoretical approaches:
- Treewidth and Grid Simulation: They represent Message Sequence Charts (MSCs)—the visual timelines of message exchanges—as directed graphs. By focusing on treewidth, a measure of graph complexity, they demonstrate that a 3-machine system can generate MSCs with arbitrarily large treewidth. This is achieved by "bouncing" messages between the three processes to simulate the structure of a 2D grid.
- Reduction from FIFO Automata: To establish undecidability, the authors reduce the problem from a FIFO automaton (a machine with a single internal queue, known to be Turing powerful). They show how a 3-machine weakly synchronous system can simulate such an automaton. In this setup, one machine acts as the primary logic processor, while the other two serve as forwarders, using dummy messages to maintain FIFO integrity across synchronization phases.
Key Insights: The Threshold of Three
The transition from two to three machines represents a critical threshold in computational power. While two machines are restricted to simple "mailbox" communication patterns, three machines allow for a "triangulation" of messages. This triangulation can be leveraged to simulate complex memory structures, like a Turing machine tape.
The study highlights a deep connection between the structural complexity of message history (treewidth) and computational power. If a system's message history can form a grid, it can likely simulate a Turing machine. The authors found that even with the restrictions of "weak synchrony," clever distribution of operations across multiple phases and machines allows for the simulation of a continuous FIFO queue.
Results and Implications
The core findings of the paper are:
- Unbounded Treewidth: Weakly synchronous p2p systems with three processes can generate MSCs of arbitrarily large treewidth (Theorem 3.3).
- Undecidability: The configuration reachability (or emptiness) problem for these 3-machine systems is undecidable (Theorem 4.2).
- Causal Ordering: This undecidability extends to Causally Ordered (CO) communication models (Corollary 4.2.1).
Conclusion and Future Work
This work settles the complexity of 3-machine weakly synchronous systems for p2p and CO models. However, other models, such as the mailbox model (where each machine has a single input queue for all senders), remain decidable even in weakly synchronous settings.
Future research directions include determining the exact computational complexity for decidable cases (like 2-machine systems), exploring alternative synchrony constraints that might preserve decidability for three machines, and developing verification heuristics for specific subclasses of 3-machine protocols used in industry.
Summary updated