Local Problems in Trees Across a Wide Range of Distributed Models

We will define all relevant models formally in Section 3, but for now the following brief definitions suffice:

• $\mathrm{■}$

  In the deterministic LOCAL model, an algorithm $A$ with locality $T$ works as follows: The adversary chooses a graph $G$ and an assignment of polynomially-sized unique identifiers. Algorithm $A$ is applied to all nodes simultaneously in parallel. When we apply $A$ to node $v$, algorithm $A$ gets to see the radius-$T$ neighborhood of $v$ and, using this information, it has to choose the output label of node $v$.

• $\mathrm{■}$

  In the randomized online-LOCAL model, an algorithm $A$ with locality $T$ works as follows: The adversary chooses a graph $G$ and a processing order $\sigma$. Then the adversary presents nodes sequentially following the order $\sigma$. Whenever a node $v$ is presented, algorithm $A$ gets to see the radius-$T$ neighborhood of $v$ and, using this information as well as all information it has seen previously and a global source of random bits, it has to choose the output label of node $v$.

This means that randomized online-LOCAL is stronger than deterministic LOCAL in at least three different ways: (1) we have access to shared randomness, (2) the sequential processing order can be used to break symmetry, and (3) there is global memory thanks to which we can remember everything we have seen so far. A reader familiar with the CONGEST model can interpret it as randomized CONGEST augmented with global memory. Note that the adversary is oblivious; it cannot adapt $G$ and $\sigma$ based on the actions of $A$.

In general, online-LOCAL (with or without randomness) is much stronger than the classical LOCAL model (with or without randomness). For example, leader election is trivial in online-LOCAL, even with locality $T=0$ (the first node that the adversary presents is marked as the leader). However, what is much more interesting is whether online-LOCAL has advantage over LOCAL for problems defined using local constraints, such as graph coloring.

We will study here locally checkable labeling problems (LCLs) [21]; these are problems that can be specified by giving a finite set of valid local neighborhoods. By prior work, we know a number of LCL problems that can separate the models in Figure 1, for example:

• $\mathrm{■}$

  Sinkless orientation has locality $\mathrm{\Theta }(\log n)$ in deterministic LOCAL, locality $\mathrm{\Theta }(\log \log n)$ in randomized LOCAL, and locality $\mathrm{\Theta }(\log \log \log n)$ in randomized CONGEST [8, 10, 16, 14, 7].

• $\mathrm{■}$

  One can construct an (artificial) LCL problem that shows that having access to shared randomness helps exponentially in comparison with private randomness, and this also gives a separation between e.g. randomized LOCAL and randomized online-LOCAL [6].

• $\mathrm{■}$

  In 2-dimensional grids, 3-coloring has polynomial locality in e.g. randomized CONGEST and non-signaling models, while it can be solved with logarithmic locality in deterministic online-LOCAL [2, 12].

• $\mathrm{■}$

  In paths, 3-coloring requires $\mathrm{\Theta }({\log }^{\ast }n)$ locality in randomized LOCAL [19, 20], while it can be solved with $O(1)$ locality in the bounded-dependence model [18].

However, we do not have any such separations in rooted trees outside the $O({\log }^{\ast }n)$ region. Moreover, in general unrooted trees, all separations are in the sub-logarithmic region. In this work we give a justification for this phenomenon.

We study in this work LCL problems in the following three main settings, all familiar from prior work:

1. 1.

   LCL problems in trees in general,

2. 2.

   LCL problems in unrooted regular trees (there are no inputs and we only care about nodes with exactly $d$ neighbors),

3. 3.

   LCL problems in rooted regular trees (there are no inputs, edges are oriented, and we only care about nodes with exactly $1$ successor and $d$ predecessors).

In all these settings, it is known that the locality of any LCL problem in deterministic LOCAL falls in one of the following classes: $O(1)$, $\mathrm{\Theta }({\log }^{\ast }n)$, $\mathrm{\Theta }(\log n)$, or $\mathrm{\Theta }(n^{1/k})$ for some $k=1,2,3,\mathrm{\dots }$ [17, 11, 9, 4, 3]. Furthermore, in the case of rooted regular trees, we can (relatively efficiently) also decide which of these classes any given LCL problem belongs to [3].

Our main contribution is showing that, in many of these complexity classes, deterministic LOCAL and randomized online-LOCAL are asymptotically equally strong:

1. 1.

   In general trees, the localities in randomized online-LOCAL and deterministic LOCAL are asymptotically equal in the region $\omega (\sqrt{n})$.

2. 2.

   In unrooted regular trees, the localities in randomized online-LOCAL and deterministic LOCAL are asymptotically equal in the region $\omega (\log n)$.

