Error-resilient Distributed Local Verification
This work addresses error-resilient verification in distributed networks, offering incremental improvements in label efficiency and error tolerance for specific graph properties.
The paper tackles the problem of verifying graph properties in distributed networks by introducing a new gadget that reduces the label count for cycle detection from 3 to 2 using a 3-hop neighborhood, and develops a framework called refix that transforms base verification algorithms to tolerate adversarial label errors, with applications to properties like cycle detection and bipartiteness.
We study verification (decision) problems for graph properties in distributed networks under the locally checkable labeling framework, where nodes use labels (proofs) and local neighborhoods to decide acceptance or rejection. Our focus is twofold. First, we study cycle detection. While it is known that this can be verified using 3 labels with access to the 1-hop neighborhood, we introduce a novel gadget that encodes direction along a path using only 2 labels and access to a 3-hop neighborhood. This yields a cycle-detection labeling scheme with just 2 labels and may be of independent interest. Second, we consider adversarially corrupted labelings, where 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, that transforms a base verification algorithm for a property P operating on labels within a d-hop neighborhood into one that tolerates up to i erroneous labels within a radius d+2i, by accessing a d+2i-hop neighborhood. We demonstrate applications to cycle detection, cycle absence, and bipartiteness, and provide lower bounds relating the number of errors to the required neighborhood size.