Document Open Access Logo

A Hierarchy of Local Decision

Authors Laurent Feuilloley, Pierre Fraigniaud, Juho Hirvonen

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.118.pdf
  • Filesize: 0.64 MB
  • 15 pages

Document Identifiers

Author Details

Laurent Feuilloley
Pierre Fraigniaud
Juho Hirvonen

Cite As Get BibTex

Laurent Feuilloley, Pierre Fraigniaud, and Juho Hirvonen. A Hierarchy of Local Decision. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 118:1-118:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.118

Abstract

We extend the notion of distributed decision in the framework of distributed network computing, inspired by recent results on so-called distributed graph automata. We show that, by using distributed decision mechanisms based on the interaction between a prover and a disprover, the size of the certificates distributed to the nodes for certifying a given network property can be drastically reduced. For instance, we prove that minimum spanning tree can be certified with O(log(n))-bit certificates in n-node graphs, with just one interaction between the prover and the disprover, while it is known that certifying MST requires Omega(log^2(n))-bit certificates if only the prover can act. The improvement can even be exponential for some simple graph properties.

For instance, it is known that certifying the existence of a nontrivial automorphism requires Omega(n^2) bits if only the prover can act. We show that there is a protocol with two interactions between the prover and the disprover enabling to certify nontrivial automorphism with O(log(n))- bit certificates. These results are achieved by defining and analysing a local hierarchy of decision which generalizes the classical notions of proof-labelling schemes and locally checkable proofs.

Subject Classification

Keywords
  • Distributed Network Computing
  • Distributed Algorithm
  • Distributed Decision
  • Locality

Metrics

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

