research-article

Weak models of distributed computing, with connections to modal logic

Authors:

Matti Järvisalo,

Antti Kuusisto,

Juhana Laurinharju,

Tuomo Lempiäinen,

Jonni VirtemaAuthors Info & Claims

PODC '12: Proceedings of the 2012 ACM symposium on Principles of distributed computing

Pages 185 - 194

https://doi.org/10.1145/2332432.2332466

Published: 16 July 2012 Publication History

Abstract

This work presents a classification of weak models of distributed computing. We focus on deterministic distributed algorithms, and we 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 ⊆ 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 ⊂≠ 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.

References

[1]

Yehuda Afek, Noga Alon, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler, and Fabian Kuhn. Beeping a maximal independent set. In Proc. DISC 2011, volume 6950 of LNCS, pages 32--50. Springer, 2011.

Digital Library

[2]

Dana Angluin. Local and global properties in networks of processors. In Proc. STOC 1980, pages 82--93. ACM Press, 1980.

Digital Library

[3]

Matti Åstrand and Jukka Suomela. Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks. In Proc. SPAA 2010, pages 294--302. ACM Press, 2010.

Digital Library

[4]

Hagit Attiya, Marc Snir, and Manfred K. Warmuth. Computing on an anonymous ring. J. ACM, 35(4):845--875, 1988.

Digital Library

[5]

Patrick Blackburn, Maarten de Rijke, and Yde Venema. Modal Logic, volume 53 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 2001.

Digital Library

[6]

Patrick Blackburn, Johan van Benthem, and Frank Wolter, editors. Handbook of Modal Logic, volume 3 of Studies in Logic and Practical Reasoning. Elsevier, 2007.

Digital Library

[7]

Paolo Boldi, Shella Shammah, Sebastiano Vigna, Bruno Codenotti, Peter Gemmell, and Janos Simon. Symmetry breaking in anonymous networks: characterizations. In Proc. ISTCS 1996, pages 16--26. IEEE, 1996.

[8]

Paolo Boldi and Sebastiano Vigna. Computing vector functions on anonymous networks. In Proc. SIROCCO 1997, pages 201--214. Carleton Scientific, 1997.

Digital Library

[9]

Paolo Boldi and Sebastiano Vigna. An effective characterization of computability in anonymous networks. In Proc. DISC 2001, volume 2180 of LNCS, pages 33--47. Springer, 2001.

Digital Library

[10]

J. A. Bondy and U. S. R. Murty. Graph Theory with Applications. North-Holland, New York, 1976.

Digital Library

[11]

Krzysztof Diks, Evangelos Kranakis, Adam Malinowski, and Andrzej Pelc. Anonymous wireless rings. Theoret. Comput. Sci., 145(1-2):95--109, 1995.

Digital Library

[12]

Kit Fine. In so many possible worlds. Notre Dame J. Formal Logic, 13(4):516--520, 1972.

[13]

Mika Göös, Juho Hirvonen, and Jukka Suomela. Lower bounds for local approximation. In Proc. PODC 2012. ACM Press, 2012.

Digital Library

[14]

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, 2012. Manuscript, arXiv:1205.2051 {cs.DC}.

[15]

Neil Immerman. Descriptive Complexity. Graduate Texts in Computer Science. Springer, 1999.

[16]

Fabian Kuhn and Roger Wattenhofer. On the complexity of distributed graph coloring. In Proc. PODC 2006, pages 7--15. ACM Press, 2006.

Digital Library

[17]

Nathan Linial. Locality in distributed graph algorithms. SIAM J. Comput., 21(1):193--201, 1992.

Digital Library

[18]

Alain Mayer, Moni Naor, and Larry Stockmeyer. Local computations on static and dynamic graphs. In Proc. ISTCS 1995, pages 268--278. IEEE, 1995.

Digital Library

[19]

Moni Naor and Larry Stockmeyer. What can be computed locally? SIAM J. Comput., 24(6):1259--1277, 1995.

Digital Library

[20]

Nancy Norris. Computing functions on partially wireless networks. In Proc. SIROCCO 1995, pages 53--64. Carleton Scientific, 1996.

[21]

David Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics and Applications. SIAM, 2000.

Digital Library

[22]

Jukka Suomela. Survey of local algorithms. ACM Comput. Surveys. To appear.

Digital Library

[23]

Stephen Wolfram. Statistical mechanics of cellular automata. Reviews of Modern Physics, 55(3):601--644, 1983.

[24]

Masafumi Yamashita and Tsunehiko Kameda. Electing a leader when processor identity numbers are not distinct (extended abstract). In Proc. WDAG 1989, volume 392 of LNCS, pages 303--314. Springer, 1989.

Digital Library

[25]

Masafumi Yamashita and Tsunehiko Kameda. Computing functions on asynchronous anonymous networks. Mathematical Systems Theory, 29(4):331--356, 1996.

[26]

Masafumi Yamashita and Tsunehiko Kameda. Computing on anonymous networks: Part I - characterizing the solvable cases. IEEE Trans. Parallel Distrib. Systems, 7(1):69--89, 1996.

Digital Library

[27]

Masafumi Yamashita and Tsunehiko Kameda. Computing on anonymous networks: Part II - decision and membership problems. IEEE Trans. Parallel Distrib. Systems, 7(1):90--96, 1996.

Digital Library

[28]

