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, 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:
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.
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