A Classification of Weak Asynchronous Models of Distributed Computing

Authors Javier Esparza , Fabian Reiter



PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2020.10.pdf
  • Filesize: 0.58 MB
  • 16 pages

Document Identifiers

Author Details

Javier Esparza
  • Technical University of Munich, Germany
Fabian Reiter
  • LIGM, Université Gustave Eiffel, Marne-la-Vallée, France

Acknowledgements

The authors thank Ahmed Bouajjani for many interesting discussions, and several anonymous reviewers for their helpful feedback.

Cite AsGet BibTex

Javier Esparza and Fabian Reiter. A Classification of Weak Asynchronous Models of Distributed Computing. In 31st International Conference on Concurrency Theory (CONCUR 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 171, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.CONCUR.2020.10

Abstract

We conduct a systematic study of asynchronous models of distributed computing consisting of identical finite-state devices that cooperate in a network to decide if the network satisfies a given graph-theoretical property. Models discussed in the literature differ in the detection capabilities of the agents residing at the nodes of the network (detecting the set of states of their neighbors, or counting the number of neighbors in each state), the notion of acceptance (acceptance by halting in a particular configuration, or by stable consensus), the notion of step (synchronous move, interleaving, or arbitrary timing), and the fairness assumptions (non-starving, or stochastic-like). We study the expressive power of the combinations of these features, and show that the initially twenty possible combinations fit into seven equivalence classes. The classification is the consequence of several equi-expressivity results with a clear interpretation. In particular, we show that acceptance by halting configuration only has non-trivial expressive power if it is combined with counting, and that synchronous and interleaving models have the same power as those in which an arbitrary set of nodes can move at the same time. We also identify simple graph properties that distinguish the expressive power of the seven classes.

Subject Classification

ACM Subject Classification
  • Theory of computation → Automata extensions
  • Theory of computation → Concurrency
  • Theory of computation → Distributed computing models
Keywords
  • Asynchrony
  • Concurrency theory
  • Weak models of distributed computing

Metrics

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

References

  1. Dana Angluin, James Aspnes, Melody Chan, Michael J Fischer, Hong Jiang, and René Peralta. Stably computable properties of network graphs. In International Conference on Distributed Computing in Sensor Systems, pages 63-74. Springer, 2005. Google Scholar
  2. Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. In PODC, pages 290-299. ACM, 2004. Google Scholar
  3. Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Computing, 18(4):235-253, 2006. Google Scholar
  4. Baruch Awerbuch. Complexity of network synchronization. J. ACM, 32(4):804-823, 1985. URL: https://doi.org/10.1145/4221.4227.
  5. Alejandro Cornejo and Fabian Kuhn. Deploying wireless networks with beeps. In DISC, volume 6343 of Lecture Notes in Computer Science, pages 148-162. Springer, 2010. Google Scholar
  6. Yuval Emek and Roger Wattenhofer. Stone age distributed computing. In PODC, pages 137-146. ACM, 2013. Google Scholar
  7. Nissim Francez. Fairness. Texts and Monographs in Computer Science. Springer, 1986. Google Scholar
  8. 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. Google Scholar
  9. Daniel Lehmann, Amir Pnueli, and Jonathan Stavi. Impartiality, justice and fairness: The ethics of concurrent termination. In ICALP, volume 115 of Lecture Notes in Computer Science, pages 264-277. Springer, 1981. Google Scholar
  10. Katsuhiko Nakamura. Synchronous to asynchronous transformation of polyautomata. J. Comput. Syst. Sci., 23(1):22-37, 1981. URL: https://doi.org/10.1016/0022-0000(81)90003-9.
  11. Saket Navlakha and Ziv Bar-Joseph. Distributed information processing in biological and computational systems. Commun. ACM, 58(1):94-102, 2015. URL: https://doi.org/10.1145/2678280.
  12. Fabian Reiter. Asynchronous distributed automata: A characterization of the modal mu-fragment. In ICALP, volume 80 of LIPIcs, pages 100:1-100:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  13. David Soloveichik, Matthew Cook, Erik Winfree, and Jehoshua Bruck. Computation with finite stochastic chemical reaction networks. Natural Computing, 7(4):615-633, 2008. Google Scholar
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