Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Balliu, Alkida; Censor-Hillel, Keren; Maus, Yannic; Olivetti, Dennis; Suomela, Jukka https://www.dagstuhl.de/lipics License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-148109
URL:

; ; ; ;

Locally Checkable Labelings with Small Messages

pdf-format:


Abstract

A rich line of work has been addressing the computational complexity of locally checkable labelings (LCLs), illustrating the landscape of possible complexities. In this paper, we study the landscape of LCL complexities under bandwidth restrictions. Our main results are twofold. First, we show that on trees, the CONGEST complexity of an LCL problem is asymptotically equal to its complexity in the LOCAL model. An analog statement for non-LCL problems is known to be false. Second, we show that for general graphs this equivalence does not hold, by providing an LCL problem for which we show that it can be solved in O(log n) rounds in the LOCAL model, but requires Ω̃(n^{1/2}) rounds in the CONGEST model.

BibTeX - Entry

@InProceedings{balliu_et_al:LIPIcs.DISC.2021.8,
  author =	{Balliu, Alkida and Censor-Hillel, Keren and Maus, Yannic and Olivetti, Dennis and Suomela, Jukka},
  title =	{{Locally Checkable Labelings with Small Messages}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14810},
  URN =		{urn:nbn:de:0030-drops-148109},
  doi =		{10.4230/LIPIcs.DISC.2021.8},
  annote =	{Keywords: distributed graph algorithms, CONGEST, locally checkable labelings}
}

Keywords: distributed graph algorithms, CONGEST, locally checkable labelings
Seminar: 35th International Symposium on Distributed Computing (DISC 2021)
Issue date: 2021
Date of publication: 04.10.2021


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