License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2018.9
URN: urn:nbn:de:0030-drops-97982
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9798/
Balliu, Alkida ;
Brandt, Sebastian ;
Olivetti, Dennis ;
Suomela, Jukka
Almost Global Problems in the LOCAL Model
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 Theta(log^* n) or Theta(log n).
- It is not possible to have a problem with complexity between omega(log^* n) and o(log n).
- In general graphs, we can construct LCL problems with infinitely many complexities between omega(log n) and n^{o(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 problems with complexities of the form Theta(n^alpha) for any rational 0 < alpha <=1/2, while for trees only complexities of the form Theta(n^{1/k}) are known. No LCL problem with complexity between omega(sqrt{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 omega(sqrt{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(sqrt{n}) in trees, while the same is not true in general graphs.
BibTeX - Entry
@InProceedings{balliu_et_al:LIPIcs:2018:9798,
author = {Alkida Balliu and Sebastian Brandt and Dennis Olivetti and Jukka Suomela},
title = {{Almost Global Problems in the LOCAL Model}},
booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)},
pages = {9:1--9:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-092-7},
ISSN = {1868-8969},
year = {2018},
volume = {121},
editor = {Ulrich Schmid and Josef Widder},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9798},
URN = {urn:nbn:de:0030-drops-97982},
doi = {10.4230/LIPIcs.DISC.2018.9},
annote = {Keywords: Distributed complexity theory, locally checkable labellings, LOCAL model}
}
|
Keywords: |
|
Distributed complexity theory, locally checkable labellings, LOCAL model |
|
Collection: |
|
32nd International Symposium on Distributed Computing (DISC 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
04.10.2018 |
