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 · 2019
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?