Jérémie Chalopin, Maria Kokkou
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.