Skip to Main content Skip to Navigation
Conference papers

Error-Sensitive Proof-Labeling Schemes

Pierre Fraigniaud 1, 2 Laurent Feuilloley 2, 1
1 GANG - Networks, Graphs and Algorithms
IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale, Inria de Paris
Abstract : Proof-labeling 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. Proof-labeling schemes are typically designed for enforcing fault-tolerance, 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 error-sensitive proof-labeling schemes. These are proof-labeling schemes which guarantee that the number of nodes detecting illegal states is linearly proportional to the edit-distance between the current state and the set of legal states. By using error-sensitive proof-labeling 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 error-sensitive proof-labeling schemes. This characterization allows us to show that classical predicates such as, e.g., acyclicity, and leader admit error-sensitive proof-labeling schemes, while others like regular subgraphs don't. We also focus on compact error-sensitive proof-labeling schemes. In particular, we show that the known proof-labeling schemes for spanning tree and minimum spanning tree, using certificates on O(logn) bits, and on O(log2n) bits, respectively, are error-sensitive, as long as the trees are locally represented by adjacency lists, and not just by parent pointers.
Complete list of metadata
Contributor : Pierre Fraigniaud Connect in order to contact the contributor
Submitted on : Wednesday, January 3, 2018 - 12:18:36 PM
Last modification on : Friday, January 21, 2022 - 3:17:21 AM



Pierre Fraigniaud, Laurent Feuilloley. Error-Sensitive Proof-Labeling Schemes. DISC 2017 - 31st International Symposium on Distributed Computing, Oct 2017, Vienna, Austria. pp.1-15, ⟨10.4230/LIPIcs.DISC.2017.16⟩. ⟨hal-01674660⟩



Les métriques sont temporairement indisponibles