2017/11/06 by Balliu, Alkida, Hirvonen, Juho, Korhonen, Janne H. +3 · 3 citations
#Computational Complexity (cs.CC) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.1711.01871
A number of recent papers -- e.g. Brandt et al. (STOC 2016), Chang et al. (FOCS 2016), Ghaffari & Su (SODA 2017), Brandt et al. (PODC 2017), and Chang & Pettie (FOCS 2017) -- have advanced our understanding of one of the most fundamental questions in theory of distributed computing: what are the possible time complexity classes of LCL problems in the LOCAL model? In essence, we have a graph problem Π in which a solution can be verified by checking all radius-O(1) neighbourhoods, and the question is what is the smallest T such that a solution can be computed so that each node chooses its own output based on its radius-T neighbourhood. Here T is the distributed time complexity of Π. The time complexity classes for deterministic algorithms in bounded-degree graphs that are known to exist by prior work are Θ(1), Θ(log^* n), Θ(log n), Θ(n1/k), and Θ(n). It is also known that there are two gaps: one between ω(1) and o(log log^* n), and another between ω(log^* n) and o(log n). It has been conjectured that many more gaps exist, and that the overall time hierarchy is relatively simple -- indeed, this is known to be the case in restricted graph families such as cycles and grids. We show that the picture is much more diverse than previously expected. We present a general technique for engineering LCL problems with numerous different deterministic time complexities, including Θ(logαn) for any α≥1, 2Θ(logαn) for any α≤ 1, and Θ(nα) for any α<1/2 in the high end of the complexity spectrum, and Θ(logαlog^* n) for any α≥ 1, \smash2Θ(logαlog^* n) for any α≤ 1, and Θ((log^* n)α) for any α≤ 1 in the low end; here α is a positive rational number.