Error-resilient Distributed Local Verification
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908905367404544 |
|---|---|
| author | Garncarek, Paweł Jurdzinski, Tomasz Kowalski, Dariusz Pramanick, Subhajit |
| author_facet | Garncarek, Paweł Jurdzinski, Tomasz Kowalski, Dariusz Pramanick, Subhajit |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_20831 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Error-resilient Distributed Local Verification Garncarek, Paweł Jurdzinski, Tomasz Kowalski, Dariusz Pramanick, Subhajit Distributed, Parallel, and Cluster Computing 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. |
| title | Error-resilient Distributed Local Verification |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2603.20831 |