Weakly synchronous systems with three machines are Turing powerful
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
An Asynchronous Distributed Framework for Large-scale Learning Based on Parameter Exchanges
In many distributed learning problems, the heterogeneous loading of computing machines may harm the overall performance of synchronous strategies. In this paper, we propose an effective asynchronous distributed framework…
Binary ClassificationGeneral ClassificationRecommendation SystemsNonlinear Magnetics Model for Permanent Magnet Synchronous Machines Capturing Saturation and Temperature Effects
This paper proposes a nonlinear magnetics model for Permanent Magnet Synchronous Machines (PMSMs) that accurately captures the effects of magnetic saturation in the machine iron and variations in rotor temperature on the…
'Viral' Turing Machines, Computation from Noise and Combinatorial Hierarchies
The interactive computation paradigm is reviewed and a particular example is extended to form the stochastic analog of a computational process via a transcription of a minimal Turing Machine into an equivalent asynchrono…
FormTuring Completeness and Sid Meier's Civilization
We prove that three strategy video games from the Sid Meier's Civilization series: Sid Meier's Civilization: Beyond Earth, Sid Meier's Civilization V, and Sid Meier's Civilization VI, are Turing complete. We achieve this…
Weakly Supervised Representation Learning for Unsynchronized Audio-Visual Events
Audio-visual representation learning is an important task from the perspective of designing machines with the ability to understand complex events. To this end, we propose a novel multimodal framework that instantiates m…
Multiple Instance LearningRepresentation Learning