New Classes of Distributed Time Complexity

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 $Pi$ 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 $Pi$. The time complexity classes for deterministic algorithms in bounded-degree graphs that are known to exist by prior work are $Theta(1)$, $Theta(log^* n)$, $Theta(log n)$, $Theta(n^{1/k})$, and $Theta(n)$. It is also known that there are two gaps: one between $omega(1)$ and $o(log log^* n)$, and another between $omega(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 $Theta(log^{alpha}n)$ for any $alphage1$, $2^{Theta(log^{alpha}n)}$ for any $alphale 1$, and $Theta(n^{alpha})$ for any $alpha <1/2$ in the high end of the complexity spectrum, and $Theta(log^{alpha}log^* n)$ for any $alphage 1$, $smash{2^{Theta(log^{alpha}log^* n)}}$ for any $alphale 1$, and $Theta((log^* n)^{alpha})$ for any $alpha le 1$ in the low end; here $alpha$ is a positive rational number.