The Landscape of Distributed Complexities on Trees and Beyond

DOI10.1145/3519270.3538452arXiv2202.04724WikidataQ130826844 ScholiaQ130826844MaRDI QIDQ6201995FDOQ6201995

Authors: Christoph Grunau, Václav Rozhoň, Sebastian F. Brandt 

Publication date: 26 March 2024

Published in: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Abstract: We study the local complexity landscape of locally checkable labeling (LCL) problems on constant-degree graphs with a focus on complexities below $lo{g}^{\ast }n$. Our contribution is threefold: Our main contribution is that we complete the classification of the complexity landscape of LCL problems on trees in the LOCAL model, by proving that every LCL problem with local complexity $o(lo{g}^{\ast }n)$ has actually complexity $O(1)$. This result improves upon the previous speedup result from $o(loglo{g}^{\ast }n)$ to $O(1)$ by [Chang, Pettie, FOCS 2017]. In the related LCA and Volume models [Alon, Rubinfeld, Vardi, Xie, SODA 2012, Rubinfeld, Tamir, Vardi, Xie, 2011, Rosenbaum, Suomela, PODC 2020], we prove the same speedup from $o(lo{g}^{\ast }n)$ to $O(1)$ for all bounded degree graphs. Similarly, we complete the classification of the LOCAL complexity landscape of oriented $d$-dimensional grids by proving that any LCL problem with local complexity $o(lo{g}^{\ast }n)$ has actually complexity $O(1)$. This improves upon the previous speed-up from $o(sqrt[d]lo{g}^{\ast }n)$ by Suomela in [Chang, Pettie, FOCS 2017].

Full work available at URL: https://arxiv.org/abs/2202.04724

zbMATH Keywords

localitygraph problemslocal modelgap resultdistributed complexity theoryLCL problemsvolume model

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

This page was built for publication: The Landscape of Distributed Complexities on Trees and Beyond

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6201995)