License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2017.16
URN: urn:nbn:de:0030-drops-80180
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8018/
Go to the corresponding LIPIcs Volume Portal

Feuilloley, Laurent ; Fraigniaud, Pierre

Error-Sensitive Proof-Labeling Schemes

pdf-format:
LIPIcs-DISC-2017-16.pdf (0.5 MB)

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(log n) bits, and on O(log^2 n) bits, respectively, are error-sensitive, 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 =	{{Error-Sensitive Proof-Labeling Schemes}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Andr{\'e}a W. Richa},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8018},
  URN =		{urn:nbn:de:0030-drops-80180},
  doi =		{10.4230/LIPIcs.DISC.2017.16},
  annote =	{Keywords: Fault-tolerance, distributed decision, distributed property testing}
}

Keywords: Fault-tolerance, distributed decision, distributed property testing
Collection: 31st International Symposium on Distributed Computing (DISC 2017)
Issue Date: 2017
Date of publication: 12.10.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI