Alkida Balliu · Keren Censor-Hillel · Yannic Maus · Dennis Olivetti · Jukka Suomela

Locally checkable labelings with small messages

DISC 2021 · 35th International Symposium on Distributed Computing, online, October 2021 · doi:10.4230/LIPIcs.DISC.2021.8

authors’ version publisher’s version arXiv.org

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 general (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 $\tilde{\Omega}(n^{1/2})$ rounds in the CONGEST model.

Publication

Seth Gilbert (Ed.): 35th International Symposium on Distributed Computing (DISC 2021), volume 209 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1–8:18, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2021

ISBN 978-3-95977-210-5

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.