Weak models of distributed computing, with connections to modal logic

DOI10.1145/2332432.2332466MaRDI QIDQ5891978zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Lauri Hella, Matti Järvisalo, Antti Kuusisto, Juhana Laurinharju, Tuomo Lempiäinen, Kerkko Luosto, Jukka Suomela, Jonni Virtema

Publication date 5 December 2014

Published in Proceedings of the 2012 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1205.2051, http://hdl.handle.net/10138/37409

zbMATH Keywords

anonymous networksdeterministic distributed algorithmsgraph problemsmodal logicport-numbering model

Mathematics Subject Classification ID

Logic in computer science (03B70) Distributed systems (68M14) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15)

Abstract: This work presents a classification of weak models of distributed computing. We focus on deterministic distributed algorithms, and study models of computing that are weaker versions of the widely-studied port-numbering model. In the port-numbering model, a node of degree d receives messages through d input ports and sends messages through d output ports, both numbered with 1,2,...,d. In this work, VVc is the class of all graph problems that can be solved in the standard port-numbering model. We study the following subclasses of VVc: VV: Input port i and output port i are not necessarily connected to the same neighbour. MV: Input ports are not numbered; algorithms receive a multiset of messages. SV: Input ports are not numbered; algorithms receive a set of messages. VB: Output ports are not numbered; algorithms send the same message to all output ports. MB: Combination of MV and VB. SB: Combination of SV and VB. Now we have many trivial containment relations, such as SB subseteq MB subseteq VB subseteq VV subseteq VVc, but it is not obvious if, for example, either of VB subseteq SV or SV subseteq VB should hold. Nevertheless, it turns out that we can identify a linear order on these classes. We prove that SB subsetneq MB = VB subsetneq SV = MV = VV subsetneq VVc. The same holds for the constant-time versions of these classes. We also show that the constant-time variants of these classes can be characterised by a corresponding modal logic. Hence the linear order identified in this work has direct implications in the study of the expressibility of modal logic. Conversely, one can use tools from modal logic to study these classes.

Recommendations

• Weak models of distributed computing, with connections to modal logic
• Modal logic and distributed message passing automata
• Programming Languages and Systems
• Distributed modal logic
• Models for quantitative distributed systems and multi-valued logics
• Models for quantitative distributed systems and multi-valued logics
• scientific article; zbMATH DE number 3855074
• scientific article; zbMATH DE number 7559466
• Model theoretical aspects of weakly aggregative modal logic
• Computer Science Logic

Cited in

(10)

• Emptiness problems for distributed automata
• Emptiness problems for distributed automata
• Broadcasting automata and patterns on \(\mathbb{Z}^2\)
• Distributed graph algorithms and their complexity: an introduction
• Programming Languages and Systems
• Weak models of distributed computing, with connections to modal logic
• Theory of graph neural networks: representation and learning
• Descriptive complexity for neural networks via Boolean networks
• Descriptive complexity for distributed computing with circuits
• Descriptive complexity for neural networks via Boolean networks

This page was built for publication: Weak models of distributed computing, with connections to modal logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5891978)