The distributed complexity of locally checkable problems on paths is decidable

Alkida Balliu, Sebastian Brandt, Yi Jun Chang, Dennis Olivetti, Mikaël Rabie, Jukka Suomela

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientificvertaisarvioitu

17 Sitaatiot (Scopus)

Abstrakti

Consider a computer network that consists of a path with n nodes. The nodes are labeled with inputs from a constant-sized set, and the task is to find output labels from a constant-sized set subject to some local constraints - -more formally, we have an LCL (locally checkable labeling) problem. How many communication rounds are needed (in the standard LOCAL model of computing) to solve this problem? It is well known that the answer is always either O(1) rounds, or (log n) rounds, or (n) rounds. In this work we show that this question is decidable (albeit PSPACE-hard): we present an algorithm that, given any LCL problem defined on a path, outputs the distributed computational complexity of this problem and the corresponding asymptotically optimal algorithm.

AlkuperäiskieliEnglanti
OtsikkoPODC 2019 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing
KustantajaACM
Sivut262-271
Sivumäärä10
ISBN (elektroninen)9781450362177
DOI - pysyväislinkit
TilaJulkaistu - 16 heinäk. 2019
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaACM Symposium on Principles of Distributed Computing - Toronto, Kanada
Kesto: 29 heinäk. 20192 elok. 2019
Konferenssinumero: 38

Conference

ConferenceACM Symposium on Principles of Distributed Computing
LyhennettäPODC
Maa/AlueKanada
KaupunkiToronto
Ajanjakso29/07/201902/08/2019

Sormenjälki

Sukella tutkimusaiheisiin 'The distributed complexity of locally checkable problems on paths is decidable'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä