Almost global problems in the LOCAL model
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
23
Series
Distributed Computing, Volume 34, issue 4, pp. 259-281
Abstract
The landscape of the distributed time complexity is nowadays well-understood for subpolynomial complexities. When we look at deterministic algorithms in the LOCAL model and locally checkable problems (LCLs) in bounded-degree graphs, the following picture emerges:There are lots of problems with time complexities of Θ(log ∗n) or Θ(log n).It is not possible to have a problem with complexity between ω(log ∗n) and o(log n).In general graphs, we can construct LCL problems with infinitely many complexities between ω(log n) and no(1).In trees, problems with such complexities do not exist. However, the high end of the complexity spectrum was left open by prior work. In general graphs there are LCL problems with complexities of the form Θ(nα) for any rational 0 < α≤ 1 / 2 , while for trees only complexities of the form Θ(n1/k) are known. No LCL problem with complexity between ω(n) and o(n) is known, and neither are there results that would show that such problems do not exist. We show that:In general graphs, we can construct LCL problems with infinitely many complexities between ω(n) and o(n).In trees, problems with such complexities do not exist. Put otherwise, we show that any LCL with a complexity o(n) can be solved in time O(n) in trees, while the same is not true in general graphs.Description
Funding Information: Open access funding provided by Aalto University. We thank the anonymous reviewers for their helpful comments and suggestions. This work was supported in part by the Academy of Finland, Grant 285721. Funding Information: Open access funding provided by Aalto University. We thank the anonymous reviewers for their helpful comments and suggestions. This work was supported in part by the Academy of Finland, Grant 285721. Publisher Copyright: © 2020, The Author(s).
Other note
Citation
Balliu, A, Brandt, S, Olivetti, D & Suomela, J 2021, 'Almost global problems in the LOCAL model', Distributed Computing, vol. 34, no. 4, pp. 259-281. https://doi.org/10.1007/s00446-020-00375-2