Distributed graph problems through an automata-theoretic lens.

We study the following algorithm synthesis question: given the description of a locally checkable graph problem $\Pi$ for paths or cycles, determine in which instances $\Pi$ is solvable, determine what is the distributed round complexity of solving $\Pi$ in the usual $\mathsf{LOCAL}$ model of distributed computing, and construct an asymptotically optimal distributed algorithm for solving $\Pi$. To answer such questions, we represent $\Pi$ as a nondeterministic finite automaton $\mathcal{M}$ over a unary alphabet. We classify the states of $\mathcal{M}$ 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 $\Pi$ 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 $\Pi$ is always solvable is co-$\mathsf{NP}$-complete. However, we show that all other questions, including the question of determining the distributed round complexity of $\Pi$ and finding an asymptotically optimal algorithm for solving $\Pi$, can be answered in polynomial time.