Document Open Access Logo

Redundancy in Distributed Proofs

Authors Laurent Feuilloley, Pierre Fraigniaud, Juho Hirvonen, Ami Paz, Mor Perry

PDF
Thumbnail PDF

File

LIPIcs.DISC.2018.24.pdf
  • Filesize: 0.54 MB
  • 18 pages

Document Identifiers

Author Details

Laurent Feuilloley
  • IRIF, CNRS and University Paris Diderot, France
Pierre Fraigniaud
  • IRIF, CNRS and University Paris Diderot, France
Juho Hirvonen
  • University of Freiburg, Germany
Ami Paz
  • IRIF, CNRS and University Paris Diderot, France
Mor Perry
  • School of Electrical Engineering, Tel-Aviv University, Israel

Funding

Research supported by the French-Israeli Laboratory on Foundations of Computer Science (FILOFOCS). The first four authors supported by the ANR project DESCARTES. The first two authors receive additional support from INRIA project GANG. Third author supported by the Ulla Tuominen Foundation. Fourth author supported by the Fondation Sciences Mathématiques de Paris (FSMP).

Cite AsGet BibTex

Laurent Feuilloley, Pierre Fraigniaud, Juho Hirvonen, Ami Paz, and Mor Perry. Redundancy in Distributed Proofs. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.DISC.2018.24

Abstract

Distributed proofs are mechanisms enabling the nodes of a network to collectively and efficiently check the correctness of Boolean predicates on the structure of the network (e.g. having a specific diameter), or on data structures distributed over the nodes (e.g. a spanning tree). We consider well known mechanisms consisting of two components: a prover that assigns a certificate to each node, and a distributed algorithm called verifier that is in charge of verifying the distributed proof formed by the collection of all certificates. We show that many network predicates have distributed proofs offering a high level of redundancy, explicitly or implicitly. We use this remarkable property of distributed proofs to establish perfect tradeoffs between the size of the certificate stored at every node, and the number of rounds of the verification protocol.

Subject Classification

ACM Subject Classification
  • Networks → Error detection and error correction
  • Theory of computation → Distributed computing models
  • Computer systems organization → Redundancy
Keywords
  • Distributed verification
  • Distributed graph algorithms
  • Proof-labeling schemes
  • Space-time tradeoffs
  • Non-determinism

Metrics

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

Related Versions

