Complexity Landscape for Local Certification

For distributed graph algorithms, the most classic measure of complexity is time, measured by the number of rounds before output. One of the most fruitful research programs on this topic has been the one of charting the complexity landscape [42]. That is, instead of considering specific problems and asking for their time complexity, a long series of papers have answered the following question: given a complexity function, is there a problem with that complexity? In this paper, we aim at starting the analogue research program for the space complexity of distributed graph algorithms.

Let us mention some elements about the time complexity landscape, in order to draw analogies with our setting later. For the sake of simplicity, we only discuss deterministic complexity of locally checkable labelings (LCLs) in bounded degree graphs in the LOCAL model. Before 2016, there were a few of classic complexities: $O(1)$ for very simple tasks, $\mathrm{\Theta }({\log }^{\ast }n)$ for tasks that could be reduced to coloring, and $O(n)$ for global problems (throughout the paper, $n$ refers to the number of nodes in the graph). Then, several seminal papers established that some problems have complexity $\mathrm{\Theta }(\log n)$ [15, 21], and that there is no problem whose complexity strictly lies between $\mathrm{\Theta }({\log }^{\ast }n)$ and $\mathrm{\Theta }(\log n)$ [21]. This gap sharply contrasts with classic computational theory where the time hierarchy theorem prevents the existence of such gaps [38]. It was also proved that in some intervals infinitely many complexities exist [6, 7, 19, 22], but not any complexity function had a corresponding problem. A key strategy in this research area is to understand the landscape for specific classes of networks such as paths [3], grids [16], trees [4, 5, 6], minor-closed graphs [20], etc. In this paper, we will follow a similar approach: characterizing which space complexities are possible depending on the structure of the network.

The space used by distributed algorithms is much less studied than the time, especially if we restrict to distributed graph algorithms. Some models where space is a well-studied measure are population protocols [2], massively parallel computing (MPC) [39] and models similar to Stone Age [26], but they are not relevant to our approach, either because they differ too much from distributed graph computing (having one-to-one communication or a centralized component) or because they fix the space complexity to constant. As far as we know, the only major line of research considering space complexity for distributed graph algorithms is self-stabilization, and more specifically the state model, where the nodes update their states by reading the states of their neighbors [1, 25]. In that model, the algorithm has to cope with transient faults, and consequently it is common to design algorithms (at least implicitly) with two components : one that builds a solution and one that checks the solution, and can reset the system if needed. Local certification was introduced to study specifically the space needed for the checking phase, by abstracting the computation of the solution into an oracle, and this is our focus today.

Informally, a local certification of a property is an assignment of labels to the nodes of the graph, such that the nodes can collectively check the correctness of a given property by inspecting the labels in their neighborhoods. This notion is known under different names, depending on the specific model considered: proof-labeling scheme [40], locally checkable proofs [36], non-deterministic local decision [33], etc. We will formally define our model in Section 2, and refer to [27] for an introduction to the notion. The (space) complexity of a certification is the maximum size of the label given to a node, and it is known to be basically equal to the space complexity of self-stabilizing algorithms.¹¹1There are some fine prints to this statement, that we will discuss later, in Section 1.4. Finally, since local certification is about decision problems, it is now standard to focus on checking graph properties (instead of solutions to graph problems), and to refer to the set of correct graphs as a language.

In local certification, the situation is similar to the pre-2016 situation for the time complexity as described above. That is, there are a few well-established complexity regimes – $O(1)$, $\mathrm{\Theta }(\log n)$, $\mathrm{\Theta }(n)$ and $\mathrm{\Theta }(n^2)$ – but no solid explanation as of why these are so common. But unlike for distributed time complexity (for LCLs on trees), we can prove that for a wide range of complexities, there exists a problem with that complexity.

The proof (deferred to Appendix A) follows a standard construction of [36]. The graphs satisfying the property are the ones made of two copies of a graph $H$, linked by a path. The graph $H$ is chosen so that it can be encoded on $f(n)$ bits, and a certification consists in giving this encoding to all nodes, so that every node knows $H$. It is known that this encoding can be checked locally when identifiers are given, hence we get the $O(f(n))$ upper bound. A counting argument allows to prove a matching lower bound [36].

At first sight, Theorem 1 gives a trivial answer to our question about the complexity landscape of local certification. But it relies crucially on several assumptions. First, in the upper bound it is necessary to have unique identifiers to avoid being fooled by symmetries at the checking phase. Also, because of the identifiers and because the value of $n$ needs to be certified, $\mathrm{\Omega }(\log n)$ bits are needed. Finally, to make the counting argument of the lower bound work, one cannot restrict too much the graphs in which to apply this theorem. This rises the three following questions that we tackle in this paper.

In other words, is the $\mathrm{\Omega }(\log n)$ a limitation of the proof technique, or could there be a gap between constant and $\mathrm{\Theta }(\log n)$, as the current state of our knowledge suggests?

This is especially relevant in conjunction with the previous question, since a unique identifier cannot be encoded in a certificate of $o(\log n)$ bits. Note that even beyond that regime, the impact of the identifiers on local decision is a well-studied topic [31, 30, 32, 29].

In the spirit of the work made on the distributed time complexity landscape, we would like to understand local certification on restricted graph classes, in which counting arguments do not apply, or only partially.

To give an overview of our techniques, let us start by describing two perspectives on constant size certification in anonymous paths. As said earlier, a basic building block is to certify with a counter that the length is equal to $imodk$ for some constant $i$ and $k$. One can see this behavior as a run in an automaton with $k$ states inducing a cycle whose initial state being $0$ mod $k$ and the final state being $i$ mod $k$. More generally, any constant size certification can be turned into a finite state automaton. There are various ways to do it, but basically, it consists in having states describing (pairs of) certificates, and transitions that connect states that would be accepted by the local verifier. The existence of an accepting run in the automaton is equivalent to the existence of a certificate assignment making the local verifier accept (see Section 3.1 for a more detailed explanation). (Also see [28], and also [23] for a similar perspective in the context of local problems.) Another point of view is the one of arithmetic. Intuitively, a set of lengths of anonymous paths that are accepted by a constant size certification corresponds to a combination of congruence relations (in other words, such a set is equal to the union of arithmetic progressions up to some point). This point of view allows, for example, to derive that the set of lengths of anonymous paths having a given constant size certification is eventually periodic.

Now, moving on to non-constant certifications, we need to introduce a non-uniform automata model. Indeed, since larger paths imply that we can use larger certificates, it also means larger automata. For each certificate size $i$, we will have an automaton ${𝒜}_i$, and we will require that an incorrect instance is rejected by all these automata, while a correct instance is accepted by at least one (small enough) ${𝒜}_i$. If a property has non-constant complexity, then it means that we will need arbitrarily large automata. If there exists a certification of size $s(n)$, then for any instance of length $n$, the automaton ${𝒜}_{s(n)}$ will have to accept. Now from the arithmetic perspective, there is an equivalence between having non-constant complexity and the fact that the set of correct lengths is not eventually periodic.

To establish a gap between constant size and $\mathrm{\Theta }(\log \log n)$ size in paths, the reasoning is the following.²²2Actually this proof gives worse constants than the ones of Theorem 5, but it is the one that generalizes to other settings. Consider a language $S$ that does not have a constant size certification. For an arbitrary $i$, we focus on the paths of $S$ that are recognized by ${𝒜}_i$ but not by ${𝒜}_1,\mathrm{\dots },{𝒜}_{i-1}$ (assume this is non-empty, which is the case for infinitely many $i$). This set is itself recognized by an automata: the intersection of ${𝒜}_i$ with the complement of the union of ${𝒜}_1,\mathrm{\dots },{𝒜}_{i-1}$. Studying the state complexity of this new automaton (which we do not discuss here) leads us to the fact that it must accept a path of length at most $2^{2^i}$. Finally, this upper bound on the minimum length for which some certificate size is needed translates into a lower bound constraint for the optimal complexity, and the double exponential translates into the double logarithm of the theorem.

This proof can be generalized without much modification to labeled paths (that is, paths with inputs) and to larger verification radius (see the full version [14]). This is pretty straightforward, given the previous proof: we use classic automata instead of unary automata, and a slightly different transformation from certification to automata. On the contrary, the proof that gives the right constants for Theorem 5 utilizes Chrobak normal form for unary automata (see full version), and does not generalize easily to the labeled case.

The proof of the analogous gap in trees (Theorem 8), is based on the same insights, but is much more involved. Basically, we adapt our automata to walk in the tree, reading the pending subtrees as labels. Two challenges are that a given tree can be read in many different ways, and that the alphabet is infinite. We argue that the complexity will be captured by the walks that follow a maximum path in the tree, and that the intersection, complement and union that are used in the proof are not harmed by the infinite alphabet.

We now turn our attention to Theorem 6, which establishes the existence of a language with optimal certification size $\mathrm{\Theta }(\log \log n)$ in anonymous unlabeled paths. Let us start by giving some intuition about how we came to this result. Intuitively, having optimal certificates of size $\mathrm{\Theta }(\log \log n)$ means that certificates of size $k$ allow to differentiate between correct and incorrect instances of size order $2^{2^k}$. When we implement simple counters modulo some constant using $k$ bits, the modulo is of order $2^k$, hence we can distinguish between correct and incorrect instances of size $2^k$ but not more, in the sense that $q$ and $q+2^k$ will be classified in the same category. Hence we need to do an “exponential jump” in terms of distinguishing capability. We now make two observations. First, given a set of pairs ${(r_i,m_i)}_{i\le \mathrm{\ell }}$, the fact that the path length is not equal to $r_{i}mod{m}_i$ for some $i\le \mathrm{\ell }$ can be certified with certificates of size $O({\max }_i\log (m_i))$. Indeed, since it is sufficient to prove that one of the modulo equation is not satisfied, we can simply give explicitly $m_i$ in all the certificates, in addition to the counter modulo $m_i$. Second, using the Chinese remainder theorem, for any two numbers $a$ and $b$, there must exist an integer $m$ exponentially smaller than $\max (a,b)$ such that $a\not\equiv bmodm$. This makes the existence of a $\mathrm{\Theta }(\log \log n)$ language believable, but making it into a real construction is another kettle of fish. We end up considering the language of the path whose length is not the product of consecutive primes. The scheme consists in certifying that either there is a gap or a repetition in the sequence of primes, via adequate counters, or there is an inconsistency between the largest prime used and what the length of the path is equal to, modulo a well-chosen (small) integer.

Theorem 7 states that in cycles there is a gap between constant and logarithmic certification size. This is in sharp contrast with the case of paths, which is surprising given the similarity of the two structures. At a very intuitive level, the difference stems from the fact that the only congruence that we can check in cycles are of the form $0modm$, and not arbitrary $imodm$. Indeed, in a path, it is easy to have one endpoint checking counter value zero and the other checking counter value $i$, while in cycles there are no endpoints. The natural way to simulate the endpoints is to designate a specific vertex $v$ in the cycle to check that the counter starts at $0$ from one side and reaches $i$ from the other side, but this is not robust. Indeed there could be more than one designated vertices and still all nodes could accept if each segment is $imodm$. This breaks the congruence, except if $i=0$. This restriction in the congruences prevents us from using the arithmetic tools of the proof of Theorem 6.

Let us now sketch the proof of the gap between certificates of size $O(1)$ and $\mathrm{\Theta }(\log n)$ in cycles. We again use an automata-like point of view, but we need to adapt it to work without starting and ending nodes. We consider a sequence of directed certificate graphs³³3We consider “graphs” and not “automata” here since we have no initial or accepting states, a sequence of certificate only gives us a walk in the graph of pairs of certificates. ${(G_i)}_i$. Here, a cycle $C$ with certificates of size $i$ $(c_1,\mathrm{\dots },c_n)$ is accepted by $G_i$ if and only if $(c_1,c_2),(c_2,c_3),\mathrm{\cdots },(c_n,c_1)$ is a closed walk in $G_i$. For the proof, we consider the first length $n_k$ that is accepted by the $k$-th graph $G_k$ (corresponding to certificates of size $k$), but not by smaller ones. Now, if the certificate size is in $o(\log n)$, this walk is much longer than the size of $G_k$, and therefore it has a lot of cycles. We define a notion of elementary cycle of the graph, and decompose this walk as a linear combination of elementary cycles. If $d$ is the greatest common divisor of these elementary cycles, then $n_k=d\times q$, for some $q$. We consider a set of numbers of the form $p\times d$, such that (1) $p$ is prime, (2) and (3) $p\times d$ is still much larger than the size of $G_k$. By a generalization of Bézout’s identity, (3) implies that all these numbers are accepted by $G_k$ hence they belong to the language. But since they are smaller than $n_k$, by minimality, they must be recognized by smaller graphs too. We argue by pigeon-hole principle that there must exist one graph $G_{k^{\prime }}$, that has two walks of lengths $p_{1}d$ and $p_{2}d$ that intersect. Then by concatenating portions of the two walks, we can prove that $G_{k^{\prime }}$ actually accepts all the cycles of size $a{p}_{1}d+b{p}_{2}d$. Finally, using again a generalization of Bézout’s identity we can prove that the cycle of length $n_k$ is also recognized by $G_{k^{\prime }}$, which contradicts the minimality of $k$.

We also establish that for several settings there is no gap in the complexity, that is, for any well-behaved function $f$, there exists a property that has certificates of size $O(f(n))$ but not $o(f(n))$.

Let us sketch the technique of the upper bound for the setting of Theorem 10: restricting to caterpillars, using certificates whose size is a function of $d$, with verification radius 2. Given a function $f$, we define a sequence of integers $(b_k)$, such that the $k$-th term is roughly $f^{-1}(\log k)$. The correct instances are of the following form: a path of length $b_k$, for some $k$, such that the $i$-th node has $i$ leaves, and except for the first one, which has $b_k$ leaves instead of 1. A compact way to certify these instances is to give $k$ to every node. The nodes in the middle check the growth of the number of attached leaves (thanks to their radius 2 verification) and the endpoints check that they have $b_k$ leaves. The diameter is $b_k$, and the number of bits used is $\log k$ which is basically $f(d)$.