{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:19:42Z","timestamp":1750220382296,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":49,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T00:00:00Z","timestamp":1626825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["60364472-SFB901"],"award-info":[{"award-number":["60364472-SFB901"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,7,21]]},"DOI":"10.1145\/3465084.3467932","type":"proceedings-article","created":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T21:09:28Z","timestamp":1627074568000},"page":"457-468","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Time-Optimal Construction of Overlay Networks"],"prefix":"10.1145","author":[{"given":"Thorsten","family":"G\u00f6tte","sequence":"first","affiliation":[{"name":"Paderborn University, Paderborn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kristian","family":"Hinnenthal","sequence":"additional","affiliation":[{"name":"Paderborn University, Paderborn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Scheideler","sequence":"additional","affiliation":[{"name":"Paderborn University, Paderborn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julian","family":"Werthmann","sequence":"additional","affiliation":[{"name":"Paderborn University, Paderborn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,7,23]]},"reference":[{"key":"e_1_3_2_2_1_1","first-page":"145","volume-title":"Yitong Yin. Fast Construction of Overlay Networks. In Proc. of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","author":"Angluin Dana","year":"2005","unstructured":"Dana Angluin , James Aspnes , Jiang Chen , Yinghua Wu , and Yitong Yin. Fast Construction of Overlay Networks. In Proc. of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) , pages 145 -- 154 , 2005 . Dana Angluin, James Aspnes, Jiang Chen, Yinghua Wu, and Yitong Yin. Fast Construction of Overlay Networks. In Proc. of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 145--154, 2005."},{"key":"e_1_3_2_2_2_1","first-page":"384","volume-title":"Proc. of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Aspnes James","year":"2003","unstructured":"James Aspnes and Gauri Shah . Skip graphs . In Proc. of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 384 -- 393 , 2003 . James Aspnes and Gauri Shah. Skip graphs. In Proc. of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 384--393, 2003."},{"key":"e_1_3_2_2_3_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1007\/978-3-540-77096-1_21","volume-title":"Eduardo Tovar, Philippas Tsigas, and Hac\u00e8 ne Fouchal","author":"Aspnes James","year":"2007","unstructured":"James Aspnes and Yinghua Wu. O(logn)-time overlay network construction from graphs with out-degree 1. In Eduardo Tovar, Philippas Tsigas, and Hac\u00e8 ne Fouchal , editors, Proc. of the 11th International Conference on Principles of Distributed Systems (OPODIS), volume 4878 of Lecture Notes in Computer Science , pages 286 -- 300 . Springer , 2007 . James Aspnes and Yinghua Wu. O(logn)-time overlay network construction from graphs with out-degree 1. In Eduardo Tovar, Philippas Tsigas, and Hac\u00e8 ne Fouchal, editors, Proc. of the 11th International Conference on Principles of Distributed Systems (OPODIS), volume 4878 of Lecture Notes in Computer Science, pages 286--300. Springer, 2007."},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331596"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS47924.2020.00026"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323195"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.78"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.29"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2018.00115"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2903137"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331609"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.02.021"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-24922-9_9"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-018-0324-8"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375847"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935783"},{"key":"e_1_3_2_2_17_1","volume-title":"Efficient algorithms for constructing very sparse spanners and emulators. ACM Transactions on Algorithms (TALG), 15(1):1--29","author":"Elkin Michael","year":"2018","unstructured":"Michael Elkin and Ofer Neiman . Efficient algorithms for constructing very sparse spanners and emulators. ACM Transactions on Algorithms (TALG), 15(1):1--29 , 2018 . Michael Elkin and Ofer Neiman. Efficient algorithms for constructing very sparse spanners and emulators. ACM Transactions on Algorithms (TALG), 15(1):1--29, 2018."},{"key":"e_1_3_2_2_18_1","first-page":"1","volume-title":"Proceedings of the 24th International Conference on Principles of Distributed Systems (OPODIS)","author":"Feldmann Michael","year":"2020","unstructured":"Michael Feldmann , Kristian Hinnenthal , and Christian Scheideler . Fast hybrid network algorithms for shortest paths in sparse graphs . In Proceedings of the 24th International Conference on Principles of Distributed Systems (OPODIS) , pages 31: 1 -- 31 :16, 2020 . Michael Feldmann, Kristian Hinnenthal, and Christian Scheideler. Fast hybrid network algorithms for shortest paths in sparse graphs. In Proceedings of the 24th International Conference on Principles of Distributed Systems (OPODIS), pages 31:1--31:16, 2020."},{"key":"e_1_3_2_2_19_1","volume-title":"Survey on algorithms for self-stabilizing overlay networks. ACM Computing Surveys, 53(4)","author":"Feldmann Michael","year":"2020","unstructured":"Michael Feldmann , Christian Scheideler , and Stefan Schmid . Survey on algorithms for self-stabilizing overlay networks. ACM Computing Surveys, 53(4) , 2020 . Michael Feldmann, Christian Scheideler, and Stefan Schmid. Survey on algorithms for self-stabilizing overlay networks. ACM Computing Surveys, 53(4), 2020."},{"key":"e_1_3_2_2_20_1","volume-title":"43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018","author":"Fichtenberger Hendrik","year":"2018","unstructured":"Hendrik Fichtenberger and Yadu Vasudev . 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 . Hendrik Fichtenberger and Yadu Vasudev. 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":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch20"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212743"},{"key":"e_1_3_2_2_23_1","volume-title":"Improved mpc algorithms for mis, matching, and coloring on trees and beyond. arXiv preprint arXiv:2002.09610","author":"Ghaffari Mohsen","year":"2020","unstructured":"Mohsen Ghaffari , Christoph Grunau , and Ce Jin . Improved mpc algorithms for mis, matching, and coloring on trees and beyond. arXiv preprint arXiv:2002.09610 , 2020 . Mohsen Ghaffari, Christoph Grunau, and Ce Jin. Improved mpc algorithms for mis, matching, and coloring on trees and beyond. arXiv preprint arXiv:2002.09610, 2020."},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405716"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2004.1354487"},{"key":"e_1_3_2_2_26_1","first-page":"1","volume-title":"Christian Sohler. Distributed Monitoring of Network Properties: The Power of Hybrid Networks. In Proc. of the 44th International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Gmyr Robert","year":"2017","unstructured":"Robert Gmyr , Kristian Hinnenthal , Christian Scheideler , and Christian Sohler. Distributed Monitoring of Network Properties: The Power of Hybrid Networks. In Proc. of the 44th International Colloquium on Automata, Languages, and Programming (ICALP) , pages 137: 1 -- 137 :15, 2017 . Robert Gmyr, Kristian Hinnenthal, Christian Scheideler, and Christian Sohler. Distributed Monitoring of Network Properties: The Power of Hybrid Networks. In Proc. of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), pages 137:1--137:15, 2017."},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-24922-9_18"},{"key":"e_1_3_2_2_28_1","volume-title":"Time-optimal construction of overlay networks. arXiv preprint arXiv:2009.03987","author":"Thorsten G\u00f6","year":"2020","unstructured":"Thorsten G\u00f6 tte, Kristian Hinnenthal , Christian Scheideler , and Julian Werthmann . Time-optimal construction of overlay networks. arXiv preprint arXiv:2009.03987 , 2020 . Thorsten G\u00f6 tte, Kristian Hinnenthal, Christian Scheideler, and Julian Werthmann. Time-optimal construction of overlay networks. arXiv preprint arXiv:2009.03987, 2020."},{"key":"e_1_3_2_2_29_1","volume-title":"Proc. of the 33rd IEEE International Parallel and Distributed Processing Symposium (IPDPS)","author":"Thorsten G\u00f6","year":"2019","unstructured":"Thorsten G\u00f6 tte, Vipin Ravindran Vijayalakshmi , and Christian Scheideler . Always be Two Steps Ahead of Your Enemy . In Proc. of the 33rd IEEE International Parallel and Distributed Processing Symposium (IPDPS) , 2019 . Thorsten G\u00f6 tte, Vipin Ravindran Vijayalakshmi, and Christian Scheideler. Always be Two Steps Ahead of Your Enemy. In Proc. of the 33rd IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2019."},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1146"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629695"},{"key":"e_1_3_2_2_32_1","volume-title":"Minimum cuts in near-linear time. Journal of the ACM (JACM), 47(1):46--76","author":"Karger David R","year":"2000","unstructured":"David R Karger . Minimum cuts in near-linear time. Journal of the ACM (JACM), 47(1):46--76 , 2000 . David R Karger. Minimum cuts in near-linear time. Journal of the ACM (JACM), 47(1):46--76, 2000."},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405719"},{"key":"e_1_3_2_2_34_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM","author":"Kwok Tsz Chiu","year":"2014","unstructured":"Tsz Chiu Kwok and Lap Chi Lau . 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. Tsz Chiu Kwok and Lap Chi Lau. 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":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384303"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2003.1209234"},{"key":"e_1_3_2_2_37_1","volume-title":"Shayan Oveis Gharan, and Luca Trevisan. Multiway spectral partitioning and higher-order cheeger inequalities. Journal of the ACM (JACM), 61(6):1--30","author":"Lee James R","year":"2014","unstructured":"James R Lee , Shayan Oveis Gharan, and Luca Trevisan. Multiway spectral partitioning and higher-order cheeger inequalities. Journal of the ACM (JACM), 61(6):1--30 , 2014 . James R Lee, Shayan Oveis Gharan, and Luca Trevisan. Multiway spectral partitioning and higher-order cheeger inequalities. Journal of the ACM (JACM), 61(6):1--30, 2014."},{"key":"e_1_3_2_2_38_1","first-page":"359","volume-title":"Proc. of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","author":"Liu Sixue Cliff","year":"2020","unstructured":"Sixue Cliff Liu , Robert E. Tarjan , and Peilin Zhong . Connected components on a PRAM in log diameter time. In Christian Scheideler and Michael Spear, editors , Proc. of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) , Virtual Event, USA , July 15-17, 2020 , pages 359 -- 369 . ACM, 2020. Sixue Cliff Liu, Robert E. Tarjan, and Peilin Zhong. Connected components on a PRAM in log diameter time. In Christian Scheideler and Michael Spear, editors, Proc. of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Virtual Event, USA, July 15-17, 2020, pages 359--369. ACM, 2020."},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89553"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755574"},{"key":"e_1_3_2_2_41_1","first-page":"323","volume-title":"Saheb-Djahromi Nasser, and Akka Zemmari. An optimal bit complexity randomized distributed mis algorithm. In International Colloquium on Structural Information and Communication Complexity (SIROCCO)","author":"M\u00e9tivier Yves","year":"2009","unstructured":"Yves M\u00e9tivier , John Michael Robson , Saheb-Djahromi Nasser, and Akka Zemmari. An optimal bit complexity randomized distributed mis algorithm. In International Colloquium on Structural Information and Communication Complexity (SIROCCO) , pages 323 -- 337 . Springer , 2009 . Yves M\u00e9tivier, John Michael Robson, Saheb-Djahromi Nasser, and Akka Zemmari. An optimal bit complexity randomized distributed mis algorithm. In International Colloquium on Structural Information and Communication Complexity (SIROCCO), pages 323--337. Springer, 2009."},{"key":"e_1_3_2_2_42_1","volume-title":"USA","author":"Oaks Scott","year":"2002","unstructured":"Scott Oaks and Li Gong . Jxta in a Nutshell. O'Reilly & Associates, Inc ., USA , 2002 . Scott Oaks and Li Gong. Jxta in a Nutshell. O'Reilly & Associates, Inc., USA, 2002."},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700371065"},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.126"},{"key":"e_1_3_2_2_45_1","first-page":"329","volume-title":"Proc. of IFIP\/ACM International Conference on Distributed Systems Platforms (Middleware)","author":"Antony I.","year":"2001","unstructured":"Antony I. T. Rowstron and Peter Druschel. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems . In Proc. of IFIP\/ACM International Conference on Distributed Systems Platforms (Middleware) , pages 329 -- 350 , 2001 . Antony I. T. Rowstron and Peter Druschel. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In Proc. of IFIP\/ACM International Conference on Distributed Systems Platforms (Middleware), pages 329--350, 2001."},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35668-1_2"},{"key":"e_1_3_2_2_47_1","volume-title":"Algorithms for random generation and counting: a Markov chain approach","author":"Sinclair Alistair","year":"2012","unstructured":"Alistair Sinclair . Algorithms for random generation and counting: a Markov chain approach . Springer Science & Business Media , 2012 . Alistair Sinclair. Algorithms for random generation and counting: a Markov chain approach. Springer Science & Business Media, 2012."},{"key":"e_1_3_2_2_48_1","first-page":"149","volume-title":"Proc. of the 2018 Conference of the ACM Special Interest Group on Data Communication (SIGCOMM)","author":"Stoica Ion","year":"2001","unstructured":"Ion Stoica , Robert Tappan Morris , David R. Karger , M. Frans Kaashoek , and Hari Balakrishnan . Chord : A scalable peer-to-peer lookup service for internet applications . In Proc. of the 2018 Conference of the ACM Special Interest Group on Data Communication (SIGCOMM) , pages 149 -- 160 , 2001 . Ion Stoica, Robert Tappan Morris, David R. Karger, M. Frans Kaashoek, and Hari Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In Proc. of the 2018 Conference of the ACM Special Interest Group on Data Communication (SIGCOMM), pages 149--160, 2001."},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214061"}],"event":{"name":"PODC '21: ACM Symposium on Principles of Distributed Computing","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Event Italy","acronym":"PODC '21"},"container-title":["Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465084.3467932","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3465084.3467932","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:25Z","timestamp":1750191505000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465084.3467932"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,21]]},"references-count":49,"alternative-id":["10.1145\/3465084.3467932","10.1145\/3465084"],"URL":"https:\/\/doi.org\/10.1145\/3465084.3467932","relation":{},"subject":[],"published":{"date-parts":[[2021,7,21]]},"assertion":[{"value":"2021-07-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}