{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:42:19Z","timestamp":1782970939055,"version":"3.54.5"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,10,7]],"date-time":"2020-10-07T00:00:00Z","timestamp":1602028800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,10,7]],"date-time":"2020-10-07T00:00:00Z","timestamp":1602028800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P 33775-N"],"award-info":[{"award-number":["P 33775-N"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2021,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Distributed proofs are mechanisms that enable 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 objects distributed over the nodes (e.g., a spanning tree). We consider well known mechanisms consisting of two components: a<jats:italic>prover<\/jats:italic>that assigns a<jats:italic>certificate<\/jats:italic>to each node, and a distributed algorithm called a<jats:italic>verifier<\/jats:italic>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<jats:italic>size of the certificate<\/jats:italic>stored at every node, and the<jats:italic>number of rounds<\/jats:italic>of the verification protocol.<\/jats:p>","DOI":"10.1007\/s00446-020-00386-z","type":"journal-article","created":{"date-parts":[[2020,10,7]],"date-time":"2020-10-07T20:02:37Z","timestamp":1602100957000},"page":"113-132","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Redundancy in distributed proofs"],"prefix":"10.1007","volume":"34","author":[{"given":"Laurent","family":"Feuilloley","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pierre","family":"Fraigniaud","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Juho","family":"Hirvonen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ami","family":"Paz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mor","family":"Perry","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,10,7]]},"reference":[{"key":"386_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Censor-Hillel, K., Khoury, S.: Near-linear lower bounds for distributed distance computations, even in sparse networks. In: 30th International Symposium on Distributed Computing (DISC), pp. 29\u201342 (2016). arXiv:1901.01630","DOI":"10.1007\/978-3-662-53426-7_3"},{"issue":"5","key":"386_CR2","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1006\/jpdc.2001.1823","volume":"62","author":"Y Afek","year":"2002","unstructured":"Afek, Y., Dolev, S.: Local stabilizer. J. Parallel Distrib. Comput. 62(5), 745\u2013765 (2002)","journal-title":"J. Parallel Distrib. Comput."},{"issue":"1","key":"386_CR3","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/S0304-3975(96)00286-1","volume":"186","author":"Y Afek","year":"1997","unstructured":"Afek, Y., Kutten, S., Yung, M.: The local detection paradigm and its applications to self-stabilization. Theor. Comput. Sci. 186(1), 199\u2013229 (1997)","journal-title":"Theor. Comput. Sci."},{"key":"386_CR4","doi-asserted-by":"crossref","unstructured":"Arfaoui, H., Fraigniaud, P., Ilcinkas, D., Mathieu, F.: Distributedly testing cycle-freeness. In: 40th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), vol. 8747, LNCS, Springer, pp. 15\u201328 (2014)","DOI":"10.1007\/978-3-319-12340-0_2"},{"key":"386_CR5","doi-asserted-by":"crossref","unstructured":"Arfaoui, H., Fraigniaud, P., Pelc, A.: Local decision and verification with bounded-size outputs. In: 15th Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), vol. 8255, LNCS, Springer, pp. 133\u2013147 (2013)","DOI":"10.1007\/978-3-319-03089-0_10"},{"key":"386_CR6","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Ostrovsky, R.: Memory-efficient and self-stabilizing network reset (extended abstract). In: Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, PODC \u201994, ACM, New York, NY, USA, pp. 254\u2013263 (1994)","DOI":"10.1145\/197917.198104"},{"key":"386_CR7","unstructured":"Awerbuch, B., Patt-Shamir, B., Varghese, G.: Self-stabilization by local checking and correction. In: 32nd Symposium on Foundations of Computer Science (FOCS), IEEE, pp. 268\u2013277 (1991)"},{"key":"386_CR8","unstructured":"Balliu, A., D\u2019Angelo, G., Fraigniaud, P., Olivetti, D.: What can be verified locally? In: 34th Symposium on Theoretical Aspects of Computer Science (STACS), vol.\u00a066, LIPIcs, pp. 8:1\u20138:13 (2017)"},{"key":"386_CR9","doi-asserted-by":"crossref","unstructured":"Bampas, E., Ilcinkas, D.: On mobile agent verifiable problems. In: 12th Latin American Symposium on Theoretical Informatics (LATIN), LNCS, vol. 9644, Springer, pp. 123\u2013137 (2016)","DOI":"10.1007\/978-3-662-49529-2_10"},{"issue":"1","key":"386_CR10","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s00446-007-0029-x","volume":"20","author":"J Beauquier","year":"2007","unstructured":"Beauquier, J., Dela\u00ebt, S., Dolev, S., Tixeuil, S.: Transient fault detectors. Distrib. Comput. 20(1), 39\u201351 (2007)","journal-title":"Distrib. Comput."},{"key":"386_CR11","doi-asserted-by":"crossref","unstructured":"Blin, L., Fraigniaud, P.: Space-optimal time-efficient silent self-stabilizing constructions of constrained spanning trees. In: 35th International Conference on Distributed Computing Systems (ICDCS), IEEE, pp. 589\u2013598 (2015)","DOI":"10.1109\/ICDCS.2015.66"},{"key":"386_CR12","doi-asserted-by":"crossref","unstructured":"Blin, L., Fraigniaud, P., Patt-Shamir, B.: On proof-labeling schemes versus silent self-stabilizing algorithms. In: 16th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), LNCS, Springer, pp. 18\u201332 (2014)","DOI":"10.1007\/978-3-319-11764-5_2"},{"key":"386_CR13","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1016\/j.tcs.2018.08.020","volume":"811","author":"K Censor-Hillel","year":"2020","unstructured":"Censor-Hillel, K., Paz, A., Perry, M.: Approximate proof-labeling schemes. Theor. Comput. Sci. 811, 112\u2013124 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"386_CR14","doi-asserted-by":"crossref","unstructured":"Chi-Chih Yao, A.: Some complexity questions related to distributive computing. In: 11th Symposium on Theory of Computing (STOC), ACM, pp. 209\u2013213 (1979)","DOI":"10.1145\/800135.804414"},{"key":"386_CR15","unstructured":"Crescenzi, P., Fraigniaud, P., Paz, A.: Trade-offs in distributed interactive proofs. In: 33rd International Symposium on Distributed Computing (DISC), pp. 13:1\u201313:17 (2019)"},{"issue":"5","key":"386_CR16","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1137\/11085178X","volume":"41","author":"A Das Sarma","year":"2012","unstructured":"Das Sarma, A., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. SIAM J. Comput. 41(5), 1235\u20131265 (2012)","journal-title":"SIAM J. Comput."},{"key":"386_CR17","doi-asserted-by":"crossref","unstructured":"Elkin, M.: Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), pp. 331\u2013340 (2004)","DOI":"10.1145\/1007352.1007407"},{"key":"386_CR18","unstructured":"Feuilloley, L., Fraigniaud, P.: Survey of distributed decision. In: Bulletin of the EATCS, vol. 119 (2016)"},{"key":"386_CR19","unstructured":"Feuilloley, L., Fraigniaud, P.: Error-sensitive proof-labeling schemes. In: 31st International Symposium on Distributed Computing (DISC), pp. 16:1\u201316:15 (2017)"},{"key":"386_CR20","unstructured":"Feuilloley, L., Fraigniaud, P., Hirvonen, J.: A hierarchy of local decision. In: 43rd International Colloquium on Automata, Languages, and Programming (ICALP), LIPIcs, pp. 118:1\u2013118:15 (2016)"},{"key":"386_CR21","unstructured":"Feuilloley, L., Fraigniaud, P., Hirvonen, J., Paz, A., Perry, M.: Redundancy in distributed proofs. In: Schmid, U., Widder, J. (eds), 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15\u201319, 2018, vol. 121, LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp. 24:1\u201324:18 (2018)"},{"key":"386_CR22","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/j.tcs.2016.11.018","volume":"709","author":"K-T Foerster","year":"2018","unstructured":"Foerster, K.-T., Luedi, T., Seidel, J., Wattenhofer, R.: Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in sdns. Theor. Comput. Sci. 709, 48\u201363 (2018)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"386_CR23","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1145\/2499228","volume":"60","author":"P Fraigniaud","year":"2013","unstructured":"Fraigniaud, P., Korman, A., Peleg, D.: Towards a complexity theory for local distributed computing. J. ACM 60(5), 35 (2013)","journal-title":"J. ACM"},{"issue":"3","key":"386_CR24","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/s00446-018-0340-8","volume":"32","author":"P Fraigniaud","year":"2019","unstructured":"Fraigniaud, P., Patt-Shamir, B., Perry, M.: Randomized proof-labeling schemes. Distrib. Comput. 32(3), 217\u2013234 (2019)","journal-title":"Distrib. Comput."},{"key":"386_CR25","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.jpdc.2017.04.003","volume":"109","author":"P Fraigniaud","year":"2017","unstructured":"Fraigniaud, P., Pelc, A.: Decidability classes for mobile agents computing. J. Parallel Distrib. Comput. 109, 117\u2013128 (2017)","journal-title":"J. Parallel Distrib. Comput."},{"key":"386_CR26","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Rajsbaum, S., Travers, C.: Minimizing the number of opinions for fault-tolerant distributed decision using well-quasi orderings. In: 12th Latin American Symposium on Theoretical Informatics (LATIN), Springer, pp. 497\u2013508 (2016)","DOI":"10.1007\/978-3-662-49529-2_37"},{"key":"386_CR27","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Rajsbaum, S., Travers, C., Kuznetsov, P., Rieutord, T.: Perfect failure detection with very few bits. In: 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), LNCS 10083, Springer, pp. 154\u2013169 (2016)","DOI":"10.1007\/978-3-319-49259-9_13"},{"key":"386_CR28","doi-asserted-by":"crossref","unstructured":"Frischknecht, S., Holzer, S., Wattenhofer, R.: Networks cannot compute their diameter in sublinear time. In: 23rd Symposium on Discrete Algorithms (SODA), ACM-SIAM, pp. 1150\u20131162 (2012)","DOI":"10.1137\/1.9781611973099.91"},{"issue":"1","key":"386_CR29","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1145\/357195.357200","volume":"5","author":"RG Gallager","year":"1983","unstructured":"Gallager, R.G., Humblet, P.A., Spira, P.M.: A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst. (TOPLAS) 5(1), 66\u201377 (1983)","journal-title":"ACM Trans. Program. Lang. Syst. (TOPLAS)"},{"issue":"1","key":"386_CR30","first-page":"1","volume":"12","author":"M G\u00f6\u00f6s","year":"2016","unstructured":"G\u00f6\u00f6s, M., Suomela, J.: Locally checkable proofs in distributed computing. Theory Comput. 12(1), 1\u201333 (2016)","journal-title":"Theory Comput."},{"key":"386_CR31","unstructured":"Itkis, G., Levin, L.: Fast and lean self-stabilizing asynchronous protocols. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, SFCS \u201994, IEEE Computer Society, Washington, DC, USA, pp. 226\u2013239 (1994)"},{"key":"386_CR32","unstructured":"Itkis, G., Levin, L.A.: Fast and lean self-stabilizing asynchronous protocols. In: 35th Symposium on Foundations of Computer Science (FOCS), IEEE, pp. 226\u2013239 (1994)"},{"key":"386_CR33","doi-asserted-by":"crossref","unstructured":"Kol, G., Oshman, R., Saxena, R.R.: Interactive distributed proofs. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC, pp. 255\u2013264 (2018)","DOI":"10.1145\/3212734.3212771"},{"key":"386_CR34","unstructured":"Korhonen, J.H., Suomela, J.: Brief announcement: Towards a complexity theory for the congested clique. In: 31st International Symposium on Distributed Computing (DISC), pp. 55:1\u201355:3 (2017)"},{"key":"386_CR35","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/s00446-007-0025-1","volume":"20","author":"A Korman","year":"2007","unstructured":"Korman, A., Kutten, S.: Distributed verification of minimum spanning trees. Distrib. Comput. 20, 253\u2013266 (2007)","journal-title":"Distrib. Comput."},{"issue":"4","key":"386_CR36","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/s00446-015-0242-y","volume":"28","author":"A Korman","year":"2015","unstructured":"Korman, A., Kutten, S., Masuzawa, T.: Fast and compact self-stabilizing verification, computation, and fault detection of an MST. Distrib. Comput. 28(4), 253\u2013295 (2015)","journal-title":"Distrib. Comput."},{"issue":"4","key":"386_CR37","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/s00446-010-0095-3","volume":"22","author":"A Korman","year":"2010","unstructured":"Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. Distrib. Comput. 22(4), 215\u2013233 (2010)","journal-title":"Distrib. Comput."},{"key":"386_CR38","volume-title":"Communication Complexity","author":"E Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, New York (1997)"},{"key":"386_CR39","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"M Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005)"},{"key":"386_CR40","doi-asserted-by":"crossref","unstructured":"Naor, M., Parter, M., Yogev, E.: The power of distributed verifiers in interactive proofs. In: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1096\u2013115 (2020)","DOI":"10.1137\/1.9781611975994.67"},{"key":"386_CR41","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Perry, M., Rosenbaum, W.: Space-time tradeoffs for distributed verification. In: 24th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 53\u201370 (2017)","DOI":"10.1007\/978-3-319-72050-0_4"},{"key":"386_CR42","doi-asserted-by":"crossref","unstructured":"Patt-Shamir, B., Perry, M.: Proof-labeling schemes: broadcast, unicast and in between. In: 19th Int. Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), LNCS 10616, Springer, pp. 1\u201317 (2017)","DOI":"10.1007\/978-3-319-69084-1_1"},{"key":"386_CR43","series-title":"Discrete Mathematics and Applications","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Discrete Mathematics and Applications. SIAM, Philadelphia (2000)"},{"key":"386_CR44","unstructured":"Peleg, D., Rubinovich, V.: A near-tight lower bound on the time complexity of distributed MST construction. In: 40th Symposium on Foundations of Computer Science (FOCS), IEEE, pp. 253\u2013261 (1999)"},{"issue":"1","key":"386_CR45","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1137\/0220006","volume":"20","author":"JD Ullman","year":"1991","unstructured":"Ullman, J.D., Yannakakis, M.: High-probability parallel transitive-closure algorithms. SIAM J. Comput. 20(1), 100\u2013125 (1991)","journal-title":"SIAM J. Comput."}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-020-00386-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-020-00386-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-020-00386-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,15]],"date-time":"2024-08-15T17:23:35Z","timestamp":1723742615000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-020-00386-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,7]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["386"],"URL":"https:\/\/doi.org\/10.1007\/s00446-020-00386-z","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,10,7]]},"assertion":[{"value":"8 October 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 September 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 October 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}