Alkida Balliu · Juho Hirvonen · Janne H. Korhonen · Tuomo Lempiäinen · Dennis Olivetti · Jukka Suomela

New classes of distributed time complexity

STOC 2018 · 50th ACM Symposium on Theory of Computing, Los Angeles, CA, USA, June 2018 · doi:10.1145/3188745.3188860

authors’ version publisher’s version


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 $\alpha \ge 1$, $2^{\Theta( \log^{\alpha} n )}$ for any $\alpha \le 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 $\alpha \ge 1$, $\smash{2^{\Theta( \log^{\alpha} \log^* n )}}$ for any $\alpha \le 1$, and $\Theta((\log^* n)^{\alpha})$ for any $\alpha \le 1$ in the low end of the complexity spectrum; here $\alpha$ is a positive rational number.


Ilias Diakonikolas, David Kempe, and Monika Henzinger (Eds.): STOC’18, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1307–1318, ACM Press, New York, 2018

ISBN 978-1-4503-5559-9


This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.