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

The distributed complexity of locally checkable problems on paths is decidable

PODC 2019 · 38th ACM Symposium on Principles of Distributed Computing, Toronto, Canada, July–August 2019 · doi:10.1145/3293611.3331606

authors’ version publisher’s version


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 $\Theta(\log^* n)$ rounds, or $\Theta(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.


Peter Robinson and Faith Ellen (Eds.): Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 262–271, ACM Press, New York, 2019

ISBN 978-1-4503-6217-7

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.