DROPS

Document

DOI: 10.4230/LIPIcs.SAND.2025.5

Undecidability of the Emptiness Problem for Weak Models of Distributed Computing

Authors: Flavio T. Principato, Javier Esparza, and Philipp Czerner

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract

Esparza and Reiter have recently conducted a systematic comparative study of weak asynchronous models of distributed computing, in which a network of identical finite-state machines acts cooperatively to decide properties of the network’s graph. They introduced a distributed automata framework encompassing many different models, and proved that w.r.t. their expressive power (the graph properties they can decide) distributed automata collapse into seven equivalence classes. In this contribution, we turn our attention to the formal verification problem: Given a distributed automaton, does it decide a given graph property? We consider a fundamental instance of this question - the emptiness problem: Given a distributed automaton, does it accept any graph at all? Our main result is negative: the emptiness problem is undecidable for six of the seven equivalence classes, and trivially decidable for the remaining class.

Cite as

Flavio T. Principato, Javier Esparza, and Philipp Czerner. Undecidability of the Emptiness Problem for Weak Models of Distributed Computing. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{principato_et_al:LIPIcs.SAND.2025.5,
  author =	{Principato, Flavio T. and Esparza, Javier and Czerner, Philipp},
  title =	{{Undecidability of the Emptiness Problem for Weak Models of Distributed Computing}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{5:1--5:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.5},
  URN =		{urn:nbn:de:0030-drops-230582},
  doi =		{10.4230/LIPIcs.SAND.2025.5},
  annote =	{Keywords: Undecidability, Emptiness Problem, distributed Automata}
}

Search Results

Documents authored by Principato, Flavio T.

Undecidability of the Emptiness Problem for Weak Models of Distributed Computing

Abstract

Cite as

Thanks for your feedback!

Could not send message