Short Graph Sketches Suffice for
Error-resilient Leader Verification in CONGEST
January 01, 1970
Abstract
Locally Checkable Proofs (LCPs) enable the verification of global graph properties from locally checkable certificates assigned by a prover. This framework has recently been extended to Locally Checkable Proofs-with-Errors (LCPE), in which an adversary may corrupt some of the certificates. Existing LCPE algorithms are designed for the LOCAL model, whose unbounded communication makes them unsuitable for direct implementation in the (logarithmically) bandwidth-restricted CONGEST model.
In this paper, we initiate the study of efficient CONGEST implementations of LCPE through the unique-leader verification problem on trees. The main challenge is that tolerating \(\varepsilon\) certificate errors requires each node to reason about its \((2\varepsilon+1)\)-hop neighborhood, whose exact topology cannot, in the worst case, be communicated efficiently in Congest – reconstructing it naively costs up to \(O(\Delta^{2\varepsilon+1}\log n)\) bits. To overcome this bottleneck, we introduce local graph sketches, together with the notions of imagined trees and imagined certifications, which compactly encode—in only \(O(\varepsilon^2\log n)\) bits at each node—precisely the information a node needs to decide. Using these techniques, we design an algorithm that tolerates up to \(\varepsilon\) adversarial certificate errors and computes the required sketches in \(O(\varepsilon^2)\) communication rounds in the CONGEST model.
We complement this with a matching impossibility result: even in the strictly more powerful LOCAL model, and even with certificates of unbounded size, no verification scheme with view distance at most \(\varepsilon\) can tolerate \(\varepsilon\) adversarial errors. Since LOCAL is strictly stronger than CONGEST, this lower bound carries over immediately, showing that a view distance beyond \(\varepsilon\) – and hence the wider neighborhood our algorithm summarizes – is unavoidable.
Keywords: Verification problem, Leader election, Locally Checkable Proof, Local Certification, Error-resilience, CONGEST Model.
1 Introduction↩︎
1.1 Background and Motivation↩︎
In general, nodes in a distributed system do not have a global view of the network. Instead, each node can access only a bounded neighborhood around itself (sometimes only its direct neighborhood), whereas many properties of interest are inherently global. Examples include determining whether the network is a tree, whether a graph is bipartite, whether a computed structure is a valid spanning tree, or whether the system remains consistent after transient faults. Such verification tasks arise in many settings, including self-stabilizing and fault-tolerant systems. For many global properties, however, purely local verification is impossible without additional information, while verifying them from scratch requires excessive communication. This motivates equipping each node with a small amount of auxiliary information that makes local verification possible.
The notion of locally verifying graph properties with the help of auxiliary information assigned to the nodes is captured by the framework of proof labeling schemes (PLS), introduced by Korman, Kutten, and Peleg [1]. In this framework, a prover first assigns a certificate (a binary string) to each node. Subsequently, a distributed verification algorithm, called the verifier, runs at every node and uses its own certificate, together with the certificates of the neighboring nodes, to output a binary decision: either accept or reject. The aim of the verifier is to distinguish between the yes and no instances of the verification problem. Later Göös and Suomela [2] generalized the idea of proof labeling schemes under the name of locally checkable proofs (LCP), where the main difference is that a node (rather the verifier) can inspect a constant radius (instead of just 1) neighborhood and that the node can access the certificates and identifier of the nodes within that neighborhood. This constant radius is called the view distance of the node. A survey by Feuilloley [3] consolidates these notions. This framework on local verification has been extended in various directions, including PLSs with restricted provers [4], randomized [5] and quantum PLSs [6], PLSs with global proofs in addition to local ones [7], and many more.
The model underlying this long line of work is the well-known LOCAL model [8], in the sense that a verifier with a view distance \(k\) can be implemented in \(k\) synchronous communication rounds (see [2] by Göös and Suomela) of the LOCAL model. In this context, the metric of interest is the certificate size (i.e., the maximum number of required bits given to any node) considered across the literature for various graph properties on different families of graphs [9]–[13]. The certificate size depends on the property being verified. Constant-size is known for several problems [2], whereas an \(O(\log n)\) size suffices for a wide range of verification problems, including unique leader, cycle-freeness, spanning tree, non-bipartiteness, minor-freeness and many more [2], [7], [14]–[21]. On the other hand, some verification problems require larger proofs, such as \(O(\log n\log W)\) bits (edge weights in \([1, W]\)) for MST verification by Korman and Kutten [22] and \(O(n\log n)\) bits for diameter \(k\) verification by Censor-Hillel, Paz and Perry [23].
1.1.0.1 Erroneous Certificates.
In this context, always expecting trustworthy certificates may be limiting in practice. Since certificates must first be generated, they may be produced using AI/ML-based techniques or randomized algorithms (e.g., Monte Carlo algorithms), both of which may introduce errors. In our context, an error could refer to a certificate that differs from the one assigned by a trustworthy prover. More generally, the verifier has no control over how the certificates are generated or transmitted, and therefore cannot always rely on their correctness. Consequently, it is natural to seek verification schemes that continue to operate correctly even when (possibly a bounded number of) certificates are erroneous. This motivates the study of verification schemes that remain robust even when the certificates are partially inaccurate. Similar motivations have recently appeared in several works on learning-augmented algorithms, where the auxiliary information provided to the nodes may be imperfect or unreliable [24]–[26]. This direction has recently attracted considerable attention across several research communities. In fact, Boyar, Ellen, and Larsen in [25] initiated the study of distributed graph algorithms in this setting, although their model (which they refer to as the prediction model) differs somewhat from ours in this paper.
1.1.0.2 LOCAL vs CONGEST.
To the best of our knowledge, none of these works considers the CONGEST model – one of the classical models in distributed computing, which assumes per-edge bandwidth. The LOCAL model, on the other hand, places no limit on message size, and thus a node can collect its full \(k\)-hop neighborhood in \(k\) rounds, whereas the CONGEST model caps every edge at \(O(\log n)\) bits per round. This gap is largely immaterial for certification so far, since the verifier for essentially every graph property studied in the literature inspects only a node’s immediate (\(1\)-hop) neighborhood. The situation changes once we allow an adversary to tamper with the certificates that the (trustworthy) prover assigns. With such corruption, a \(1\)-hop view can be too unreliable. This motivates a more general formulation, in which the adversary may modify the certificates of at most \(\varepsilon\) nodes within the \(k\)-hop neighborhood of each node. Now, a node can no longer rely on its immediate neighborhood alone and must examine a wider neighborhood. Collecting a \(k\)-hop neighborhood costs merely \(k\) rounds in LOCAL, but the \(k\)-hop neighborhood contains \(O(\Delta^k \log n)\) bits of information, which in CONGEST model, requires round complexity up to \(O(\Delta^k)\) in the worst case (\(\Delta\) is the maximum degree). The central challenge of this work is to verify the desired property correctly using substantially smaller \(O(\varepsilon^2 \log n)\) information than this naive \(O(\Delta^k \log n)\) bound.
1.2 Our Model and Definitions↩︎
1.2.0.1 Graphs.
A graph \(G(V,E)\) in our consideration is a tree with \(|V| = n\) nodes. For a node \(v\), we use the notation \(N_{k}(v)\), called the \(k\)-hop neighborhood of \(v\), to denote the set of all nodes within the distance \(k\) hops from \(v\) (the shortest path from \(v\) to any node in \(N_k(v)\) has \(\leq k\) edges), including \(v\) itself. We assume that the nodes of a tree possess unique identifiers (or IDs for short) from the set \(\{1,2, \dots, poly(n)\}\) on \(O(\log n)\) bits. However, our techniques do not rely on the availability of node IDs. It is sufficient to assume that each node \(v\) has a distinct local port numbering from the set \(\{1,2, \dots, deg(v)\}\) to its incident edges. Note that the port numbers assigned to the two endpoints of an edge are independent and need not coincide.
1.2.0.2 Local Verification with Certificates.
A convenient way to describe the verification process is through a prover-verifier paradigm. The prover gives a certificate assignment5 \(C\) on a graph \(G\), which is a function \(C: V \rightarrow \{0,1\}^*\) that associates with every node a binary string. A binary string assigned to a node \(v\) is called the certificate of \(v\). The prover’s objective is to have all nodes accept, irrespective of whether the instance is a yes-instance or a no-instance.
A verifier is a distributed algorithm \(\mathcal{A}\) running at each node that takes the triple \((G, L, v)\) as input and outputs either \(0\) or \(1\). For a natural number \(k\) and a node \(v \in G\), let \(G[N_k(v)]\) be the subgraph induced by the nodes in \(N_k(v)\) and \(C[N_k(v)]: N_k(v) \rightarrow \{0,1\}^*\) be the restriction of \(C\) to \(N_k(v)\). A verifier \(\mathcal{A}\) is called a local verifier if there exists a \(k\) such that \(\mathcal{A}(G, L, v) = \mathcal{A}(G[N_k(v)], L[N_k(v)], v)\) for all \(G, L\) and \(v\), which intuitively means that the output of a node \(v\) depends only the information (inputs or certificates) of the nodes within its \(k\)-hop neighborhood. We call this \(k\) the view distance of \(v\) (which, in the distributed setting, is equivalently the view distance of \(\mathcal{A}\)).
In the context of verifying a graph property (recall that a graph property is a set of graphs that is closed under isomorphism), we say that a graph property \(\mathcal{P}\) admits a locally checkable proof labeling scheme if there is a prover-verifier pair \((f,\mathcal{A})\), where the prover \(f\) gives a certificate assignment function \(C\) for each \(G \in \mathcal{P}\) and \(\mathcal{A}\) is a local verifier (with a view distance \(k\)) such that the following two properties hold. Completeness: If \(G \in \mathcal{P}\), there should be a certificate assignment function \(C\) on \(G\) provided by the prover \(f\) (i.e., \(f(G) = C\)) such that \(\mathcal{A}(G[N_k(v)], C[N_k(v), v]) = 1\) for all \(v\). Soundness: If \(G \notin \mathcal{P}\), then for every certificate assignment \(C\) on \(G\), there must be at least one node \(v\) such that \(\mathcal{A}(G[N_k(v)], C[N_k(v)], v) = 0\).
For our convenience, we say that the node \(v\) accepts (resp. rejects) when the verifier \(\mathcal{A}\) outputs \(1\) (resp. \(0\)). We emphasize the fact that when \(G\) does not satisfy the property \(\mathcal{P}\), there must exist at least one rejecting node for any certificate assignment function.
1.2.0.3 Oracle vs Adversary (The Error Model).
To introduce the concept of certificates with errors in a convenient way, we distinguish two entities that assign certificates to nodes: the oracle and the adversary. So far in the above discussion of the model, the prover \(f\) is a trustworthy oracle. We denote the certificate assignment function provided by an oracular prover by \(C_O\) and the corresponding verifier by \(\mathcal{A}_0\). We refer to the pair \((C_O, \mathcal{A}_0)\) as the oracular scheme.
On the other hand, we consider a setting in which an adversary can modify the certificates assigned to the graph nodes by an oracular prover to potentially cause all nodes to accept even when \(G\notin \mathcal{P}\) or some nodes to reject when \(G \in \mathcal{P}\). We represent the certificate assignment function after the adversarial modification by \(C_{adv}\).
In our paper, we assume that \(C_{adv}\) differs from \(C_O\) in at most \(\varepsilon\) nodes within \(N_{2\varepsilon+1}(v)\) for every node \(v\), i.e., the adversary is allowed to introduce at most \(\varepsilon\) modifications within the \((2\varepsilon+1)\)-hop neighborhood of each node \(v\). We call each such modification an error. Under this adversarial model, the definition of completeness must be modified to account for certificates with errors, whereas the definition of soundness remains unchanged.
- Error-resilient Completeness: If \(G \in \mathcal{P}\), there is a certificate assignment \(C_O\) on \(G\) such that for every \(C_{adv}\) differing from \(C_O\) in at most \(\varepsilon\) nodes within \(N_{2\varepsilon+1}(v)\) for every node \(v\), we have \(\mathcal{A}(G[N_{k}(v)], C_{adv}[N_k(v)], v) = 1\) for all \(v\).
In this setting, we refer to the pair \((C_{adv}, \mathcal{A})\) as the adversarial scheme. In our description, we use the term the oracular setting to mean the error-free setting in which certificates are not modified by the adversary, and the term the adversarial setting to mean the setting in which certificates might be influenced by the adversary.
1.3 The Problem Definition: unique-leader↩︎
In this paper, we consider the popular verification problem of determining whether a graph has a unique leader [2], [19]. For simplicity, we assume that each node is initially assigned a binary input, rather than a unique identifier. These inputs are part of the problem instance and should not be confused with certificates, which are assigned later by the prover. The leader node in the graph gets \(\mathcal{L}\), and the rest of the nodes get \(\mathcal{N}\). In this paper, we study the property \(\mathcal{P}=\mathrm{\small unique-leader}{}\). The corresponding yes and no instances are defined as follows. An instance is a yes-instance for unique-leader if exactly one node in the graph is assigned input bit \(\mathcal{L}\). An instance is a no-instance whenever either no node or more than one node is assigned input bit \(\mathcal{L}\). We say that a scheme \((C, \mathcal{A})\) solves unique-leader if both completeness and soundness are satisfied.
1.3.0.1 Warm-up: unique-leader in Oracular Setting.
It is straightforward to verify unique-leader using the following known scheme, which we mention briefly.
The certificate assignment function \(C_O(v) = 0\) if \(v\) is the node with the input bit \(1\) (leader). For any other node \(v\) (non-leader), \(C_O(v)\) is the breadth-first search (BFS) distance to the leader.
We use \(\mathcal{A}_0\) to denote the verification algorithm executed at each node \(v\) that uses the certificates of \(v\) and its neighboring nodes. More precisely, a node \(v\) with input bit \(0\) checks whether exactly one neighbor, namely its parent, has certificate \(C_O(v)-1\), while every other neighbor, namely its children, has certificate \(C_O(v)+1\). If \(v\) is the leader (i.e., the unique node with input bit \(1\)), it has no parent, and therefore all of its neighbors must have certificate \(C_O(v)+1\). A node accepts if the corresponding condition is satisfied; otherwise, it rejects.
The correctness of the above scheme is well known and straightforward. Hence, we do not include it in our paper. As \(\mathcal{A}_0\) requires only the certificates of neighboring nodes, the distinction between the LOCAL and CONGEST models is immaterial in this setting. Also, observe that the above scheme uses certificates of size \(O(\log n)\). In fact, this certificate size is optimal for an arbitrary graph with a matching lower bound, established by Göös and Suomela [2]. We refer to \(\mathcal{A}_0\) as the base verification algorithm henceforth (when \(\varepsilon = 0\)).
1.4 Our Results and Roadmap↩︎
We initiate the study of efficient CONGEST implementations of error-resilient local verification on the unique-leader problem in this paper. We begin, in Section 2, with an impossibility result (see Theorem 1) which shows that tolerating \(\varepsilon\) errors, even if \(\varepsilon\) errors are spread across the entire graph (rather than within the neighborhood of every node) forces every node to examine a neighborhood strictly larger than \(N_{\varepsilon}\) and this holds already in the LOCAL model, which is strictly more powerful than CONGEST. The lower bound illustrates the need to learn large neighborhoods to solve problems in the context of error-resilience. In the CONGEST model, learning the entire \(\varepsilon\)-hop neighborhood may need \(\Omega(\Delta^\varepsilon)\) rounds.
Our positive results circumvent this problem. We present an algorithm that requires nodes to learn the certificates of nodes within their \(2\varepsilon+1\)-hop neighborhood to verify unique-leader and we separate it into two parts: learning and decision. The key observation is that the decision part never requires the exact structure of the neighborhood: a compact summary suffices. Hence, in the learning part, we introduce a novel technique, which we refer to as (local) graph sketches, which is used to describe all relevant information about its \(2\varepsilon+1\)-hop neighborhood in a compact form that a node can learn in \(O(\varepsilon^2)\) CONGEST round. The construction is given as sketch-construction() (Algorithm [alg:sketch]) in Section 4.
The decision part is our algorithm refix-leader (Section 3): it takes the compressed neighborhood information, searches for a correction of at most \(\varepsilon\) certificates under which the error-free base verifier accepts, and decides in a single round of local computation. The correctness of refix-leader hinges on one lemma (Lemma 2). As its proof is long and largely self-contained, we state and use it in the analysis but defer the proof to Section 5 for space management. We conclude in Section 6 with open problems and future directions.
Although learning logically precedes decision, we present them in the opposite order: the decision algorithm first (Section 3), then the sketch construction (Section 4). This lets us first fix exactly what information the decision part consumes — the interface the sketch must provide — and only then show how to compute it, which we find considerably clearer than specifying the compression before its purpose is known. We believe the graph-sketch technique is of independent interest and opens several directions for verification problems. The broad idea of summarizing a graph compactly to compute on it efficiently has been studied before, in settings different from ours [27]–[29]; we expect such compression to find further use in communication-efficient, error-resilient solutions based on certificates, and in the advice model.
For the reader’s convenience, we include Table 1 at the end of the paper, summarizing the main variables and notations used throughout.
2 Impossibility Result↩︎
We establish the following impossibility result in the LOCAL model. Since LOCAL is strictly more powerful than CONGEST, the lower bound immediately carries over to the CONGEST model. This impossibility holds even when the adversary may modify the certificates of at most \(\varepsilon\) nodes in the entire graph (rather than within the neighborhood of every node, which would allow for more than \(\varepsilon\) errors in the entire graph distributed among multiple neighborhoods).
Theorem 1. In adversarial setting, there is no scheme \((C_{adv},\mathcal{A})\) solving unique-leader on arbitrary trees with \(\varepsilon\) errors in which the verifier \(\mathcal{A}\) has view distance at most \(\varepsilon\) even if certificates are allowed to have an unbounded size.
Proof. Assume for the sake of contradiction that such a scheme \((C_{adv},\mathcal{A})\) exists, where \(\mathcal{A}\) has view distance \(\varepsilon\). By error-resilient completeness, for every yes-instance, there is an oracular certificate assignment \(C_O\) under which every node accepts, and continues to accept under every assignment obtained by modifying at most \(\varepsilon\) certificates within the \(\varepsilon\)-hop neighborhood of each node.
The yes-instance. Let \(G_Y=(v_0,v_1,\dots,v_{4\varepsilon+2})\) be a path on \(4\varepsilon+3\) nodes, where \(v_0\) is the unique leader (input bit \(\mathcal{L}\)). By completeness, fix an oracular certificate assignment \(C_O\) under which every node of \(G_Y\) accepts and keeps accepting under any admissible adversarial modification. For \(0\le j\le 4\varepsilon+2\), let \(c_j=C_O(v_j)\). Their actual values are irrelevant to this proof, and we use them only to construct the certificate assignment for the second tree.
We highlight a property we need. We say that a node \(v\) in a tree \(G\) has a yes-view if there exists a tree \(G'\), a node \(v' \in G'\) and an oracular certification \(C_O'\) on \(G'\) such that views of \(v\) and \(v'\) are identical in tree structure and input bits, and the certification within the view of \(v\) differs in at most \(\varepsilon\) nodes from \(C_O'\) on nodes within the view of \(v'\). By error-resilient completeness, node \(v\) must accept if it has a yes-view.
The no-instance. Let \(G_N=(u_0,u_1,\dots,u_{4\varepsilon+2})\) be a path on the same number of nodes, but with two leaders: \(u_0\) and \(u_{4\varepsilon+2}\) have input bits \(\mathcal{L}\), and every other node has input bit \(\mathcal{N}\). We now define a certificate assignment \(C\) on \(G_N\) by copying \(C_O\) inward from each end, reflected about the midpoint (central node \(u_{2\varepsilon+1}\)) of the path: \(C(u_j)=c_{\min\{j,\,4\varepsilon+2-j\}},\) where \(0\le j\le4\varepsilon+2\)
Fix a node \(u_m\). If \(m\le 2\varepsilon+1\), then we compare \(u_m \in G_N\) and \(v_m \in G_Y\); otherwise we compare \(u_{4\varepsilon+2-m} \in G_N\) and \(v_m \in G_Y\). These cases are analogous, so we present only the case for \(m\le 2\varepsilon+1\). We show that \(u_m\) has a yes-view by comparing it to the view of \(v_m\) under the oracular certification \(C_O\). The view of \(u_m\) consists of the nodes \(u_{\max\{0, m-\varepsilon\}},\dots, u_{\min \{4\varepsilon+2, m+\varepsilon\}}\), and likewise the view of \(v_m\) consists of \(v_{\max\{0, m-\varepsilon\}},\dots, v_{\min \{4\varepsilon+2, m+\varepsilon\}}\). Since \(m\le2\varepsilon+1\), the largest index appearing in either view is \(m+\varepsilon \le 3\varepsilon +1 < 4\varepsilon+2\). Hence, neither view reaches the right endpoint of the path. In particular, the right leader \(u_{4\varepsilon+2}\) of \(G_N\) never lies in \(u_m\)’s view. The two views thus span the same range of indices and have the same path structure. Moreover, if \(m \geq \varepsilon+1\), neither view contains index \(0\), so neither contains a leader. If \(m\leq \varepsilon\), both views contain index \(0\) and no other leader index, and \(u_0 \in G_N\) and \(v_0 \in G_Y\) are both leaders. Either way, the leaders align on both views. Hence, the two views agree in structure and in leader placement, and can differ only in certificates. By construction \(C(u_j) = c_j = C_O(v_j)\) for all \(j \leq 2\varepsilon+1\), so a difference can occur only at an index \(j > 2\varepsilon+1\). But \(u_m\)’s view reaches only up to index \(m+\varepsilon\), and since \(m \leq 2\varepsilon+1\), it contains at most \((m+\varepsilon)-(2\varepsilon+2)+1 \;=\; m-\varepsilon-1 \;\le\; \varepsilon\) indices above \(2\varepsilon+1\). Hence, the two views differ in at most \(\varepsilon\) certificates, so \(u_m\) has a yes-view and \(\mathcal{A}\) makes \(u_m\) accept.
Consequently \(\mathcal{A}\) accepts at every node of \(G_N\), even though \(G_N\) has two leaders and is a no-instance of unique-leader. This contradicts soundness and completes the proof. ◻
3 unique-leader in Adversarial Setting (with Errors)↩︎
The impossibility of Section 2 shows that, in the adversarial setting, every node must inspect a neighborhood of radius at least \(\varepsilon+1\) to decide correctly. The algorithm we develop in this section requires a view distance of \(2\varepsilon+1\). One of the main challenges here is due to CONGEST – how can a node learn about its \(2\varepsilon+1\)-hop neighborhood within \(poly(\varepsilon)\) rounds?
We split the task into two logical parts. The first is learning the neighborhood: rather than reconstructing the exact \((2\varepsilon+1)\)-hop neighborhood, each node learns a compact summary of it, which we
call a graph sketch. This construction succeeds only when the certificates a node sees are within \(\varepsilon\) corrections of a certification that the base algorithm \(\mathcal{A}_0\) would accept; if no such correction exists, the construction cannot produce a valid sketch, and we say the node encounters a sketch rejection. A sketch rejection can arise only when the node ought to
reject in the first place — either the instance has no unique leader, or the certificates are too corrupted to be fixed — so a node that encounters one simply rejects. It therefore suffices, for the rest of this section, to reason about nodes that obtain a
valid sketch. We defer the construction to Section 4. In the present section, we assume each node has already obtained its graph sketch; we state precisely what information the sketch provides and use it to decide
locally. The second part is thus deciding: given the sketch, each node runs refix-leader, which we present and prove correct in Sections 3.2–5. Only afterward, in Section 4, do we show how the data must be transmitted to compute the sketch.
3.1 General Idea of the Algorithm refix-leader↩︎
We begin with a graph sketch \(S_G^v\), from which a node \(v\) obtains the following information. Although the sketch (of a particular size) may encode additional information, we list only the information required by our algorithm.
The number of nodes in \(N_{2\varepsilon+1}(v)\) in \(G\).
For each \(u \in N_1(v)\), the adversarial label \(C_{adv}(u)\) together with the port at \(v\) leading to node \(u\).
For every sequence of certificates \((c_1, c_2, \dots, c_k)\) with \(k \le 4\varepsilon+3\), every pair of positions \(m,j \in \{1, \dots, k\}\), and every pair \(u_1, u_2\) of neighbors of \(v\), the node \(v\) knows whether the sequence is realizable at positions \(m,j\) through \(u_1, u_2\): that is, whether there exists a path \(P = (v_1, v_2, \dots, v_k)\) contained entirely within \(N_{2\varepsilon+1}(v)\) such that (i) \(v\) occupies position \(m\) in \(P\), i.e.\(v = v_m\), (ii) a node \(x\) with input \(\mathcal{L}\) occupies position \(j\) in \(P\), i.e.\(x = v_j\), (iii) \(u_1 = v_{m-1}\) whenever \(m \ge 2\), and \(u_2 = v_{m+1}\) whenever \(m \le k-1\) (the path enters and leaves \(v\) through the specified neighbors) and (iv) the adversarial certificates along \(P\) match the sequence, i.e.\(C_{adv}(v_i) = c_i\) for every \(i\).
The procedure by which a node constructs (or obtains) the graph sketch of its \(N_{2\varepsilon+1}\) is described in Section 4 – for now, we assume a node has it and describe how it decides. A node might not learn the exact structure of the neighborhood from the sketch, so it instead considers every neighborhood that is consistent with what the sketch records. We formalize this next with the following definitions: the neighborhood a node imagines, the certificates it carries, and the corrections the node finds.
Definition 1 (Imagined Tree). Let \(S_G^v\) denote the graph sketch that node \(v\) obtains in \(G\) – which captures only part of \(N_{2\varepsilon+1}(v)\). A tree \(G^v\) for the node \(v\) is an imagined tree* consistent with \(S_G^v\) if, under the same graph sketching procedure, the sketch that \(v\) obtains in \(G^v\) equals \(S_G^v\).*
Notice that \(2\) neighboring nodes \(u,v\) may imagine different imagined trees \(G_u,G_v\). For example, in Figure 2 node \(v\) may imagine the tree on the right, while node \(u\) may imagine the tree on the left (which in this case is the original tree).
The (actual) neighborhood \(N_{2\varepsilon+1}(v)\) in \(G\) is one imagined tree, and in general, there may be several, since \(S_G^v\) need not determine the neighborhood uniquely. However, \(G^v\) and \(N_{2\varepsilon+1}(v)\) in \(G\) have the same number of nodes, as the sketch encodes the number of nodes in \(N_{2\varepsilon+1}(v)\). Each imagined tree carries certificates that the node actually reads and uses to make further decisions.
Definition 2 (Sketch Certificates). Consider an imagined tree \(G^v\) consistent with \(S_G^v\). The certificate assignment that \(G^v\) carries is called the sketch certificate assignment and denoted \(C_{sk}^v\). The value \(C_{sk}^v(u)\) is the sketch certificate of node \(u\) in \(G^v\).
We now define the notion of imagined certificates from the perspective of the node \(v\), which captures the notion that each \(v\) looks for corrections to the sketch certificates on \(G^v\).
Definition 3 (Imagined Certificates). For node \(v\), a function \(C_{im}^v\) on the nodes of \(G^v\) is called an imagined certificate assignment function, if \(C_{im}^v\) is the certificate assignment function that causes \(v\) to accept, i.e., \(C_{im}^v\) differs from \(C_{adv}\) in at most \(\varepsilon\) nodes within \(N_{2\varepsilon+1}(v)\) and the base algorithm \(\mathcal{A}_0\) makes all nodes within \(N_{2\varepsilon}(v)\) accept using \(C_{im}^v\). To refer to this, we sometimes say that \(v\) imagines \(C_{im}^v\) (this is local from a node’s perspective and may not extend to a global one).
In words, \(v\) considers every imagined tree \(G^v\) consistent with its sketch, and in each one searches for an imagined certification, i.e., an override of the certificates of at most \(\varepsilon\) nodes within its \(2\varepsilon+1\)-hop neighborhood under which \(\mathcal{A}_0\) makes every node accept throughout \(N_{2\varepsilon}(v)\). If some imagined tree admits such a certification, \(v\) accepts; otherwise, it rejects. If the adversary introduced at most \(\varepsilon\) errors, then the actual \(N_{2\varepsilon+1}(v)\) in \(G\) is one of these imagined trees, and correcting those errors is a valid certification on it, so \(v\) accepts.
The check is limited to \(N_{2\varepsilon}(v)\) (rather than \(N_{2\varepsilon+1}(v)\)) because modifying the certificate of some node \(u\) in \(v\)’s local computation may affect the decisions of \(u\) and its neighbors under \(\mathcal{A}_0\), and nodes on the boundary \(N_{2\varepsilon+1}(v) \setminus N_{2\varepsilon}(v)\) may have neighbors whose labels are unknown to \(v\) (and hence it cannot be sure about their decision).
halt and reject
3.2 Correctness of Algorithm refix-leader↩︎
Here we analyze the correctness of refix-leader. We state the following theorem.
Theorem 2. refix-leader together with \(C_{adv}\) verifies unique-leader in \(O(\varepsilon^2)\) CONGEST
rounds, even when \(C_{adv}\) differs from \(C_O\) in at most \(\varepsilon\) nodes within \(N_{2\varepsilon+1}(v)\) for
every node \(v\).
Completeness is straightforward, and we prove it in Lemma 1 below. The major one is soundness, and its difficulty is that adjacent nodes \(u\) and \(v\) might reconstruct different imagined trees \(G^u\) and \(G^v\) and choose different imagined certifications \(C_{im}^u\) and \(C_{im}^v\) on them. We begin with completeness, which is immediate, and then turn to soundness.
Lemma 1 (Completeness). If \(G\) has a unique leader, refix-leader makes every \(v\) accept, for every adversarial certificate
assignment \(C_{adv}\) that differs from \(C_O\) in at most \(\varepsilon\) nodes within \(N_{2\varepsilon+1}(v)\).
Proof. This is quite straightforward. For an arbitrary node \(v\), consider the imagined tree to be the exact neighborhood \(N_{2\varepsilon+1}(v)\) of \(G\) itself, which is consistent with \(v\)’s sketch. On it, we take the certificate assignment function \(C_O\) restricted to \(N_{2\varepsilon+1}(v)\). Under \(C_O\), every node accepts according to the algorithm \(\mathcal{A}_0\), so in particular, all nodes within \(N_{2\varepsilon}(v)\) accept. This proves the lemma. ◻
This settles completeness. For soundness, suppose \(G\) does not have a unique leader, yet, for contradiction, refix-leader makes every node accept. Then each \(v\) imagines a certification \(C_{im}^v\) on some imagined tree \(G^v\). The following lemma is key: adjacent nodes agree on each other’s imagined certificates.
Its proof is the most involved part of the analysis, so we state it here and use it to prove soundness. Due to space management, we defer its proof to Section 5.
Lemma 2. Let \(u\) and \(v\) be adjacent nodes in \(G\) that imagines trees \(G^u\) and \(G^v\) and certifications \(C_{im}^u\) and \(C_{im}^v\) respectively (recall Definition 1-3). Then \(C_{im}^u(u)=C_{im}^v(u)\) and \(C_{im}^u(v)=C_{im}^v(v)\).
Assuming Lemma 2, soundness follows by stitching the local certifications into a single global one. We emphasize that soundness does not rely on the error bound: even if \(C_{adv} = C_O\), some node must reject whenever \(G\) lacks a unique leader.
Lemma 3 (Soundness). When \(G\) does not have a unique leader, for any proof \(C\), refix-leader makes at least one node
reject.
Proof. Suppose, for contradiction, that refix-leader makes every node accept. Then each node \(v\) imagines a certification \(C_{im}^v\) on some
imagined tree \(G^v\). Define a certificate assignment \(C\) on \(G\) by \(C(v) = C_{im}^v(v)\) for each node \(v\), i.e., every node receives the certificate it imagines for itself. We show that \(\mathcal{A}_0\) makes every node of \(G\) accept under \(C\). Fix a node \(v\). Since refix-leader makes it accept using \(C_{im}^v\), the base algorithm \(\mathcal{A}_0\) must make every node within \(N_{2\varepsilon}(v)\) of \(G^v\) accept under \(C_{im}^v\). By Lemma 2, for every neighbor \(u\) of \(v\) we have \(C_{im}^v(u) =
C_{im}^u(u) = C(u)\). Thus \(C\) agrees with \(C_{im}^v\) on all of \(N_1(v)\). As \(\mathcal{A}_0\) inspects only
\(N_1(v)\) to decide for \(v\), and it makes \(v\) accept under \(C_{im}^v\), it also makes \(v\) accept under \(C\). Hence, \(\mathcal{A}_0\) accepts every node of \(G\) under \(C\), but
\(\mathcal{A}_0\) is a correct error-free verifier for unique-leader, so it must reject some node when \(G\) does not have exactly one leader – a
contradiction. ◻
Lemma 1 (completeness) and 3 (soundness) together establish correctness of Theorem 2. The CONGEST round complexity is shown in Section 4.
4 Graph Sketches in \(O(\varepsilon^2)\) CONGEST Rounds↩︎
We now present the algorithm that constructs the graph sketches described in Section 3.1. Recall that it may return a sketch rejection instead of a proper sketch if it is clear that the instance (graph and adversarial certification) should be rejected. Otherwise, every node obtains a proper sketch. For convenience, we use the phrase acceptable certification to denote a certificate assignment function under which \(\mathcal{A}_0\) makes every node accept.
4.0.0.1 Overview:
Notice that an acceptable certification on a \((2\varepsilon+1)\)-hop neighborhood can be easily encoded if one knows the graph structure – it is sufficient to point out which node \(r\) has the smallest certificate, and the certificates of every other node is determined by the distance to \(r\), see Figure 1.
However, we transmit adversarial certificates instead of an acceptable one. If there exists an acceptable certification \(C\) of nodes that differs from the adversarial \(C_{adv}\) in at most \(\varepsilon\) nodes in \((2\varepsilon+1)\)-hop neighborhood, then we can transmit \(C\) in the compact form above together with the list of deviations from \(C_{adv}\), which allow the adversarial certificates to be reconstructed. Otherwise, we can return the sketch rejection, since in that case, the adversary must have violated the constraint of \(\varepsilon\) modifications in \((2\varepsilon+1)\)-hop neighborhood for every node. The main challenge is that learning the exact \((2\varepsilon+1)\)-hop neighborhood is too expensive in the CONGEST model. Fortunately, a node do not need the exact structure of the graph to be encoded in the sketch in Section 3.
Instead, each node \(v\) only needs to know, for each certificate sequence \(S\), whether a path through \(v\) whose adversarial certificates match \(S\) exists.6 Consequently, all the paths with the same certificates only need to be represented by a single sequence. In fact, rather than transmitting the list of sequences of certificates, we build a tree that corresponds to a subgraph of \(G\) and contains all the unique sequences of certificates and no other sequence.
The algorithm works in phases \(j=0,\dots,2\varepsilon\). At the start of a \(j\)-th phase, each node \(v\) knows the tree containing information about its \(j\)-hop neighborhood. Each node \(v\) transmits this tree to each neighbor. Similarly, \(v\) receives the trees from each of its neighbor \(u\) – each tree contain information about \(j\) hop neighborhood of \(u\). Node \(v\) then processes these trees to construct a single tree that represents its \(j+1\)-hop neighborhood that can be used in the next phase. There are \(2\varepsilon+1\) phases, each lasting only \(O(\varepsilon)\) CONGEST rounds, for a total of \(O(\varepsilon^2)\) CONGEST rounds. Next we will present more precise description of the algorithm.
4.1 Learning Local Neighborhood Subroutine↩︎
We present the description of a \(j\)-th phase from the perspective of \(v\), ref. to Algorithm [alg:sketch].
4.1.0.1 Preliminaries.
As mentioned in the overview, node \(v\) knows a subtree \(T^v\) of \(G\) and its adversarial certification such that for every sequence of labels \(S\) that occurs on some path \(P\) in \(G\) going through \(v\) and up to \(2\) neighbors of \(v\), possibly with a position \(i\) within the sequence marked for a node with input \(\mathcal{L}\), there exists a path \(P'\) in \(T^v\) with the same sequence of labels going through \(v\) and through the same neighbor(s) of \(v\) with a node marked \(\mathcal{L}\) (if applies) at the specified position \(i\) and vice versa – for every sequence in \(T^v\) there exists a corresponding sequence in \(G\). Furthermore, for each neighbor \(u\) of \(v\), the node \(v\) knows the number \(n_u^v\) of nodes at distance \(j\) from \(v\) whose path to \(v\) passes through \(u\).
In the base case of \(j=0\), each node \(v\) knows the tree \(T^v\) representing its \(0\)-hop neighborhood, namely \(v\) knows itself and its adversarial label \(C_{adv}(v)\). Additionally, \(v\) knows \(n_u^v = 0\) when \(j=0\). Based on \(T^v\), for each neighbor \(u\) of \(v\), node \(v\) prepares new trees \(T_{v \rightarrow u}\) that will be transmitted to \(u\).7 The tree \(T_{v \rightarrow u}\) is guaranteed to be small enough that \(O(\varepsilon)\) CONGEST rounds will suffice to transmit its structure and encode all the certificates on it. An edge \(e\) in tree \(T_{v \rightarrow u}\) may represent an entire path \(P\) in the original tree \(T^v\). The weight \(w(e)\) of edge \(e\) is the number of edges in \(P\). Nodes of \(T_{v \rightarrow u}\) that are not interior to such a compressed path are called explicit.
4.1.0.2 Construction.
Based on the adversarial certificate assignment of tree \(T^v\), node \(v\) searches for an imagined certification \(C'\) of \(T^v\). If no such imagined certification exists, then \(v\) rejects; this is a sketch rejection. Otherwise, \(v\) finds the node \(r\) with the smallest certificate in \(T^v\).
The tree \(T_{v \rightarrow u}\) contains the node \(v\), the neighbor \(u\) of \(v\) with the edge \(\{u,v\}\) (with weight \(1\)), node \(r\) and all the nodes and edges (with weight \(1\) each) between \(v\) and \(r\). Furthermore, we add and connect to tree \(T_{v \rightarrow u}\) each node \(w \in T^v\) such that \(C'(w) \neq C_{adv}(w)\).8
Connecting a node \(u\) to the tree \(T_{v \rightarrow u}\) is done by finding the shortest path \(P\) in \(T^v\) between \(u\) and the nearest node \(w\) represented (explicit or not) in \(T_{v \rightarrow u}\). If \(w\) is explicit in \(T_{v \rightarrow u}\), then we simply add an edge \(e=\{u,w\}\) with weight \(w(e)\) equal to the length of \(P\). If \(w\) is not explicit, then \(w\) lies on a path connecting two explicit nodes in \(T_{v \rightarrow u}\), which is represented by a single edge \(e\) with \(w(e)>1\). In this case we add the node \(w\) to the tree \(T_{v \rightarrow u}\), splitting the edge \(e\), and we connect node \(u\) to node \(w\).
Finally, for each explicit node \(w\), we also store the length \(L_w\) of the longest path from node \(w\) within \(T^v\) that does not have any edges represented in tree \(T_{v \rightarrow u}\). This length \(L_w\) represents a path of nodes \(x\) in \(T^v\) with adversarial certificates \(C_{adv}(x)=C_{adv}(w)+dist(w,x)\). This ends the construction of the tree \(T_{v \rightarrow u}\). In addition to the tree \(T_{v \rightarrow u}\), node \(v\) also sends to each neighbor \(u\) the number \(n_{v \rightarrow u}\) of nodes at distance \(j\) from \(v\) that lie on the side of edge \(\{u,v\}\) that \(v\) is on. The value \(n_{v \rightarrow u}\) is computed as the sum of \(n_w^v\) over all neighbors \(w \neq u\) of \(v\), plus \(1\) to account for node \(v\) itself.
4.1.0.3 Learning the start-of-phase tree.
We now need to show that what a node receives by the end of phase \(j\) is sufficient to build the tree \(T\) it needs in the beginning of phase \(j+1\). We will show that the tree \(T\) we build (i) does not encode any sequence that does not exist in \(G\) and (ii) encodes all sequences that exist in \(G\).
Let us first build \(T\). During phase \(j\), node \(v\) receives trees \(T_{u \rightarrow v}\) from each neighbor \(u\). Each tree \(T_{u \rightarrow v}\) encodes a subtree of the tree \(T^u\) that node \(u\) started phase \(j\) with. Trees \(T^u\) are themselves subtrees of \(G\). Thus, \(v\) can merge trees \(T_{u \rightarrow v}\) into a subtree \(T\) of \(G\).9
Showing (i), i.e., all the sequences encoded in \(T\) are also encoded in \(G\), is trivial. Since \(T\) is a subtree of \(G\), then for every sequence in \(T\) there exists a corresponding sequence in \(G\).
It remains to show (ii), i.e., no sequences in \(G\) were omitted during our construction. Take any sequence \(S\) that corresponds to some path \(P\) in \(G\) passing through \(v\) and two10 neighbors \(u_1,u_2\) of \(v\) such that \(P\) lies within \(j+1\)-hop neighborhood of \(v\). We will show that the sequence \(S\) also occurs in \(T\). We split \(S\) into two subsequences around the position of \(v\): \(S_1\) containing certificates before position of \(v\) and certificate of \(v\) itself and \(S_2\) containing certificates after position of \(v\) and certificate of \(v\) itself. Without loss of generality assume that \(S_1\) contains the position corresponding to \(u_1\) and \(S_2\) contains the position corresponding to \(u_2\).
Notice that subsequence \(S_1\) corresponds to nodes within \(j\)-hop neighborhood of \(u_1\), thus \(S_1\) occurs in \(T^{u_1}\). Now we show that \(S_1\) is encoded in \(T_{u_1 \rightarrow v}\) (proof for \(S_2\) is analogous). Consider path \(P_1\) in \(T^{u_1}\) that corresponds to sequence \(S_1\). If \(P_1\) fully overlaps with some path on \(T_{u_1 \rightarrow v}\), then \(S_1\) is trivially encoded by \(T_{u_1 \rightarrow v}\). Otherwise, path \(P_1\) only partially overlaps with nodes in \(T_{u_1 \rightarrow v}\) and at some point branches off the nodes represented in \(T_{u_1 \rightarrow v}\). Let \(w\) be the furthest node from \(v\) on \(P_1\) that is explicit in \(T_{u_1 \rightarrow v}\). Consider any node \(x\) on \(P_1\) after \(w\), i.e., such that \(dist(x,v)>dist(x,w)\). Notice that \(C_{adv}(x)=C'(x)\) as otherwise \(x\) would be added and connected to the tree \(T_{u_1 \rightarrow v}\). Thus, \(C_{adv}(x)=C'(x)=C'(r)+dist(x,r)=C'(w)+dist(w,x)\), which is represented in \(T_{u_1 \rightarrow v}\) by the length \(L_w \geq dist(w,x)\) of the branch at \(w\). Therefore, there exists a path in \(T_{u_1 \rightarrow v}\) and a length \(L_w\) of the branch at \(w\) that together encode a path corresponding to the sequence \(S_1\).
Thus, when node \(v\) merges \(T_{u_1 \rightarrow v}\) and \(T_{u_2 \rightarrow v}\) (and other trees), it creates a path in \(T\) that corresponds to \(S\), which completes the proof of (ii).
4.2 Round Complexity↩︎
In this section, we calculate how many CONGEST rounds are required to perform all the transmissions described above. Each node \(v\) transmits the tree \(T_{v \rightarrow u}\) and the number \(n_{v \rightarrow u}\) to each neighbor \(u\). The tree \(T_{v \rightarrow u}\) is composed of
path from \(v\) to \(r\), of length at most \(j\) and the label \(C'(r)\)
for every node \(w\) such that \(C_{adv}(w)\neq C'(w)\), we put at most \(2\) nodes and edges in \(T_{v \rightarrow u}\) and we store \(C_{adv}(w)\)
for every explicit node \(w\) in \(T_{v \rightarrow u}\) we store the length of the longest branching from \(w\) that does not go through any edge in \(T_{v \rightarrow u}\)
In total, node \(v\) transmits up to \(N=(j+1)+(2\varepsilon)\) nodes, \(N-1\) edges with their weights, \(1+\varepsilon\) certificates and additional \(N\) numbers (lengths of branches) to transmit the tree \(T_{v \rightarrow u}\). Furthermore, node \(v\) transmits to each neighbor \(u\) the number \(n_{v \rightarrow u}\). In total, \(O(\varepsilon)\) CONGEST messages are sufficient to make all the transmissions in \(j\)-th phase, which proves the round complexity in Theorem 2.
4.3 Decoding the Graph Sketch↩︎
In this section we describe how to obtain the information necessary in Section 3 from our construction. Recall the information we needed:
The number of nodes in \(N_{2\varepsilon+1}(v)\) in \(G\).
For each \(u \in N_1(v)\), the adversarial label \(C_{adv}(u)\) together with the port at \(v\) leading to node \(u\).
For every sequence of certificates \((c_1, c_2, \dots, c_k)\) with \(k \le 4\varepsilon+3\), every pair of positions \(m,j \in \{1, \dots, k\}\), and every pair \(u_1, u_2\) of neighbors of \(v\), the node \(v\) knows whether the sequence is realizable at positions \(m,j\) through \(u_1, u_2\): that is, whether there exists a path \(P = (v_1, v_2, \dots, v_k)\) contained entirely within \(N_{2\varepsilon+1}(v)\) such that (i) \(v\) occupies position \(m\) in \(P\), i.e.\(v = v_m\), (ii) a node \(x\) with input \(\mathcal{L}\) occupies position \(j\) in \(P\), i.e.\(x = v_j\); if such a node does not exist then \(j = \bot\), (iii) \(u_1 = v_{m-1}\) whenever \(m \ge 2\), and \(u_2 = v_{m+1}\) whenever \(m \le k-1\) (the path enters and leaves \(v\) through the specified neighbors), and (iv) the adversarial certificates along \(P\) match the sequence, i.e.\(C_{adv}(v_i) = c_i\) for every \(i\).
After \(2\varepsilon+1\) phases described in Subsection 4.1, each node \(v\) knows a subtree \(T\) of \(G\) and its adversarial certificate assignment such that for every unique sequence of labels \(S\) that occurs on some path \(P\) in \(G\) going through \(v\) and up to \(2\) neighbors of \(v\), possibly with a position \(i\) within the sequence marked for a node with input \(\mathcal{L}\), there exists a path \(P'\) in \(T\) with the same sequence of labels going through \(v\) and through the same neighbor(s) of \(v\) with a node marked \(\mathcal{L}\) (if applies) at the specified position \(i\).
Furthermore, each node \(v\) knows for each of its neighbors \(u\), the number \(n_{u \rightarrow v}\) of nodes at distance \(j\) from \(v\) that have node \(u\) on the path towards \(v\), for every \(1 \leq j \leq 2\varepsilon+1\).
Thus, each node \(v\) can calculate the graph sketch necessary in Section 3:
The number of nodes in Item [item:sketch-number-of-nodes] is the sum of numbers \(n_{u \rightarrow v}\) for all neighbors \(u\) of \(v\) across all the phases.
The adversarial certificate and port number of each neighbor \(u\) of \(v\) in Item [item:sketch-neighbors] was learned in phase \(0\).
The tree \(T^v\) at each node \(v\) known after the last phase11 contains all the same sequences of certificates (with positions of node \(v\), its neighbors and possibly a node with input \(\mathcal{L}\)) as in the original graph \(G\). Thus, each node \(v\) can check for each sequence of certificates (with the positions of respective nodes of interest) in \(T^v\) to know Item [item:sketch-sequence].
\(T^v \gets\) the single node \(v\) with certificate \(C_{adv}(v)\)
\(n_u^v \gets 0\) for every neighbor \(u\) of \(v\)
return \(T^v\) and \(n_u^v\) for each neighbor \(u\) of \(v\) as the encoding of the sketch \(S_G^v\)
5 Proof of Lemma 2↩︎
This section is devoted to the proof of Lemma 2, the one component of the soundness argument (Lemma 3) we deferred. Recall the claim: any two adjacent nodes \(u\) and \(v\), correcting the certificates they read independently and on separate imagined graphs \(G^u\) and \(G^v\), must nonetheless agree on each other’s imagined certificates – \(C_{im}^u(u) = C_{im}^v(u)\) and \(C_{im}^u(v) = C_{im}^v(v)\). This local agreement is exactly what allows the individual imagined certifications to be stitched into a single consistent assignment on \(G\) in the soundness proof.
The major issue is that adjacent nodes \(u\) and \(v\) might reconstruct different imagined trees \(G^u\) and \(G^v\) and choose different imagined certifications \(C_{im}^u\) and \(C_{im}^v\) on them. To relate what \(u\) and \(v\) imagine, we require a common ground, and the following notion of brothers lets you do that by matching paths in \(G^u\) and \(G^v\) to a path in \(G\).
Fix a node \(w\) and let \(P = (v_1, v_2, \dots, v_k)\) be a path in \(G\) that passes through \(w\) lying within \(N_{2\varepsilon+1}(w)\). By item [itm:one] of the sketch, \(G_w\) contains at least one path \(X = (x_1, x_2, \dots, x_k)\) carrying the same certificate sequence, i.e., \(C_{sk}^w(x_j) = C_{adv}(v_j)\) for every \(j\), with \(w\) in the recorded position. We fix one such \(X\) and call it a brother of \(P\) in \(G_w\), and we call \(x_j\) the brother of \(v_j\) for every \(j\). The imagined certification \(C_{im}^w\) assigns a certificate to each \(x_j\) and let \(a_j^w = C_{im}^w(x_j)\) be the certificates that \(w\) imagines along \(P\). The certificates \(a_j^w\) satisfy two properties.
\(a_j^w = C_{adv}(v_j)\) for all but at most \(\varepsilon\) indices \(j\). Indeed, \(X\) lies within \(G_w\), so \(C_{im}^w\) differs from \(C_{sk}^w\) on at most \(\varepsilon\) of its nodes and \(C_{sk}^w(x_j) = C_{adv}(v_j)\) by construction of \(X\).
Under \(C_{im}^w\), every node within \(2\varepsilon\) hops from \(w\) in \(G_w\) accepts according to \(\mathcal{A}_0\). This covers all of \(x_1, \dots, x_k\) except possibly the two endpoints \(x_1\) and \(x_k\), which may fall outside \(N_{2\varepsilon}(w)\).
We make the notion of brother symmetric and transitive, i.e., (i) if \(P_u\) in \(G^u\) is a brother of \(P\) in \(G\), then \(P\) is also a brother of \(P_u\), and (ii) if \(P_1\) is a brother of \(P_2\) and \(P_2\) is a brother of \(P_3\), then \(P_1\) is a brother of \(P_3\). This lets us relate paths across two different imagined trees \(G^u\) and \(G^v\), i.e., if \(X_u\) in \(G^u\) and \(X_v\) in \(G^v\) are both brothers of the same path \(P\) of \(G\), they are brothers of each other. We extend this relation to nodes, i.e., if \(P\) and \(P'\) are brothers, then the \(j\)-th node of \(P\) and the \(j\)-th node of \(P'\) are brothers too, for every \(j\).
Remark 1. Every path \(P_u\) through \(u\) in \(G^u\) has a brother in (original tree) \(G\) and a brother in \(G^v\) for every \(v \neq u\). Similarly, any node \(w\) in \(G^u\) must have at least one brother in the original tree \(G\) and at least one brother in \(G^v\) for every \(v \neq u\).
See Figure 2 for an illustration. Notice that there is no one-to-one relation between a path in \(G\) and a path in \(G_v\), nor between a node in \(G\) and a node in \(G_v\).
With brothers in hand, we can compare what different nodes imagine.
The proof of Lemma 2 combines two things. The first is a property of certifications accepted by \(\mathcal{A}_0\), which is a distance labeling from its unique smallest-certificate node, its root, so that once the root is located, every certificate is determined by a distance to it. The second is the uniqueness of accepting certification along a path with fixed endpoints (Claim 1), which allows us to transfer agreement from a few matched positions to the entire path. We first establish this claim, then prove the lemma by case analysis.
Remark 2 (Acceptable certification). Under any certificate assignment function \(C'\) acceptable by \(\mathcal{A}_0\), each node \(v\) with certificate \(C'(v)\) must have at most12 one adjacent node with certificate \(C'(v)-1\) and all other neighbors must have certificate \(C'(v)+1\).
Remark 2 follows directly from the description of the base algorithm \(\mathcal{A}_0\).
Claim 1.
Consider a path \(P = (v_0, v_1, \ldots, v_k)\) and any fixed \(a,b \in \mathbb{N}\cup \{0\}\). Then, there is at most one certificate assignment function \(C\) on \(P\) such that \(C(v_0) = a\), \(C(v_k) = b\), under which every node of \(P\) accepts according to \(\mathcal{A}_0\).
Proof of Claim 1. If no accepting certification with the prescribed endpoints exists, then the claim holds trivially, so assume at least one does, and we show that it is unique. We argue by induction on the path length \(k\).
Inductive hypothesis \(H(k')\) for \(1 \leq k'<k\): For any \(a',b' \in \mathbb{N}\cup \{0\}\), for any path \(P'\) of length \(k'\) with endpoint nodes assigned the certificates \(a'\) and \(b'\), there exists at most one certificate assignment function \(C\) under which every node on \(P'\) accepts according to the algorithm \(\mathcal{A}_0\).
Base case \(H(1)\): A path \((u_0, u_1)\) with fixed endpoint labels \(C(u_0) = a'\) and \(C(u_1) = b'\) either satisfies the acceptance conditions of \(\mathcal{A}_0\) or not. In either case, at most one certificate assignment function exists. Thus \(H(1)\) holds.
Inductive step (\(H(k') \Rightarrow H(k'+1)\)): Let \(P'=(u_0,u_1,\dots,u_{k'+1})\) be a path of length \(k'+1\) with endpoint certificates \(a',b'\) where \(a' \neq 0\) or \(b' \neq 0\). If no proof satisfies these constraints while making all nodes accept under \(\mathcal{A}_0\), then \(H(k'+1)\) holds trivially.
Otherwise, let \(C'\) be such a certificate assignment function on \(P'\) and let \(m = \max\{C'(u_0),\dots,\) \(C'(u_{k'+1})\}\). We show that no internal node \(u_j\) (\(1 \leq j \leq k'\)) can have certificate \(m\). Suppose \(C'(u_j) = m\) for some \(1 \leq j \leq k'\). By Remark 2, node \(u_j\) requires at most \(1\) neighbor with the certificate \(m-1\) and all others with \(m+1\). But both neighbors \(u_{j-1}\) and \(u_{j+1}\) satisfy \(C'(u_{j-1}) \leq m\) and \(C'(u_{j+1}) \leq m\) by maximality, so neither has the certificate \(m+1\), which contradicts Remark 2. Therefore, no internal node of \(P'\) can have the certificate \(m\).
Consequently, \(m\) appears only at endpoints of \(P'\). Without loss of generality, let \(C'(u_0)=m=a'\). Remark 2 forces \(C'(u_1) \in \{m-1, m+1\}\), and by maximality \(C'(u_1) = m-1 = a'-1\). Deleting \(u_0\) leaves the path \((u_1, \dots, u_{k'+1})\) of length \(k'\) with fixed endpoint certificates \(a'-1\) and \(b'\). By \(H(k')\) applied to \((u_1, \dots, u_{k'+1})\) with endpoint labels \(a'-1\) and \(b'\), at most one proof of this subpath exists. Hence, at most one proof on \(P'\) exists, establishing \(H(k'+1)\).
This completes the proof of Claim 1. ◻
We are now ready to prove Lemma 2.
Proof of Lemma 2. Let \(T_u\) denote the subgraph of \(G^u\) induced by the nodes that are \(2\varepsilon+1\) hops away from both \(u\) and \(v\), i.e., \(N_{2\varepsilon+1}(u) \cap N_{2\varepsilon+1}(v)\) in \(G^u\). If a node \(w \in T_u\) is exactly \(2\varepsilon+1\) hops away from either \(u\) or \(v\), then \(w\) is called an outer node, otherwise \(w\) is an inner node. Let node \(r_u \in T_u\), called root, be the node with the smallest imagined certificate, i.e., \(C_{im}^u(r_u) = \min_{w \in T_u}C_{im}^u(w)\).1314 We define analogously \(T_v\) as a subgraph of \(G^v\), inner and outer nodes in \(T_v\), and a root node \(r_v\) in \(T_v\).
Remark 3. If \(r_u\) is a root of \(T_u\), then for any node \(w \in T_u\) we have \(C_{im}^u(w)=C_{im}^u(r_u)+dist(r_u,w)\).
The remark above follows immediately from the fact that an imagined certification is accepted by \(\mathcal{A}_0\), which means that the certificates increase by \(1\) with each hop away from the leader.
We consider the following cases:
Case 1: \(r_u\) is an inner node
Case 2: \(r_u\) is an outer node
Case 1: Since \(r_u\) has the smallest certificate in \(T_u\), then \(r_u\) does not have a parent in \(T_u\). The only nodes without parents in an acceptable certification must have certificate \(0\), so \(C_{im}^u(r_u)=0\). It follows that \(C_{im}^u(u)=dist(r_u,u)\) and \(C_{im}^u(v)=dist(r_u,v)\).
If a node in an acceptable certification has label \(0\), then it must be the leader – in this case, it means that node \(r_u\) corresponds to the \(\mathcal{L}\) position in some sequence of certificates in the graph sketch. Thus, according to Remark 1, \(r_u\) is a brother of a node \(r\) in \(G\) such that \(r\) received input \(\mathcal{L}\).
Furthermore, \(r_u\) has a brother \(w\) in \(G^v\) in the same position relative to nodes \(u\) and \(v\), so \(w\) is also an inner node in \(T_v\). Since \(w\) is a brother of \(r_u\), then it corresponds to the \(\mathcal{L}\) position, thus \(C_{im}^v(w)=0\). Again, we get that \(C_{im}^v(u)=dist(w,u)\) and \(C_{im}^v(v)=dist(w,v)\). Since \(w\) and \(r_u\) occupy the same position in the corresponding sequence of labels in the graph sketch, then they are at the same distance from \(u\) and they are at the same distance from \(v\). Thus, \(C_{im}^u(u)=dist(r_u,u)=dist(w,u)=C_{im}^v(u)\) and \(C_{im}^u(v)=dist(r_u,v)=dist(w,v)=C_{im}^v(v)\), which proves the lemma in this case.
Case 2: In this case, let us fix a path \(P_u\) in \(T_u\) that starts in \(r_u\) and ends in \(u\) or \(v\) (whichever is further). Notice that \(P_u\) contains \(2\varepsilon+2\) nodes.15 According to Remark 1, the path \(P_u\) has a brother \(P_v\) in \(G^v\). Since they are brothers, they correspond to the same sequence \(S\) of sketch labels.16 Node \(u\) modified up to \(\varepsilon\) labels in \(S\) to obtain \(C_{im}^u\) on \(P_u\) and node \(v\) modified up to \(\varepsilon\) labels in \(S\) to obtain \(C_{im}^v\) on \(P_v\). In total up to \(2\varepsilon\) modifications were introduced to \(S\) out of \(2\varepsilon+2\) labels in \(S\). Thus, there are at least \(2\) nodes \(u_1,u_2 \in P_u\) with unchanged labels that have brothers \(v_1,v_2 \in P_v\) also with unchanged labels, i.e., \(C_{im}^u(u_1)=C_{sk}^u(u_1)=C_{sk}^v(v_1)=C_{im}^v(v_1)\) and \(C_{im}^u(u_2)=C_{sk}^u(u_2)=C_{sk}^v(v_2)=C_{im}^v(v_2)\).
According to Remark 3, since \(r_u\) has the smallest label on \(P_u\), we get that \(C_{im}^u(x)=C_{im}^u(r_u)+dist(r_u,x)\) for all \(x \in P_u\). In particular, \(C_{im}^u(u_1)=C_{im}^u(r_u)+dist(r_u,u_1)\) and \(C_{im}^u(u_2)=C_{im}^u(r_u)+dist(r_u,u_2)\). Their brothers \(v_1\) and \(v_2\) in \(P_v\) have the same labels and positions as \(u_1\) and \(u_2\) in \(P_u\). Without loss of generality assume \(u_1\) is closer than \(u_2\) to \(r_u\). Thus, \(C_{im}^v(v_1) = C_{im}^u(u_1) < C_{im}^u(u_2)= C_{im}^v(v_2)\). According to Claim 1, there is at most one acceptable certificate assignment function of nodes on the subpath \(P_v' \subseteq P_v\) that starts in \(v_1\) with label \(C_{im}^v(v_1)\) and ends in \(v_2\) with label \(C_{im}^v(v_2)\). Notice that the certificate assignment function \(C_{im}^v\) on the nodes starting from \(v_1\), through \(v_2\) and ending at \(u\) or \(v\) (whichever is further) must be the same as the certificate assignment function \(C_{im}^u\) on the brothers of those nodes in \(P_u\). In particular, \(C_{im}^u(u)=C_{im}^v(u)\) and \(C_{im}^u(v)=C_{im}^v(v)\), which proves the lemma in this case.
In both cases, the lemma follows. ◻
6 Future Works and Concluding Remarks↩︎
We initiated the study of error-resilient local verification in the bandwidth-restricted Congest model, using unique-leader on trees as a first testbed. Our central message is that
error-resilience does not require a node to reconstruct its full \((2\varepsilon+1)\)-hop neighborhood: a compact \(O(\varepsilon^2\log n)\)-bit local graph sketch captures exactly
the information the verifier consumes, letting each node decide via refix-leader after only \(O(\varepsilon^2)\) rounds of sketch-construction.
The most immediate open direction is to generalize beyond trees to arbitrary graphs. The obstacle is cycles: as illustrated in Figure 3, when two neighbors \(v\) and \(x\) each report information about a common node \(w\) to \(u\), node \(u\) cannot tell whether the two images refer to the same node, and transmitting node identifiers to disambiguate is too costly in Congest. Resolving this identity ambiguity within the sketch framework is the key challenge for the general case. In fact, a larger graph can be constructed to generalize this difficulty. The compression technique can be modified to distinguish nodes based on their IDs.
More broadly, we believe the local graph sketch technique—and the accompanying notions of imagined trees and imagined certifications—are of independent interest. Summarizing a neighborhood compactly enough to compute on it, without learning its exact structure, is a natural primitive for communication-efficient, error-resilient certification, and we expect these ideas to extend to other fundamental verification problems (cycle-freeness, spanning trees, and beyond) as well as to the advice/prediction model, where auxiliary information may likewise be imperfect.
| Variable | Description |
|---|---|
| \(u,v, \dots, y\) | Node variables (possibly with superscripts and subscripts) |
| \(a,b,c\) | Certificate variables (possibly with superscripts and subscripts) |
| \(C\) | Certificate assignment function (possibly with superscripts and subscripts) |
| \(i,j,k\) | Index variables |
| \(T\) | Tree variable (possibly with superscripts and subscripts) |
| \(P\) | Path variable (possibly with superscripts and subscripts) |
| \(S\) | Set or Sequence (of certificates) variable (possibly with superscripts and subscripts) |
| \(\mathcal{A}\) | Verifier (possibly with superscripts and subscripts) |
Acknowledgment:↩︎
This work is supported by Polish National Science Centre project no./39/B/ST6/03288.
References↩︎
pgarn@cs.uni.wroc.pl↩︎tju@cs.uni.wroc.pl↩︎darek.liv@gmail.com↩︎suvo.iitg17@gmail.com↩︎In some of the previous works, this certificate assignment function is also called a proof on \(G\).↩︎
For the clarity of presentation, in this paragraph we omit that the position of node \(v\), its two neighbors, and possibly the position of the leader are also recorded with each sequence of labels.↩︎
The trees sent to different neighbors will be almost identical. Thus, this part can be adapted to using broadcast messages, with very little overhead caused by the small differences.↩︎
Connecting this node may add an edge with weight greater than \(1\).↩︎
Since positions of \(v\) and \(u\) are marked in each \(T_{u \rightarrow v}\), then parts of the trees that overlap are correctly merged.↩︎
A path passing through only \(1\) neighbor of \(v\) is analyzed analogously.↩︎
It may be convenient to think it is the tree known at the start of phase \(2\varepsilon+1\), i.e., an artificial phase after the last phase.↩︎
If \(C'(v)=0\), then there is no parent.↩︎
The root of \(T_u\) does not have to be the leader. There may be no leader inside \(T_u\), but \(T_u\) still has the node with the smallest certificate and the certificate may be greater than \(0\).↩︎
There is exactly \(1\) such node \(r_u\). If there were multiple such nodes \(r_u\) and \(r_u'\), then somewhere on the path between them there would be a node \(w\) that either has \(2\) parents or that is adjacent to a node with the same label; in either case the node \(w\) rejects according to \(\mathcal{A}_0\), which contradicts our assumption that \(C_{im}(u)\) is an imagined certification (imagined certification must be accepted by \(\mathcal{A}_0\)).↩︎
By definition of an inner node, \(r_u\) is at distance \(2\varepsilon+1\) from \(u\) or \(v\). Together with the node \(u\) or \(v\), this constitutes a path of length exactly \(2\varepsilon+2\).↩︎
Note that the brother \(w\) in \(P_v\) of root \(r_u\) in \(P_u\) does not necessarily have to be the root in \(P_v\). They have the same sketch labels, but their imagined labels may differ significantly.↩︎