New classes of distributed time complexity

DOI10.1145/3188745.3188860MaRDI QIDQ5230383zbMATH OpenOpenAlexWikidataFDO

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

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.01871, https://aaltodoc.aalto.fi/handle/123456789/37232

zbMATH Keywords

graph algorithmsLOCAL modeldistributed complexity theorylocally checkable labellings

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Distributed algorithms (68W15)

Abstract: 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(lo{g}^{\ast }n)$, $Theta(logn)$, $Theta(n^{1/k})$, and $Theta(n)$. It is also known that there are two gaps: one between $omega(1)$ and $o(loglo{g}^{\ast }n)$, and another between $omega(lo{g}^{\ast }n)$ and $o(logn)$. 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(lo{g}^{alpha}n)$ for any $alphage1$, $2^{Theta(lo{g}^{alpha}n)}$ for any $alphale1$, and $Theta(n^{alpha})$ for any $alpha<1/2$ in the high end of the complexity spectrum, and $Theta(lo{g}^{alpha}lo{g}^{\ast }n)$ for any $alphage1$, $smash{2}^{Theta(lo{g}^{alpha}lo{g}^{\ast }n)}$ for any $alphale1$, and $Theta((lo{g}^{\ast }n{)}^{alpha})$ for any $alphale1$ in the low end; here $alpha$ is a positive rational number.

Recommendations

• scientific article; zbMATH DE number 7561283
• scientific article; zbMATH DE number 4050992
• Efficient distributed algorithms by using the archimedean time assumption
• Average and Randomized Complexity of Distributed Problems
• scientific article; zbMATH DE number 1202979
• Some distributed algorithms revisited
• On the Complexity of Distributed Splitting Problems
• Distributed algorithms for time optimal reachability analysis
• scientific article; zbMATH DE number 4043263
• Time-message trade-offs in distributed algorithms

Cited in

(20)

• scientific article; zbMATH DE number 7561283 (Why is no real title available?)
• The complexity landscape of distributed locally checkable problems on trees
• Completing the node-averaged complexity landscape of LCLs on trees
• Brief announcement: Local advice and local decompression
• Constant space and non-constant time in distributed computing
• Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics
• Classification of distributed binary labeling problems
• Fast deterministic algorithms for highly-dynamic networks
• Almost global problems in the LOCAL model
• Distributed graph problems through an automata-theoretic Lens
• Exponential speedup over locality in \textsf{MPC} with optimal memory
• scientific article; zbMATH DE number 4043263 (Why is no real title available?)
• Local-on-average distributed tasks
• Distributed graph problems through an automata-theoretic lens
• The distributed complexity of locally checkable labeling problems beyond paths and trees
• A time hierarchy theorem for the LOCAL model
• LCL problems on grids
• Almost global problems in the LOCAL model
• Local mending
• Efficient distributed algorithms by using the archimedean time assumption

This page was built for publication: New classes of distributed time complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230383)