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

doi:10.1145/3293611.3331606

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

14 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	PODC 2019 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing
Publisher	ACM
Pages	262-271
Number of pages	10
ISBN (Electronic)	9781450362177
DOIs	https://doi.org/10.1145/3293611.3331606
Publication status	Published - 16 Jul 2019
MoE publication type	A4 Article in a conference publication
Event	ACM Symposium on Principles of Distributed Computing - Toronto, Canada Duration: 29 Jul 2019 → 2 Aug 2019 Conference number: 38

Conference

Conference	ACM Symposium on Principles of Distributed Computing
Abbreviated title	PODC
Country/Territory	Canada
City	Toronto
Period	29/07/2019 → 02/08/2019

Keywords

Complexity
Decidability
Distributed computing

Access to Document

10.1145/3293611.3331606

https://arxiv.org/abs/1811.01672

OpenUrl availability

Full text

Cite this

@inproceedings{d7110633eb6247d08865f4e269f30fce,

title = "The distributed complexity of locally checkable problems on paths is decidable",

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

keywords = "Complexity, Decidability, Distributed computing",

author = "Alkida Balliu and Sebastian Brandt and Chang, {Yi Jun} and Dennis Olivetti and Mika{\"e}l Rabie and Jukka Suomela",

year = "2019",

month = jul,

day = "16",

doi = "10.1145/3293611.3331606",

language = "English",

pages = "262--271",

booktitle = "PODC 2019 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing",

publisher = "ACM",

address = "United States",

note = "ACM Symposium on Principles of Distributed Computing, PODC ; Conference date: 29-07-2019 Through 02-08-2019",

}

Balliu, A, Brandt, S, Chang, YJ, Olivetti, D, Rabie, M & Suomela, J 2019, The distributed complexity of locally checkable problems on paths is decidable. in PODC 2019 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. ACM, pp. 262-271, ACM Symposium on Principles of Distributed Computing, Toronto, Ontario, Canada, 29/07/2019. https://doi.org/10.1145/3293611.3331606

The distributed complexity of locally checkable problems on paths is decidable. / Balliu, Alkida; Brandt, Sebastian; Chang, Yi Jun et al.

PODC 2019 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. ACM, 2019. p. 262-271.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

TY - GEN

T1 - The distributed complexity of locally checkable problems on paths is decidable

AU - Balliu, Alkida

AU - Brandt, Sebastian

AU - Chang, Yi Jun

AU - Olivetti, Dennis

AU - Rabie, Mikaël

AU - Suomela, Jukka

N1 - Conference code: 38

PY - 2019/7/16

Y1 - 2019/7/16

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

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

KW - Complexity

KW - Decidability

KW - Distributed computing

UR - http://www.scopus.com/inward/record.url?scp=85070965603&partnerID=8YFLogxK

U2 - 10.1145/3293611.3331606

DO - 10.1145/3293611.3331606

M3 - Conference contribution

AN - SCOPUS:85070965603

SP - 262

EP - 271

BT - PODC 2019 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing

PB - ACM

T2 - ACM Symposium on Principles of Distributed Computing

Y2 - 29 July 2019 through 2 August 2019

ER -

The distributed complexity of locally checkable problems on paths is decidable

Abstract

Conference

Keywords

Access to Document

OpenUrl availability

Other files and links

Fingerprint

Cite this