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

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

19 Downloads (Pure)


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 Π.
Original languageEnglish
Title of host publication34th International Symposium on Distributed Computing
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages3
ISBN (Electronic)978-3-95977-168-9
Publication statusPublished - 7 Oct 2020
MoE publication typeA4 Conference publication
EventInternational Symposium on Distributed Computing - Virtual, Online, Germany
Duration: 12 Oct 202016 Oct 2020
Conference number: 32


ConferenceInternational Symposium on Distributed Computing
Abbreviated titleDISC
CityVirtual, Online
Internet address


  • algorithm synthesis
  • locally checkable labeling problems
  • LOCAL model
  • locality
  • distributed computational complexity
  • nondeterministic finite automata


Dive into the research topics of 'Brief Announcement: Distributed Graph Problems Through an Automata-Theoretic Lens'. Together they form a unique fingerprint.

Cite this