Error-resilient Distributed Local Verification DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06

Paweł Garncarek, Tomasz Jurdziński, Dariusz Kowalski, Subhajit Pramanick · 2026

Read Error-resilient Distributed Local Verification DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06 by Paweł Garncarek, Tomasz Jurdziński, Dariusz Kowalski, Subhajit Pramanick (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-20831.txt.

Introduction

Garncarek and co-authors study local verification of graph properties with proofs that may contain errors. In locally checkable proofs, nodes accept or reject based on nearby labels. First they tackle cycle existence in a graph. Three labels and view distance one suffice, and this is tight. A new gadget encodes direction with two labels at distance three. They then build refix, a tool that hardens verifiers against corrupted labels. Lower bounds tie the error count to the view distance needed.

Catalog record

CREATORPaweł Garncarek, Tomasz Jurdziński, Dariusz Kowalski, Subhajit Pramanick
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE95246
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.20831

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Error-resilient Distributed Local Verification DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06 Paweł Garncarek, Tomasz Jurdziński, Dariusz Kowalski, Subhajit Pramanick Abstract . We investigate well-known verification (decision) problems concerning graph properties in distributed networks, where nodes are augmented with labels (or proofs) that provide auxiliary information to assist local computation. These problems are commonly formalized in the framework of locally checkable labeling : if a graph satisfies a given property, then there exists a labeling under which all nodes accept using a local verification algorithm, whereas if the property is not satisfied, then for every labeling of the graph, at least one node must reject. In this computation, nodes generally access a particular local neighborhood to decide whether to accept or reject (equivalent to LOCAL model). In this domain, O ⁡ ( log ⁡ n ) O(\log n) works like a gold standard of labeling size (the maximum number of bits for labels), in the sense that O ⁡ ( log ⁡ n ) O(\log n) label-size is often the best we can hope for most of the fundamental verification problems. Our focus is twofold. First, among multiple properties we mention in the paper, we put particular emphasis on verifying whether the graph has a cycle or not, majorly because this can be verified with only 3 3 labels and access to 1 1 hop neighborhood, with a matching lower bound. What is more interesting is that, we introduce a novel gadget for encoding direction along a path using only 2 2 labels and a 3 3 -hop neighborhood accessibility for each node, which enables a cycle-detection labeling scheme with just 2 2 labels. This gadget may be of independent interest for other verification tasks. Second, we consider adversarially corrupted labelings, in which each node has access to a local neighborhood, within which a fraction of nodes may receive erroneous labels . We introduce a general algorithmic framework, called refix , which transforms a base (error-free) verification algorithm for a property 𝒫 \mathcal{P} operating on labels within d d -hop neighborhood, into one that tolerates up to i i erroneous labels within a neighborhood of radius d + 2 ​ i d+2i , at the cost of accessing the labels within the d + 2 ​ i d+2i -hop neighborhood. We illustrate the applicability of our framework on several graph properties, including cycle detection, cycle absence, and bipartiteness. In presence of erroneous labels, we provide lower bounds to establish the correlation between the number of errors and accessibility of the required neighborhood. 1. Introduction In many distributed systems, nodes are required not only to compute a solution, but also to locally verify that a desired global structure or property is present in the network. Such tasks give rise to verification problems , where the goal is to determine whether a graph satisfies a specified property using only local information, where the term graph property corresponds to a family of graphs closed under isomorphism. In the context of yes–no verification problems, a standard and well-accepted model requires the following: (i) for a yes-instance, all nodes must output 1 ; and (ii) for a no-instance, at least one node must output 0 . In distributed graph algorithms, the model in which nodes are provided with task-specific auxiliary information is well established and widely studied ( 6 ; 23 ; 3 ; 4 ; 8 ; 15 ) . This auxiliary information appears in the literature under various names, including advice ( 2 ) , labels , certificates ( 9 ) , and proofs ( 12 ; 22 ; 23 ) . A local verification of a property consists of assigning labels to the nodes of a graph so that nodes can collectively check the correctness of the property by inspecting the labels within their (possibly larger-radius) neighborhoods. This notion has been studied under several closely related names, including proof labeling schemes ( 23 ) , locally checkable proofs ( 21 ) , local decision ( 20 ) , local certification scheme ( 9 ) etc. Despite the differing terminology, these models share the same underlying goal: enabling nodes to locally verify global graph properties, see a survey by Feuilloley ( 18 ) . A graph property is locally verifiable if it can be checked by a local verification algorithm (formally defined later in Section 2 ), also known as a verifier , that accepts every graph satisfying the property and rejects every graph that does not. Throughout this paper, we adopt a consistent terminology among these closely related notions. We refer to the information provided to nodes as labels , the collection of all node labels as a labeling of the graph G , and the combination of a labeling with a local verification algorithm as a locally checkable labeling scheme (or simply a labeling scheme ). In continuation of the above discussion, a line of work focuses on verifying properties or solving graph problems using small (size with respect to the number of required bits) labels. Although certain graph problems, such as computing a minimum spanning tree in weighted graphs, have been studied in ( 19 ) with constant-size advice (on average per node), a labeling size of O(\log n) has emerged as a near gold standard for most local verification problems ( 20 ; 16 ) , including verifying the existence of a unique leader ( 17 ) , checking acyclicity ( 1 ; 25 ) , non-bipartiteness ( 22 ) and minor-freeness ( 7 ) . In a recent line of works ( 11 ; 13 ; 14 ) , it has been shown that planar graphs and graphs of bounded genus can be verified with O(\log n) bits. Some verification problems requires even larger labels: for example, MST-verification problem ( 24 ) requires even larger labels of size O(\log n\log W) , where W is the largest weight of an edge. In this direction, Balliu et al. ( 5 ) characterize the power of local distributed verification through a hierarchy of decision classes. It is common intuition that hereditary properties, i.e., removing a node or an edge may yield a graph that falls in the same class as the original one, are easier to certify (using O(\log n) size labels) in the sense that information about every single node or edge is not required to be encoded in the labeling. However, certain fundamental verification problems—such as determining whether a graph contains a cycle—remain particularly interesting when restricted to constant-size labelings. We talk more about this in Section 1 . Problem View dist. # Labels POS / NEG Theorem Cycle detection 1 3 + Thm. 1 1 2 – Thm. 2 3 2 + Thm. 3 Cycle absence 1 n + ( 25 ; 22 ) d \sqrt[2d+1]{n-2d} – ( 25 ) & Thm. 7 Bipartiteness 1 2 + trivial Table 1. State of the art results without errors. Column “POS / NEG” states if the result is achievable ( + ) or impossible ( - ). Problem # Err. Err. dist. View dist. # Labels POS/NEG Ref. Cycle detection i any i \infty

Read the complete text