Abstract
Prooflabeling schemes are known mechanisms providing nodes of networks with certificates that can be verified locally by distributed algorithms. Given a boolean predicate on network states, such schemes enable to check whether the predicate is satisfied by the actual state of the network, by having nodes interacting with their neighbors only. Prooflabeling schemes are typically designed for enforcing faulttolerance, by making sure that if the current state of the network is illegal with respect to some given predicate, then at least one node will detect it. Such a node can raise an alarm, or launch a recovery procedure enabling the system to return to a legal state. In this paper, we introduce errorsensitive prooflabeling schemes. These are prooflabeling schemes which guarantee that the number of nodes detecting illegal states is linearly proportional to the editdistance between the current state and the set of legal states. By using errorsensitive prooflabeling schemes, states which are far from satisfying the predicate will be detected by many nodes, enabling fast return to legality. We provide a structural characterization of the set of boolean predicates on network states for which there exist errorsensitive prooflabeling schemes. This characterization allows us to show that classical predicates such as, e.g., acyclicity, and leader admit errorsensitive prooflabeling schemes, while others like regular subgraphs don't. We also focus on compact errorsensitive prooflabeling schemes. In particular, we show that the known prooflabeling schemes for spanning tree and minimum spanning tree, using certificates on O(log n) bits, and on O(log^2 n) bits, respectively, are errorsensitive, as long as the trees are locally represented by adjacency lists, and not just by parent pointers.
BibTeX  Entry
@InProceedings{feuilloley_et_al:LIPIcs:2017:8018,
author = {Laurent Feuilloley and Pierre Fraigniaud},
title = {{ErrorSensitive ProofLabeling Schemes}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {16:116:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770538},
ISSN = {18688969},
year = {2017},
volume = {91},
editor = {Andr{\'e}a W. Richa},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8018},
URN = {urn:nbn:de:0030drops80180},
doi = {10.4230/LIPIcs.DISC.2017.16},
annote = {Keywords: Faulttolerance, distributed decision, distributed property testing}
}
Keywords: 

Faulttolerance, distributed decision, distributed property testing 
Collection: 

31st International Symposium on Distributed Computing (DISC 2017) 
Issue Date: 

2017 
Date of publication: 

12.10.2017 