Brief announcement: Distributed graph problems through an automata-theoretic lens

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 locality of Π, and construct an asymptotically optimal distributed algorithm for solving Π (in the usual LOCAL model of distributed computing). To answer such questions, we represent Π as a nondeterministic finite automaton M over a unary alphabet, and identify polynomial-time-computable properties of automaton M that capture the locality and solvability of problem Π.ISSN:1868-896