{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,23]],"date-time":"2025-05-23T10:40:09Z","timestamp":1747996809071,"version":"3.41.0"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,5,11]],"date-time":"2025-05-11T00:00:00Z","timestamp":1746921600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,5,11]],"date-time":"2025-05-11T00:00:00Z","timestamp":1746921600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"ISF","award":["2070442"],"award-info":[{"award-number":["2070442"]}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["2402836","2348346"],"award-info":[{"award-number":["2402836","2348346"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2025,6]]},"DOI":"10.1007\/s00446-025-00483-x","type":"journal-article","created":{"date-parts":[[2025,5,11]],"date-time":"2025-05-11T07:09:46Z","timestamp":1746947386000},"page":"113-130","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Tight bounds on the message complexity of distributed tree verification"],"prefix":"10.1007","volume":"38","author":[{"given":"Shay","family":"Kutten","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Robinson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ming Ming","family":"Tan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,11]]},"reference":[{"issue":"8","key":"483_CR1","doi-asserted-by":"publisher","first-page":"2515","DOI":"10.1109\/26.310604","volume":"42","author":"B Awerbuch","year":"1994","unstructured":"Awerbuch, B., Bar-Noy, A., Gopal, M.: Approximate distributed bellman-ford algorithms. IEEE Trans. Commun. 42(8), 2515\u20132517 (1994)","journal-title":"IEEE Trans. Commun."},{"issue":"2","key":"483_CR2","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1145\/77600.77618","volume":"37","author":"B Awerbuch","year":"1990","unstructured":"Awerbuch, B., Goldreich, O., Vainish, R., Peleg, D.: A trade-off between information and communication in broadcast protocols. J. ACM (JACM) 37(2), 238\u2013256 (1990)","journal-title":"J. ACM (JACM)"},{"key":"483_CR3","doi-asserted-by":"crossref","unstructured":"Afek, Y., Kutten, S., Yung, M.: Memory-efficient self stabilizing protocols for general networks. In: Distributed Algorithms: 4th International Workshop Bari, Italy, September 24\u201326, 1990 Proceedings 4, pp. 15\u201328 (1991). Springer","DOI":"10.1007\/3-540-54099-7_2"},{"key":"483_CR4","doi-asserted-by":"publisher","first-page":"1091","DOI":"10.4153\/CJM-1966-109-8","volume":"18","author":"CT Benson","year":"1966","unstructured":"Benson, C.T.: Minimal regular graphs of girths eight and twelve. Can. J. Math. 18, 1091\u20131094 (1966)","journal-title":"Can. J. Math."},{"key":"483_CR5","unstructured":"Bollob\u00e1s, B.: Extremal graph theory. Courier Corporation (2004)"},{"issue":"6","key":"483_CR6","doi-asserted-by":"publisher","first-page":"1184","DOI":"10.1137\/0221070","volume":"21","author":"B Dixon","year":"1992","unstructured":"Dixon, B., Rauch, M., Tarjan, R.E.: Verification and sensitivity analysis of minimum spanning trees in linear time. SIAM J. Comput. 21(6), 1184\u20131192 (1992)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"483_CR7","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1145\/1054916.1054931","volume":"35","author":"M Elkin","year":"2004","unstructured":"Elkin, M.: Distributed approximation: a survey. ACM SIGACT News 35(4), 40\u201357 (2004)","journal-title":"ACM SIGACT News"},{"issue":"2","key":"483_CR8","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/3380546","volume":"67","author":"M Elkin","year":"2020","unstructured":"Elkin, M.: A simple deterministic distributed MST algorithm with near-optimal time and message complexities. J. ACM 67(2), 13\u201311315 (2020)","journal-title":"J. ACM"},{"key":"483_CR9","volume-title":"An introduction to probability theory and its applications","author":"W Feller","year":"1991","unstructured":"Feller, W.: An introduction to probability theory and its applications, vol. 2. Wiley, Hoboken (1991)"},{"key":"483_CR10","unstructured":"Feuilloley, L., Fraigniaud, P.: Survey of distributed decision. Bulletin of EATCS 1(119) (2016)"},{"issue":"5","key":"483_CR11","doi-asserted-by":"publisher","first-page":"1","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 (JACM) 60(5), 1\u201326 (2013)","journal-title":"J. ACM (JACM)"},{"issue":"1","key":"483_CR12","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1145\/7531.7919","volume":"34","author":"GN Frederickson","year":"1987","unstructured":"Frederickson, G.N., Lynch, N.A.: Electing a leader in a synchronous ring. J. ACM (JACM) 34(1), 98\u2013115 (1987)","journal-title":"J. ACM (JACM)"},{"issue":"1","key":"483_CR13","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)"},{"key":"483_CR14","doi-asserted-by":"publisher","unstructured":"Ghaffari, M., Kuhn, F.: Distributed MST and broadcast with fewer messages, and faster gossiping. In: Schmid, U., Widder, J. (eds.) 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15\u201319, 2018. LIPIcs, vol. 121, pp. 30\u201313012. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2018). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2018.30","DOI":"10.4230\/LIPIcs.DISC.2018.30"},{"key":"483_CR15","unstructured":"Gmyr, R., Pandurangan, G.: Time-message trade-offs in distributed algorithms. In: DISC. LIPIcs, vol. 121, pp. 32\u201313218. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2018)"},{"key":"483_CR16","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Trygub, A.: A near-optimal deterministic distributed synchronizer. In: PODC, pp. 180\u2013189. ACM (2023)","DOI":"10.1145\/3583668.3594598"},{"key":"483_CR17","doi-asserted-by":"crossref","unstructured":"Harel, D.: A linear algorithm for finding dominators in flow graphs and related problems. In: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pp. 185\u2013194 (1985)","DOI":"10.1145\/22145.22166"},{"issue":"3","key":"483_CR18","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1137\/16M1097808","volume":"50","author":"M Henzinger","year":"2021","unstructured":"Henzinger, M., Krinninger, S., Nanongkai, D.: A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. SIAM J. Comput. 50(3), 16\u20139816137 (2021). https:\/\/doi.org\/10.1137\/16M1097808","journal-title":"SIAM J. Comput."},{"key":"483_CR19","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF02526037","volume":"18","author":"V King","year":"1997","unstructured":"King, V.: A simpler minimum spanning tree verification algorithm. Algorithmica 18, 263\u2013270 (1997)","journal-title":"Algorithmica"},{"key":"483_CR20","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). https:\/\/doi.org\/10.1007\/s00446-007-0025-1","journal-title":"Distrib. Comput."},{"key":"483_CR21","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, 215\u2013233 (2010). https:\/\/doi.org\/10.1007\/s00446-010-0095-3","journal-title":"Distrib. Comput."},{"issue":"2","key":"483_CR22","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1007\/s00224-013-9479-7","volume":"53","author":"L Kor","year":"2013","unstructured":"Kor, L., Korman, A., Peleg, D.: Tight bounds for distributed minimum-weight spanning tree verification. Theory Comput. Syst. 53(2), 318\u2013340 (2013)","journal-title":"Theory Comput. Syst."},{"key":"483_CR23","doi-asserted-by":"crossref","unstructured":"King, V., Kutten, S., Thorup, M.: Construction and impromptu repair of an MST in a distributed network with $$o(m)$$ communication. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pp. 71\u201380 (2015)","DOI":"10.1145\/2767386.2767405"},{"key":"483_CR24","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/BF02278852","volume":"7","author":"S Katz","year":"1993","unstructured":"Katz, S., Perry, K.J.: Self-stabilizing extensions for meassage-passing systems. Distrib. Comput. 7, 17\u201326 (1993)","journal-title":"Distrib. Comput."},{"issue":"1","key":"483_CR25","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1145\/2699440","volume":"62","author":"S Kutten","year":"2015","unstructured":"Kutten, S., Pandurangan, G., Peleg, D., Robinson, P., Trehan, A.: On the complexity of universal leader election. J. ACM 62(1), 7\u20131727 (2015). https:\/\/doi.org\/10.1145\/2699440","journal-title":"J. ACM"},{"issue":"3","key":"483_CR26","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/S0020-0190(97)00050-1","volume":"62","author":"V King","year":"1997","unstructured":"King, V., Poon, C.K., Ramachandran, V., Sinha, S.: An optimal erew pram algorithm for minimum spanning tree verification. Inf. Process. Lett. 62(3), 153\u2013159 (1997)","journal-title":"Inf. Process. Lett."},{"key":"483_CR27","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Patt-Shamir, B.: Fast routing table construction using small messages. In: Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing, pp. 381\u2013390 (2013)","DOI":"10.1145\/2488608.2488656"},{"issue":"5","key":"483_CR28","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/j.jlap.2008.08.004","volume":"78","author":"M Leucker","year":"2009","unstructured":"Leucker, M., Schallhart, C.: A brief account of runtime verification. J. Logic Algebraic Program. 78(5), 293\u2013303 (2009)","journal-title":"J. Logic Algebraic Program."},{"key":"483_CR29","doi-asserted-by":"crossref","unstructured":"Mashreghi, A., King, V.: Time-communication trade-offs for minimum spanning tree construction. In: Proceedings of the 18th International Conference on Distributed Computing and Networking, Hyderabad, India, January 5\u20137, 2017, p. 8. ACM, (2017). http:\/\/dl.acm.org\/citation.cfm?id=3007775","DOI":"10.1145\/3007748.3007775"},{"key":"483_CR30","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"483_CR31","doi-asserted-by":"crossref","unstructured":"Nanongkai, D.: Distributed approximation algorithms for weighted shortest paths. In: Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, pp. 565\u2013573 (2014)","DOI":"10.1145\/2591796.2591850"},{"key":"483_CR32","doi-asserted-by":"crossref","unstructured":"Naor, M., Parter, M., Yogev, E.: The power of distributed verifiers in interactive proofs. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1096\u2013115 (2020). SIAM","DOI":"10.1137\/1.9781611975994.67"},{"key":"483_CR33","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: a Locality-sensitive Approach. SIAM (2000)","DOI":"10.1137\/1.9780898719772"},{"issue":"1","key":"483_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3022730","volume":"14","author":"M Parter","year":"2018","unstructured":"Parter, M., Peleg, D.: Fault-tolerant approximate BFS structures. ACM Trans. Algor (TALG) 14(1), 1\u201315 (2018)","journal-title":"ACM Trans. Algor (TALG)"},{"key":"483_CR35","doi-asserted-by":"publisher","unstructured":"Pai, S., Pandurangan, G., Pemmaraju, S.V., Riaz, T., Robinson, P.: Symmetry breaking in the congest model: Time- and message-efficient algorithms for ruling sets. In: Richa, A.W. (ed.) 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria. LIPIcs, vol. 91, pp. 38\u201313816. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2017). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2017.38","DOI":"10.4230\/LIPIcs.DISC.2017.38"},{"key":"483_CR36","doi-asserted-by":"crossref","unstructured":"Pai, S., Pandurangan, G., Pemmaraju, S.V., Robinson, P.: Can we break symmetry with $$o (m)$$ communication? In: PODC\u201921: Proceedings of the 2021 ACM symposium on principles of distributed computing, pp. 247\u2013257 (2021)","DOI":"10.1145\/3465084.3467909"},{"issue":"1","key":"483_CR37","first-page":"13","volume":"16","author":"G Pandurangan","year":"2020","unstructured":"Pandurangan, G., Robinson, P., Scquizzato, M.: A time- and message-optimal distributed algorithm for minimum spanning trees. ACM Trans. Algor. 16(1), 13\u201311327 (2020)","journal-title":"ACM Trans. Algor."},{"issue":"1","key":"483_CR38","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D Peleg","year":"1989","unstructured":"Peleg, D., Sch\u00e4ffer, A.A.: Graph spanners. J Graph Theory 13(1), 99\u2013116 (1989)","journal-title":"J Graph Theory"},{"issue":"5","key":"483_CR39","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1137\/11085178X","volume":"41","author":"AD Sarma","year":"2012","unstructured":"Sarma, A.D., 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."},{"issue":"4","key":"483_CR40","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1145\/322154.322161","volume":"26","author":"RE Tarjan","year":"1979","unstructured":"Tarjan, R.E.: Applications of path compression on balanced trees. J. ACM (JACM) 26(4), 690\u2013715 (1979)","journal-title":"J. ACM (JACM)"},{"issue":"1","key":"483_CR41","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0095-8956(91)90097-4","volume":"52","author":"R Wenger","year":"1991","unstructured":"Wenger, R.: Extremal graphs with no c4\u2019s, c6\u2019s, or c10\u2019s. J Comb Theory, Series B 52(1), 113\u2013116 (1991)","journal-title":"J Comb Theory, Series B"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-025-00483-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-025-00483-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-025-00483-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,23]],"date-time":"2025-05-23T10:03:46Z","timestamp":1747994626000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-025-00483-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,11]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["483"],"URL":"https:\/\/doi.org\/10.1007\/s00446-025-00483-x","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2025,5,11]]},"assertion":[{"value":"27 January 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 April 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 May 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflcit of interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}