{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,17]],"date-time":"2025-11-17T21:40:43Z","timestamp":1763415643832,"version":"3.37.3"},"reference-count":57,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,2,15]],"date-time":"2023-02-15T00:00:00Z","timestamp":1676419200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,2,15]],"date-time":"2023-02-15T00:00:00Z","timestamp":1676419200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100008007","name":"Universit\u00e4t Paderborn","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008007","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2023,9]]},"abstract":"Abstract<\/jats:title>This article shows how to construct an overlay network of constant degree and diameter$$O(\\log n)$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>log<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>in$$O(\\log n)$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>log<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>time starting from an arbitrary weakly connected graph. We assume a synchronous communication network in which nodes can send messages to nodes they know the identifier of, and new connections can be established by sending node identifiers. Suppose the initial network\u2019s graph is weakly connected and has constant degree. In that case, our algorithm constructs the desired topology with each node sending and receiving only$$O(\\log n)$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>log<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>messages in each round in$$O(\\log n)$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>log<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>time w.h.p., which beats the currently best$$O(\\log ^{3\/2} n)$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>log<\/mml:mo>3<\/mml:mn>\/<\/mml:mo>2<\/mml:mn><\/mml:mrow><\/mml:msup>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>time algorithm of G\u00f6tte et al. (International colloquium on structural information and communication complexity (SIROCCO), Springer, 2019). Since the problem cannot be solved faster than by using pointer jumping for$$O(\\log n)$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>log<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>rounds (which would even require each node to communicate$$\\Omega (n)$$<\/jats:tex-math>\u03a9<\/mml:mi>(<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>bits), our algorithm is asymptotically optimal. We achieve this speedup by using short random walks to repeatedly establish random connections between the nodes that quickly reduce the conductance of the graph using an observation of Kwok and Lau (Approximation, randomization, and combinatorial optimization. Algorithms and techniques (APPROX\/RANDOM 2014), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014). Additionally, we show how our algorithm can be used to efficiently solve graph problems inhybrid networks<\/jats:italic>(Augustine et al. in Proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms, SIAM, 2020). Motivated by the idea that nodes possess two different modes of communication, we assume that communication of theinitial<\/jats:italic>edges is unrestricted, whereas only polylogarithmically many messages can be sent over edges that have been established throughout an algorithm\u2019s execution. For an (undirected) graphG<\/jats:italic>with arbitrary degree, we show how to compute connected components, a spanning tree, and biconnected components in$$O(\\log n)$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>log<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>time w.h.p. Furthermore, we show how to compute an MIS in$$O(\\log d + \\log \\log n)$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>log<\/mml:mo>d<\/mml:mi>+<\/mml:mo>log<\/mml:mo>log<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>time w.h.p., whered<\/jats:italic>is the initial degree ofG<\/jats:italic>.<\/jats:p>","DOI":"10.1007\/s00446-023-00442-4","type":"journal-article","created":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T07:33:16Z","timestamp":1676619196000},"page":"313-347","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Time-optimal construction of overlay networks"],"prefix":"10.1007","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9798-6993","authenticated-orcid":false,"given":"Thorsten","family":"G\u00f6tte","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kristian","family":"Hinnenthal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Scheideler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julian","family":"Werthmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,2,15]]},"reference":[{"issue":"4","key":"442_CR1","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","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 7(4), 567\u2013583 (1986)","journal-title":"J. Algorithms"},{"key":"442_CR2","doi-asserted-by":"crossref","unstructured":"Angluin, D., Aspnes, J., Chen, J., Wu, Y., Yin, Y.: Fast construction of overlay networks. In: Proceeding of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 145\u2013154 (2005)","DOI":"10.1145\/1073970.1073991"},{"key":"442_CR3","unstructured":"Aspnes, J., Shah, G.: Skip graphs. In: Proceeding of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 384\u2013393 (2003)"},{"key":"442_CR4","doi-asserted-by":"crossref","unstructured":"Aspnes, J., Wu, Y.: O(logn)-time overlay network construction from graphs with out-degree 1. In: Tovar, E., Tsigas, P., Fouchal, H. (eds.) Proceedings of the 11th International Conference on Principles of Distributed Systems (OPODIS), volume 4878 of Lecture Notes in Computer Science, pp. 286\u2013300. Springer (2007)","DOI":"10.1007\/978-3-540-77096-1_21"},{"key":"442_CR5","doi-asserted-by":"crossref","unstructured":"Assadi, S., Sun, X., Weinstein, O.: Massively parallel algorithms for finding well-connected components in sparse graphs. In: Robinson, P., Ellen, F. (eds.) Proceedings of the 2019ACM Symposium on Principles of Distributed Computing (PODC), pp. 461\u2013470. ACM (2019)","DOI":"10.1145\/3293611.3331596"},{"key":"442_CR6","doi-asserted-by":"crossref","unstructured":"Augustine, J., Choudhary, K., Cohen, A., Peleg, D., Sivasubramaniam, S., Sourav, S.: Distributed graph realizations . In: 2020 IEEE International Parallel and Distributed Processing Symposium (IPDPS), New Orleans, LA, USA, May 18\u201322, 2020, pp. 158\u2013167. IEEE (2020)","DOI":"10.1109\/IPDPS47924.2020.00026"},{"key":"442_CR7","doi-asserted-by":"crossref","unstructured":"Augustine, J., Ghaffari, M., Gmyr, R., Hinnenthal, K., Kuhn, F., Li, J., Scheideler, C.: Distributed computation in node-capacitated networks. In: Proceedings of the 31st Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) (2019)","DOI":"10.1145\/3323165.3323195"},{"key":"442_CR8","doi-asserted-by":"crossref","unstructured":"Augustine, J., Hinnenthal, K., Kuhn, F., Scheideler, C., Schneider, P.: Shortest paths in a hybrid network model. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1280\u20131299. SIAM (2020)","DOI":"10.1137\/1.9781611975994.78"},{"key":"442_CR9","doi-asserted-by":"crossref","unstructured":"Augustine, J., Pandurangan, G., Robinson, P., Roche, S.T., Upfal, E.: Enabling robust and efficient distributed computation in dynamic peer-to-peer networks. In: Proceedings of 56th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 350\u2013369 (2015)","DOI":"10.1109\/FOCS.2015.29"},{"key":"442_CR10","doi-asserted-by":"crossref","unstructured":"Augustine, J., Sivasubramaniam, S.: Spartan: a framework for sparse robust addressable networks. In: Proceedings of the 32nd IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 1060\u20131069 (2018)","DOI":"10.1109\/IPDPS.2018.00115"},{"issue":"5\u20136","key":"442_CR11","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/s00446-009-0088-2","volume":"22","author":"L Barenboim","year":"2010","unstructured":"Barenboim, L., Elkin, M.: Sublogarithmic distributed MIS algorithm for sparse graphs using Nash\u2013Williams decomposition. Distrib. Comput. 22(5\u20136), 363\u2013379 (2010)","journal-title":"Distrib. Comput."},{"issue":"3","key":"442_CR12","doi-asserted-by":"publisher","first-page":"20:1","DOI":"10.1145\/2903137","volume":"63","author":"L Barenboim","year":"2016","unstructured":"Barenboim, L., Elkin, M., Pettie, S., Schneider, J.: The locality of distributed symmetry breaking. J. ACM 63(3), 20:1-20:45 (2016)","journal-title":"J. ACM"},{"key":"442_CR13","doi-asserted-by":"crossref","unstructured":"Behnezhad, S., Brandt, S., Derakhshan, M., Fischer, M., Hajiaghayi, T.M., Karp, R.M., Uitto, J.: Massively parallel computation of matching and MIS in sparse graphs. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pp. 481\u2013490 (2019)","DOI":"10.1145\/3293611.3331609"},{"key":"442_CR14","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2013.02.021","volume":"512","author":"A Berns","year":"2013","unstructured":"Berns, A., Ghosh, S., Pemmaraju, S.V.: Building self-stabilizing overlay networks with the transitive closure framework. Theor. Comput. Sci. 512, 2\u201314 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"442_CR15","doi-asserted-by":"crossref","unstructured":"Brandt, S., Fischer, M., Uitto, J.: Breaking the linear-memory barrier in MPC: fast MIS on trees with strongly sublinear memory. In: International Colloquium on Structural Information and Communication Complexity, pp. 124\u2013138. Springer (2019)","DOI":"10.1007\/978-3-030-24922-9_9"},{"issue":"1","key":"442_CR16","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/s00446-018-0324-8","volume":"32","author":"K Censor-Hillel","year":"2019","unstructured":"Censor-Hillel, K., Fischer, E., Schwartzman, G., Vasudev, Y.: Fast distributed algorithms for testing graph properties. Distrib. Comput. 32(1), 41\u201357 (2019)","journal-title":"Distrib. Comput."},{"key":"442_CR17","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1145\/375827.375847","volume":"48","author":"KWA Chong","year":"2001","unstructured":"Chong, K.W.A., Han, Y., Lam, T.W.: Concurrent threads and optimal parallel minimum spanning trees algorithm. J. ACM 48, 297\u2013323 (2001)","journal-title":"J. ACM"},{"key":"442_CR18","unstructured":"Drees, M., Gmyr, R., Scheideler, C.: Churn- and dos-resistant overlay networks based on network reconfiguration. In: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)"},{"issue":"1","key":"442_CR19","first-page":"1","volume":"15","author":"M Elkin","year":"2018","unstructured":"Elkin, M., Neiman, O.: Efficient algorithms for constructing very sparse spanners and emulators. ACM Trans. Algorithms (TALG) 15(1), 1\u201329 (2018)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"442_CR20","unstructured":"Feldmann, M., Hinnenthal, K., Scheideler, C.: Fast hybrid network algorithms for shortest paths in sparse graphs. In: Proceedings of the 24th International Conference on Principles of Distributed Systems (OPODIS), pp. 31:1\u201331:16 (2020)"},{"key":"442_CR21","doi-asserted-by":"crossref","unstructured":"Feldmann, M., Scheideler, C., Schmid, S.: Survey on algorithms for self-stabilizing overlay networks. ACM Comput. Surv. 53(4) (2020)","DOI":"10.1145\/3397190"},{"key":"442_CR22","unstructured":"Fichtenberger, H., Vasudev, Y.: A two-sided error distributed property tester for conductance. In: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)"},{"key":"442_CR23","doi-asserted-by":"crossref","unstructured":"Ghaffari, M.: An improved distributed algorithm for maximal independent set. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete algorithms (SODA), pp. 270\u2013277. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch20"},{"key":"442_CR24","doi-asserted-by":"crossref","unstructured":"Ghaffari, M.: Distributed maximal independent set using small messages. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201919, pp. 805\u2013820. Society for Industrial and Applied Mathematics (2019)","DOI":"10.1137\/1.9781611975482.50"},{"key":"442_CR25","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Gouleakis, T., Konrad, C., Mitrovi\u0107, S., Rubinfeld, R.: Improved massively parallel computation algorithms for MIS, matching, and vertex cover. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, pp. 129\u2013138 (2018)","DOI":"10.1145\/3212734.3212743"},{"key":"442_CR26","unstructured":"Ghaffari, M., Grunau, C., Jin, C.: Improved MPC algorithms for MIS, matching, and coloring on trees and beyond. In: Attiya, H. (ed.) 34th International Symposium on Distributed Computing (DISC 2020), volume 179 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 34:1\u201334:18. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2020)"},{"key":"442_CR27","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Grunau, C., Rozhon, V.: Improved deterministic network decomposition. In: D\u00e1niel, M. (ed.) Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10\u201313, pp. 2904\u20132923. SIAM (2021)","DOI":"10.1137\/1.9781611976465.173"},{"key":"442_CR28","doi-asserted-by":"crossref","unstructured":"Gilbert, S., Pandurangan, G., Robinson, P., Trehan, A.: Dconstructor: Efficient and robust network construction with polylogarithmic overhead. In: Proceedings of ACM Symposium on Principles of Distributed Computing (PODC), pp. 438\u2013447. ACM (2020)","DOI":"10.1145\/3382734.3405716"},{"key":"442_CR29","unstructured":"Gkantsidis, C., Mihail, M., Saberi, A.: Random walks in peer-to-peer networks. In: Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). IEEE (2004)"},{"key":"442_CR30","unstructured":"Gmyr, R., Hinnenthal, K., Scheideler, C., Sohler, C.: Distributed Monitoring of Network Properties: The Power of Hybrid Networks. In: Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 137:1\u2013137:15 (2017)"},{"key":"442_CR31","doi-asserted-by":"crossref","unstructured":"G\u00f6tte, T., Hinnenthal, K., Scheideler, C.: Faster construction of overlay networks. In: International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 262\u2013276. Springer (2019)","DOI":"10.1007\/978-3-030-24922-9_18"},{"key":"442_CR32","doi-asserted-by":"crossref","unstructured":"G\u00f6tte, T., Vijayalakshmi, V.R., Scheideler, C.: Always be two steps ahead of your enemy. In: Proceedings of the 33rd IEEE International Parallel and Distributed Processing Symposium (IPDPS) (2019)","DOI":"10.1109\/IPDPS.2019.00114"},{"key":"442_CR33","unstructured":"Haeupler, B., Li, J.: Faster distributed shortest path approximations via shortcuts. In: Schmid, U, Widder, J. (eds.) 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15\u201319, 2018, volume 121 of LIPIcs, pp. 33:1\u201333:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"issue":"1","key":"442_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.2000.1146","volume":"39","author":"S Halperin","year":"2001","unstructured":"Halperin, S., Zwick, U.: Optimal randomized EREW PRAM algorithms for finding spanning forests. J. Algorithms 39(1), 1\u201346 (2001)","journal-title":"J. Algorithms"},{"issue":"6","key":"442_CR35","doi-asserted-by":"publisher","first-page":"36:1","DOI":"10.1145\/2629695","volume":"61","author":"R Jacob","year":"2014","unstructured":"Jacob, R., Richa, A.W., Scheideler, C., Schmid, S., T\u00e4ubig, H.: Skip+: a self-stabilizing skip graph. J. ACM 61(6), 36:1-36:26 (2014)","journal-title":"J. ACM"},{"issue":"1","key":"442_CR36","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1145\/331605.331608","volume":"47","author":"DR Karger","year":"2000","unstructured":"Karger, D.R.: Minimum cuts in near-linear time. J. ACM (JACM) 47(1), 46\u201376 (2000)","journal-title":"J. ACM (JACM)"},{"key":"442_CR37","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, pp. 300\u2013309 (2004)","DOI":"10.1145\/1011767.1011811"},{"key":"442_CR38","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Schneider, P.: Computing shortest paths and diameter in the hybrid network model. In: Proceedings of the 39th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 109\u2013118. ACM (2020)","DOI":"10.1145\/3382734.3405719"},{"key":"442_CR39","unstructured":"Kwok, T.C., Lau, L.C.: Lower bounds on expansions of graph powers. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2014). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2014)"},{"key":"442_CR40","doi-asserted-by":"crossref","unstructured":"\u0141\u0105cki, Jakub, Mitrovi\u0107, Slobodan, Onak, Krzysztof, Sankowski, Piotr: Walking randomly, massively, and efficiently. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 364\u2013377 (2020)","DOI":"10.1145\/3357713.3384303"},{"key":"442_CR41","unstructured":"Law, C., Siu, K.-Y.: Distributed construction of random expander networks. In: Proceedings IEEE INFOCOM 2003, The 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, San Franciso, CA, USA, March 30\u2013April 3, 2003, pp. 2133\u20132143. IEEE Computer Society (2003)"},{"issue":"6","key":"442_CR42","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2665063","volume":"61","author":"JR Lee","year":"2014","unstructured":"Lee, J.R., Gharan, S.O., Trevisan, L.: Multiway spectral partitioning and higher-order Cheeger inequalities. J. ACM (JACM) 61(6), 1\u201330 (2014)","journal-title":"J. ACM (JACM)"},{"key":"442_CR43","doi-asserted-by":"crossref","unstructured":"Liu, S.C., Tarjan, R.E., Zhong, P.: Connected components on a PRAM in log diameter time. In: Scheideler, C., Spear, M. (eds.) Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Virtual Event, USA, July 15\u201317, 2020, pp. 359\u2013369. ACM (2020)","DOI":"10.1145\/3350755.3400249"},{"key":"442_CR44","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L., Simonovits, M.: The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume. In: Proceedings of 31st Annual Symposium on Foundations of Computer Science (FOCS), pp. 346\u2013354. IEEE (1990)","DOI":"10.1109\/FSCS.1990.89553"},{"issue":"4","key":"442_CR45","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M Luby","year":"1986","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15(4), 1036\u20131053 (1986)","journal-title":"SIAM J. Comput."},{"key":"442_CR46","doi-asserted-by":"crossref","unstructured":"Miller, G.L., Peng, R. , Vladu, A., Xu, S.C.: Improved parallel algorithms for spanners and hopsets. In: Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 192\u2013201 (2015)","DOI":"10.1145\/2755573.2755574"},{"key":"442_CR47","doi-asserted-by":"crossref","unstructured":"M\u00e9tivier, Y., Robson, J.M., Nasser, S.-D., Zemmari, A.: An optimal bit complexity randomized distributed MIS algorithm. In: International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 323\u2013337. Springer (2009)","DOI":"10.1007\/978-3-642-11476-2_25"},{"key":"442_CR48","volume-title":"Jxta in a Nutshell","author":"S Oaks","year":"2002","unstructured":"Oaks, S., Gong, L.: Jxta in a Nutshell. O\u2019Reilly & Associates Inc, USA (2002)"},{"key":"442_CR49","doi-asserted-by":"publisher","first-page":"1879","DOI":"10.1137\/S0097539700371065","volume":"31","author":"S Pettie","year":"2002","unstructured":"Pettie, S., Ramachandran, V.: A randomized time-work optimal parallel algorithm for finding a minimum spanning forest. SIAM J. Comput. 31, 1879\u20131895 (2002)","journal-title":"SIAM J. Comput."},{"key":"442_CR50","doi-asserted-by":"crossref","unstructured":"Robinson, P.: Being fast means being chatty: the local information cost of graph spanners. In: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2105\u20132120 (2021)","DOI":"10.1137\/1.9781611976465.126"},{"key":"442_CR51","doi-asserted-by":"crossref","unstructured":"Rowstron, A.I.T., Druschel, P.: Pastry: scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In: Proceedings of IFIP\/ACM International Conference on Distributed Systems Platforms (Middleware), pp. 329\u2013350 (2001)","DOI":"10.1007\/3-540-45518-3_18"},{"key":"442_CR52","doi-asserted-by":"crossref","unstructured":"Sarma, A.D., Molla, A.R., Pandurangan, G., Upfal, E.: Fast distributed pagerank computation. In: International Conference on Distributed Computing and Networking, pp. 11\u201326. Springer (2013)","DOI":"10.1007\/978-3-642-35668-1_2"},{"key":"442_CR53","unstructured":"Sinclair, A.: Algorithms for Random Generation and Counting: A Markov chain approach. Springer, New York (2012)"},{"issue":"1","key":"442_CR54","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0890-5401(89)90067-9","volume":"82","author":"A Sinclair","year":"1989","unstructured":"Sinclair, A., Jerrum, M.: Approximate counting, uniform generation and rapidly mixing Markov chains. Inf. Comput. 82(1), 93\u2013133 (1989)","journal-title":"Inf. Comput."},{"key":"442_CR55","doi-asserted-by":"crossref","unstructured":"Stoica, I., Morris, R.T., Karger, D.R., Kaashoek, M.F., Balakrishnan, H.: Chord: a scalable peer-to-peer lookup service for internet applications. In: Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication (SIGCOMM), pp. 149\u2013160 (2001)","DOI":"10.1145\/964723.383071"},{"issue":"4","key":"442_CR56","doi-asserted-by":"publisher","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"RE Tarjan","year":"1985","unstructured":"Tarjan, R.E., Vishkin, U.: An efficient parallel biconnectivity algorithm. SIAM J. Comput. 14(4), 862\u2013874 (1985)","journal-title":"SIAM J. Comput."},{"key":"442_CR57","unstructured":"Xu, S.C.: Exponential Start Time Clustering and its Applications in Spectral Graphy Theory. PhD thesis, Carnegie Mellon University, Pittsburgh, August 2017. CMU CS Tech Report CMU-CS-17-120"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-023-00442-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-023-00442-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-023-00442-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,14]],"date-time":"2024-10-14T12:59:39Z","timestamp":1728910779000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-023-00442-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,15]]},"references-count":57,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["442"],"URL":"https:\/\/doi.org\/10.1007\/s00446-023-00442-4","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2023,2,15]]},"assertion":[{"value":"15 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 January 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 February 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}