{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,29]],"date-time":"2026-06-29T01:46:45Z","timestamp":1782697605893,"version":"3.54.5"},"reference-count":61,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T00:00:00Z","timestamp":1773792000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T00:00:00Z","timestamp":1773792000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005717","name":"University of Haifa","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005717","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2026,6]]},"abstract":"Abstract<\/jats:title>\n \n In this work we present the first\n constant-round<\/jats:italic>\n algorithms for computing spanners and approximate All-Pairs Shortest Paths (APSP) in the distributed\n Congested Clique<\/jats:sc>\n model. Specifically, we show the following results for undirected\n n<\/jats:italic>\n -node graphs.\n \n \n \n For every integer\n \n $$k \\ge 1$$<\/jats:tex-math>\n <\/jats:inline-formula>\n ,\n O<\/jats:italic>\n (1)-round algorithms for constructing\n O<\/jats:italic>\n (\n k<\/jats:italic>\n )-spanners with\n \n $$O(n^{1+1\/k})$$<\/jats:tex-math>\n <\/jats:inline-formula>\n edges in\n unweighted<\/jats:italic>\n graphs, and\n O<\/jats:italic>\n (\n k<\/jats:italic>\n )-spanners with\n \n $$O(n^{1+1\/k} \\log {n})$$<\/jats:tex-math>\n <\/jats:inline-formula>\n edges in\n weighted<\/jats:italic>\n graphs.\n <\/jats:p>\n <\/jats:list-item>\n \n \n An\n O<\/jats:italic>\n (1)-round algorithm for\n \n $$O(\\log {n})$$<\/jats:tex-math>\n <\/jats:inline-formula>\n -approximation for APSP in\n unweighted<\/jats:italic>\n graphs.\n <\/jats:p>\n <\/jats:list-item>\n \n \n An\n O<\/jats:italic>\n (1)-round algorithm for\n \n $$O(\\log ^2{n})$$<\/jats:tex-math>\n <\/jats:inline-formula>\n -approximation for APSP in\n weighted<\/jats:italic>\n graphs.\n <\/jats:p>\n <\/jats:list-item>\n <\/jats:list>\n All our algorithms are randomized and succeed with high probability. Prior to our work, the fastest algorithms for computing\n O<\/jats:italic>\n (\n k<\/jats:italic>\n )-spanners in this model require\n \n $${{\\,\\textrm{poly}\\,}}(\\log {k})$$<\/jats:tex-math>\n <\/jats:inline-formula>\n rounds [Parter, Yogev, DISC \u201918] [Biswas, Dory, Ghaffari, Mitrovic, Nazari, SPAA \u201921], and the fastest algorithms for approximate shortest paths require\n \n $${{\\,\\textrm{poly}\\,}}(\\log {\\log {n}})$$<\/jats:tex-math>\n <\/jats:inline-formula>\n rounds [Dory, Parter, PODC \u201920]. Our results extend to the closely related massively parallel computation (MPC) model with near-linear memory per machine, leading to the first\n O<\/jats:italic>\n (1)-round algorithms for spanners and approximate shortest paths in this model as well.\n <\/jats:p>","DOI":"10.1007\/s00446-025-00503-w","type":"journal-article","created":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T01:33:31Z","timestamp":1773797611000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Constant-round spanners and shortest paths in congested clique and MPC"],"prefix":"10.1007","volume":"39","author":[{"given":"Michal","family":"Dory","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Orr","family":"Fischer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Seri","family":"Khoury","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dean","family":"Leitersdorf","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,3,18]]},"reference":[{"issue":"1","key":"503_CR1","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I Alth\u00f6fer","year":"1993","unstructured":"Alth\u00f6fer, I., Das, G., Dobkin, D., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete & Computational Geometry 9(1), 81\u2013100 (1993)","journal-title":"Discrete & Computational Geometry"},{"key":"503_CR2","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Peleg, D.: Network synchronization with polylogarithmic overhead. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science (FOCS), pages 514\u2013522, (1990)","DOI":"10.1109\/FSCS.1990.89572"},{"issue":"2","key":"503_CR3","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1137\/0405013","volume":"5","author":"B Awerbuch","year":"1992","unstructured":"Awerbuch, B., Peleg, D.: Routing with polynomial communication-space trade-off. SIAM Journal on Discrete Mathematics 5(2), 151\u2013162 (1992)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"503_CR4","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Patt-Shamir, B., Peleg, D., Saks, M.: Adapting to asynchronous dynamic networks. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing (STOC), pages 557\u2013570, (1992)","DOI":"10.1145\/129712.129767"},{"issue":"3","key":"503_CR5","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/j.ipl.2007.11.001","volume":"106","author":"S Baswana","year":"2008","unstructured":"Baswana, S.: Streaming algorithm for graph spanners? single pass and constant processing time per edge. Inf. Process. Lett. 106(3), 110\u2013114 (2008)","journal-title":"Inf. Process. Lett."},{"key":"503_CR6","doi-asserted-by":"crossref","unstructured":"Bui, H.D., Chandra, S., Chang, Y.J., Dory, M., Leitersdorf, D.: Improved all-pairs approximate shortest paths in congested clique. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing (PODC), pages 391\u2013400, (2024)","DOI":"10.1145\/3662158.3662804"},{"key":"503_CR7","doi-asserted-by":"crossref","unstructured":"Biswas, A S., Dory, M., Ghaffari, M., Mitrovic, S., Nazari, Y.: Massively parallel algorithms for distance approximation and spanners. SPAA 2021, (2021)","DOI":"10.1145\/3409964.3461784"},{"key":"503_CR8","unstructured":"Behnezhad, S., Derakhshan, M., Hajiaghayi, M.: Brief announcement: Semi-mapreduce meets congested clique. CoRR, (2018) arXiv:abs\/1802.10297"},{"key":"503_CR9","unstructured":"Bodwin, G., Krinninger, S.: Fully dynamic spanners with worst-case update time. In 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, pages 17:1\u201317:18, (2016)"},{"key":"503_CR10","unstructured":"Becker, R., Karrenbauer, A., Krinninger, S., Lenzen, C.: Near-optimal approximate shortest paths and transshipment in distributed and streaming models. In 31 International Symposium on Distributed Computing, (2017)"},{"issue":"4","key":"503_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2344422.2344425","volume":"8","author":"S Baswana","year":"2012","unstructured":"Baswana, S., Khurana, S., Sarkar, S.: Fully dynamic randomized algorithms for graph spanners. ACM Transactions on Algorithms 8(4), 1\u201351 (2012)","journal-title":"ACM Transactions on Algorithms"},{"issue":"4","key":"503_CR12","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1145\/1198513.1198518","volume":"2","author":"S Baswana","year":"2006","unstructured":"Baswana, S., Sen, S.: Approximate distance oracles for unweighted graphs in expected O(n2) time. ACM Transactions on Algorithms 2(4), 557\u2013577 (2006)","journal-title":"ACM Transactions on Algorithms"},{"issue":"4","key":"503_CR13","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1002\/rsa.20130","volume":"30","author":"S Baswana","year":"2007","unstructured":"Baswana, S., Sen, S.: A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Structures & Algorithms 30(4), 532\u2013563 (2007)","journal-title":"Random Structures & Algorithms"},{"key":"503_CR14","doi-asserted-by":"crossref","unstructured":"Censor-Hillel, K., Dory, M., Korhonen, J.H., Leitersdorf., D.: Fast approximate shortest paths in the congested clique. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019., pages 74\u201383, (2019)","DOI":"10.1145\/3293611.3331633"},{"key":"503_CR15","doi-asserted-by":"crossref","unstructured":"Censor-Hillel, K., Dory, M.: Distributed spanner approximation. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC), pages 139\u2013148, (2018)","DOI":"10.1145\/3212734.3212758"},{"key":"503_CR16","doi-asserted-by":"crossref","unstructured":"Chechik, S.: Compact routing schemes with improved stretch. In Proceedings of the 2013 ACM symposium on Principles of distributed computing (PODC), pages 33\u201341, (2013)","DOI":"10.1145\/2484239.2484268"},{"issue":"6","key":"503_CR17","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00446-016-0270-2","volume":"32","author":"K Censor-Hillel","year":"2019","unstructured":"Censor-Hillel, K., Kaski, P., Korhonen, J.H., Lenzen, C., Paz, A., Suomela, J.: Algebraic methods in the congested clique. Distributed Computing 32(6), 461\u2013478 (2019)","journal-title":"Distributed Computing"},{"key":"503_CR18","doi-asserted-by":"crossref","unstructured":"Censor-Hillel, K., Kavitha, T., Paz, A., Yehudayoff, A.: Distributed construction of purely additive spanners. In International Symposium on Distributed Computing (DISC), pages 129\u2013142, (2016)","DOI":"10.1007\/978-3-662-53426-7_10"},{"key":"503_CR19","doi-asserted-by":"crossref","unstructured":"Censor-Hillel, K., Leitersdorf, D., Turner, E.: Sparse matrix multiplication and triangle listing in the congested clique model. Theoretical Computer Science, (2019)","DOI":"10.1016\/j.tcs.2019.11.006"},{"key":"503_CR20","unstructured":"Cormen, T H., Leiserson, C E., Rivest, R L., Stein, C.: Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, (2009)"},{"key":"503_CR21","doi-asserted-by":"crossref","unstructured":"Chechik, S., Zhang, T.: Constant-round near-optimal spanners in congested clique. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (PODC), pages 325\u2013334, (2022)","DOI":"10.1145\/3519270.3538439"},{"key":"503_CR22","unstructured":"Dean, J., Ghemawat, S.: MapReduce: Simplified data processing on large clusters. In Proceedings of the 6th Conference on Symposium on Operating Systems Design & Implementation (OSDI), pages 10\u201310, Berkeley, CA, USA, 2004. USENIX Association"},{"key":"503_CR23","doi-asserted-by":"crossref","unstructured":"Derbel, B., Gavoille, C., Peleg, D., Viennot, L.: On the locality of distributed sparse spanner construction. In Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing (PODC), pages 273\u2013282, (2008)","DOI":"10.1145\/1400751.1400788"},{"key":"503_CR24","doi-asserted-by":"crossref","unstructured":"Dory, M., Matar, S.: Massively parallel algorithms for approximate shortest paths. In Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 415\u2013426, (2024)","DOI":"10.1145\/3626183.3659978"},{"key":"503_CR25","unstructured":"Dinitz, M., Nazari, Y.: Distributed distance-bounded network design through distributed convex programming. In 21st International Conference on Principles of Distributed Systems, OPODIS 2017, pages 5:1\u20135:19, (2017)"},{"key":"503_CR26","unstructured":"Dinitz, M., Nazari, Y.: Massively parallel approximate distance sketches. In 23rd International Conference on Principles of Distributed Systems, OPODIS 2019, December 17-19, 2019, Neuch\u00e2tel, Switzerland, pages 35:1\u201335:17, (2019)"},{"key":"503_CR27","doi-asserted-by":"crossref","unstructured":"Dory, M., Parter, M.: Exponentially faster shortest paths in the congested clique. In Proceedings of the 39th Symposium on Principles of Distributed Computing (PODC), pages 59\u201368, (2020)","DOI":"10.1145\/3382734.3405711"},{"issue":"2","key":"503_CR28","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1145\/1103963.1103968","volume":"1","author":"M Elkin","year":"2005","unstructured":"Elkin, M.: Computing almost shortest paths. ACM Transactions on Algorithms 1(2), 283\u2013323 (2005)","journal-title":"ACM Transactions on Algorithms"},{"key":"503_CR29","doi-asserted-by":"crossref","unstructured":"Elkin, M.: A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners. In Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing (PODC), pages 185\u2013194, (2007)","DOI":"10.1145\/1281100.1281128"},{"issue":"2","key":"503_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1921659.1921666","volume":"7","author":"M Elkin","year":"2011","unstructured":"Elkin, M.: Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. ACM Transactions on Algorithms 7(2), 1\u201317 (2011)","journal-title":"ACM Transactions on Algorithms"},{"key":"503_CR31","doi-asserted-by":"crossref","unstructured":"Elkin, M., Matar, S.: Near-additive spanners in low polynomial deterministic congest time. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC), pages 531\u2013540, (2019)","DOI":"10.1145\/3293611.3331635"},{"issue":"1","key":"503_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3274651","volume":"15","author":"M Elkin","year":"2018","unstructured":"Elkin, M., Neiman, O.: Efficient algorithms for constructing very sparse spanners and emulators. ACM Transactions on Algorithms 15(1), 1\u201329 (2018)","journal-title":"ACM Transactions on Algorithms"},{"key":"503_CR33","unstructured":"Erd\u0151s, P.: Extremal problems in graph theory. In: Theory Of Graphs And Its Applications. Proceedings of Symposium Smolenice, pp. 29\u201336. Publ. House Cszechoslovak Acad. Sci, Prague (1964)"},{"key":"503_CR34","doi-asserted-by":"crossref","unstructured":"Elkin, M., Zhang, J.: Efficient algorithms for constructing (1+$$\\varepsilon$$, $$\\beta$$)-spanners in the distributed and streaming models. In Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing (PODC), pages 160\u2013168, (2004)","DOI":"10.1145\/1011767.1011791"},{"key":"503_CR35","doi-asserted-by":"crossref","unstructured":"Fischer, O., Horowitz, A., Oshman, R.: Massively parallel computation in a heterogeneous regime. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (PODC), pages 345\u2013355, (2022)","DOI":"10.1145\/3519270.3538450"},{"key":"503_CR36","doi-asserted-by":"crossref","unstructured":"Filtser, A., Kapralov, M., Nouri, N.: Graph spanners by sketching in dynamic streams and the simultaneous communication model. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1894\u20131913. SIAM, (2021)","DOI":"10.1137\/1.9781611976465.113"},{"key":"503_CR37","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Kuhn, F., Uitto, J.: Conditional hardness results for massively parallel computation from distributed lower bounds. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1650\u20131663. IEEE, (2019)","DOI":"10.1109\/FOCS.2019.00097"},{"key":"503_CR38","doi-asserted-by":"crossref","unstructured":"Goodrich, M T., Sitchinava, N., Zhang,Q.: Sorting, searching, and simulation in the mapreduce framework. In International Symposium on Algorithms and Computation, pages 374\u2013383. Springer, (2011)","DOI":"10.1007\/978-3-642-25591-5_39"},{"key":"503_CR39","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1016\/j.tcs.2015.09.029","volume":"608","author":"JW Hegeman","year":"2015","unstructured":"Hegeman, J.W., Pemmaraju, S.V.: Lessons from the congested clique applied to mapreduce. Theoretical Computer Science 608, 268\u2013281 (2015)","journal-title":"Theoretical Computer Science"},{"key":"503_CR40","unstructured":"Holzer, S., Pinsker,N.: Approximation of distances and shortest paths in the broadcast congest clique. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, (2016)"},{"key":"503_CR41","doi-asserted-by":"crossref","unstructured":"Isard, M., Budiu, M., Yu, Y., Birrell, A., Fetterly, D.: Dryad: distributed data-parallel programs from sequential building blocks. In Proceedings of the 2nd ACM SIGOPS\/EuroSys European Conference on Computer Systems 2007, pages 59\u201372, (2007)","DOI":"10.1145\/1272996.1273005"},{"key":"503_CR42","doi-asserted-by":"crossref","unstructured":"Izumi, T., Le Gall, F.: Quantum distributed algorithm for the all-pairs shortest path problem in the congest-clique model. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC), pages 84\u201393, (2019)","DOI":"10.1145\/3293611.3331628"},{"key":"503_CR43","doi-asserted-by":"crossref","unstructured":"Jurdzi\u0144ski, T., Nowicki, K.: Mst in o(1) rounds of congested clique. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201918, page 2620\u20132632, USA, (2018) Society for Industrial and Applied Mathematics","DOI":"10.1137\/1.9781611975031.167"},{"key":"503_CR44","unstructured":"Korhonen, JH.: Deterministic MST sparsification in the congested clique. CoRR, arXiv:abs\/1605.02022, 2016"},{"key":"503_CR45","doi-asserted-by":"crossref","unstructured":"Karloff, H., Suri, S., Vassilvitskii, S.: A model of computation for mapreduce. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 938\u2013948. SIAM, (2010)","DOI":"10.1137\/1.9781611973075.76"},{"key":"503_CR46","doi-asserted-by":"crossref","unstructured":"Kapralov, M., Woodruff, D.: Spanners and sparsifiers in dynamic streams. In Proceedings of the 2014 ACM symposium on Principles of distributed computing (PODC), pages 272\u2013281, (2014)","DOI":"10.1145\/2611462.2611497"},{"key":"503_CR47","first-page":"42","volume":"2013","author":"C Lenzen","year":"2013","unstructured":"Lenzen, C.: Optimal deterministic routing and sorting on the congested clique. In Proc. PODC 2013, 42\u201350 (2013)","journal-title":"In Proc. PODC"},{"key":"503_CR48","doi-asserted-by":"crossref","unstructured":"Le Gall, F.: Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems. In International Symposium on Distributed Computing, pages 57\u201370. Springer, (2016)","DOI":"10.1007\/978-3-662-53426-7_5"},{"issue":"1","key":"503_CR49","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193\u2013201 (1992)","journal-title":"SIAM J. Comput."},{"key":"503_CR50","doi-asserted-by":"crossref","unstructured":"Nowicki, K.: A deterministic algorithm for the MST problem in constant rounds of congested clique. STOC 2021, (2021)","DOI":"10.1145\/3406325.3451136"},{"key":"503_CR51","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. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2000)"},{"key":"503_CR52","doi-asserted-by":"crossref","unstructured":"Pemmaraju, S V.: Equitable coloring extends chernoff-hoeffding bounds. In 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM, volume 2129 of Lecture Notes in Computer Science, pages 285\u2013296. Springer, (2001)","DOI":"10.1007\/3-540-44666-4_31"},{"issue":"3","key":"503_CR53","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/s00446-009-0091-7","volume":"22","author":"S Pettie","year":"2010","unstructured":"Pettie, S.: Distributed algorithms for ultrasparse spanners and linear size skeletons. Distrib. Comput. 22(3), 147\u2013166 (2010)","journal-title":"Distrib. Comput."},{"issue":"1","key":"503_CR54","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. Journal of graph theory 13(1), 99\u2013116 (1989)","journal-title":"Journal of graph theory"},{"issue":"4","key":"503_CR55","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1137\/0218050","volume":"18","author":"D Peleg","year":"1989","unstructured":"Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. SIAM Journal on computing 18(4), 740\u2013747 (1989)","journal-title":"SIAM Journal on computing"},{"issue":"3","key":"503_CR56","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1145\/65950.65953","volume":"36","author":"D Peleg","year":"1989","unstructured":"Peleg, D., Upfal, E.: A trade-off between space and efficiency for routing tables. Journal of the ACM 36(3), 510\u2013530 (1989)","journal-title":"Journal of the ACM"},{"key":"503_CR57","unstructured":"Parter, M., Yogev,E.: Congested clique algorithms for graph spanners. In 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018, pages 40:1\u201340:18, (2018)"},{"key":"503_CR58","doi-asserted-by":"crossref","unstructured":"Roditty, L., Thorup, M., Zwick, U: Deterministic constructions of approximate distance oracles and spanners. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 261\u2013272, (2005)","DOI":"10.1007\/11523468_22"},{"key":"503_CR59","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures (SPAA), pages 1\u201310, (2001)","DOI":"10.1145\/378580.378581"},{"key":"503_CR60","unstructured":"White, T.: Hadoop: The Definitive Guide. O\u2019Reilly Media, Inc., (2012)"},{"key":"503_CR61","unstructured":"Zaharia, M., Chowdhury, M., Franklin, M J., Shenker, S., Stoica, I.: Spark: Cluster computing with working sets. In 2nd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud), 2010"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-025-00503-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-025-00503-w","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-025-00503-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,29]],"date-time":"2026-06-29T01:39:40Z","timestamp":1782697180000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-025-00503-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,18]]},"references-count":61,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["503"],"URL":"https:\/\/doi.org\/10.1007\/s00446-025-00503-w","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,18]]},"assertion":[{"value":"5 January 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 December 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 March 2026","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 no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"8"}}