License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2023.9
URN: urn:nbn:de:0030-drops-185433
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18543/
Go to the corresponding LIPIcs Volume Portal

Ahvonen, Veeti ; Heiman, Damian ; Hella, Lauri ; Kuusisto, Antti

Descriptive Complexity for Distributed Computing with Circuits

pdf-format:
LIPIcs-MFCS-2023-9.pdf (0.7 MB)

Abstract

We consider distributed algorithms in the realistic scenario where distributed message passing is operated by circuits. We show that within this setting, modal substitution calculus MSC precisely captures the expressive power of circuits. The result is established via constructing translations that are highly efficient in relation to size. We also observe that the coloring algorithm based on Cole-Vishkin can be specified by logarithmic size programs (and thus also logarithmic size circuits) in the bounded-degree scenario.

BibTeX - Entry

@InProceedings{ahvonen_et_al:LIPIcs.MFCS.2023.9,
  author =	{Ahvonen, Veeti and Heiman, Damian and Hella, Lauri and Kuusisto, Antti},
  title =	{{Descriptive Complexity for Distributed Computing with Circuits}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{9:1--9:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18543},
  URN =		{urn:nbn:de:0030-drops-185433},
  doi =		{10.4230/LIPIcs.MFCS.2023.9},
  annote =	{Keywords: Descriptive complexity, distributed computing, logic, graph coloring}
}

Keywords: Descriptive complexity, distributed computing, logic, graph coloring
Collection: 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Issue Date: 2023
Date of publication: 21.08.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI