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

Yi-Jun Chang; Jan Studený; Jukka Suomela

doi:10.4230/LIPIcs.DISC.2020.41

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

Yi-Jun Chang, Jan Studený, Jukka Suomela

ETH Zurich

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference contribution › Scientific › vertaisarvioitu

19 Lataukset (Pure)

Abstrakti

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

Alkuperäiskieli	Englanti
Otsikko	34th International Symposium on Distributed Computing
Kustantaja	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Sivumäärä	3
Vuosikerta	179
ISBN (elektroninen)	978-3-95977-168-9
DOI - pysyväislinkit	https://doi.org/10.4230/LIPIcs.DISC.2020.41
Tila	Julkaistu - 7 lokak. 2020
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisuussa
Tapahtuma	International Symposium on Distributed Computing - Virtual, Online, Saksa Kesto: 12 lokak. 2020 → 16 lokak. 2020 Konferenssinumero: 32 http://www.disc-conference.org/wp/disc2020/

Conference

Conference	International Symposium on Distributed Computing
Lyhennettä	DISC
Maa/Alue	Saksa
Kaupunki	Virtual, Online
Ajanjakso	12/10/2020 → 16/10/2020
www-osoite	http://www.disc-conference.org/wp/disc2020/

Pääsy asiakirjaan

10.4230/LIPIcs.DISC.2020.41Lisenssi: CC BY

Chang_Brief.LIPIcs-DISC-2020-41Final published version, 357 KBLisenssi: CC BY

OpenUrl-saatavuus

Koko teksti

Siteeraa tätä

@inproceedings{174c3bc222b344e2a866b8805e4a38a1,

title = "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 Π.",

keywords = "algorithm synthesis, locally checkable labeling problems, LOCAL model, locality, distributed computational complexity, nondeterministic finite automata",

author = "Yi-Jun Chang and Jan Studen{\'y} and Jukka Suomela",

year = "2020",

month = oct,

day = "7",

doi = "10.4230/LIPIcs.DISC.2020.41",

language = "English",

volume = "179",

booktitle = "34th International Symposium on Distributed Computing",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

address = "Germany",

note = "International Symposium on Distributed Computing, DISC ; Conference date: 12-10-2020 Through 16-10-2020",

url = "http://www.disc-conference.org/wp/disc2020/",

}

Chang, Y-J, Studený, J & Suomela, J 2020, Brief Announcement: Distributed Graph Problems Through an Automata-Theoretic Lens. julkaisussa 34th International Symposium on Distributed Computing. Vuosikerta 179, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, International Symposium on Distributed Computing, Virtual, Online, Saksa, 12/10/2020. https://doi.org/10.4230/LIPIcs.DISC.2020.41

Brief Announcement: Distributed Graph Problems Through an Automata-Theoretic Lens. / Chang, Yi-Jun; Studený, Jan ; Suomela, Jukka.
34th International Symposium on Distributed Computing. Vuosikerta 179 Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference contribution › Scientific › vertaisarvioitu

TY - GEN

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

AU - Chang, Yi-Jun

AU - Studený, Jan

AU - Suomela, Jukka

N1 - Conference code: 32

PY - 2020/10/7

Y1 - 2020/10/7

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

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

KW - algorithm synthesis

KW - locally checkable labeling problems

KW - LOCAL model

KW - locality

KW - distributed computational complexity

KW - nondeterministic finite automata

U2 - 10.4230/LIPIcs.DISC.2020.41

DO - 10.4230/LIPIcs.DISC.2020.41

M3 - Conference contribution

VL - 179

BT - 34th International Symposium on Distributed Computing

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - International Symposium on Distributed Computing

Y2 - 12 October 2020 through 16 October 2020

ER -

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

Abstrakti

Conference

Pääsy asiakirjaan

OpenUrl-saatavuus

Sormenjälki

Siteeraa tätä