LIPIcs.DISC.2018.25.pdf
- Filesize: 491 kB
- 17 pages
Document
Local Verification of Global Proofs
Authors
Laurent Feuilloley 
,
-
Part of:
Volume:
32nd International Symposium on Distributed Computing (DISC 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Distributed Computing (DISC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-10-04
File
Document Identifiers
Author Details
Cite AsGet BibTex
Laurent Feuilloley and Juho Hirvonen. Local Verification of Global Proofs. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.DISC.2018.25
https://doi.org/10.4230/LIPIcs.DISC.2018.25
Abstract
In this work we study the cost of local and global proofs on distributed verification. In this setting the nodes of a distributed system are provided with a nondeterministic proof for the correctness of the state of the system, and the nodes need to verify this proof by looking at only their local neighborhood in the system.
Previous works have studied the model where each node is given its own, possibly unique, part of the proof as input. The cost of a proof is the maximum size of an individual label. We compare this model to a model where each node has access to the same global proof, and the cost is the size of this global proof.
It is easy to see that a global proof can always include all of the local proofs, and every local proof can be a copy of the global proof. We show that there exists properties that exhibit these relative proof sizes, and also properties that are somewhere in between. In addition, we introduce a new lower bound technique and use it to prove a tight lower bound on the complexity of reversing distributed decision and establish a link between communication complexity and distributed proof complexity.
Subject Classification
ACM Subject Classification
- Theory of computation → Distributed computing models
- Theory of computation → Proof complexity
Keywords
- Proof-labeling schemes
- distributed verification
- non-determinism
- local proofs
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Lazslo Babai, Peter Frankl, and Janos Simon. Complexity classes in communication complexity theory. In Proc. 27th Annual Symposium on Foundations of Computer Science (FOCS 1986), pages 337-347, 1986. URL: http://dx.doi.org/10.1109/SFCS.1986.15.
-
Jørgen Bang-Jensen and Gregory Gutin. Digraphs - theory, algorithms and applications. Springer, 2002.
- Keren Censor-Hillel, Ami Paz, and Mor Perry. Approximate proof-labeling schemes. In Structural Information and Communication Complexity - 24th International Colloquium, SIROCCO 2017, Porquerolles, France, June 19-22, 2017, Revised Selected Papers, pages 71-89, 2017. URL: http://dx.doi.org/10.1007/978-3-319-72050-0_5.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009. URL: http://mitpress.mit.edu/books/introduction-algorithms.
- 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.
- Laurent Feuilloley and Pierre Fraigniaud. Error-sensitive proof-labeling schemes. In 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria, pages 16:1-16:15, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.DISC.2017.16.
- Laurent Feuilloley, Pierre Fraigniaud, and Juho Hirvonen. A Hierarchy of Local Decision. In Proc. 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 118:1-118:15, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.118.
- Pierre Fraigniaud, Amos Korman, and David Peleg. Local distributed decision. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 708-717, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.17.
- 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.
- Mika Göös, Toniann Pitassi, and Thomas Watson. The landscape of communication complexity classes. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 86:1-86:15, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.86.
- 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.
- Tom Gur and Ron D. Rothblum. Non-interactive proofs of proximity. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015, pages 133-142, 2015. URL: http://dx.doi.org/10.1145/2688073.2688079.
- 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.
- Amos Korman, Shay Kutten, and David Peleg. Proof labeling schemes. In Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing, PODC 2005, Las Vegas, NV, USA, July 17-20, 2005, pages 9-18, 2005. URL: http://dx.doi.org/10.1145/1073814.1073817.
- 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.
- Elias Koutsoupias and Christos H. Papadimitriou. Worst-case equilibria. Computer Science Review, 3(2):65-69, 2009. URL: http://dx.doi.org/10.1016/j.cosrev.2009.04.003.
- Fabian Kuhn. The price of locality: exploring the complexity of distributed coordination primitives. PhD thesis, ETH Zurich, 2005. URL: http://d-nb.info/977273725.
-
Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, 1997.
- 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.
- Rafail Ostrovsky, Mor Perry, and Will Rosenbaum. Space-time tradeoffs for distributed verification. In Structural Information and Communication Complexity - 24th International Colloquium, SIROCCO 2017, Porquerolles, France, June 19-22, 2017, Revised Selected Papers, pages 53-70, 2017. URL: http://dx.doi.org/10.1007/978-3-319-72050-0_4.
- Christos H. Papadimitriou. Algorithms, games, and the internet. In Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pages 749-753, 2001. URL: http://dx.doi.org/10.1145/380752.380883.
- Boaz Patt-Shamir and Mor Perry. Proof-labeling schemes: Broadcast, unicast and in between. In Stabilization, Safety, and Security of Distributed Systems - 19th International Symposium, SSS 2017, Boston, MA, USA, November 5-8, 2017, Proceedings, pages 1-17, 2017. URL: http://dx.doi.org/10.1007/978-3-319-69084-1_1.