Weakly Synchronous Systems with Three Machines Are Turing Powerful - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Conference Papers Year : 2023

Weakly Synchronous Systems with Three Machines Are Turing Powerful

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.
Fichier principal
Vignette du fichier
conference.pdf (1.71 Mo) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-04273451 , version 1 (07-11-2023)

Identifiers

Cite

Cinzia Di Giusto, Davide Ferré, Etienne Lozes, Nicolas Nisse. Weakly Synchronous Systems with Three Machines Are Turing Powerful. RP 2023 - 17th International Conference on Reachability Problems, 2023, Nice, France. pp.28-41, ⟨10.1007/978-3-031-45286-4_3⟩. ⟨hal-04273451⟩
39 View
19 Download

Altmetric

Share

Gmail Facebook X LinkedIn More