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 | |
Publication status | Published - 16 Jul 2019 |
MoE publication type | A4 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