References

  1. 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.
  2. Heger Arfaoui and Pierre Fraigniaud. What can be computed without communications? SIGACT News, 45(3):82-104, 2014. URL: http://dx.doi.org/10.1145/2670418.2670440.
  3. Heger Arfaoui, Pierre Fraigniaud, David Ilcinkas, and Fabien Mathieu. Distributedly testing cycle-freeness. In Graph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers, pages 15-28, 2014. URL: http://dx.doi.org/10.1007/978-3-319-12340-0_2.
  4. Heger Arfaoui, Pierre Fraigniaud, and Andrzej Pelc. Local decision and verification with bounded-size outputs. In Stabilization, Safety, and Security of Distributed Systems - 15th International Symposium, SSS 2013, Osaka, Japan, November 13-16, 2013. Proceedings, pages 133-147, 2013. URL: http://dx.doi.org/10.1007/978-3-319-03089-0_10.
  5. Yuval Emek, Jochen Seidel, and Roger Wattenhofer. Computability in anonymous networks: Revocable vs. irrecovable outputs. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, pages 183-195, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43951-7_16.
  6. Laurent Feuilloley and Pierre Fraigniaud. Randomized local network computing. In Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, OR, USA, June 13-15, 2015, pages 340-349, 2015. URL: http://dx.doi.org/10.1145/2755573.2755596.
  7. Laurent Feuilloley, Pierre Fraigniaud, and Juho Hirvonen. A hierarchy of local decision. CoRR, abs/1602.08925, 2016. Google Scholar
  8. Patrik Floréen, Marja Hassinen, Joel Kaasinen, Petteri Kaski, Topi Musto, and Jukka Suomela. Local approximability of max-min and min-max linear programs. Theory Comput. Syst., 49(4):672-697, 2011. URL: http://dx.doi.org/10.1007/s00224-010-9303-6.
  9. Klaus-Tycho Förster, Thomas Luedi, Jochen Seidel, and Roger Wattenhofer. Local checkability, no strings attached. In Proceedings of the 17th International Conference on Distributed Computing and Networking, Singapore, January 4-7, 2016, page 21, 2016. URL: http://dx.doi.org/10.1145/2833312.2833315.
  10. Pierre Fraigniaud, Mika Göös, Amos Korman, and Jukka Suomela. What can be decided locally without identifiers? In ACM Symposium on Principles of Distributed Computing, PODC'13, Montreal, QC, Canada, July 22-24, 2013, pages 157-165, 2013. URL: http://dx.doi.org/10.1145/2484239.2484264.
  11. Pierre Fraigniaud, Magnús M. Halldórsson, and Amos Korman. On the impact of identifiers on local decision. In Principles of Distributed Systems, 16th International Conference, OPODIS 2012, Rome, Italy, December 18-20, 2012. Proceedings, pages 224-238, 2012. URL: http://dx.doi.org/10.1007/978-3-642-35476-2_16.
  12. Pierre Fraigniaud, Juho Hirvonen, and Jukka Suomela. Node labels in local decision. In Structural Information and Communication Complexity - 22nd International Colloquium, SIROCCO 2015, Montserrat, Spain, July 14-16, 2015, Post-Proceedings, pages 31-45, 2015. URL: http://dx.doi.org/10.1007/978-3-319-25258-2_3.
  13. Pierre Fraigniaud, Amos Korman, and David Peleg. Towards a complexity theory for local distributed computing. J. ACM, 60(5):35, 2013. URL: http://dx.doi.org/10.1145/2499228.
  14. Pierre Fraigniaud, Sergio Rajsbaum, and Corentin Travers. Locality and checkability in wait-free computing. Distributed Computing, 26(4):223-242, 2013. URL: http://dx.doi.org/10.1007/s00446-013-0188-x.
  15. Pierre Fraigniaud, Sergio Rajsbaum, and Corentin Travers. On the number of opinions needed for fault-tolerant run-time monitoring in distributed systems. In Runtime Verification - 5th International Conference, RV 2014, Toronto, ON, Canada, September 22-25, 2014. Proceedings, pages 92-107, 2014. URL: http://dx.doi.org/10.1007/978-3-319-11164-3_9.
  16. Mika Göös and Jukka Suomela. Locally checkable proofs. In Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, PODC 2011, San Jose, CA, USA, June 6-8, 2011, pages 159-168, 2011. URL: http://dx.doi.org/10.1145/1993806.1993829.
  17. Gene Itkis and Leonid A. Levin. Fast and lean self-stabilizing asynchronous protocols. In 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994, pages 226-239, 1994. URL: http://dx.doi.org/10.1109/SFCS.1994.365691.
  18. Amos Korman and Shay Kutten. Distributed verification of minimum spanning trees. Distributed Computing, 20(4):253-266, 2007. Google Scholar
  19. 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.
  20. 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.
  21. Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. What cannot be computed locally! In Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, PODC 2004, St. John’s, Newfoundland, Canada, July 25-28, 2004, pages 300-309, 2004. URL: http://dx.doi.org/10.1145/1011767.1011811.
  22. Christoph Lenzen, Yvonne Anne Oswald, and Roger Wattenhofer. What can be approximated locally?: case study: dominating sets in planar graphs. In SPAA 2008: Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Munich, Germany, June 14-16, 2008, pages 46-54, 2008. URL: http://dx.doi.org/10.1145/1378533.1378540.
  23. Christoph Lenzen and Roger Wattenhofer. Leveraging Linial’s locality limit. In Distributed Computing, 22nd International Symposium, DISC 2008, Arcachon, France, September 22-24, 2008. Proceedings, pages 394-407, 2008. URL: http://dx.doi.org/10.1007/978-3-540-87779-0_27.
  24. Nathan Linial. Locality in distributed graph algorithms. SIAM J. Comput., 21(1):193-201, 1992. URL: http://dx.doi.org/10.1137/0221015.
  25. Baruch Mor, Pierre Fraigniaud, and Boaz Patt-Shamir. Randomized proof-labeling schemes. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21-23, 2015, pages 315-324, 2015. URL: http://dx.doi.org/10.1145/2767386.2767421.
  26. 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.
  27. David Peleg. Distributed Computing: A Locality-Sensitive Approach, volume 5. SIAM, 2000. Google Scholar
  28. Fabian Reiter. Distributed graph automata. In 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, July 6-10, 2015, pages 192-201, 2015. URL: http://dx.doi.org/10.1109/LICS.2015.27.
  29. Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. Distributed verification and hardness of distributed approximation. SIAM J. Comput., 41(5):1235-1265, 2012. URL: http://dx.doi.org/10.1137/11085178X.
  30. Marcus Schaefer. Deciding the Vapnik-Cervonenkis dimension in Σ^p₃-complete. J. Comput. Syst. Sci., 58(1):177-182, 1999. URL: http://dx.doi.org/10.1006/jcss.1998.1602.
  31. Marcus Schaefer and Christopher Umans. Completeness in the polynomial-time hierarchy: A compendium. SIGACT news, 33(3):32-49, 2002. Google Scholar
  32. Jukka Suomela. Survey of local algorithms. ACM Comput. Surv., 45(2):24, 2013. URL: http://dx.doi.org/10.1145/2431211.2431223.
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