LIPIcs.DISC.2020.41.pdf
- Filesize: 357 kB
- 3 pages
Document
Brief Announcement: Distributed Graph Problems Through an Automata-Theoretic Lens
Authors
Yi-Jun Chang 
,
Jan Studený ,
Jukka Suomela
-
Part of:
Volume:
34th International Symposium on Distributed Computing (DISC 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Distributed Computing (DISC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-10-07
File
Document Identifiers
Author Details
Cite As Get BibTex
Yi-Jun Chang, Jan Studený, and Jukka Suomela. Brief Announcement: Distributed Graph Problems Through an Automata-Theoretic Lens. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 41:1-41:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.DISC.2020.41
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 Π.
Subject Classification
ACM Subject Classification
- Theory of computation → Formal languages and automata theory
- Theory of computation → Models of computation
- Theory of computation → Distributed algorithms
Keywords
- Algorithm synthesis
- locally checkable labeling problems
- LOCAL model
- locality
- distributed computational complexity
- nondeterministic finite automata
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela. The Distributed Complexity of Locally Checkable Problems on Paths is Decidable. In Proc. PODC, 2019. URL: https://doi.org/10.1145/3293611.3331606.
-
Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, and Jukka Suomela. Classification of distributed binary labeling problems. In Proc. DISC, 2020.
- Sebastian Brandt, Juho Hirvonen, Janne H Korhonen, Tuomo Lempiäinen, Patric R J Östergård, Christopher Purcell, Joel Rybicki, Jukka Suomela, and Przemysław Uznański. LCL problems on grids. In Proc. PODC, 2017. URL: https://doi.org/10.1145/3087801.3087833.
- Moni Naor and Larry Stockmeyer. What Can be Computed Locally? SIAM Journal on Computing, 24(6):1259-1277, 1995. URL: https://doi.org/10.1137/S0097539793254571.