Leader Election via Unique Sink Orientation
For distributed computing researchers, it extends the class of graphs where leader election can be locally checked, and offers a general method to convert LCLs into self-stabilizing algorithms.
The paper proves that leader election can be expressed as a Locally Checkable Labeling (LCL) on dismantlable graphs using O(Δ) bits per node, and provides a generic transformation from LCLs to silent self-stabilizing algorithms. This is the first local labeling result for dismantlable graphs.
A Locally Checkable Labeling (LCL) is a distributed constraint satisfaction problem defined on a bounded-degree graph that relates a finite set of input labels to a finite set of output labels through a finite set of locally checkable constraints. In this work we define labels and local constraints that encode solutions to two classical problems: leader election and spanning tree construction. It is known that leader election cannot be expressed as an LCL in arbitrary graphs using constant-size labels. In fact, it is known that there does not exist a finite set of labels and local constraints for leader election even for the class of rings. On the other hand, there exists a finite set of labels and local constraints characterizing leader election on trees. In this work, we prove that there exists a finite set of labels and local constraints for leader election also in the much larger class of dismantlable graphs. Our labels need one bit per edge or equivalently $O(Δ)$ bits per node (where $Δ$ is the maximum degree in the graph) and are checkable within the graph induced by the 1-neighborhood of each node. To the best of our knowledge, these are the first local labeling results tailored to dismantlable graphs, potentially highlighting structural properties useful for designing labels and constraints for additional LCL problems. Finally, we present a generic transformation that converts any finite set of labels and local constraints into a silent self-stabilizing algorithm by adding only one extra state, assuming a Gouda fair scheduler. This transformation may be of independent interest.