References

  1. Amir Abboud, Keren Censor-Hillel, and Seri Khoury. Near-linear lower bounds for distributed distance computations, even in sparse networks. In 30th Int. Symposium on Distributed Computing (DISC), pages 29-42, 2016. Full version at arXiv:1605.05109. Google Scholar
  2. 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.
  3. Yehuda Afek, Shay Kutten, and Moti Yung. The local detection paradigm and its applications to self-stabilization. Theoretical Computer Science, 186(1):199-229, 1997. URL: http://dx.doi.org/10.1016/S0304-3975(96)00286-1.
  4. Heger Arfaoui, Pierre Fraigniaud, David Ilcinkas, and Fabien Mathieu. Distributedly testing cycle-freeness. In 40th Int. Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 8747 of LNCS, pages 15-28. Springer, 2014. Google Scholar
  5. Heger Arfaoui, Pierre Fraigniaud, and Andrzej Pelc. Local decision and verification with bounded-size outputs. In 15th Symp. on Stabilization, Safety, and Security of Distributed Systems (SSS), volume 8255 of LNCS, pages 133-147. Springer, 2013. Google Scholar
  6. Baruch Awerbuch, Boaz Patt-Shamir, and George Varghese. Self-stabilization by local checking and correction. In 32nd Symposium on Foundations of Computer Science (FOCS), pages 268-277. IEEE, 1991. Google Scholar
  7. Alkida Balliu, Gianlorenzo D'Angelo, Pierre Fraigniaud, and Dennis Olivetti. What can be verified locally? In 34th Symposium on Theoretical Aspects of Computer Science (STACS), volume 66 of LIPIcs, pages 8:1-8:13, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2017.8.
  8. Evangelos Bampas and David Ilcinkas. On mobile agent verifiable problems. In 12th Latin American Symposium on Theoretical Informatics (LATIN), LNCS 9644, pages 123-137. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-662-49529-2_10.
  9. Mor Baruch, Pierre Fraigniaud, and Boaz Patt-Shamir. Randomized proof-labeling schemes. In 24th Symposium on Principles of Distributed Computing (PODC), pages 315-324. ACM, 2015. URL: http://dx.doi.org/10.1145/2767386.2767421.
  10. 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.
  11. Lélia Blin and Pierre Fraigniaud. Space-optimal time-efficient silent self-stabilizing constructions of constrained spanning trees. In 35th Int. Conference on Distributed Computing Systems (ICDCS), pages 589-598. IEEE, 2015. URL: http://dx.doi.org/10.1109/ICDCS.2015.66.
  12. Lélia Blin, Pierre Fraigniaud, and Boaz Patt-Shamir. On proof-labeling schemes versus silent self-stabilizing algorithms. In 16th Int. Symp. on Stabilization, Safety, and Security of Distributed Systems (SSS), LNCS, pages 18-32. Springer, 2014. Google Scholar
  13. Keren Censor-Hillel, Ami Paz, and Mor Perry. Approximate proof labeling schemes. In 24th Int. Colloquium on Structural Information and Communication Complexity (SIROCCO), 2017. Google Scholar
  14. A. Das Sarma, S. Holzer, L. Kor, A. Korman, D. Nanongkai, G. Pandurangan, D. Peleg, and R. Wattenhofer. Distributed verification and hardness of distributed approximation. SIAM J. Comput., 41(5):1235-1265, 2012. Google Scholar
  15. Laurent Feuilloley and Pierre Fraigniaud. Survey of distributed decision. Bulletin of the EATCS, 119, 2016. URL: http://bulletin.eatcs.org/index.php/beatcs/article/view/411/391.
  16. Laurent Feuilloley and Pierre Fraigniaud. Error-sensitive proof-labeling schemes. In 31st International Symposium on Distributed Computing (DISC), pages 16:1-16:15, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.DISC.2017.16.
  17. Laurent Feuilloley, Pierre Fraigniaud, and Juho Hirvonen. A Hierarchy of Local Decision. In 43rd Int. Colloquium on Automata, Languages, and Programming (ICALP), LIPIcs, pages 118:1-118:15, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.118.
  18. Klaus-Tycho Foerster, Thomas Luedi, Jochen Seidel, and Roger Wattenhofer. Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in sdns. Theor. Comput. Sci., 709:48-63, 2018. URL: http://dx.doi.org/10.1016/j.tcs.2016.11.018.
  19. Pierre Fraigniaud, Amos Korman, and David Peleg. Towards a complexity theory for local distributed computing. J. ACM, 60(5):35, 2013. Google Scholar
  20. Pierre Fraigniaud and Andrzej Pelc. Decidability classes for mobile agents computing. J. Parallel Distrib. Comput., 109:117-128, 2017. URL: http://dx.doi.org/10.1016/j.jpdc.2017.04.003.
  21. Pierre Fraigniaud, Sergio Rajsbaum, and Corentin Travers. Minimizing the number of opinions for fault-tolerant distributed decision using well-quasi orderings. In 12th Latin American Symposium on Theoretical Informatics (LATIN), pages 497-508. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-662-49529-2_37.
  22. Pierre Fraigniaud, Sergio Rajsbaum, Corentin Travers, Petr Kuznetsov, and Thibault Rieutord. Perfect failure detection with very few bits. In 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), LNCS 10083, pages 154-169. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-319-49259-9_13.
  23. Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer. Networks cannot compute their diameter in sublinear time. In 23rd Symposium on Discrete Algorithms (SODA), pages 1150-1162. ACM-SIAM, 2012. Google Scholar
  24. R. G. Gallager, P. A. Humblet, and P. M. Spira. A distributed algorithm for minimum-weight spanning trees. ACM Transactions on Programming Languages and Systems (TOPLAS), 5(1):66-77, 1983. URL: http://dx.doi.org/10.1145/357195.357200.
  25. Mika Göös and Jukka Suomela. Locally checkable proofs in distributed computing. Theory of Computing, 12(1):1-33, 2016. URL: http://dx.doi.org/10.4086/toc.2016.v012a019.
  26. Gene Itkis and Leonid A. Levin. Fast and lean self-stabilizing asynchronous protocols. In 35th Symposium on Foundations of Computer Science (FOCS), pages 226-239. IEEE, 1994. URL: http://dx.doi.org/10.1109/SFCS.1994.365691.
  27. Gillat Kol, Rotem Oshman, and Raghuvansh R. Saxena. Interactive distributed proofs. In 37th ACM Symposium on Principles of Distributed Computing (PODC 2018), to appear. Google Scholar
  28. Janne H. Korhonen and Jukka Suomela. Brief announcement: Towards a complexity theory for the congested clique. In 31st International Symposium on Distributed Computing (DISC), pages 55:1-55:3, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.DISC.2017.55.
  29. Amos Korman and Shay Kutten. Distributed verification of minimum spanning trees. Distributed Computing, 20:253-266, 2007. Google Scholar
  30. 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.
  31. 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.
  32. Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, New York, 1997. Google Scholar
  33. Rafail Ostrovsky, Mor Perry, and Will Rosenbaum. Space-time tradeoffs for distributed verification. In 24th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pages 53-70, 2017. URL: http://dx.doi.org/10.1007/978-3-319-72050-0_4.
  34. Boaz Patt-Shamir and Mor Perry. Proof-labeling schemes: Broadcast, unicast and in between. In 19th Int. Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), LNCS 10616, pages 1-17. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-319-69084-1_1.
  35. David Peleg. Distributed Computing: A Locality-Sensitive Approach. Discrete Mathematics and Applications. SIAM, Philadelphia, 2000. Google Scholar
  36. David Peleg and Vitaly Rubinovich. A near-tight lower bound on the time complexity of distributed MST construction. In 40th Symp. on Foundations of Computer Science (FOCS), pages 253-261. IEEE, 1999. URL: http://dx.doi.org/10.1109/SFFCS.1999.814597.
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 Imprint Privacy Contact