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 proceedingConference article in proceedingsScientificpeer-review

17 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 languageEnglish
Title of host publicationPODC 2019 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing
PublisherACM
Pages262-271
Number of pages10
ISBN (Electronic)9781450362177
DOIs
Publication statusPublished - 16 Jul 2019
MoE publication typeA4 Conference publication
EventACM Symposium on Principles of Distributed Computing - Toronto, Canada
Duration: 29 Jul 20192 Aug 2019
Conference number: 38

Conference

ConferenceACM Symposium on Principles of Distributed Computing
Abbreviated titlePODC
Country/TerritoryCanada
CityToronto
Period29/07/201902/08/2019

Keywords

  • Complexity
  • Decidability
  • Distributed computing

Fingerprint

Dive into the research topics of 'The distributed complexity of locally checkable problems on paths is decidable'. Together they form a unique fingerprint.

Cite this