{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,13]],"date-time":"2026-10-13T17:47:11Z","timestamp":1791913631088,"version":"4.3.4"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,2,8]],"date-time":"2021-02-08T00:00:00Z","timestamp":1612742400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,2,8]],"date-time":"2021-02-08T00:00:00Z","timestamp":1612742400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["Discovery Grant"],"award-info":[{"award-number":["Discovery Grant"]}],"id":[{"id":"10.13039\/501100002790","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,8]]},"DOI":"10.1007\/s00446-020-00387-y","type":"journal-article","created":{"date-parts":[[2021,2,9]],"date-time":"2021-02-09T07:53:17Z","timestamp":1612857197000},"page":"283-299","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Broadcast and minimum spanning tree with o(m) messages in the asynchronous CONGEST model"],"prefix":"10.1007","volume":"34","author":[{"given":"Ali","family":"Mashreghi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Valerie","family":"King","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,2,8]]},"reference":[{"key":"387_CR1","doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Graph sketches: sparsification, spanners, and subgraphs. In: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pp. 5\u201314. ACM (2012)","DOI":"10.1145\/2213556.2213560"},{"issue":"4","key":"387_CR2","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1145\/4221.4227","volume":"32","author":"B Awerbuch","year":"1985","unstructured":"Awerbuch, B.: Complexity of network synchronization. J ACM 32(4), 804\u2013823 (1985)","journal-title":"J ACM"},{"key":"387_CR3","doi-asserted-by":"crossref","unstructured":"Awerbuch, B.: Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of computing, pp. 230\u2013240. ACM (1987)","DOI":"10.1145\/28395.28421"},{"key":"387_CR4","volume-title":"On the Message Complexity of Broadcast: A Basic Lower Bound","author":"B Awerbuch","year":"1987","unstructured":"Awerbuch, B., Goldreich, O., Vainish, R.: On the Message Complexity of Broadcast: A Basic Lower Bound. Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge (1987)"},{"issue":"2","key":"387_CR5","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 37(2), 238\u2013256 (1990)","journal-title":"J ACM"},{"issue":"3","key":"387_CR6","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1109\/TDSC.2007.1007","volume":"4","author":"B Awerbuch","year":"2007","unstructured":"Awerbuch, B., Kutten, S., Mansour, Y., Patt-Shamir, B., Varghese, G.: A time-optimal self-stabilizing synchronizer using a phase clock. IEEE Trans Dependable Secure Comput 4(3), 180\u2013190 (2007)","journal-title":"IEEE Trans Dependable Secure Comput"},{"key":"387_CR7","unstructured":"Awerbuch, B., Peleg, D.: Network synchronization with polylogarithmic overhead. In: 31st Annual Symposium on Foundations of Computer Science, 1990. Proceedings., pp. 514\u2013522. IEEE (1990)"},{"key":"387_CR8","doi-asserted-by":"crossref","unstructured":"Chin, F., Ting, H.: An almost linear time and o (nlogn+ e) messages distributed algorithm for minimum-weight spanning trees. In: 26th Annual Symposium on Foundations of Computer Science, pp. 257\u2013266. IEEE (1985)","DOI":"10.1109\/SFCS.1985.7"},{"key":"387_CR9","unstructured":"Elkin, M.: A faster distributed protocol for constructing a minimum spanning tree. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 359\u2013368. Society for Industrial and Applied Mathematics (2004)"},{"issue":"2","key":"387_CR10","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1137\/S0097539704441058","volume":"36","author":"M Elkin","year":"2006","unstructured":"Elkin, M.: An unconditional lower bound on the time-approximation trade-off for the distributed minimum spanning tree problem. SIAM J. Comput. 36(2), 433\u2013456 (2006)","journal-title":"SIAM J. Comput."},{"key":"387_CR11","doi-asserted-by":"crossref","unstructured":"Elkin, M.: Synchronizers, spanners. In: Kao, Ming-Yang (ed) Encyclopedia of Algorithms, pp. 1\u201399. Springer (2008)","DOI":"10.1007\/978-0-387-30162-4_417"},{"key":"387_CR12","doi-asserted-by":"publisher","unstructured":"Elkin, M.: Distributed exact shortest paths in sublinear time. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pp. 757\u2013770. ACM, New York, NY, USA (2017). https:\/\/doi.org\/10.1145\/3055399.3055452","DOI":"10.1145\/3055399.3055452"},{"key":"387_CR13","doi-asserted-by":"crossref","unstructured":"Elkin, M.: A simple deterministic distributed mst algorithm, with near-optimal time and message complexities. arXiv preprint arXiv:1703.02411 (2017)","DOI":"10.1145\/3087801.3087823"},{"key":"387_CR14","doi-asserted-by":"crossref","unstructured":"Emek, Y., Korman, A.: Efficient threshold detection in a distributed environment. In: Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp. 183\u2013191. ACM (2010)","DOI":"10.1145\/1835698.1835742"},{"key":"387_CR15","doi-asserted-by":"crossref","unstructured":"Faloutsos, M., Molle, M.: Optimal distributed algorithm for minimum spanning trees revisited. In: Proceedings of the Fourteenth Annual ACM Symposium on Principles of DistributCd computing, pp. 231\u2013237. ACM (1995)","DOI":"10.1145\/224964.225474"},{"key":"387_CR16","doi-asserted-by":"crossref","unstructured":"Gafni, E.: Improvements in the time complexity of two message-optimal election algorithms. In: Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, pp. 175\u2013185. ACM (1985)","DOI":"10.1145\/323596.323612"},{"issue":"1","key":"387_CR17","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. 5(1), 66\u201377 (1983)","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"1","key":"387_CR18","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1137\/S0097539794261118","volume":"27","author":"JA Garay","year":"1998","unstructured":"Garay, J.A., Kutten, S., Peleg, D.: A sublinear time distributed algorithm for minimum-weight spanning trees. SIAM J. Comput. 27(1), 302\u2013316 (1998)","journal-title":"SIAM J. Comput."},{"key":"387_CR19","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). Leibniz International Proceedings in Informatics (LIPIcs), vol. 121, pp. 30:1\u201330:12. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2018.30. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/9819","DOI":"10.4230\/LIPIcs.DISC.2018.30"},{"key":"387_CR20","doi-asserted-by":"publisher","unstructured":"Gmyr, R., Pandurangan, G.: Time-Message Trade-Offs in Distributed Algorithms. In: Schmid, U., Widder , J. (eds.) 32nd International Symposium on Distributed Computing (DISC 2018), Leibniz International Proceedings in Informatics (LIPIcs), vol. 121, pp. 32:1\u201332:18. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2018.32. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/9821","DOI":"10.4230\/LIPIcs.DISC.2018.32"},{"key":"387_CR21","doi-asserted-by":"crossref","unstructured":"Kapron, B.M., King, V., Mountjoy, B.: Dynamic graph connectivity in polylogarithmic worst case time. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1131\u20131142. Society for Industrial and Applied Mathematics (2013)","DOI":"10.1137\/1.9781611973105.81"},{"key":"387_CR22","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. ACM (2015)","DOI":"10.1145\/2767386.2767405"},{"issue":"1","key":"387_CR23","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 leader election. J. ACM 62(1), 7 (2015)","journal-title":"J. ACM"},{"key":"387_CR24","doi-asserted-by":"crossref","unstructured":"Kutten, S., Peleg, D.: Fast distributed construction of k-dominating sets and applications. In: Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, pp. 238\u2013251. ACM (1995)","DOI":"10.1145\/224964.224990"},{"key":"387_CR25","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, p.\u00a08. ACM (2017)","DOI":"10.1145\/3007748.3007775"},{"key":"387_CR26","unstructured":"Mashreghi, A., King, V.: Brief announcement: faster asynchronous mst and low diameter tree construction with sublinear communication. In: 33rd International Symposium on Distributed Computing (DISC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2019)"},{"key":"387_CR27","unstructured":"Mashreghi, A., King, V.: Faster asynchronous mst and low diameter tree construction with sublinear communication. arXiv preprint arXiv:1907.12152 (2019)"},{"key":"387_CR28","doi-asserted-by":"crossref","unstructured":"Pandurangan, G., Robinson, P., Scquizzato, M.: A time-and message-optimal distributed algorithm for minimum spanning trees. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 743\u2013756. ACM (2017)","DOI":"10.1145\/3055399.3055449"},{"issue":"5","key":"387_CR29","doi-asserted-by":"publisher","first-page":"1427","DOI":"10.1137\/S0097539700369740","volume":"30","author":"D Peleg","year":"2000","unstructured":"Peleg, D., Rubinovich, V.: A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction. SIAM J. Comput. 30(5), 1427\u20131442 (2000). https:\/\/doi.org\/10.1137\/S0097539700369740","journal-title":"SIAM J. Comput."},{"key":"387_CR30","doi-asserted-by":"crossref","unstructured":"Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. In: Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, pp. 77\u201385. ACM (1987)","DOI":"10.1145\/41840.41847"},{"issue":"5","key":"387_CR31","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":"3","key":"387_CR32","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/BF02242717","volume":"8","author":"G Singh","year":"1995","unstructured":"Singh, G., Bernstein, A.J.: A highly asynchronous minimum spanning tree protocol. Distrib. Comput. 8(3), 151\u2013161 (1995)","journal-title":"Distrib. Comput."}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-020-00387-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-020-00387-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-020-00387-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T05:04:28Z","timestamp":1626843868000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-020-00387-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,8]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["387"],"URL":"https:\/\/doi.org\/10.1007\/s00446-020-00387-y","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,8]]},"assertion":[{"value":"28 February 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 December 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 February 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}