PODC 2012 · 31st Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, Madeira, Portugal, July 2012 · doi:10.1145/2332432.2332466

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 it sends messages through *d* output ports, both numbered with 1, 2, …, *d*. In this work, VV_{c} is the class of all *graph problems* that can be solved in the standard port-numbering model. We study the following subclasses of VV_{c}:

- 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 ⊆ MB ⊆ VB ⊆ VV ⊆ VV_{c}, but it is not obvious if, e.g., either of VB ⊆ SV or SV ⊆ VB should hold. Nevertheless, it turns out that we can identify a *linear order* on these classes. We prove that SB ⊊ MB = VB ⊊ SV = MV = VV ⊊ VV_{c}. 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, we can use tools from modal logic to study these classes.

Darek Kowalski and Alessandro Panconesi (Eds.): *PODC’12, Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing, July 16–18, 2012, Madeira, Portugal*, pages 185–194, ACM Press, New York, 2012

ISBN 978-1-4503-1450-3

- Lauri Hella, Matti Järvisalo, Antti Kuusisto, Juhana Laurinharju, Tuomo Lempiäinen, Kerkko Luosto, Jukka Suomela, and Jonni Virtema: Weak models of distributed computing, with connections to modal logic ·
*Distributed Computing*28:31–53, 2015