{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T14:55:28Z","timestamp":1762786528073,"version":"build-2065373602"},"reference-count":59,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T00:00:00Z","timestamp":1740528000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T00:00:00Z","timestamp":1740528000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002666","name":"Aalto University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002666","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Locally Checkable Labeling () problems are graph problems in which a solution is correct if it satisfies some given constraints in the local neighborhood of each node. Example problems in this class include maximal matching, maximal independent set, and colorings. A successful line of research has been studying the complexities of s on paths\/cycles, trees, and general graphs, providing many interesting results for the  model of distributed computing. In this work, we initiate the study of  problems in the low-space Massively Parallel Computation () model. In particular, on forests, we provide a method that, given the complexity of an  problem in the  model, automatically provides an exponentially faster algorithm for the low-space  setting that uses optimal global memory, that is, truly linear. While restricting to forests may seem to weaken the results, we emphasize that all known (conditional) lower bounds for the  setting are obtained through lower bounds for  problems in the distributed setting in\n                    <jats:italic>tree-like networks<\/jats:italic>\n                    (either trees or high-girth graphs), and hence the  problems that we study are challenging already on trees. Moreover, our algorithms use optimal global memory, i.e., memory linear in the number of edges of the graph. In contrast, most of the state-of-the-art algorithms use more than linear global memory. Further, they typically start with a dense graph, sparsify it, and then solve the problem on the residual graph, exploiting the relative increase in global memory. On forests this is not possible, hence using optimal memory requires new solutions.\n                  <\/jats:p>","DOI":"10.1007\/s00446-025-00477-9","type":"journal-article","created":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T08:03:19Z","timestamp":1740556999000},"page":"397-434","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Exponential speedup over locality in MPC with optimal memory"],"prefix":"10.1007","volume":"38","author":[{"given":"Alkida","family":"Balliu","sequence":"first","affiliation":[]},{"given":"Sebastian","family":"Brandt","sequence":"additional","affiliation":[]},{"given":"Manuela","family":"Fischer","sequence":"additional","affiliation":[]},{"given":"Rustam","family":"Latypov","sequence":"additional","affiliation":[]},{"given":"Yannic","family":"Maus","sequence":"additional","affiliation":[]},{"given":"Dennis","family":"Olivetti","sequence":"additional","affiliation":[]},{"given":"Jara","family":"Uitto","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,2,26]]},"reference":[{"key":"477_CR1","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"1986","author":"N Alon","year":"1986","unstructured":"Alon, N., Babai, L., Itai, A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms 1986, 567\u2013583 (1986). https:\/\/doi.org\/10.1016\/0196-6774(86)90019-2","journal-title":"J. Algorithms"},{"key":"477_CR2","doi-asserted-by":"publisher","unstructured":"Andoni, A., Nikolov, A., Onak, K. and Yaroslavtsev, G.: Parallel algorithms for geometric graph problems. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 574\u2013583 (2014). https:\/\/doi.org\/10.1145\/2591796.2591805","DOI":"10.1145\/2591796.2591805"},{"issue":"1\u201317","key":"477_CR3","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1145\/3382734.3405703","volume":"17","author":"A Balliu","year":"2020","unstructured":"Balliu, A., Brandt, S., Efron, Y., Hirvonen, J., Maus, Y., Olivetti, D., Suomela, J.: Classification of distributed binary labeling problems. In DISC. 17(1\u201317), 17 (2020). https:\/\/doi.org\/10.1145\/3382734.3405703","journal-title":"In DISC."},{"key":"477_CR4","doi-asserted-by":"publisher","unstructured":"Balliu, A., Brandt, S., Hirvonen, J., Olivetti, D., Rabie, M., Suomela, J.: Lower bounds for maximal matchings and maximal independent sets. In: Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pp. 481\u2013497 (2019). https:\/\/doi.org\/10.1109\/FOCS.2019.00037","DOI":"10.1109\/FOCS.2019.00037"},{"key":"477_CR5","doi-asserted-by":"crossref","unstructured":"Balliu, A., Brandt, S., Kuhn, F., Olivetti, D.: Distributed $$\\Delta $$-coloring plays hide-and-seek. In: Proceedings of the Symposium on Theory of Computing (STOC) (2022). arxiv:2110.00643","DOI":"10.1145\/3519935.3520027"},{"key":"477_CR6","doi-asserted-by":"publisher","unstructured":"Balliu, A., Brandt, S., Olivetti, D.: Distributed lower bounds for ruling sets. In: Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pp. 365\u2013376 (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00042","DOI":"10.1109\/FOCS46700.2020.00042"},{"key":"477_CR7","doi-asserted-by":"publisher","unstructured":"Balliu, A., Brandt, S., Olivetti, D., Studen\u00fd, J., Suomela, J., Tereshchenko, A.: Locally checkable problems in rooted trees. In: Proceedings of the International Symposium on Principles of Distributed Computing (PODC), pp. 263\u2013272 (2021). https:\/\/doi.org\/10.1145\/3465084.3467934","DOI":"10.1145\/3465084.3467934"},{"key":"477_CR8","doi-asserted-by":"publisher","unstructured":"Balliu, A., Brandt, S., Olivetti, D., Suomela, J.: Almost global problems in the LOCAL model. In: Proceedings of the International Symposium on Distributed Computing (DISC), vol. 9, no. (1\u20139), p. 16 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2018.9","DOI":"10.4230\/LIPIcs.DISC.2018.9"},{"key":"477_CR9","doi-asserted-by":"publisher","unstructured":"Balliu, A., Censor-Hillel, K., Maus, Y., Olivetti, D., Suomela, J.: Locally checkable labelings with small messages. In: Proceedings of the International Symposium on Distributed Computing (DISC), vol. 8, no. (1\u20138), p. 18 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2021.8","DOI":"10.4230\/LIPIcs.DISC.2021.8"},{"key":"477_CR10","doi-asserted-by":"publisher","unstructured":"Balliu, A., Hirvonen, J., Korhonen, J.H., Lempi\u00e4inen, T., Olivetti, D., Suomela, J.: New classes of distributed time complexity. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 1307\u20131318 (2018). https:\/\/doi.org\/10.1145\/3188745.3188860","DOI":"10.1145\/3188745.3188860"},{"key":"477_CR11","doi-asserted-by":"publisher","unstructured":"Balliu, A., Hirvonen, J., Olivetti, D., Suomela, J.: Hardness of minimal symmetry breaking in distributed computing. In: Proceedings of the International Symposium on Principles of Distributed Computing (PODC), pp. 369\u2013378 (2019). https:\/\/doi.org\/10.1145\/3293611.3331605","DOI":"10.1145\/3293611.3331605"},{"key":"477_CR12","doi-asserted-by":"publisher","unstructured":"Bamberger, P., Kuhn, F., Maus, Y.: Efficient deterministic distributed coloring with small bandwidth. In: Proceedings of the International Symposium on Principles of Distributed Computing (PODC), pp. 243\u2013252 (2020). https:\/\/doi.org\/10.1145\/3382734.3404504","DOI":"10.1145\/3382734.3404504"},{"issue":"6","key":"477_CR13","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1145\/3125644","volume":"64","author":"P Beame","year":"2017","unstructured":"Beame, P., Koutris, P., Suciu, D.: Communication steps for parallel query processing. J. ACM 64(6), 40 (2017). https:\/\/doi.org\/10.1145\/3125644","journal-title":"J. ACM"},{"key":"477_CR14","doi-asserted-by":"publisher","unstructured":"Behnezhad, S., Brandt, S., Derakhshan, M., Fischer, M., Hajiaghayi, M., Karp, R.M., Uitto, J.: Massively parallel computation of matching and MIS in sparse graphs. In: Proceedings of the International Symposium on Principles of Distributed Computing (PODC), pp. 481\u2013490 (2019). https:\/\/doi.org\/10.1145\/3293611.3331609","DOI":"10.1145\/3293611.3331609"},{"key":"477_CR15","doi-asserted-by":"publisher","unstructured":"Behnezhad, S., Dhulipala, L., Esfandiari, H., Lacki, J., Mirrokni, V.: Near-optimal massively parallel graph connectivity. In: Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pp. 1615\u20131636 (2020). https:\/\/doi.org\/10.1109\/FOCS.2019.00095","DOI":"10.1109\/FOCS.2019.00095"},{"key":"477_CR16","doi-asserted-by":"publisher","unstructured":"Brandt, S., Fischer, M., Uitto, J.: Breaking the linear-memory barrier in MPC: fast MIS on trees with strongly sublinear memory. In: Proceedings of the International Colloquium on Structural Information and Communication Complexity, vol. 124\u2013138 (2019). https:\/\/doi.org\/10.1007\/978-3-030-24922-9_9","DOI":"10.1007\/978-3-030-24922-9_9"},{"key":"477_CR17","doi-asserted-by":"publisher","unstructured":"Brandt, S., Fischer, O., Hirvonen, J., Keller, B., Lempi\u00e4inen, T., Rybicki, J., Suomela, J., Uitto, J.: A lower bound for the distributed Lov\u00e1sz local lemma. In: Proceedings of the Symposium on Theory of Computing (STOC). ACM Press, pp. 479\u2013488 (2016). https:\/\/doi.org\/10.1145\/2897518.2897570","DOI":"10.1145\/2897518.2897570"},{"key":"477_CR18","doi-asserted-by":"publisher","unstructured":"Brandt, S., Hirvonen, J., Korhonen, J.H., Lempi\u00e4inen, T., \u00d6sterg\u00e5rd, P.R.J., Purcell, C., Rybicki, J., Suomela, J., Uzna\u0144ski, P.: LCL problems on grids. In: Proceedings of the International Symposium on Principles of Distributed Computing (PODC), vol. 101\u2013110 (2017). https:\/\/doi.org\/10.1145\/3087801.3087833","DOI":"10.1145\/3087801.3087833"},{"issue":"1","key":"477_CR19","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1137\/17M1117537","volume":"48","author":"Y-J Chang","year":"2019","unstructured":"Chang, Y.-J., Kopelowitz, T., Pettie, S.: An exponential separation between randomized and deterministic complexity in the LOCAL model. SIAM J. Comput. 48(1), 122\u2013143 (2019). https:\/\/doi.org\/10.1137\/17M1117537","journal-title":"SIAM J. Comput."},{"issue":"1","key":"477_CR20","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1137\/17M1157957","volume":"48","author":"Y-J Chang","year":"2019","unstructured":"Chang, Y.-J., Pettie, S.: A time hierarchy theorem for the LOCAL model. SIAM J. Comput. 48(1), 33\u201369 (2019). https:\/\/doi.org\/10.1137\/17M1157957","journal-title":"SIAM J. Comput."},{"key":"477_CR21","doi-asserted-by":"publisher","unstructured":"Chang, Y.-J.: The complexity landscape of distributed locally checkable problems on trees. In: Proceedings of the International Symposium on Distributed Computing (DISC), vol. 18, no. (1\u201318), p. 17 (2020). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2020.18","DOI":"10.4230\/LIPIcs.DISC.2020.18"},{"key":"477_CR22","doi-asserted-by":"publisher","unstructured":"Chang, Y.-J., Fischer, M., Ghaffari, M., Uitto, J., Zheng, Y.: The complexity of $$(\\Delta + 1)$$ coloring in congested clique, massively parallel computation, and centralized local computation. In: Proceedings of the International Symposium on Principles of Distributed Computing (PODC), pp 471\u2013480 (2019). https:\/\/doi.org\/10.1145\/3293611.3331607","DOI":"10.1145\/3293611.3331607"},{"key":"477_CR23","doi-asserted-by":"publisher","unstructured":"Chang, Y.-J., Fischer, M., Ghaffari, M., Uitto, J., Zheng, Y.: The complexity of $$(\\Delta +1)$$ coloring in congested clique, massively parallel computation, and centralized local computation. In: Proceedings of the International Symposium on Principles of Distributed Computing (PODC), vol. 471\u2013480 (2019). https:\/\/doi.org\/10.1145\/3293611.3331607","DOI":"10.1145\/3293611.3331607"},{"key":"477_CR24","doi-asserted-by":"publisher","DOI":"10.1145\/3365004","author":"Y-J Chang","year":"2019","unstructured":"Chang, Y.-J., He, Q., Li, W., Pettie, S., Uitto, J.: Distributed edge coloring and a special case of the constructive Lov\u00e1sz local lemma. ACM Trans. Algorithms (2019). https:\/\/doi.org\/10.1145\/3365004","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"477_CR25","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/S0019-9958(86)80023-7","volume":"70","author":"R Cole","year":"1986","unstructured":"Cole, R., Vishkin, U.: Deterministic coin tossing with applications to optimal parallel list ranking. Inf. Control. 70(1), 32\u201353 (1986). https:\/\/doi.org\/10.1016\/S0019-9958(86)80023-7","journal-title":"Inf. Control."},{"key":"477_CR26","doi-asserted-by":"publisher","unstructured":"Coy, S., Czumaj, A.: Deterministic massively parallel connectivity. In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022) (2022). https:\/\/doi.org\/10.1145\/3519935.3520055","DOI":"10.1145\/3519935.3520055"},{"key":"477_CR27","doi-asserted-by":"publisher","unstructured":"Czumaj, A., Davies, P., Parter, M.: Graph sparsification for derandomizing massively parallel computation with low space. In: Proceedings of the Symposium on Parallel Algorithms and Architectures (SPAA), pp. 175\u2013185 (2020). https:\/\/doi.org\/10.1145\/3350755.3400282","DOI":"10.1145\/3350755.3400282"},{"key":"477_CR28","doi-asserted-by":"publisher","unstructured":"Czumaj, A., Davies, P., Parter, M.: Component stability in low-space massively parallel computation. In: Proceedings of the International Symposium on Principles of Distributed Computing (PODC), pp. 481\u2013491 (2021). https:\/\/doi.org\/10.1145\/3465084.3467903","DOI":"10.1145\/3465084.3467903"},{"key":"477_CR29","doi-asserted-by":"publisher","unstructured":"Czumaj, A., Davies, P., Parter, M.: Improved deterministic $$(\\Delta +1)$$ coloring in low-space MPC. In: Proceedings of the International Symposium on Principles of Distributed Computing (PODC), pp. 469\u2013479 (2021). https:\/\/doi.org\/10.1145\/3465084.3467937","DOI":"10.1145\/3465084.3467937"},{"key":"477_CR30","doi-asserted-by":"crossref","unstructured":"Dean, J., Ghemawat, S.: MapReduce: Simplified Data Processing on Large Clusters. In: Communications of the ACM, pp. 107\u2013113 (2008)","DOI":"10.1145\/1327452.1327492"},{"key":"477_CR31","doi-asserted-by":"publisher","unstructured":"Dory, M., Fischer, O., Khoury, S., Leitersdorf, D.: Constant-round spanners and shortest paths in congested clique and MPC. In: Proceedings of the International Symposium on Principles of Distributed Computing (PODC), pp. 223\u2013233 (2021). https:\/\/doi.org\/10.1145\/3465084.3467928","DOI":"10.1145\/3465084.3467928"},{"key":"477_CR32","doi-asserted-by":"publisher","unstructured":"Fischer, M., Ghaffari, M.: Sublogarithmic distributed algorithms for Lov\u00e1sz local lemma, and the complexity hierarchy. In: Proceedings of the International Symposium on Distributed Computing (DISC), vol. 18, no. (1\u201318), p. 16 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2017.18","DOI":"10.4230\/LIPIcs.DISC.2017.18"},{"key":"477_CR33","doi-asserted-by":"publisher","unstructured":"Ghaffari, M.: An improved distributed algorithm for maximal independent set. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 270\u2013277 (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch20","DOI":"10.1137\/1.9781611974331.ch20"},{"key":"477_CR34","doi-asserted-by":"publisher","unstructured":"Ghaffari, M., Grunau, C., Jin, C.: Improved MPC algorithms for MIS, matching, and coloring on trees and beyond. In: Proceedings of the International Symposium on Distributed Computing (DISC), vol. 34, no. (1\u201334), p. 18 (2020). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2020.34","DOI":"10.4230\/LIPIcs.DISC.2020.34"},{"key":"477_CR35","doi-asserted-by":"publisher","unstructured":"Ghaffari, M., Grunau, C., Rozhon, V.: Improved deterministic network decomposition. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2904\u20132923 (2021). https:\/\/doi.org\/10.1137\/1.9781611976465.173","DOI":"10.1137\/1.9781611976465.173"},{"key":"477_CR36","doi-asserted-by":"publisher","unstructured":"Ghaffari, M., Harris, D.G., Kuhn, F.: On derandomizing local distributed algorithms. In: Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pp. 662\u2013673 (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00069","DOI":"10.1109\/FOCS.2018.00069"},{"key":"477_CR37","doi-asserted-by":"publisher","unstructured":"Ghaffari, M., Kuhn, F., Uitto, J.: Conditional hardness results for massively parallel computation from distributed lower bounds. In: Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pp. 1650\u20131663 (2019). https:\/\/doi.org\/10.1109\/FOCS.2019.00097","DOI":"10.1109\/FOCS.2019.00097"},{"key":"477_CR38","doi-asserted-by":"publisher","unstructured":"Ghaffari, M., Hsin-Hao, S.: Distributed degree splitting, edge coloring, and orientations. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2505\u20132523 (2017). https:\/\/doi.org\/10.1137\/1.9781611974782.166","DOI":"10.1137\/1.9781611974782.166"},{"key":"477_CR39","doi-asserted-by":"publisher","unstructured":"Ghaffari, M., Uitto, J.: Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1636\u20131653 (2019). https:\/\/doi.org\/10.1137\/1.9781611975482.99","DOI":"10.1137\/1.9781611975482.99"},{"issue":"4","key":"477_CR40","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1137\/0401044","volume":"1","author":"AV Goldberg","year":"1988","unstructured":"Goldberg, A.V., Plotkin, S.A., Shannon, G.E.: Parallel symmetry-breaking in sparse graphs. SIAM J. Discret. Math. 1(4), 434\u2013446 (1988). https:\/\/doi.org\/10.1137\/0401044","journal-title":"SIAM J. Discret. Math."},{"key":"477_CR41","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 (ISAAC), pp. 374\u2013383 (2011)","DOI":"10.1007\/978-3-642-25591-5_39"},{"key":"477_CR42","doi-asserted-by":"crossref","unstructured":"Grunau, C., Rozhon, V., Brandt, S.: The landscape of distributed complexities on trees and beyond (2022). arxiv:2202.04724 [cs.DS]","DOI":"10.1145\/3519270.3538452"},{"key":"477_CR43","doi-asserted-by":"publisher","unstructured":"Isard, M., Budiu, M., Yuan, Y., Birrell, A., Fetterly, D.: Dryad: distributed data-parallel programs from sequential building blocks. In: SIGOPS Operating Systems Review, pp. 59\u201372 (2007). https:\/\/doi.org\/10.1145\/1272996.1273005","DOI":"10.1145\/1272996.1273005"},{"key":"477_CR44","doi-asserted-by":"publisher","unstructured":"Karloff, H.J., Suri, S., Vassilvitskii, S.: A model of computation for mapreduce. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 938\u2013948 (2010). https:\/\/doi.org\/10.1137\/1.9781611973075.76","DOI":"10.1137\/1.9781611973075.76"},{"key":"477_CR45","doi-asserted-by":"publisher","unstructured":"Kiveris, R., Lattanzi, S., Mirrokni, V., Rastogi, V., Vassilvitskii, S.: Connected components in mapreduce and beyond. In: ACM Symposium on Cloud Computing, vol. 18, no. (1\u201318), p. 13 (2014). https:\/\/doi.org\/10.1145\/2670979.2670997","DOI":"10.1145\/2670979.2670997"},{"key":"477_CR46","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1145\/2742012","volume":"63","author":"F Kuhn","year":"2016","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: Local computation: lower and upper bounds. J. ACM 63, 171\u20131744 (2016). https:\/\/doi.org\/10.1145\/2742012","journal-title":"J. ACM"},{"key":"477_CR47","doi-asserted-by":"publisher","unstructured":"Lenzen, C.: Optimal deterministic routing and sorting on the congested clique. In: Proceedings of the International Symposium on Principles of Distributed Computing (PODC), pp. 42\u201350 (2013). https:\/\/doi.org\/10.1145\/2484239.2501983","DOI":"10.1145\/2484239.2501983"},{"key":"477_CR48","doi-asserted-by":"publisher","unstructured":"Lenzen, C., Wattenhofer, R.: Brief announcement: exponential speed-up of local algorithms using non-local communication. In: Proceedings of the International Symposium on Principles of Distributed Computing (PODC), pp. 295\u2013296 (2010). https:\/\/doi.org\/10.1145\/1835698.1835772","DOI":"10.1145\/1835698.1835772"},{"key":"477_CR49","doi-asserted-by":"publisher","unstructured":"Linial, N.: Distributive graph algorithms - global solutions from local data. In: Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pp. 331\u2013335 (1987). https:\/\/doi.org\/10.1109\/SFCS.1987.20","DOI":"10.1109\/SFCS.1987.20"},{"issue":"1","key":"477_CR50","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). https:\/\/doi.org\/10.1137\/0221015","journal-title":"SIAM J. Comput."},{"key":"477_CR51","doi-asserted-by":"publisher","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 1\u201310 (1985). https:\/\/doi.org\/10.1145\/22145.22146","DOI":"10.1145\/22145.22146"},{"issue":"1989","key":"477_CR52","first-page":"47","volume":"5","author":"GL Miller","year":"1989","unstructured":"Miller, G.L., Reif, J.H.: Parallel tree contraction part 1: fundamentals. Adv. Comput. Res. 5(1989), 47\u201372 (1989)","journal-title":"Adv. Comput. Res."},{"issue":"6","key":"477_CR53","doi-asserted-by":"publisher","first-page":"1259","DOI":"10.1137\/S0097539793254571","volume":"24","author":"M Naor","year":"1995","unstructured":"Naor, M., Stockmeyer, L.: What can be computed locally? SIAM J. Comput. 24(6), 1259\u20131277 (1995). https:\/\/doi.org\/10.1137\/S0097539793254571","journal-title":"SIAM J. Comput."},{"key":"477_CR54","doi-asserted-by":"publisher","unstructured":"Panconesi, A., Rizzi, R.: Some simple distributed algorithms for sparse networks. Distrib. Comput. 14(2), 97\u2013100 (2001). https:\/\/doi.org\/10.1007\/PL00008932","DOI":"10.1007\/PL00008932"},{"key":"477_CR55","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed computing: a locality-sensitive approach. Soc. Ind. Appl. Math. (2000). https:\/\/doi.org\/10.1137\/1.9780898719772","journal-title":"Soc. Ind. Appl. Math."},{"key":"477_CR56","doi-asserted-by":"publisher","DOI":"10.1145\/3232536","author":"T Roughgarden","year":"2018","unstructured":"Roughgarden, T., Vassilvitskii, S., Wang, J.R.: Shuffles and circuits (on lower bounds for modern parallel computation). J. ACM (2018). https:\/\/doi.org\/10.1145\/3232536","journal-title":"J. ACM"},{"key":"477_CR57","doi-asserted-by":"publisher","unstructured":"Rozhon, V., Ghaffari, M.: Polylogarithmic-time deterministic network decomposition and distributed derandomization. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 350\u2013363 (2020). https:\/\/doi.org\/10.1145\/3357713.3384298","DOI":"10.1145\/3357713.3384298"},{"key":"477_CR58","doi-asserted-by":"publisher","unstructured":"White, T.: Hadoop: The Definitive Guide. O\u2019Reilly Media, Inc., Sebastopol (2012). https:\/\/doi.org\/10.5555\/1717298","DOI":"10.5555\/1717298"},{"key":"477_CR59","doi-asserted-by":"publisher","unstructured":"Zaharia, M., Chowdhury, M., Franklin, M.J., Shenker, S., Stoica, I.: Spark: cluster computing with working sets. In: USENIX Workshop on Hot Topics in Cloud Computing (HotCloud) (2010). https:\/\/doi.org\/10.5555\/1863103.1863113","DOI":"10.5555\/1863103.1863113"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-025-00477-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-025-00477-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-025-00477-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T14:53:42Z","timestamp":1762786422000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-025-00477-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,26]]},"references-count":59,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["477"],"URL":"https:\/\/doi.org\/10.1007\/s00446-025-00477-9","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2025,2,26]]},"assertion":[{"value":"15 January 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 February 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 February 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 have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}