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 language | English |
|---|---|
| Title of host publication | 34th International Symposium on Distributed Computing |
| Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| Number of pages | 3 |
| Volume | 179 |
| ISBN (Electronic) | 978-3-95977-168-9 |
| DOIs | |
| Publication status | Published - 7 Oct 2020 |
| MoE publication type | A4 Conference publication |
| Event | International Symposium on Distributed Computing - Virtual, Online, Germany Duration: 12 Oct 2020 → 16 Oct 2020 Conference number: 32 http://www.disc-conference.org/wp/disc2020/ |
Conference
| Conference | International Symposium on Distributed Computing |
|---|---|
| Abbreviated title | DISC |
| Country/Territory | Germany |
| City | Virtual, Online |
| Period | 12/10/2020 → 16/10/2020 |
| Internet address |
Keywords
- algorithm synthesis
- locally checkable labeling problems
- LOCAL model
- locality
- distributed computational complexity
- nondeterministic finite automata