Weakly synchronous systems with three machines are Turing powerful
Cinzia Di Giusto Davide Ferré Etienne Lozes Nicolas Nisse
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.