How local constraints influence network diameter and applications to LCL generalizations

Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron.

OPODIS 2024

doi:

Links

ArXiv version

Abstract

In this paper, we investigate how local rules enforced at every node can influence the topology of a network. More precisely, we establish several results on the diameter of trees as a function of the number of nodes, as listed below. These results have important consequences on the landscape of locally checkable labelings (LCL) on unbounded degree graphs, a case in which our lack of knowledge is in striking contrast with that of bounded degree graphs, that has been intensively studied recently.

First, we show that the diameter of a tree can be controlled very precisely by a local checker (that is, a distributed decision algorithm that accepts a graph iff all nodes accept locally), granted that its checkability radius is allowed to be at least $2$ (and that the target diameter is not too close to $n$). As a corollary, we prove that the gaps in the landscape of LCLs (in bounded-degree graphs) basically disappear in unbounded degree graphs.>

Second, we prove that for checkers at distance 1, the maximum diameter can only be trivial (constant or linear), while the minimum diameter can in addition be $\Theta(\log n)$ and $\Theta(n^{1/k})$ for $k\in \mathbb{N}$. These functions interestingly coincide with the known regimes for LCLs.

Third, we explore computational restrictions of local checkers. In particular, we introduce a class of checkers, that we call degree-myopic, that cannot distinguish perfectly the degrees of their neighbors. With these checkers, we show that the maximum diameter can only be $O(1)$, $\Theta(\sqrt{n})$, $\Theta(\log{n}/\log \log n)$, $\Theta(\log{n})$, or $\Omega(n)$. Since gaps do appear in the maximum diameter, one can hope that an interesting LCL landscape exists for restricted local checkers.

In addition to the LCL motivation, we hope that our distributed lenses can help give a new point of view on how global structures, such as living beings, can be maintained by local phenomena; understanding the trade-off between the power of the checking and the possible resulting shapes.

Notes