@article{HJKLLLSV:DC2015,
author = {Lauri Hella and Matti J\"arvisalo and
Antti Kuusisto and Juhana Laurinharju and
Tuomo Lempi\"ainen and Kerkko Luosto and
Jukka Suomela and Jonni Virtema},
title = {Weak Models of Distributed Computing,
with Connections to Modal Logic},
journal = {Distributed Computing},
volume = {28},
number = {1},
pages = {31--53},
year = {2015},
}
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.