3. 3.

   In rooted regular trees, the localities in randomized online-LOCAL and deterministic LOCAL are asymptotically equal in the region $\omega ({\log }^{\ast }n)$.

By prior work, the relation between deterministic LOCAL and randomized online-LOCAL was well-understood in the $o(\log \log \log n)$ region for rooted (not necessarily regular) trees [1]; see Figure 3 for the state of the art before this work. Putting together prior results and new results, the landscape shown in Figure 2 emerges.

We give an overview of key ideas in Section 2. We formally define LCL problems and the models of computing in Section 3, and then we are ready to analyze the sub-logarithmic region in rooted regular trees in Section 4. For the remaining results, please refer to the full version of the paper [13].

First, we have prior work that is based on the idea of classification of LCLs, see e.g. [3]. The high-level strategy is as follows:

1. 1.

   Define some property $P$ so that, for any given LCL $\mathrm{\Pi }$, we can decide whether $\mathrm{\Pi }$ has property $P$.

2. 2.

   Show that, if $\mathrm{\Pi }$ can be solved with locality $o(n)$ in deterministic LOCAL, then this implies that $\mathrm{\Pi }$ must have property $P$.

3. 3.

   Show that any problem with property $P$ can be solved with locality $O(\sqrt{n})$ in deterministic LOCAL.

Such a strategy not only shows that there is a gap in the complexity landscape, but it also usually gives an efficient strategy for determining what is the complexity of a given LCL (as we will need to check some set of properties $P_1,P_2,\mathrm{\dots }$ and see which of them holds for a given $\mathrm{\Pi }$ in order to determine where we are in the complexity landscape). For such results our key idea is to modify the second step as follows:

1. 2’.

   Show that, if $\mathrm{\Pi }$ can be solved with locality $o(n)$ in randomized online-LOCAL, then this implies that $\mathrm{\Pi }$ must have property $P$.

Note that we do not need to change the third step; as soon as we establish property $P$, the pre-existing deterministic LOCAL algorithm kicks in. This is, in essence, what we do in the technical section: we take the prior classification from [3] for rooted regular trees in the sub-logarithmic region and show that it can be extended to cover the entire range of models all the way from deterministic LOCAL to randomized online-LOCAL.

Second, we have also prior work based on speedup simulation arguments, see e.g. [5]. The high-level strategy there is as follows:

Assume we are given some algorithm $𝒜$ that solves $\mathrm{\Pi }$ with locality $o(n)$ in deterministic LOCAL. Then we can construct a new algorithm ${𝒜}^{\prime }$ that uses $𝒜$ as a black box to solve $\mathrm{\Pi }$ with locality $O(\sqrt{n})$ in deterministic LOCAL.

Unlike classification-style arguments, this does not (directly) yield an algorithm for determining the complexity of a given LCL problem. In essence, this can be seen as a black-box simulation of $𝒜$. For speedup-style arguments, the key idea for us to proceed is as follows:

Assume we are given some algorithm $𝒜$ that solves $\mathrm{\Pi }$ with locality $o(n)$ in randomized online-LOCAL. Then we can construct a new algorithm ${𝒜}^{\prime }$ that uses $𝒜$ as a black box to solve $\mathrm{\Pi }$ with locality $O(\sqrt{n})$. Moreover, we can simulate ${𝒜}^{\prime }$ efficiently in the deterministic LOCAL model.

Here a key challenge is that we need to explicitly change models; while in general deterministic LOCAL is not strong enough to simulate randomized online-LOCAL, we show that in this case such a simulation is possible. Starting with the argument from [5], we show that sublinear-locality randomized online-LOCAL algorithms not only admit speedup inside randomized online-LOCAL, but also a simulation in deterministic LOCAL. Formally, we prove the following in the full version of this paper [13]:

In this section we define locally checkable labeling (LCL) problems. We first recall the most general definition due to Naor and Stockmeyer [21]:

We use this definition to refer to problems in the case of general, that is, not necessarily regular trees. For regular trees, we use two other formalisms, one for the case of rooted and one for that of unrooted trees. These are simpler to work with and require checking only labels in the immediate vicinity of a node or half-edge. We note there is precedent in the literature for taking this approach (see, e.g., [3]).

Under this formalism, leaves may be labeled arbitrarily. When $\mathrm{\Pi }$ is clear from the context, we refer to the elements of $((\begin{array}{c}\mathrm{\Sigma }\\ \mathrm{\Delta }\end{array}))$ as node configurations.

Meanwhile, in the case of unrooted trees, we work with LCL problems where the labels are placed on half-edges (instead of nodes) and are subject to node and edge constraints.

As in the preceding definition, leaves are unconstrained and may be labeled arbitrarily. As before, if such an LCL problem $\mathrm{\Pi }$ on regular unrooted trees is clear from the context, we refer to the elements of $((\begin{array}{c}\mathrm{\Sigma }\\ \mathrm{\Delta }\end{array}))$ as node configurations and to those of $((\begin{array}{c}\mathrm{\Sigma }\\ 2\end{array}))$ as edge configurations.

Next we formally define the LOCAL model and its extensions.

Let $d$ be a depth parameter that we fix later, and let $\mathrm{\Delta }$ be the number of children of internal nodes. We now construct the input instance as follows:

Note that trees constructed in this way have $n=(|\mathrm{\Sigma }|+1)\cdot {\mathrm{\Delta }}^{d+1}\cdot \frac{{\mathrm{\Delta }}^{2d+1}-1}{\mathrm{\Delta }-1}$ nodes. Moreover, choosing $(b,u,C)$ uniquely fixes the construction. Let $𝒫$ be the set of choices for $(b,u,C)$.

We can now fix depth parameter $d$ such that $d>{\log }_{\mathrm{\Delta }}(2|\mathrm{\Sigma }|)$ and $d>T(n)$. Recall that $T(n)=o(\log n)$, and hence such $d$ exists.

Throughout this discussion, we let ${\mathrm{Pr}}_R(\cdot )$ denote the probability of an event when the randomness is over some source $R$ for which the probability is being defined.

For each instance $(b,u,C)$, we fix the order middle nodes $M$ such that it is consistent across all instances. We then reveal these middle nodes to $𝒜$ in this order. Let $S\in \overline{\mathrm{\Sigma }}={\mathrm{\Sigma }}^{{\mathrm{\Delta }}^{2d+1}(|\mathrm{\Sigma }|+1)}$ be the random sequence of labels generated by $𝒜$ for the middle nodes $M$. Since the locality of $𝒜$ is , the algorithm does not get to see the roots or the leaves of these height-$2d$ trees. In particular, the algorithm does not get to know which instance $(b,u,C)$ we have chosen. Hence $S$ must be independent of the choice of $(b,u,C)$.

Note that while the output $S$ for nodes $M$ is independent of $(b,u,C)$, the output that $𝒜$ produces for the rest of the nodes of the input may be dependent of $(b,u,C)$. We denote this random variable by ${𝒜}^{+}(b,u,C)$.

We now analyze the failure probability of $𝒜$ to show that there exists a fixed labeling $\overline{\sigma \ast }$ for middle nodes $M$ such that the labeling is still completable for each input instance $(b,u,C)$. Let $ℱ$ denote the event that algorithm $𝒜$ fails to solve the problem. By assumption, $𝒜$ succeeds with high probability; hence ${\mathrm{Pr}}_{S,{𝒜}^{+}(b,u,C)}(ℱ)\le \frac{1}{n}$ for all choices of $(b,u,C)\in 𝒫$. We can now pick a labeling of the middle nodes that minimizes the average failure probability:

This definition ensures the following: Give that the algorithm labels nodes $M$ with $\overline{\sigma \ast }$, the total probability of failure over all instances $(b,u,C)$ is minimized. In some sense, $\overline{\sigma \ast }$ is the best labeling for $M$ when the algorithm know nothing about the instance. Note that $\overline{\sigma \ast }$ is a concrete element of $\overline{\mathrm{\Sigma }}$ and hence does not depend on the randomness of the algorithm. We can formalize this idea:

We are now ready to extract from algorithm $𝒜$ a coprime certificate for $O({\log }^{\ast }n)$ solvability. The idea is to pick a subset of input instances $𝒫$ that – along with the labeling $\overline{\sigma \ast }$ – form the pairs of sequences of trees of the certificate. We defer the proof of why this implies the existence of a locality-$O({\log }^{\ast }n)$ LOCAL algorithm to previous work [4].

Let ${\mathrm{\Sigma }}_{𝒯}=\{{\sigma }_1,{\sigma }_2,\mathrm{\dots },{\sigma }_t\}\subseteq \mathrm{\Sigma }$ be the set of labels appearing in $\overline{\sigma \ast }$, and let $(u_1,u_2,\mathrm{\dots },u_t)$ be some middle nodes in the input instances such that node $u_i$ has label ${\sigma }_i$ according to $\overline{\sigma \ast }$. Note that there are $|\mathrm{\Sigma }|+1$ chunks whereas . Therefore, we get the following result by the pigeonhole principle:

With these definitions of labels ${\mathrm{\Sigma }}_{𝒯}=({\sigma }_1,\mathrm{\dots },{\sigma }_t)$, chunk $C_0$, and nodes $(u_1,\mathrm{\dots },u_t)$, we are ready to prove our main result: