Abstract
Introduced by Korman, Kutten, and Peleg (PODC 2005), a proof labeling scheme (PLS) is a distributed verification system dedicated to evaluating if a given configured graph satisfies a certain property. It involves a centralized prover, whose role is to provide proof that a given configured graph is a yesinstance by means of assigning labels to the nodes, and a distributed verifier, whose role is to verify the validity of the given proof via local access to the assigned labels. In this paper, we introduce the notion of a locally restricted PLS in which the prover’s power is restricted to that of a LOCAL algorithm with a polylogarithmic number of rounds. To circumvent inherent impossibilities of PLSs in the locally restricted setting, we turn to models that relax the correctness requirements by allowing the verifier to accept some noinstances as long as they are not "too far" from satisfying the property in question. To this end, we evaluate (1) distributed graph optimization problems (OptDGPs) based on the notion of an approximate proof labeling scheme (APLS) (analogous to the type of relaxation used in sequential approximation algorithms); and (2) configured graph families (CGFs) based on the notion of a testing proof labeling schemes (TPLS) (analogous to the type of relaxation used in property testing algorithms). The main contribution of the paper comes in the form of two generic compilers, one for OptDGPs and one for CGFs: given a blackbox access to an APLS (resp., PLS) for a large class of OptDGPs (resp., CGFs), the compiler produces a locally restricted APLS (resp., TPLS) for the same problem, while losing at most a (1 + ε) factor in the scheme’s relaxation guarantee. An appealing feature of the two compilers is that they only require a logarithmic additive label size overhead.
BibTeX  Entry
@InProceedings{emek_et_al:LIPIcs.DISC.2022.20,
author = {Emek, Yuval and Gil, Yuval and Kutten, Shay},
title = {{Locally Restricted Proof Labeling Schemes}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {20:120:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772556},
ISSN = {18688969},
year = {2022},
volume = {246},
editor = {Scheideler, Christian},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17211},
URN = {urn:nbn:de:0030drops172111},
doi = {10.4230/LIPIcs.DISC.2022.20},
annote = {Keywords: proof labeling schemes, generic compilers, SLOCAL algorithms}
}
Keywords: 

proof labeling schemes, generic compilers, SLOCAL algorithms 
Collection: 

36th International Symposium on Distributed Computing (DISC 2022) 
Issue Date: 

2022 
Date of publication: 

17.10.2022 