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

Weak models of distributed computing, with connections to modal logic

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

authors’ version publisher’s version arXiv.org

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 it 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 ⊆ MB ⊆ VB ⊆ VV ⊆ VVc, 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 ⊊ 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, we can use tools from modal logic to study these classes.

Publication

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

Links

Journal Version

© ACM 2012 — This is the authors’ version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proc. 31st Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. http://doi.acm.org/10.1145/2332432.2332466

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.