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

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

5 Downloads (Pure)

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 Π.
Original languageEnglish
Title of host publication34th International Symposium on Distributed Computing
PublisherSchloss Dagstuhl-Leibniz-Zentrum fuer Informatik
Number of pages3
Volume179
ISBN (Electronic)978-3-95977-168-9
DOIs
Publication statusPublished - 7 Oct 2020
MoE publication typeA4 Article in a conference publication
EventInternational Symposium on Distributed Computing - Virtual, Online, Germany
Duration: 12 Oct 202016 Oct 2020
Conference number: 32
http://www.disc-conference.org/wp/disc2020/

Conference

ConferenceInternational Symposium on Distributed Computing
Abbreviated titleDISC
CountryGermany
CityVirtual, Online
Period12/10/202016/10/2020
Internet address

Keywords

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

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

Cite this