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 Π 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 ), Θ( n 1/ k ), and Θ( n ). It is also known that there are two gaps: one between ω(1) and o (loglog * 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, 2 Θ(log α log * n ) for any α ≤ 1, and Θ((log * n ) α ) for any α ≤ 1 in the low end of the complexity spectrum; here α is a positive rational number.

Authors

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

Keywords

• LOCAL model
• distributed complexity theory
• graph algorithms
• locally checkable labellings