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 ? over a unary alphabet, and identify polynomial-time-computable properties of automaton ? that capture the locality and solvability of problem ?