Brief Announcement: Distributed Graph Problems Through an Automata-Theoretic Lens

Abstract

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 Π.