Document Open Access Logo

Asynchronous Distributed Automata: A Characterization of the Modal Mu-Fragment

Author Fabian Reiter

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2017.100.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Subject Classification

Keywords
  • finite automata
  • distributed computing
  • modal logic
  • mu-calculus

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We establish the equivalence between a class of asynchronous distributed automata and a small fragment of least fixpoint logic, when restricted to finite directed graphs. More specifically, the logic we consider is (a variant of) the fragment of the modal mu-calculus that allows least fixpoints but forbids greatest fixpoints. The corresponding automaton model uses a network of identical finite-state machines that communicate in an asynchronous manner and whose state diagram must be acyclic except for self-loops. Exploiting the connection with logic, we also prove that the expressive power of those machines is independent of whether or not messages can be lost.

Cite As Get BibTex

Fabian Reiter. Asynchronous Distributed Automata: A Characterization of the Modal Mu-Fragment. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 100:1-100:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.100

Author Details

Fabian Reiter

References

  1. Patrick Blackburn, Maarten de Rijke, and Yde Venema. Modal logic, volume 53 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge, 2002. URL: http://dx.doi.org/10.1017/CBO9781107050884.
  2. Patrick Blackburn and Johan van Benthem. Modal logic: a semantic perspective. In Patrick Blackburn, Johan van Benthem, and Frank Wolter, editors, Handbook of Modal Logic, volume 3 of Studies in Logic and Practical Reasoning, pages 1-84. Elsevier, 2007. URL: http://dx.doi.org/10.1016/S1570-2464(07)80004-8.
  3. Julian Bradfield and Colin Stirling. Modal mu-calculi. In Patrick Blackburn, Johan van Benthem, and Frank Wolter, editors, Handbook of Modal Logic, volume 3 of Studies in Logic and Practical Reasoning, pages 721-756. Elsevier, 2007. URL: http://dx.doi.org/10.1016/S1570-2464(07)80015-2.
  4. Erich Grädel, Phokion G. Kolaitis, Leonid Libkin, Maarten Marx, Joel Spencer, Moshe Y. Vardi, Yde Venema, and Scott Weinstein. Finite Model Theory and Its Applications. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2007. URL: http://dx.doi.org/10.1007/3-540-68804-8.
  5. 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. In Darek Kowalski and Alessandro Panconesi, editors, ACM Symposium on Principles of Distributed Computing, PODC'12, Funchal, Madeira, Portugal, July 16-18, 2012, pages 185-194. ACM, 2012. URL: http://dx.doi.org/10.1145/2332432.2332466.
  6. 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(1):31-53, 2015. URL: http://dx.doi.org/10.1007/s00446-013-0202-3.
  7. Antti Kuusisto. Modal logic and distributed message passing automata. In Simona Ronchi Della Rocca, editor, Computer Science Logic 2013 (CSL 2013), CSL 2013, September 2-5, 2013, Torino, Italy, volume 23 of LIPIcs, pages 452-468. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2013. URL: http://dx.doi.org/10.4230/LIPIcs.CSL.2013.452.
  8. Antti Kuusisto. Infinite networks, halting and local algorithms. In Adriano Peron and Carla Piazza, editors, Proceedings Fifth International Symposium on Games, Automata, Logics and Formal Verification, GandALF 2014, Verona, Italy, September 10-12, 2014, volume 161 of EPTCS, pages 147-160, 2014. URL: http://dx.doi.org/10.4204/EPTCS.161.14.
  9. Giacomo Lenzi. The modal μ-calculus: a survey. TASK Quarterly - Scientific Bulletin of the Academic Computer Centre in Gdansk, 9(3):293-316, 2005. URL: http://task.gda.pl/quart/05-3.html.
  10. Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann, 1996. Google Scholar
  11. David Peleg. Distributed Computing: A Locality-Sensitive Approach, volume 5 of SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics (SIAM), 2000. URL: http://dx.doi.org/10.1137/1.9780898719772.
  12. Jukka Suomela. Survey of local algorithms. ACM Comput. Surv., 45(2):24:1-24:40, 2013. URL: http://dx.doi.org/10.1145/2431211.2431223.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact