Distributed Computation with Local Advice

We will work in the usual LOCAL model of distributed computing. In an $n$-node graph, the nodes are labeled with unique identifiers from $\{1,2,\mathrm{\dots },\mathrm{poly}(n)\}$. We emphasize that the advice may depend on the assignment of identifiers, and algorithm $𝒜$ can freely make use of both the advice and the identifiers.

Our work shows that for many problems the key threshold is not whether we can achieve $1$ bit of advice per node, but whether we can make the advice arbitrarily sparse, that is, make the ratio between $1$s and $0$s assigned to the nodes of the graph to be an arbitrarily small constant. This is particularly useful, as it enables us to compose multiple sparse advice schemes, so that it suffices to use just one bit per node in total (we will elaborate on this in Section 1.7). Hence, a large part of this paper addresses the following question:

The notion of the sparsity of the advice is discussed in more detail later in the paper. In this context, our paper shows that some problems can be solved with arbitrarily sparse advice. On the other hand, we also show that assuming the Exponential-Time Hypothesis, for any constant $c$, there exist problems that cannot be solved with $c$ bits of advice. Finally, there are some problems like 3-coloring that can be solved with 1 bit of advice, but where it is not clear whether it can be solved with arbitrarily sparse advice. We discuss all of those points in more detail in the remaining part of this section; we refer to the full version of this work for the omitted proofs.

Locally checkable labeling problems (LCL), first introduced by Naor and Stockmeyer [50] in the 1990s, are one of the most extensively studied families of problems in the theory of distributed graph algorithms. These are graph problems that can be specified by giving a finite set of valid local neighborhoods. Many key problems such as vertex coloring, edge coloring, maximal independent set, maximal matching, sinkless orientation, and many other splitting and orientation problems are examples of LCLs, at least when restricted to bounded-degree graphs. Thanks to the extensive research effort since 2016, we now understand very well the landscape of all LCL problems and their computational complexities across different models of distributed computing [5, 3, 11, 28, 2, 19, 54, 9, 10, 30, 4].

At this point a natural question is whether the assumption about bounded growth is necessary. Could we solve all LCL problems in all graphs with $1$ bit of advice? In Section 4 we show that the answer is likely to be no:

The intuition here is that if some LCL problem $\mathrm{\Pi }$ can be solved with, say, $1$ bit of advice per node with some local algorithm $𝒜$, then we could solve it with a centralized sequential algorithm as follows: check all $2^n$ possible assignments of advice, apply $𝒜$ to decode the advice, and see if the solution is feasible. The total running time (from the centralized sequential perspective) would be $2^n\cdot n\cdot s(n)$, where $s(n)$ is the time we need to simulate $𝒜$ at one node. Then we need to show that assuming the Exponential-Time Hypothesis, this is too fast for some LCL problem $\mathrm{\Pi }$. However, the key obstacle is that it may be computationally expensive to simulate $𝒜$, as it might perform arbitrarily complicated calculations that depend on the numerical values of the unique identifiers, and we cannot directly bound $s(n)$.

Now we move on to a specific graph problem: we study the task of finding balanced and almost-balanced orientations. The goal is to orient the edges so that for each node indegree and outdegree differ by at most $1$. This is a hard problem to solve in a distributed setting, while slightly more relaxed versions of the problem admit efficient (but not constant-time) algorithms [29].

Our schema for encoding $\mathrm{\Delta }$-colorings consists of three steps. First, we compute a vertex coloring with $O({\mathrm{\Delta }}^2)$ colors, with the help of advice. Then we reduce the number of colors down to $\mathrm{\Delta }+1$, using the algorithm by [21, 6, 45]. Finally, we follow the key idea of the algorithm by Panconesi and Srinivasan [52] to turn $(\mathrm{\Delta }+1)$-coloring into a $\mathrm{\Delta }$-coloring, and again we will need some advice to make this part efficient.

So far we have seen primarily results of two flavors: many problems can be solved with $1$ bit of advice so that we can make the advice arbitrarily sparse, while there are also some problems that require arbitrarily many bits of advice.

We now turn our attention to a problem that seems to lie right at the boundary of what can be done with only $1$ bit per node: vertex $3$-coloring in any $3$-colorable graph. Note that this is a problem that is hard to solve without advice not only in the distributed setting (it is a global problem) but also in the centralized setting (it is an NP-hard problem).

In the centralized setting, $1$ bit of advice per node makes the problem easy. To see this, we can simply use the bit to indicate which nodes are of color $3$. Then the rest of the graph has to be bipartite, and we can simply find a proper $2$-coloring in polynomial time.

In the distributed setting, the trivial solution does not work: $2$-coloring in bipartite graphs is still a global problem. Nevertheless, we show that $3$-coloring is still doable with $1$ bit of advice:

Our encoding essentially uses one bit to encode one of the color classes, but we adjust the encoding slightly so that throughout the graph there are local hints that help us to also choose the right parity for the region that we need to $2$-color.

Here, our encoding genuinely needs one bit per node (it just barely suffices); we cannot make our advice arbitrarily sparse.

We already discussed some of the proof ingredients above. However, there is one additional technique that we use in many of our algorithms: the framework of composable schemas.

It turns out that for many problems, it is easier to work with advice schemas in which only a few nodes carry advice bits, but they may carry many bits of advice. In Definition 2 we give the formal definition of such a schema, and in Definition 4 we give the formal definition of composable schemas, which satisfy the additional property that the ratio between the total number of bits held by the nodes, and the total number of nodes, can be made arbitrarily small in every large-enough neighborhood.

While the definition is a bit technical, it has two key properties, which we discuss in more detail in the full version of this work:

1. 1.

   As the name suggests, composable schemas can be easily composed, in the following sense: once we have (1) a composable schema for solving ${\mathrm{\Pi }}_1$ and (2) a composable schema for solving ${\mathrm{\Pi }}_2$ assuming an oracle for ${\mathrm{\Pi }}_1$, we can also compose them and obtain (3) a composable schema that solves ${\mathrm{\Pi }}_2$ without the oracle. This way we can solve problems in a modular fashion, in essence using schemas as “subroutines.”

2. 2.

   A composable schema can be then encoded with only $1$ bit of advice per node, and we can make the advice arbitrarily sparse.

For example, our algorithms for finding almost-balanced orientations and $\mathrm{\Delta }$-coloring with advice are based on the framework of composable schemas.

Our work suggests a number of open questions:

1. 1.

   Our negative result in Section 4 assumes the Exponential-Time Hypothesis. Is it possible to prove an unconditional lower bound without such assumptions? Can we exhibit a concrete LCL problem $\mathrm{\Pi }$ that is unconditionally hard?

2. 2.

   We conjecture that the advice for vertex $3$-coloring in $3$-colorable graphs cannot be made arbitrarily sparse. Is this true?

3. 3.

   We also conjecture that for a sufficiently large $d$, vertex $d$-coloring in $d$-colorable graphs cannot be encoded with one bit per node. Is this true? This is closely linked with the discussion on the trade-off conjecture in e.g. [1, 7].

4. 4.

   Our schema for distributed decompression is asymptotically optimal, but there is room for improving additive constants. Here is a concrete open question: Let $G=(V,E)$ be a $3$-regular graph, and let $X\subseteq E$ be an arbitrary set of edges. Is it possible to encode $X$ using only $2$ bits per node so that it can be decompressed locally? (Note that $1$ bit per node is trivially impossible, while $3$ bits per node is trivial. If we delete one edge from each connected component, an encoding with $2$ bits per node follows from $2$-degeneracy.)

In the LOCAL model of distributed computation, each node of an $n$-node graph is equipped with a unique ID, typically in $\{1,\mathrm{\dots },n^c\}$, for some constant $c$. Initially, each node in the graph knows its own ID, its degree (i.e., the number of neighboring nodes), the maximum degree $\mathrm{\Delta }$ in the graph, and the total number of nodes. Then, the computation proceeds in synchronous rounds where at each round each node exchanges messages with its neighbors and performs some local computation. The size of the messages can be arbitrarily large and the local computation can be arbitrarily heavy. The runtime of an algorithm is defined as the number of rounds it requires such that all nodes terminate and produce an output.

We formally define an LCL problem $\mathrm{\Pi }$ as a tuple $({\mathrm{\Sigma }}_{\mathrm{in}},{\mathrm{\Sigma }}_{\mathrm{out}},C,r)$ where each element of the tuple is defined as follows. The parameters ${\mathrm{\Sigma }}_{\mathrm{in}}$ and ${\mathrm{\Sigma }}_{\mathrm{out}}$ are finite sets of input and output labels, respectively. The parameter $r$ is a positive integer called checkability radius of $\mathrm{\Pi }$, i.e., it determines how far in the graph each node needs to check in order to verify the validity of a given solution. The parameter $C$ determines the constraints of $\mathrm{\Pi }$, that is, $C$ is a finite set of labeled graphs $H$ containing a vertex of eccentricity at most $r$, where each edge-endpoint pair $(uv,v)\in E_H\times V_H$ has a label ${\mathrm{\ell }}_{\mathrm{in}}\in {\mathrm{\Sigma }}_{\mathrm{in}}$ and a label ${\mathrm{\ell }}_{\mathrm{out}}\in {\mathrm{\Sigma }}_{\mathrm{out}}$.

Let $\mathrm{\Pi }=({\mathrm{\Sigma }}_{\mathrm{in}},{\mathrm{\Sigma }}_{\mathrm{out}},C,r)$ be an LCL problem and let $G=(V,E)$ be a graph where each edge-endpoint pair $(uv,v)$ is labeled with a label from ${\mathrm{\Sigma }}_{\mathrm{in}}$. The task of solving $\mathrm{\Pi }$ on $G$ requires labeling each edge-endpoint pair $(uv,v)\in E\times V$ with a label in ${\mathrm{\Sigma }}_{\mathrm{out}}$ such that, for each node $v\in V$ it holds that the graph induced by the nodes at distance at most $r$ from $v$ and edges that have at least one endpoint at distance at most $r-1$ from $v$ is isomorphic to some (labeled) graph in $C$.

We now formally define the notion of advice schema.

Moreover, we distinguish three possible types of advice schemas:

1. 1.

   If all nodes of the graph receive bit-strings of the same length, then the schema is called uniform fixed-length.

2. 2.

   If a subset of nodes receives bit-strings of the same length, and all the others receive bit-strings of length $0$, then the schema is called subset fixed-length.

3. 3.

   If a subset of nodes receives a bit-string of possibly different positive lengths, and all the others receive bit-strings of length $0$, then the schema is called variable-length. Observe that an advice schema, as defined in Definition 2 and without further assumptions, is variable-length.

In the second and third cases, the nodes having non-zero bit-strings assigned are called bit-holding nodes. Moreover, observe that Type 1 is a special case of Type 2, which is a special case of Type 3.

For uniform fixed-length advice schemas where all nodes receive one bit, we define the notion of sparsity, which captures the fact that the ratio between nodes receiving a $1$ and nodes receiving a $0$ can be made arbitrarily small.

The main idea that we will use to devise our advice schemas is the following. Given some problem $\mathrm{\Pi }$, it may be cumbersome to directly define an advice schema for it. Instead, it may be easier to do this operation gradually. In more detail, many problems can be solved as follows: first, find a solution for some subproblem; then, use the solution for the subproblem in order to solve the problem more easily. As a running example, consider the following problem $\mathrm{\Pi }$.

• $\mathrm{■}$

  The input is a bipartite graph where all nodes have even degree.

• $\mathrm{■}$

  It is required to output a coloring of the edges, say red and blue, such that each node has the same number of red and blue incident edges.

Consider the following three problems.

• $\mathrm{■}$

  Let ${\mathrm{\Pi }}_{\mathrm{v}}$ be the problem of computing a $2$-coloring of the nodes, say, black and white.

• $\mathrm{■}$

  Let ${\mathrm{\Pi }}_{\mathrm{e}}$ be the problem of outputting a $2$-coloring of the edges, such that each node has the same number of red and blue incident edges, assuming that we are given as input a $2$-coloring of the nodes and a balanced orientation of the edges, and assuming that all nodes have even degree.

• $\mathrm{■}$

  Let ${\mathrm{\Pi }}_{\mathrm{o}}$ be the problem of orienting all edges such that each node has the same number of incoming and outgoing edges, assuming that all nodes have even degree.

Consider the following algorithm. First, solve ${\mathrm{\Pi }}_{\mathrm{v}}$ and ${\mathrm{\Pi }}_{\mathrm{o}}$. Then, solve ${\mathrm{\Pi }}_{\mathrm{e}}$, by coloring red the edges oriented from black to white, and by coloring blue the edges oriented from white to black. Observe that this algorithm solves $\mathrm{\Pi }$.

In other words, we decomposed $\mathrm{\Pi }$ into three different subproblems: two of them are “hard” problems (${\mathrm{\Pi }}_{\mathrm{v}}$ and ${\mathrm{\Pi }}_{\mathrm{o}}$), for which some advice is needed if we want to solve them fast, and one (${\mathrm{\Pi }}_{\mathrm{e}}$) is trivial once we are given as input the solution for the other two. The idea now is to devise two different advice schemas for ${\mathrm{\Pi }}_{\mathrm{v}}$ and ${\mathrm{\Pi }}_{\mathrm{o}}$ separately.

• $\mathrm{■}$

  For ${\mathrm{\Pi }}_{\mathrm{v}}$ there is a trivial advice schema: use $1$ bit to encode the $2$-coloring of the nodes.

• $\mathrm{■}$

  For ${\mathrm{\Pi }}_{\mathrm{o}}$ the advice schema is non-trivial, and we will show how it can be done by using $1$ bit per node.

While both schemas use only $1$ bit per node, we cannot directly combine these two schemas into a single schema that uses $1$ bit per node. For this reason, we will devise our schemas in a more high-level way. In particular, for most of the results of this paper, we will not directly provide a uniform fixed-length advice schema that uses one bit per node, but we will start by devising variable-length schemas. Variable-length schemas provide a simpler way to encode information: we can choose a subset of nodes and assign bit-strings to them, without worrying about how these strings will be later encoded by giving one bit to each node. Moreover, the variable-length schemas that we provide satisfy a property called composability, which we will formally define later. Intuitively, this property requires the ability to make the set of bit-holding nodes of a variable-length schema to be arbitrarily sparse. For example, for ${\mathrm{\Pi }}_{\mathrm{v}}$, we do not really need to provide the color of all nodes: we assign $1$ bit to a sparse set of nodes (encoding their color), and to all other nodes we do not assign any bit. The nodes that have no bit assigned can still recover a $2$-coloring by simple propagation. For ${\mathrm{\Pi }}_{\mathrm{o}}$, things are more complicated, but a composable variable-length schema can be obtained as well.

Once we have a composable schema for all subproblems that are used to solve our problem of interest, we apply, as a black box, a lemma to obtain a single variable-length schema for our problem. Then, again as a black box, we convert such a schema into a uniform fixed-length schema that uses a single bit per node.

Summarizing, many of the results that we provide about schemas that use a single bit per node are based on the following idea:

• $\mathrm{■}$

  We first decompose a problem of interest into many subproblems;

• $\mathrm{■}$

  We show that, for each of the subproblems, it is possible to devise a variable-length schema that satisfies some desirable properties;

• $\mathrm{■}$

  We prove that such properties imply that we can compose many variable-length schemas into a single one that satisfies the same properties;

• $\mathrm{■}$

  We prove that the resulting variable-length schema implies a uniform fixed-length schema that uses a single bit per node.

Note that the last two steps are done in a problem-independent way. The conditions that allow to combine multiple variable-length schemas are expressed in Definition 4, that, on a high level, states the following. We want our variable-length schema to be tunable as a function of three parameters $\alpha$, $\gamma$, and $c$. The schema needs to satisfy that in each $\alpha$-radius neighborhood there are at most $\gamma$ bit-holding nodes, and that the number of bits held by these nodes is upper bounded by $c\alpha /{\gamma }^3$. Hence, a composable schema is a collection of schemas, one for each choice of parameters $\alpha$, $\gamma$, and $c$.

In general, in an advice schema our advice bits may depend on the numerical values of the identifiers, and the algorithm $𝒜$ that solves the problem may make use of the advice bits and the numerical values of the identifiers. However, here we will show that we can essentially for free eliminate the dependency on the numerical values of the identifiers.

A distributed algorithm is called order-invariant [50] if the output remains the same if we change the numerical values of the identifiers but preserve their relative order. Put otherwise, an order-invariant algorithm may make use of the graph structure, local inputs (which in our case includes the advice), and the relative order of the identifiers, but not the numerical values of the identifiers.

Naor and Stockmeyer [50] showed that constant-time distributed algorithms that solve LCL problems can be made order-invariant, and since then order-invariant algorithms have played a key role in many lower-bound results related to constant-time distributed algorithms, see e.g. [32, 33].

We say that graph problem $\mathrm{\Pi }$ is component-wise-defined if the following holds: a valid solution for graph $G$ is also a valid solution for a connected component that is isomorphic to $G$. Put otherwise, we can always solve $\mathrm{\Pi }$ by splitting the graph into connected components and solving $\mathrm{\Pi }$ separately in each component. In essence all graph problems of interest (especially in the distributed setting) are component-wise defined, but one can come up with problems that do not satisfy this property (a trivial example being the task of outputting the number of nodes in the graph).

We say that graph problem $\mathrm{\Pi }$ is a finite-input problem if the nodes and edges are either unlabeled, or they are labeled with labels from some finite set ${\mathrm{\Sigma }}_{\mathrm{in}}$.

Note that Theorem 5 below is applicable to LCL problems (they are component-wise defined, and in any LCL we have a bounded $\mathrm{\Delta }$ and bounded alphabets ${\mathrm{\Sigma }}_{\mathrm{in}},{\mathrm{\Sigma }}_{\mathrm{out}}$), but also to many other problems that are not locally checkable. We emphasize that we will assume some bound on the maximum degree $\mathrm{\Delta }$, but if we have an encoding schema that works for any $\mathrm{\Delta }$, we can apply the following result separately for each $\mathrm{\Delta }$.

In the full version of this work, we show that in graphs with sub-exponential growth, any LCL can be solved with one bit of advice per node. We now show that one bit does not suffice in general, assuming the Exponential-Time Hypothesis [37].

Recall that the Exponential-Time Hypothesis states that there is a positive constant $\delta >0$ such that 3-SAT cannot be solved in time $O(2^{\delta n})$, where $n$ is the number of variables in the 3-SAT instance.