Error-Sensitive Proof-Labeling Schemes

Laurent Feuilloley, Pierre Fraigniaud.

Journal of Parallel and Distributed Computing


Publisher's version ArXiv version DISC version Slides Poster


Linear link between errors 
		and rejection
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(\log n)$ bits, and on $O\left(\log^2n\right)$ bits, respectively, are error-sensitive, as long as the trees are locally represented by adjacency lists, and not just by parent pointers.

Talks and posters

I presented the conference version of the paper at DISC and at the annual meeting of the French project ANR DESCARTES on 3rd October 2017, at DISC on 19th October 2017, in Lyon on 28th November 2017 for the days of the CNRS GT CoA, and in Bordeaux on 4th December 2017 for the distributed algorithms seminar.

I presented the poster at HALG 2018, and at the PhD seminar of the SIF (French Computer science society).


  • The journal version has basically the same technical content has the conference version. The introduction has been changed quite a lot, and the conclusion now has a list of open problems. The proofs and figures have been improved.