Document Open Access Logo

Error-Sensitive Proof-Labeling Schemes

Authors Laurent Feuilloley, Pierre Fraigniaud

PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.16.pdf
  • Filesize: 0.52 MB
  • 15 pages

Document Identifiers

Author Details

Laurent Feuilloley
Pierre Fraigniaud

Cite As Get BibTex

Laurent Feuilloley and Pierre Fraigniaud. Error-Sensitive Proof-Labeling Schemes. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.DISC.2017.16

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.

Subject Classification

Keywords
  • Fault-tolerance
  • distributed decision
  • distributed property testing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Yehuda Afek and Shlomi Dolev. Local stabilizer. J. Parallel Distrib. Comput., 62(5):745-765, 2002. URL: http://dx.doi.org/10.1006/jpdc.2001.1823.
  2. Yehuda Afek, Shay Kutten, and Moti Yung. The local detection paradigm and its application to self-stabilization. Theor. Comput. Sci., 186(1-2):199-229, 1997. URL: http://dx.doi.org/10.1016/S0304-3975(96)00286-1.
  3. Baruch Awerbuch, Shay Kutten, Yishay Mansour, Boaz Patt-Shamir, and George Varghese. Time optimal self-stabilizing synchronization. In 25th ACM Symposium on Theory of Computing (STOC), pages 652-661, 1993. URL: http://dx.doi.org/10.1145/167088.167256.
  4. Baruch Awerbuch, Boaz Patt-Shamir, and George Varghese. Self-stabilization by local checking and correction (extended abstract). In 32nd IEEE Symposium on Foundations of Computer Science (FOCS), pages 268-277, 1991. URL: http://dx.doi.org/10.1109/SFCS.1991.185378.
  5. Joffroy Beauquier, Sylvie Delaët, Shlomi Dolev, and Sébastien Tixeuil. Transient fault detectors. Distributed Computing, 20(1):39-51, 2007. URL: http://dx.doi.org/10.1007/s00446-007-0029-x.
  6. Lélia Blin and Pierre Fraigniaud. Space-optimal time-efficient silent self-stabilizing constructions of constrained spanning trees. In 35th IEEE International Conference on Distributed Computing Systems (ICDCS), pages 589-598, 2015. URL: http://dx.doi.org/10.1109/ICDCS.2015.66.
  7. Lélia Blin, Pierre Fraigniaud, and Boaz Patt-Shamir. On proof-labeling schemes versus silent self-stabilizing algorithms. In 16th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 18-32, 2014. URL: http://dx.doi.org/10.1007/978-3-319-11764-5_2.
  8. Zvika Brakerski and Boaz Patt-Shamir. Distributed discovery of large near-cliques. Distributed Computing, 24(2):79-89, 2011. Google Scholar
  9. Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman, and Yadu Vasudev. Fast distributed algorithms for testing graph properties. In 30th International Symposium on Distributed Computing (DISC), pages 43-56, 2016. URL: http://dx.doi.org/10.1007/978-3-662-53426-7_4.
  10. Guy Even, Moti Medina, and Dana Ron. Best of two local models: Local centralized and local distributed algorithms. Technical report, arXiv CoRR abs/1402.3796, 2014. Google Scholar
  11. Laurent Feuilloley and Pierre Fraigniaud. Survey of distributed decision. Bulletin of the EATCS, 119, 2016. Google Scholar
  12. Pierre Fraigniaud, Amos Korman, and David Peleg. Towards a complexity theory for local distributed computing. J. ACM, 60(5):35:1-35:26, 2013. URL: http://dx.doi.org/10.1145/2499228.
  13. Pierre Fraigniaud, Ivan Rapaport, Ville Salo, and Ioan Todinca. Distributed testing of excluded subgraphs. In 30th Int. Symposium on Distributed Computing (DISC), volume 9888 of LNCS, pages 342-356. Springer, 2016. Google Scholar
  14. Oded Goldreich. A brief introduction to property testing. In Studies in Complexity and Cryptography - Miscellanea on the Interplay between Randomness and Computation, number 6650 in LNCS, pages 465-469. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-22670-0_31.
  15. Oded Goldreich. Introduction to testing graph properties. In Studies in Complexity and Cryptography - Miscellanea on the Interplay between Randomness and Computation, number 6650 in LNCS, pages 470-506. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-22670-0_32.
  16. Mika Göös, Juho Hirvonen, Reut Levi, Moti Medina, and Jukka Suomela. Non-local probes do not help with many graph problems. In 30th International Symposium on Distributed Computing (DISC), pages 201-214, 2016. URL: http://dx.doi.org/10.1007/978-3-662-53426-7_15.
  17. Mika Göös and Jukka Suomela. Locally checkable proofs in distributed computing. Theory of Computing, 12(19):1-33, 2016. URL: http://dx.doi.org/10.4086/toc.2016.v012a019.
  18. Tom Gur and Ron D. Rothblum. Non-interactive proofs of proximity. In 6th Conference on Innovations in Theoretical Computer Science (ITCS), pages 133-142, 2015. URL: http://dx.doi.org/10.1145/2688073.2688079.
  19. Liah Kor, Amos Korman, and David Peleg. Tight bounds for distributed MST verification. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 69-80, 2011. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2011.69.
  20. Amos Korman and Shay Kutten. Distributed verification of minimum spanning trees. Distributed Computing, 20(4):253-266, 2007. URL: http://dx.doi.org/10.1007/s00446-007-0025-1.
  21. Amos Korman, Shay Kutten, and Toshimitsu Masuzawa. Fast and compact self-stabilizing verification, computation, and fault detection of an MST. Distributed Computing, 28(4):253-295, 2015. URL: http://dx.doi.org/10.1007/s00446-015-0242-y.
  22. Amos Korman, Shay Kutten, and David Peleg. Proof labeling schemes. Distributed Computing, 22(4):215-233, 2010. URL: http://dx.doi.org/10.1007/s00446-010-0095-3.
  23. Nathan Linial. Locality in distributed graph algorithms. SIAM J. Comput., 21(1):193-201, 1992. URL: http://dx.doi.org/10.1137/0221015.
  24. László Lovász and Katalin Vesztergombi. Non-deterministic graph property testing. Combinatorics, Probability & Computing, 22(5):749-762, 2013. URL: http://dx.doi.org/10.1017/S0963548313000205.
  25. Moni Naor and Larry J. Stockmeyer. What can be computed locally? SIAM J. Comput., 24(6):1259-1277, 1995. URL: http://dx.doi.org/10.1137/S0097539793254571.
  26. Michal Parnas and Dana Ron. Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. Theoretical Compututer Science, 381(1-3):183-196, 2007. URL: http://dx.doi.org/10.1016/j.tcs.2007.04.040.
  27. David Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact