Distributed graph problems through an automata-theoretic lens
share
We study the following algorithm synthesis question: given the description of a locally checkable graph problem Π for paths or cycles, determine in which instances Π is solvable, determine what is the distributed round complexity of solving Π in the usual 𝖫𝖮𝖢𝖠𝖫 model of distributed computing, and construct an asymptotically optimal distributed algorithm for solving Π. To answer such questions, we represent Π as a nondeterministic finite automaton ℳ over a unary alphabet. We classify the states of ℳ into repeatable states, flexible states, mirror-flexible states, loops, and mirror-flexible loops; all of these can be decided in polynomial time. We show that these five classes of states completely answer all questions related to the solvability and distributed computational complexity of Π on cycles. On paths, there is one case in which the question of solvability coincides with the classical universality problem for unary regular languages, and hence determining if a given problem Π is always solvable is co-𝖭𝖯-complete. However, we show that all other questions, including the question of determining the distributed round complexity of Π and finding an asymptotically optimal algorithm for solving Π, can be answered in polynomial time.
READ FULL TEXT