Masafumi Yamashita and Tsunehiko Kameda. Leader election problem on networks in which processor identity numbers are not distinct. IEEE Trans. Parallel Distrib. Systems, 10(9):878--887, 1999.

Digital Library

Cited By

Sato RYamada MKashima HWallach HLarochelle HBeygelzimer Ad'Alché-Buc FFox E(2019)Approximation ratios of graph neural networks for combinatorial problemsProceedings of the 33rd International Conference on Neural Information Processing Systems10.5555/3454287.3454654(4081-4090)Online publication date: 8-Dec-2019
https://dl.acm.org/doi/10.5555/3454287.3454654
Shimi A(2019)The Splendors and Miseries of RoundsACM SIGACT News10.1145/3364626.336463550:3(35-50)Online publication date: 24-Sep-2019
https://dl.acm.org/doi/10.1145/3364626.3364635
Kuusisto AReiter F(2019)Emptiness problems for distributed automataInformation and Computation10.1016/j.ic.2019.104503(104503)Online publication date: Dec-2019
https://doi.org/10.1016/j.ic.2019.104503
Show More Cited By

Index Terms

Weak models of distributed computing, with connections to modal logic
1. Computer systems organization
  1. Architectures
    1. Distributed architectures
2. Software and its engineering
  1. Software organization and properties
    1. Software system structures
      1. Distributed systems organizing principles

Recommendations

A modal logic internalizing normal proofs

In the proof-theoretic study of logic, the notion of normal proof has been understood and investigated as a metalogical property. Usually we formulate a system of logic, identify a class of proofs as normal proofs, and show that every proof in the ...
Elementary Definability and Completeness in General and Positive Modal Logic

The paper generalises Goldblatt's completeness proof for Lemmon–Scott formulas to various modal propositional logics without classical negation and without ex falso , up to positive modal logic, where conjunction and disjunction, and where necessity and ...
Some Connections between Topological and Modal Logic
Abstract
We study modal logics based on neighbourhood semantics using methods and theorems having their origin in topological model theory. We thus obtain general results concerning completeness of modal logics based on neighbourhood semantics as well as ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '12: Proceedings of the 2012 ACM symposium on Principles of distributed computing

July 2012

410 pages

ISBN:9781450314503

DOI:10.1145/2332432

General Chair:
Darek Kowalski
U. of Liverpool, UK and IMDEA Networks, Spain
,
Program Chair:
Alessandro Panconesi
Sapienza, University of Rome, Italy

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
INESC-ID: INESC-ID Lisboa

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 July 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PODC '12

Sponsor:

SIGOPS
SIGACT
INESC-ID

PODC '12: ACM Symposium on Principles of Distributed Computing

July 16 - 18, 2012

Madeira, Portugal

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
211
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)3

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sato RYamada MKashima HWallach HLarochelle HBeygelzimer Ad'Alché-Buc FFox E(2019)Approximation ratios of graph neural networks for combinatorial problemsProceedings of the 33rd International Conference on Neural Information Processing Systems10.5555/3454287.3454654(4081-4090)Online publication date: 8-Dec-2019
https://dl.acm.org/doi/10.5555/3454287.3454654
Shimi A(2019)The Splendors and Miseries of RoundsACM SIGACT News10.1145/3364626.336463550:3(35-50)Online publication date: 24-Sep-2019
https://dl.acm.org/doi/10.1145/3364626.3364635
Kuusisto AReiter F(2019)Emptiness problems for distributed automataInformation and Computation10.1016/j.ic.2019.104503(104503)Online publication date: Dec-2019
https://doi.org/10.1016/j.ic.2019.104503
Bollig BBouyer PReiter F(2019)Identifiers in RegistersFoundations of Software Science and Computation Structures10.1007/978-3-030-17127-8_7(115-132)Online publication date: 8-Apr-2019
https://dl.acm.org/doi/10.1007/978-3-030-17127-8_7
Hella LJärvisalo MKuusisto ALaurinharju JLempiäinen TLuosto KSuomela JVirtema J(2018)Weak models of distributed computing, with connections to modal logicDistributed Computing10.1007/s00446-013-0202-328:1(31-53)Online publication date: 26-Dec-2018
https://dl.acm.org/doi/10.1007/s00446-013-0202-3
Kuusisto AReiter F(2017)Emptiness Problems for Distributed AutomataElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.256.15256(210-222)Online publication date: 6-Sep-2017
https://doi.org/10.4204/EPTCS.256.15
IZUMI T(2015)Distributed Graph Algorithms and their Complexity: An IntroductionInterdisciplinary Information Sciences10.4036/iis.2015.L.0421:4(351-370)Online publication date: 2015
https://doi.org/10.4036/iis.2015.L.04
Hendrickx JTsitsiklis J(2015)Fundamental limitations for anonymous distributed systems with broadcast communications2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton)10.1109/ALLERTON.2015.7446980(9-16)Online publication date: Sep-2015
https://doi.org/10.1109/ALLERTON.2015.7446980
Nickson TPotapov I(2015)Broadcasting Automata and Patterns on ℤ2Automata, Universality, Computation10.1007/978-3-319-09039-9_14(297-340)Online publication date: 2015
https://doi.org/10.1007/978-3-319-09039-9_14
Kuusisto A(2014)Infinite Networks, Halting and Local AlgorithmsElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.161.14161(147-160)Online publication date: 24-Aug-2014
https://doi.org/10.4204/EPTCS.161.14
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten