Short Graph Sketches Suffice for Error-resilient Leader Verification in CONGEST Pawel Garncarek1∗, Tomasz Jurdziński1†, Dariusz Kowalski2‡, Subhajit Pramanick1§ 1
Institute of Computer Science, University of Wroclaw, Poland 2 Department of Computer Science, Augusta University, USA
Abstract
arXiv:2607.09522v1 [cs.DC] 10 Jul 2026
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 ε certificate errors requires each node to reason about its (2ε + 1)-hop neighborhood, whose exact topology cannot, in the worst case, be communicated efficiently in Congest – reconstructing it naively costs up to O(∆2ε+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(ε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 ε adversarial certificate errors and computes the required sketches in O(ε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 ε can tolerate ε adversarial errors. Since LOCAL is strictly stronger than CONGEST, this lower bound carries over immediately, showing that a view distance beyond ε – and hence the wider neighborhood our algorithm summarizes – is unavoidable. Keywords: Verification problem, Leader election, Locally Checkable Proof, Local Certification, Error-resilience, CONGEST Model.
∗
[email protected] [email protected] ‡ [email protected] § [email protected] †
1
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 [26]. 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 [23] 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 [11] consolidates these notions. This framework on local verification has been extended in various directions, including PLSs with restricted provers [9], randomized [3] and quantum PLSs [18], PLSs with global proofs in addition to local ones [15], and many more. The model underlying this long line of work is the well-known LOCAL model [29], in the sense that a verifier with a view distance k can be implemented in k synchronous communication rounds (see [23] 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 [6, 12, 19, 20, 21]. The certificate size depends on the property being verified. Constant-size is known for several problems [23], 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, 5, 10, 13, 14, 15, 16, 17, 23, 28]. 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 [25] and O(n log n) bits for diameter k verification by Censor-Hillel, Paz and Perry [8]. 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 2
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 [4, 7, 27]. This direction has recently attracted considerable attention across several research communities. In fact, Boyar, Ellen, and Larsen in [7] 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. 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 ε 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(∆k log n) bits of information, which in CONGEST model, requires round complexity up to O(∆k ) in the worst case (∆ is the maximum degree). The central challenge of this work is to verify the desired property correctly using substantially smaller O(ε2 log n) information than this naive O(∆k log n) bound.
1.2
Our Model and Definitions
Graphs. A graph G(V, E) in our consideration is a tree with |V | = n nodes. For a node v, we use the notation Nk (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 Nk (v) has ≤ 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, . . . , 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, . . . , 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. Local Verification with Certificates. A convenient way to describe the verification process is through a prover-verifier paradigm. The prover gives a certificate assignment 1 C on a graph G, which is a function C : V → {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 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 ∈ G, let G[Nk (v)] be the subgraph induced by the nodes in Nk (v) and C[Nk (v)] : Nk (v) → {0, 1}∗ be the restriction 1
In some of the previous works, this certificate assignment function is also called a proof on G.
3
of C to Nk (v). A verifier A is called a local verifier if there exists a k such that A(G, L, v) = A(G[Nk (v)], L[Nk (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 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 P admits a locally checkable proof labeling scheme if there is a prover-verifier pair (f, A), where the prover f gives a certificate assignment function C for each G ∈ P and A is a local verifier (with a view distance k) such that the following two properties hold. Completeness: If G ∈ P, there should be a certificate assignment function C on G provided by the prover f (i.e., f (G) = C) such that A(G[Nk (v)], C[Nk (v), v]) = 1 for all v. Soundness: If G ∈ / P, then for every certificate assignment C on G, there must be at least one node v such that A(G[Nk (v)], C[Nk (v)], v) = 0. For our convenience, we say that the node v accepts (resp. rejects) when the verifier A outputs 1 (resp. 0). We emphasize the fact that when G does not satisfy the property P, there must exist at least one rejecting node for any certificate assignment function. 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 CO and the corresponding verifier by A0 . We refer to the pair (CO , A0 ) 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 ∈ / P or some nodes to reject when G ∈ P. We represent the certificate assignment function after the adversarial modification by Cadv . In our paper, we assume that Cadv differs from CO in at most ε nodes within N2ε+1 (v) for every node v, i.e., the adversary is allowed to introduce at most ε modifications within the (2ε + 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 ∈ P, there is a certificate assignment CO on G such that for every Cadv differing from CO in at most ε nodes within N2ε+1 (v) for every node v, we have A(G[Nk (v)], Cadv [Nk (v)], v) = 1 for all v. In this setting, we refer to the pair (Cadv , 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 [16, 23]. 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 4
gets L, and the rest of the nodes get N . In this paper, we study the property P = 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 L. An instance is a noinstance whenever either no node or more than one node is assigned input bit L. We say that a scheme (C, A) solves unique-leader if both completeness and soundness are satisfied. Warm-up: unique-leader in Oracular Setting. It is straightforward to verify uniqueleader using the following known scheme, which we mention briefly. The certificate assignment function CO (v) = 0 if v is the node with the input bit 1 (leader). For any other node v (non-leader), CO (v) is the breadth-first search (BFS) distance to the leader. We use A0 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 CO (v) − 1, while every other neighbor, namely its children, has certificate CO (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 CO (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 A0 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 [23]. We refer to A0 as the base verification algorithm henceforth (when ε = 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 ε errors, even if ε 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ε 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 ε-hop neighborhood may need Ω(∆ε ) rounds. Our positive results circumvent this problem. We present an algorithm that requires nodes to learn the certificates of nodes within their 2ε + 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ε+1-hop neighborhood in a compact form that a node can learn in O(ε2 ) CONGEST round. The construction is given as sketch-construction() (Algorithm 2) 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 ε certificates under which the errorfree 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,
5
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 [1, 22, 24]; 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 ε nodes in the entire graph (rather than within the neighborhood of every node, which would allow for more than ε errors in the entire graph distributed among multiple neighborhoods). Theorem 1. In adversarial setting, there is no scheme (Cadv , A) solving unique-leader on arbitrary trees with ε errors in which the verifier A has view distance at most ε even if certificates are allowed to have an unbounded size. Proof. Assume for the sake of contradiction that such a scheme (Cadv , A) exists, where A has view distance ε. By error-resilient completeness, for every yes-instance, there is an oracular certificate assignment CO under which every node accepts, and continues to accept under every assignment obtained by modifying at most ε certificates within the ε-hop neighborhood of each node. The yes-instance. Let GY = (v0 , v1 , . . . , v4ε+2 ) be a path on 4ε + 3 nodes, where v0 is the unique leader (input bit L). By completeness, fix an oracular certificate assignment CO under which every node of GY accepts and keeps accepting under any admissible adversarial modification. For 0 ≤ j ≤ 4ε + 2, let cj = CO (vj ). 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 ′ on G′ such that views of v and v ′ exists a tree G′ , a node v ′ ∈ G′ and an oracular certification CO are identical in tree structure and input bits, and the certification within the view of v differs in ′ on nodes within the view of v ′ . By error-resilient completeness, node v at most ε nodes from CO must accept if it has a yes-view. The no-instance. Let GN = (u0 , u1 , . . . , u4ε+2 ) be a path on the same number of nodes, but with two leaders: u0 and u4ε+2 have input bits L, and every other node has input bit N . We now define a certificate assignment C on GN by copying CO inward from each end, reflected about the midpoint (central node u2ε+1 ) of the path: C(uj ) = cmin{j, 4ε+2−j} , where 0 ≤ j ≤ 4ε + 2 Fix a node um . If m ≤ 2ε + 1, then we compare um ∈ GN and vm ∈ GY ; otherwise we compare u4ε+2−m ∈ GN and vm ∈ GY . These cases are analogous, so we present only the case for m ≤ 2ε+1. 6
We show that um has a yes-view by comparing it to the view of vm under the oracular certification CO . The view of um consists of the nodes umax{0,m−ε} , . . . , umin{4ε+2,m+ε} , and likewise the view of vm consists of vmax{0,m−ε} , . . . , vmin{4ε+2,m+ε} . Since m ≤ 2ε + 1, the largest index appearing in either view is m + ε ≤ 3ε + 1 < 4ε + 2. Hence, neither view reaches the right endpoint of the path. In particular, the right leader u4ε+2 of GN never lies in um ’s view. The two views thus span the same range of indices and have the same path structure. Moreover, if m ≥ ε + 1, neither view contains index 0, so neither contains a leader. If m ≤ ε, both views contain index 0 and no other leader index, and u0 ∈ GN and v0 ∈ GY 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(uj ) = cj = CO (vj ) for all j ≤ 2ε + 1, so a difference can occur only at an index j > 2ε + 1. But um ’s view reaches only up to index m + ε, and since m ≤ 2ε + 1, it contains at most (m + ε) − (2ε + 2) + 1 = m − ε − 1 ≤ ε indices above 2ε + 1. Hence, the two views differ in at most ε certificates, so um has a yes-view and A makes um accept. Consequently A accepts at every node of GN , even though GN has two leaders and is a noinstance 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 ε + 1 to decide correctly. The algorithm we develop in this section requires a view distance of 2ε + 1. One of the main challenges here is due to CONGEST – how can a node learn about its 2ε + 1-hop neighborhood within poly(ε) rounds? We split the task into two logical parts. The first is learning the neighborhood: rather than reconstructing the exact (2ε + 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 ε corrections of a certification that the base algorithm A0 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
v , from which a node v obtains the following information. Although We begin with a graph sketch SG the sketch (of a particular size) may encode additional information, we list only the information required by our algorithm.
1. The number of nodes in N2ε+1 (v) in G. 2. For each u ∈ N1 (v), the adversarial label Cadv (u) together with the port at v leading to node u.
7
3. For every sequence of certificates (c1 , c2 , . . . , ck ) with k ≤ 4ε + 3, every pair of positions m, j ∈ {1, . . . , k}, and every pair u1 , u2 of neighbors of v, the node v knows whether the sequence is realizable at positions m, j through u1 , u2 : that is, whether there exists a path P = (v1 , v2 , . . . , vk ) contained entirely within N2ε+1 (v) such that (i) v occupies position m in P , i.e. v = vm , (ii) a node x with input L occupies position j in P , i.e. x = vj , (iii) u1 = vm−1 whenever m ≥ 2, and u2 = vm+1 whenever m ≤ k − 1 (the path enters and leaves v through the specified neighbors) and (iv) the adversarial certificates along P match the sequence, i.e. Cadv (vi ) = ci for every i. The procedure by which a node constructs (or obtains) the graph sketch of its N2ε+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. v denote the graph sketch that node v obtains in G – which Definition 1 (Imagined Tree). Let SG v if, captures only part of N2ε+1 (v). A tree Gv for the node v is an imagined tree consistent with SG v. under the same graph sketching procedure, the sketch that v obtains in Gv equals SG
Notice that 2 neighboring nodes u, v may imagine different imagined trees Gu , Gv . 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 N2ε+1 (v) in G is one imagined tree, and in general, there may be v need not determine the neighborhood uniquely. However, Gv and N several, since SG 2ε+1 (v) in G have the same number of nodes, as the sketch encodes the number of nodes in N2ε+1 (v). Each imagined tree carries certificates that the node actually reads and uses to make further decisions. v . The Definition 2 (Sketch Certificates). Consider an imagined tree Gv consistent with SG v . certificate assignment that Gv carries is called the sketch certificate assignment and denoted Csk v v The value Csk (u) is the sketch certificate of node u in G .
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 Gv . v on the nodes of Gv is called Definition 3 (Imagined Certificates). For node v, a function Cim v an imagined certificate assignment function, if Cim is the certificate assignment function that causes v differs from C v to accept, i.e., Cim adv in at most ε nodes within N2ε+1 (v) and the base algorithm v . To refer to this, we sometimes say that v A0 makes all nodes within N2ε (v) accept using Cim v imagines Cim (this is local from a node’s perspective and may not extend to a global one).
In words, v considers every imagined tree Gv consistent with its sketch, and in each one searches for an imagined certification, i.e., an override of the certificates of at most ε nodes within its 2ε + 1hop neighborhood under which A0 makes every node accept throughout N2ε (v). If some imagined tree admits such a certification, v accepts; otherwise, it rejects. If the adversary introduced at most ε errors, then the actual N2ε+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 N2ε (v) (rather than N2ε+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 A0 , and nodes on the boundary N2ε+1 (v) \ N2ε (v) may have neighbors whose labels are unknown to v (and hence it cannot be sure about their decision). 8
v , ε) for node v Algorithm 1: refix-leader(A0 ,SG v do 1 foreach imagined tree Gv consistent with SG v on Gv differing from C v in at most ε nodes within 2 foreach certificate assignment Cim sk 3 4
N2ε+1 (v) do v then if all nodes within N2ε (v) accept according to A0 under Cim halt and accept
5 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 Cadv verifies unique-leader in O(ε2 ) CONGEST rounds, even when Cadv differs from CO in at most ε nodes within N2ε+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 u and C v on them. We begin with Gu and Gv and choose different imagined certifications Cim im 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 Cadv that differs from CO in at most ε nodes within N2ε+1 (v). Proof. This is quite straightforward. For an arbitrary node v, consider the imagined tree to be the exact neighborhood N2ε+1 (v) of G itself, which is consistent with v’s sketch. On it, we take the certificate assignment function CO restricted to N2ε+1 (v). Under CO , every node accepts according to the algorithm A0 , so in particular, all nodes within N2ε (v) accept. This proves the lemma. This settles completeness. For soundness, suppose G does not have a unique leader, yet, for v contradiction, refix-leader makes every node accept. Then each v imagines a certification Cim on some imagined tree Gv . 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 Gu and Gv and certifications u and C v respectively (recall Definition 1-3). Then C u (u) = C v (u) and C u (v) = C v (v). Cim im im im im im 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 Cadv = CO , 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 on some imagined tree Gv . Define a certificate assignment C on G v imagines a certification Cim v by C(v) = Cim (v) for each node v, i.e., every node receives the certificate it imagines for itself. We 9
9 5 7
8 6
7
7
9 v
8
8 9
9 9
9
Figure 1: An example graph with constructed acceptable certificates C ′ , from the perspective on node v (at the center). The dotted lines represent edges that v does not know about. In this case, the root rv will be the node with certificate C ′ (rv ) = 5 and every node w must have certificate C ′ (w) = C ′ (rv ) + dist(rv , w) to match the root. show that A0 makes every node of G accept under C. Fix a node v. Since refix-leader makes it v , the base algorithm A must make every node within N (v) of Gv accept under accept using Cim 0 2ε v v (u) = C u (u) = C(u). Thus C agrees Cim . By Lemma 2, for every neighbor u of v we have Cim im v on all of N (v). As A inspects only N (v) to decide for v, and it makes v accept under with Cim 1 0 1 v , it also makes v accept under C. Hence, A accepts every node of G under C, but A is a Cim 0 0 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(ε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 A0 makes every node accept. Overview: Notice that an acceptable certification on a (2ε + 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 Cadv in at most ε nodes in (2ε + 1)-hop neighborhood, then we can transmit C in the compact form above together with the list of deviations from Cadv , 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 10
of ε modifications in (2ε + 1)-hop neighborhood for every node. The main challenge is that learning the exact (2ε + 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.2 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, . . . , 2ε. 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ε + 1 phases, each lasting only O(ε) CONGEST rounds, for a total of O(ε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 2. 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 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 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 nvu 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 Cadv (v). Additionally, v knows nvu = 0 when j = 0. Based on T v , for each neighbor u of v, node v prepares new trees Tv→u that will be transmitted to u.3 The tree Tv→u is guaranteed to be small enough that O(ε) CONGEST rounds will suffice to transmit its structure and encode all the certificates on it. An edge e in tree Tv→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 Tv→u that are not interior to such a compressed path are called explicit. 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 Tv→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 2 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. 3 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.
11
and connect to tree Tv→u each node w ∈ T v such that C ′ (w) ̸= Cadv (w).4 Connecting a node u to the tree Tv→u is done by finding the shortest path P in T v between u and the nearest node w represented (explicit or not) in Tv→u . If w is explicit in Tv→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 Tv→u , which is represented by a single edge e with w(e) > 1. In this case we add the node w to the tree Tv→u , splitting the edge e, and we connect node u to node w. Finally, for each explicit node w, we also store the length Lw of the longest path from node w within T v that does not have any edges represented in tree Tv→u . This length Lw represents a path of nodes x in T v with adversarial certificates Cadv (x) = Cadv (w) + dist(w, x). This ends the construction of the tree Tv→u . In addition to the tree Tv→u , node v also sends to each neighbor u the number nv→u of nodes at distance j from v that lie on the side of edge {u, v} that v is on. The value nv→u is computed as the sum of nvw over all neighbors w ̸= u of v, plus 1 to account for node v itself. 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 Tu→v from each neighbor u. Each tree Tu→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 Tu→v into a subtree T of G.5 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 two6 neighbors u1 , u2 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: S1 containing certificates before position of v and certificate of v itself and S2 containing certificates after position of v and certificate of v itself. Without loss of generality assume that S1 contains the position corresponding to u1 and S2 contains the position corresponding to u2 . Notice that subsequence S1 corresponds to nodes within j-hop neighborhood of u1 , thus S1 occurs in T u1 . Now we show that S1 is encoded in Tu1 →v (proof for S2 is analogous). Consider path P1 in T u1 that corresponds to sequence S1 . If P1 fully overlaps with some path on Tu1 →v , then S1 is trivially encoded by Tu1 →v . Otherwise, path P1 only partially overlaps with nodes in Tu1 →v and at some point branches off the nodes represented in Tu1 →v . Let w be the furthest node from v on P1 that is explicit in Tu1 →v . Consider any node x on P1 after w, i.e., such that dist(x, v) > dist(x, w). Notice that Cadv (x) = C ′ (x) as otherwise x would be added and connected to the tree Tu1 →v . Thus, Cadv (x) = C ′ (x) = C ′ (r) + dist(x, r) = C ′ (w) + dist(w, x), which is represented in Tu1 →v by the length Lw ≥ dist(w, x) of the branch at w. Therefore, there exists a path in Tu1 →v and a length Lw of the branch at w that together encode a path corresponding to the sequence S1 . 4
Connecting this node may add an edge with weight greater than 1. Since positions of v and u are marked in each Tu→v , then parts of the trees that overlap are correctly merged. 6 A path passing through only 1 neighbor of v is analyzed analogously. 5
12
Thus, when node v merges Tu1 →v and Tu2 →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 Tv→u and the number nv→u to each neighbor u. The tree Tv→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 Cadv (w) ̸= C ′ (w), we put at most 2 nodes and edges in Tv→u and we store Cadv (w) • for every explicit node w in Tv→u we store the length of the longest branching from w that does not go through any edge in Tv→u In total, node v transmits up to N = (j + 1) + (2ε) nodes, N − 1 edges with their weights, 1 + ε certificates and additional N numbers (lengths of branches) to transmit the tree Tv→u . Furthermore, node v transmits to each neighbor u the number nv→u . In total, O(ε) 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: 1. The number of nodes in N2ε+1 (v) in G. 2. For each u ∈ N1 (v), the adversarial label Cadv (u) together with the port at v leading to node u. 3. For every sequence of certificates (c1 , c2 , . . . , ck ) with k ≤ 4ε + 3, every pair of positions m, j ∈ {1, . . . , k}, and every pair u1 , u2 of neighbors of v, the node v knows whether the sequence is realizable at positions m, j through u1 , u2 : that is, whether there exists a path P = (v1 , v2 , . . . , vk ) contained entirely within N2ε+1 (v) such that (i) v occupies position m in P , i.e. v = vm , (ii) a node x with input L occupies position j in P , i.e. x = vj ; if such a node does not exist then j = ⊥, (iii) u1 = vm−1 whenever m ≥ 2, and u2 = vm+1 whenever m ≤ k − 1 (the path enters and leaves v through the specified neighbors), and (iv) the adversarial certificates along P match the sequence, i.e. Cadv (vi ) = ci for every i. After 2ε + 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 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 L (if applies) at the specified position i. Furthermore, each node v knows for each of its neighbors u, the number nu→v of nodes at distance j from v that have node u on the path towards v, for every 1 ≤ j ≤ 2ε + 1. Thus, each node v can calculate the graph sketch necessary in Section 3:
13
1. The number of nodes in Item 1 is the sum of numbers nu→v for all neighbors u of v across all the phases. 2. The adversarial certificate and port number of each neighbor u of v in Item 2 was learned in phase 0. 3. The tree T v at each node v known after the last phase7 contains all the same sequences of certificates (with positions of node v, its neighbors and possibly a node with input 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 3.
Algorithm 2: sketch-construction(ε) at node v 1 T v ← the single node v with certificate Cadv (v) 2 nv u ← 0 for every neighbor u of v 3 for j = 0 to 2ε do 4 find a certificate assignment C ′ on T v differing from the adversarial certificates of T v
on at most ε nodes, under which A0 makes every node of T v accept if no such C ′ exists then halt and reject (sketch rejection); r ← the node of T v with the smallest certificate under C ′ foreach neighbor u of v do Tv→u ← the path from v to r in T v , plus u with the edge {u, v}, each edge of weight 1 foreach node x of T v with C ′ (x) ̸= Cadv (x) do y ← the nearest node to x represented in Tv→u ; if needed, make y explicit, splitting its weighted edge add x and the edge {x, y} with weight distT v (x, y); store Cadv (x)
5 6 7 8
9 10
11
foreach explicit node w of Tv→u do store the length of the longest path of T v from w avoiding the edges of Tv→u P send Tv→u , nv→u = 1 + w̸=u nvw to u
12 13 14
receive a tree and a count from every neighbor u; merge each received tree into T v by identifying v and the edge {u, v}; update nvu to the received count
15
v 16 return T v and nv u for each neighbor u of v as the encoding of the sketch SG
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 Gu and Gv , must nonetheless agree on u (u) = C v (u) and C u (v) = C v (v). This local agreement each other’s imagined certificates – Cim im im im 7
It may be convenient to think it is the tree known at the start of phase 2ε + 1, i.e., an artificial phase after the last phase.
14
10
x3 0 10 x2 u v 10 x1 9 8 7
6
10 0 x3 10 0 0 x2 u v 10 0 x1 9 8 7
y 5
6
y0 5
Figure 2: An example illustrating brothers. Let the left graph be the original graph G with the adversarial certificates, while the right graph be the imagined graph Gv with the sketch certificates. Notice that G and Gv have the same sequences of certificates and the same numbers of nodes at every distance j from v, i.e., Gv is an imagined graph of G. Paths (x1 , . . . , y) in G, (x′1 , . . . , y ′ ) in Gv and (x′2 , . . . , y ′ ) in Gv are brothers of each other. Similarly, Paths (x2 , . . . , y) in G, (x3 , . . . , y) in G and (x′3 , . . . , y ′ ) in Gv are brothers of each other. Furthermore, nodes x1 in G, x′1 in Gv and x′2 in Gv are brothers. 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 Gu u and C v on them. To relate what u and and Gv and choose different imagined certifications Cim im v imagine, we require a common ground, and the following notion of brothers lets you do that by matching paths in Gu and Gv to a path in G. Fix a node w and let P = (v1 , v2 , . . . , vk ) be a path in G that passes through w lying within N2ε+1 (w). By item 3 of the sketch, Gw contains at least one path X = (x1 , x2 , . . . , xk ) carrying the w (x ) = C same certificate sequence, i.e., Csk j adv (vj ) for every j, with w in the recorded position. We fix one such X and call it a brother of P in Gw , and we call xj the brother of vj for every j. The w assigns a certificate to each x and let aw = C w (x ) be the certificates imagined certification Cim j j im j that w imagines along P . The certificates aw satisfy two properties. j w (P1) aw j = Cadv (vj ) for all but at most ε indices j. Indeed, X lies within Gw , so Cim differs from w w Csk on at most ε of its nodes and Csk (xj ) = Cadv (vj ) by construction of X. w , every node within 2ε hops from w in G accepts according to A . This covers (P2) Under Cim w 0 all of x1 , . . . , xk except possibly the two endpoints x1 and xk , which may fall outside N2ε (w).
We make the notion of brother symmetric and transitive, i.e., (i) if Pu in Gu is a brother of P in G, then P is also a brother of Pu , and (ii) if P1 is a brother of P2 and P2 is a brother of P3 , then P1 is a brother of P3 . This lets us relate paths across two different imagined trees Gu and Gv , i.e., if Xu in Gu and Xv in Gv 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 Pu through u in Gu has a brother in (original tree) G and a brother in Gv for every v ̸= u. Similarly, any node w in Gu must have at least one brother in the original tree G and at least one brother in Gv for every v ̸= 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 Gv , nor between a node in G and a node in Gv . With brothers in hand, we can compare what different nodes imagine. 15
The proof of Lemma 2 combines two things. The first is a property of certifications accepted by A0 , 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 A0 , each node v with certificate C ′ (v) must have at most8 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 A0 . Claim 1. Consider a path P = (v0 , v1 , . . . , vk ) and any fixed a, b ∈ N ∪ {0}. Then, there is at most one certificate assignment function C on P such that C(v0 ) = a, C(vk ) = b, under which every node of P accepts according to A0 . 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 ≤ k ′ < k: For any a′ , b′ ∈ N ∪ {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 A0 . Base case H(1): A path (u0 , u1 ) with fixed endpoint labels C(u0 ) = a′ and C(u1 ) = b′ either satisfies the acceptance conditions of A0 or not. In either case, at most one certificate assignment function exists. Thus H(1) holds. Inductive step (H(k ′ ) ⇒ H(k ′ + 1)): Let P ′ = (u0 , u1 , . . . , uk′ +1 ) be a path of length k ′ + 1 with endpoint certificates a′ , b′ where a′ ̸= 0 or b′ ̸= 0. If no proof satisfies these constraints while making all nodes accept under A0 , then H(k ′ + 1) holds trivially. Otherwise, let C ′ be such a certificate assignment function on P ′ and let m = max{C ′ (u0 ), . . . , ′ C (uk′ +1 )}. We show that no internal node uj (1 ≤ j ≤ k ′ ) can have certificate m. Suppose C ′ (uj ) = m for some 1 ≤ j ≤ k ′ . By Remark 2, node uj requires at most 1 neighbor with the certificate m − 1 and all others with m + 1. But both neighbors uj−1 and uj+1 satisfy C ′ (uj−1 ) ≤ m and C ′ (uj+1 ) ≤ 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 ′ (u0 ) = m = a′ . Remark 2 forces C ′ (u1 ) ∈ {m − 1, m + 1}, and by maximality C ′ (u1 ) = m − 1 = a′ − 1. Deleting u0 leaves the path (u1 , . . . , uk′ +1 ) of length k ′ with fixed endpoint certificates a′ − 1 and b′ . By H(k ′ ) applied to (u1 , . . . , uk′ +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 Tu denote the subgraph of Gu induced by the nodes that are 2ε + 1 hops away from both u and v, i.e., N2ε+1 (u)∩N2ε+1 (v) in Gu . If a node w ∈ Tu is exactly 2ε+1 hops away 8
If C ′ (v) = 0, then there is no parent.
16
from either u or v, then w is called an outer node, otherwise w is an inner node. Let node ru ∈ Tu , u (r ) = min u 910 called root, be the node with the smallest imagined certificate, i.e., Cim u w∈Tu Cim (w). v We define analogously Tv as a subgraph of G , inner and outer nodes in Tv , and a root node rv in Tv . u (w) = C u (r )+dist(r , w). Remark 3. If ru is a root of Tu , then for any node w ∈ Tu we have Cim u im u
The remark above follows immediately from the fact that an imagined certification is accepted by A0 , which means that the certificates increase by 1 with each hop away from the leader. We consider the following cases: • Case 1: ru is an inner node • Case 2: ru is an outer node Case 1: Since ru has the smallest certificate in Tu , then ru does not have a parent in Tu . The u (r ) = 0. only nodes without parents in an acceptable certification must have certificate 0, so Cim u u (u) = dist(r , u) and C u (v) = dist(r , v). It follows that Cim u u im If a node in an acceptable certification has label 0, then it must be the leader – in this case, it means that node ru corresponds to the L position in some sequence of certificates in the graph sketch. Thus, according to Remark 1, ru is a brother of a node r in G such that r received input L. Furthermore, ru has a brother w in Gv in the same position relative to nodes u and v, so w is also an inner node in Tv . Since w is a brother of ru , then it corresponds to the L position, v (w) = 0. Again, we get that C v (u) = dist(w, u) and C v (v) = dist(w, v). Since w thus Cim im im and ru 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, u (u) = dist(r , u) = dist(w, u) = C v (u) and C u (v) = dist(r , v) = dist(w, v) = C v (v), which Cim u u im im im proves the lemma in this case. Case 2: In this case, let us fix a path Pu in Tu that starts in ru and ends in u or v (whichever is further). Notice that Pu contains 2ε + 2 nodes.11 According to Remark 1, the path Pu has a brother Pv in Gv . Since they are brothers, they correspond to the same sequence S of sketch u on P and node v modified up to labels.12 Node u modified up to ε labels in S to obtain Cim u v on P . In total up to 2ε modifications were introduced to S out of ε labels in S to obtain Cim v 2ε + 2 labels in S. Thus, there are at least 2 nodes u1 , u2 ∈ Pu with unchanged labels that have u (u ) = C u (u ) = C v (v ) = C v (v ) and brothers v1 , v2 ∈ Pv also with unchanged labels, i.e., Cim 1 im 1 sk 1 sk 1 u u v v Cim (u2 ) = Csk (u2 ) = Csk (v2 ) = Cim (v2 ). u (x) = C u (r ) + According to Remark 3, since ru has the smallest label on Pu , we get that Cim im u u (u ) = C u (r ) + dist(r , u ) and C u (u ) = C u (r ) + dist(ru , x) for all x ∈ Pu . In particular, Cim u 1 1 im u im 2 im u 9
The root of Tu does not have to be the leader. There may be no leader inside Tu , but Tu still has the node with the smallest certificate and the certificate may be greater than 0. 10 There is exactly 1 such node ru . If there were multiple such nodes ru and ru′ , 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 A0 , which contradicts our assumption that Cim (u) is an imagined certification (imagined certification must be accepted by A0 ). 11 By definition of an inner node, ru is at distance 2ε+1 from u or v. Together with the node u or v, this constitutes a path of length exactly 2ε + 2. 12 Note that the brother w in Pv of root ru in Pu does not necessarily have to be the root in Pv . They have the same sketch labels, but their imagined labels may differ significantly.
17
w v
x
w
w0
v
x
u
u
Figure 3: An example of a situation where node u cannot decide whether nodes w and w′ it learns about from v and x respectively are actually the same node. Thus, node u cannot decide what is the exact structure of the graph. dist(ru , u2 ). Their brothers v1 and v2 in Pv have the same labels and positions as u1 and u2 in v (v ) = C u (u ) < Pu . Without loss of generality assume u1 is closer than u2 to ru . Thus, Cim 1 im 1 u v Cim (u2 ) = Cim (v2 ). According to Claim 1, there is at most one acceptable certificate assignment v (v ) and ends in v function of nodes on the subpath Pv′ ⊆ Pv that starts in v1 with label Cim 1 2 v v with label Cim (v2 ). Notice that the certificate assignment function Cim on the nodes starting from v1 , through v2 and ending at u or v (whichever is further) must be the same as the certificate u on the brothers of those nodes in P . In particular, C u (u) = C v (u) and assignment function Cim u im im u v Cim (v) = Cim (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ε + 1)-hop neighborhood: a compact O(ε2 log n)-bit local graph sketch captures exactly the information the verifier consumes, letting each node decide via refix-leader after only O(ε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. 18
Variable u, v, . . . , y a, b, c C i, j, k T P S A
Description Node variables (possibly with superscripts and subscripts) Certificate variables (possibly with superscripts and subscripts) Certificate assignment function (possibly with superscripts and subscripts) Index variables Tree variable (possibly with superscripts and subscripts) Path variable (possibly with superscripts and subscripts) Set or Sequence (of certificates) variable (possibly with superscripts and subscripts) Verifier (possibly with superscripts and subscripts) Table 1: List of Variables
Acknowledgment: This work is supported by Polish National Science Centre project no. 2020/39/B/ST6/03288.
References [1] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Analyzing graph structure via linear measurements. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 459–467. SIAM, 2012. [2] Heger Arfaoui, Pierre Fraigniaud, David Ilcinkas, and Fabien Mathieu. Distributedly testing cycle-freeness. In Dieter Kratsch and Ioan Todinca, editors, Graph-Theoretic Concepts in Computer Science, pages 15–28, Cham, 2014. Springer International Publishing. [3] Mor Baruch, Pierre Fraigniaud, and Boaz Patt-Shamir. Randomized proof-labeling schemes. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC ’15, page 315–324, New York, NY, USA, 2015. Association for Computing Machinery. [4] Naama Ben-David, Muhammad Ayaz Dzulfikar, Faith Ellen, and Seth Gilbert. Byzantine agreement with predictions. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’25, page 3–14, New York, NY, USA, 2025. Association for Computing Machinery. [5] Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron. Local certification of graph decompositions and applications to minor-free classes. Journal of Parallel and Distributed Computing, 193:104954, 2024. [6] Nicolas Bousquet, Laurent Feuilloley, and Sébastien Zeitoun. Complexity Landscape for Local Certification. In Dariusz R. Kowalski, editor, 39th International Symposium on Distributed Computing (DISC 2025), volume 356 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1–18:21, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
19
[7] Joan Boyar, Faith Ellen, and Kim S. Larsen. Brief announcement: Distributed graph algorithms with predictions. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’25, page 322–325, New York, NY, USA, 2025. Association for Computing Machinery. [8] Keren Censor-Hillel, Ami Paz, and Mor Perry. Approximate proof-labeling schemes. Theoretical Computer Science, 811:112–124, 2020. Special issue on Structural Information and Communication Complexit. [9] Yuval Emek, Yuval Gil, and Shay Kutten. Locally restricted proof labeling schemes. In Christian Scheideler, editor, 36th International Symposium on Distributed Computing, DISC 2022, Augusta, Georgia, USA, October 25-27, 2022, LIPIcs, pages 20:1–20:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. [10] Louis Esperet and Benjamin Lévêque. Local certification of graphs on surfaces. Theoretical Computer Science, 909:68–75, 2022. [11] Laurent Feuilloley. Introduction to local certification. Discrete Mathematics & Theoretical Computer Science, 23(Distributed Computing and Networking), 2021. [12] Laurent Feuilloley, Nicolas Bousquet, and Théo Pierron. What can be certified compactly? compact local certification of mso properties in tree-like graphs. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, PODC’22, page 131–140, New York, NY, USA, 2022. Association for Computing Machinery. [13] Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Éric Rémila, and Ioan Todinca. Compact distributed certification of planar graphs. In Proceedings of the 39th Symposium on Principles of Distributed Computing, PODC ’20, page 319–328, New York, NY, USA, 2020. Association for Computing Machinery. [14] Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Éric Rémila, and Ioan Todinca. Local certification of graphs with bounded genus. Discrete Applied Mathematics, 325:9–36, 2023. [15] Laurent Feuilloley and Juho Hirvonen. Local Verification of Global Proofs. In Ulrich Schmid and Josef Widder, editors, 32nd International Symposium on Distributed Computing (DISC 2018), volume 121 of Leibniz International Proceedings in Informatics (LIPIcs), pages 25:1– 25:17, Dagstuhl, Germany, 2018. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. [16] Laurent Feuilloley, Josef Erik Sedláček, and Martin Slávik. Proving there is a leader without naming it. arXiv preprint arXiv:2511.15491, 2025. [17] Pierre Fraigniaud, Amos Korman, and David Peleg. Towards a complexity theory for local distributed computing. J. ACM, 60(5), October 2013. [18] Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, and Ami Paz. Distributed Quantum Proofs for Replicated Data. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 of Leibniz International Proceedings in Informatics (LIPIcs), pages 28:1–28:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. 20
[19] Pierre Fraigniaud, Frédéric Mazoit, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. Distributed Certification for Classes of Dense Graphs. In Rotem Oshman, editor, 37th International Symposium on Distributed Computing (DISC 2023), volume 281 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1–20:17, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. [20] Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. A meta-theorem for distributed certification. Algorithmica, 86(2):585–612, 2024. [21] Pawel Garncarek, Tomasz Jurdzinski, Dariusz Kowalski, and Subhajit Pramanick. Distributed local verification using proofs with (out) errors. arXiv preprint arXiv:2603.20831, 2026. [22] Mohsen Ghaffari and Krzysztof Nowicki. Congested clique algorithms for the minimum cut problem. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, pages 357–366, 2018. [23] Mika Göös and Jukka Suomela. Locally checkable proofs in distributed computing. Theory of Computing, 12:1–33, 2016. [24] Tomasz Jurdziński and Krzysztof Nowicki. Mst in o (1) rounds of congested clique. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2620–2632. SIAM, 2018. [25] Amos Korman and Shay Kutten. Distributed verification of minimum spanning trees. Distributed Comput., 20(4):253–266, 2007. [26] Amos Korman, Shay Kutten, and David Peleg. Proof labeling schemes. In Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing (PODC ’05), PODC ’05, page 9–18, New York, NY, USA, 2005. Association for Computing Machinery. [27] Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM (JACM), 68(4):1–25, 2021. [28] Rafail Ostrovsky, Mor Perry, and Will Rosenbaum. Space-time tradeoffs for distributed verification. In International Colloquium on Structural Information and Communication Complexity, pages 53–70. Springer, 2017. [29] David Peleg. Distributed computing: a locality-sensitive approach. SIAM, 2000.
21