{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T16:41:55Z","timestamp":1787503315857,"version":"build-2736575974"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,7,11]],"date-time":"2020-07-11T00:00:00Z","timestamp":1594425600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ERC Consolidator grant","award":["864228."],"award-info":[{"award-number":["864228."]}]},{"DOI":"10.13039\/501100001659","name":"German Research Foundation","doi-asserted-by":"crossref","award":["160364472"],"award-info":[{"award-number":["160364472"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Comput. Surv."],"published-print":{"date-parts":[[2021,7,31]]},"abstract":"<jats:p>The maintenance of efficient and robust overlay networks is one of the most fundamental and reoccurring themes in networking. This article presents a survey of state-of-the-art algorithms to design and repair overlay networks in a distributed manner. In particular, we discuss basic algorithmic primitives to preserve connectivity, review algorithms for the fundamental problem of graph linearization, and then survey self-stabilizing algorithms for metric and scalable topologies. We also identify open problems and avenues for future research.<\/jats:p>","DOI":"10.1145\/3397190","type":"journal-article","created":{"date-parts":[[2020,7,7]],"date-time":"2020-07-07T08:38:30Z","timestamp":1594111110000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Survey on Algorithms for Self-stabilizing Overlay Networks"],"prefix":"10.1145","volume":"53","author":[{"given":"Michael","family":"Feldmann","sequence":"first","affiliation":[{"name":"Paderborn University, Paderborn, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian","family":"Scheideler","sequence":"additional","affiliation":[{"name":"Paderborn University, Paderborn, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7798-1711","authenticated-orcid":false,"given":"Stefan","family":"Schmid","sequence":"additional","affiliation":[{"name":"Faculty of Computer Science, University of Vienna, Vienna, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,7,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073970.1073991"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290674"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77096-1_21"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9099-9"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21938"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185377"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/NetSys.2013.11"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21741-3_16"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS\u201911)","author":"Berns Andrew","unstructured":"Andrew Berns , Sukumar Ghosh , and Sriram V. Pemmaraju . 2011. Building self-stabilizing overlay networks with the transitive closure framework . In Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS\u201911) . 62--76. DOI:https:\/\/doi.org\/10.1007\/978-3-642-24550-3_7 10.1007\/978-3-642-24550-3_7 Andrew Berns, Sukumar Ghosh, and Sriram V. Pemmaraju. 2011. Building self-stabilizing overlay networks with the transitive closure framework. In Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS\u201911). 62--76. DOI:https:\/\/doi.org\/10.1007\/978-3-642-24550-3_7"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2018.00032"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_12"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/361179.361202"},{"key":"e_1_2_1_13_1","volume-title":"The MIT Press","author":"Dolev Shlomi","unstructured":"Shlomi Dolev . 2000. Self-stabilization. The MIT Press , Cambridge, MA . Shlomi Dolev. 2000. Self-stabilization. The MIT Press, Cambridge, MA."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.5"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-03232-6_2"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-69084-1_17"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/P2P.2014.6934300"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11764-5_4"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-013-9504-x"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-017-9823-4"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1151659.1159931"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-03232-6_4"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 4th USENIX Symposium on Internet Technologies and Systems (USITS\u201903)","volume":"4","author":"Harvey Nicholas J. A.","year":"2003","unstructured":"Nicholas J. A. Harvey , Michael B. Jones , Stefan Saroiu , Marvin Theimer , and Alec Wolman . 2003 . SkipNet: A scalable overlay network with practical locality properties . In Proceedings of the 4th USENIX Symposium on Internet Technologies and Systems (USITS\u201903) , Vol. 4 . USENIX Association, Berkeley, CA, 9--9. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id&equals;1251460.1251469. Nicholas J. A. Harvey, Michael B. Jones, Stefan Saroiu, Marvin Theimer, and Alec Wolman. 2003. SkipNet: A scalable overlay network with practical locality properties. In Proceedings of the 4th USENIX Symposium on Internet Technologies and Systems (USITS\u201903), Vol. 4. USENIX Association, Berkeley, CA, 9--9. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id&equals;1251460.1251469."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 18th International Workshop on Network and Operating Systems Support for Digital Audio and Video. ACM, 75--80","author":"Huang Cheng","unstructured":"Cheng Huang , Angela Wang , Jin Li , and Keith W. Ross . 2008. Understanding hybrid CDN-P2P: Why limelight needs its own red swoosh . In Proceedings of the 18th International Workshop on Network and Operating Systems Support for Digital Audio and Video. ACM, 75--80 . Cheng Huang, Angela Wang, Jin Li, and Keith W. Ross. 2008. Understanding hybrid CDN-P2P: Why limelight needs its own red swoosh. In Proceedings of the 18th International Workshop on Network and Operating Systems Support for Digital Audio and Video. ACM, 75--80."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629695"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.07.029"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPADS.2010.42"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the International Workshop on Peer-to-Peer Systems. Springer, 98--107","author":"Frans Kaashoek M.","year":"2003","unstructured":"M. Frans Kaashoek and David R Karger . 2003 . Koorde: A simple degree-optimal distributed hash table . In Proceedings of the International Workshop on Peer-to-Peer Systems. Springer, 98--107 . M. Frans Kaashoek and David R Karger. 2003. Koorde: A simple degree-optimal distributed hash table. In Proceedings of the International Workshop on Peer-to-Peer Systems. Springer, 98--107."},{"key":"e_1_2_1_29_1","volume-title":"Navigation in a small world. Nature 406, 6798","author":"Kleinberg Jon M.","year":"2000","unstructured":"Jon M. Kleinberg . 2000. Navigation in a small world. Nature 406, 6798 ( 2000 ), 845. Jon M. Kleinberg. 2000. Navigation in a small world. Nature 406, 6798 (2000), 845."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2012.115"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03578-9_14"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9431-2"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21741-3_14"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/11558989_2"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/858336.858339"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-05118-0_2"},{"key":"e_1_2_1_37_1","first-page":"1","article-title":"A survey and comparison of peer-to-peer overlay network schemes","volume":"7","author":"Lua Eng Keong","year":"2005","unstructured":"Eng Keong Lua , Jon Crowcroft , Marcelo Pias , Ravi Sharma , Steven Lim , et\u00a0al. 2005 . A survey and comparison of peer-to-peer overlay network schemes . IEEE Commun. Surv. Tutor. 7 , 1 -- 4 (2005), 72--93. Eng Keong Lua, Jon Crowcroft, Marcelo Pias, Ravi Sharma, Steven Lim, et\u00a0al. 2005. A survey and comparison of peer-to-peer overlay network schemes. IEEE Commun. Surv. Tutor. 7, 1--4 (2005), 72--93.","journal-title":"IEEE Commun. Surv. Tutor."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2019.00093"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073970.1073992"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148109.1148162"},{"key":"e_1_2_1_41_1","volume-title":"Peer-to-peer-netzwerke: Algorithmen und Methoden","author":"Mahlmann Peter","year":"2007","unstructured":"Peter Mahlmann and Christian Schindelhauer . 2007 . Peer-to-peer-netzwerke: Algorithmen und Methoden . Springer-Verlag . Peter Mahlmann and Christian Schindelhauer. 2007. Peer-to-peer-netzwerke: Algorithmen und Methoden. Springer-Verlag."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45748-8_5"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/777412.777421"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.08.029"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972870.10"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/319056.319004"},{"key":"e_1_2_1_47_1","unstructured":"Joseph Poon and Thaddeus Dryja. 2016. The bitcoin lightning network: Scalable off-chain instant payments. Retrieved from https:\/\/lightning.network\/lightning-network-paper.pdf.  Joseph Poon and Thaddeus Dryja. 2016. The bitcoin lightning network: Scalable off-chain instant payments. Retrieved from https:\/\/lightning.network\/lightning-network-paper.pdf."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/383059.383072"},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the USENIX Annual Technical Conference","volume":"6","author":"Rhea Sean","year":"2004","unstructured":"Sean Rhea , Dennis Geels , Timothy Roscoe , John Kubiatowicz , et\u00a0al. 2004 . Handling churn in a DHT . In Proceedings of the USENIX Annual Technical Conference , Vol. 6 . Boston, MA, 127--140. Sean Rhea, Dennis Geels, Timothy Roscoe, John Kubiatowicz, et\u00a0al. 2004. Handling churn in a DHT. In Proceedings of the USENIX Annual Technical Conference, Vol. 6. Boston, MA, 127--140."},{"key":"e_1_2_1_50_1","volume-title":"Contemporary and Emerging Applications","author":"Andr\u00e9a","year":"2018","unstructured":"Andr\u00e9a W. Richa and Christian Scheideler . 2018 . Overlay networks for peer-to-peer networks. In Handbook of Approximation Algorithms and Metaheuristics , Second Edition, Volume 2 : Contemporary and Emerging Applications . Chapman and Hall\/CRC. Andr\u00e9a W. Richa and Christian Scheideler. 2018. Overlay networks for peer-to-peer networks. In Handbook of Approximation Algorithms and Metaheuristics, Second Edition, Volume 2: Contemporary and Emerging Applications. Chapman and Hall\/CRC."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24550-3_31"},{"key":"e_1_2_1_52_1","volume-title":"Proceedings of the 27th International Conference on Concurrency Theory (CONCUR\u201916)","author":"Rickmann Christina","year":"2016","unstructured":"Christina Rickmann , Christoph Wagner , Uwe Nestmann , and Stefan Schmid . 2016 . Topological self-stabilization with name-passing process calculi . In Proceedings of the 27th International Conference on Concurrency Theory (CONCUR\u201916) . 19:1--19:15. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2016.19 10.4230\/LIPIcs.CONCUR.2016.19 Christina Rickmann, Christoph Wagner, Uwe Nestmann, and Stefan Schmid. 2016. Topological self-stabilization with name-passing process calculi. In Proceedings of the 27th International Conference on Concurrency Theory (CONCUR\u201916). 19:1--19:15. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2016.19"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45518-3_18"},{"key":"e_1_2_1_54_1","volume-title":"How to spread adversarial nodes?: Rotate! In Proceedings of the 37th Annual ACM Symposium on Theory of Computing. ACM, 704--713","author":"Scheideler Christian","unstructured":"Christian Scheideler . 2005. How to spread adversarial nodes?: Rotate! In Proceedings of the 37th Annual ACM Symposium on Theory of Computing. ACM, 704--713 . Christian Scheideler. 2005. How to spread adversarial nodes?: Rotate! In Proceedings of the 37th Annual ACM Symposium on Theory of Computing. ACM, 704--713."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-03232-6_16"},{"key":"e_1_2_1_56_1","volume-title":"Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS\u201915)","author":"Scheideler Christian","year":"2015","unstructured":"Christian Scheideler , Alexander Setzer , and Thim Strothmann . 2015 . Towards establishing monotonic searchability in self-stabilizing data structures . In Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS\u201915) . 24:1--24:17. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.OPODIS.2015.24 10.4230\/LIPIcs.OPODIS.2015.24 Christian Scheideler, Alexander Setzer, and Thim Strothmann. 2015. Towards establishing monotonic searchability in self-stabilizing data structures. In Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS\u201915). 24:1--24:17. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.OPODIS.2015.24"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53426-7_6"},{"key":"e_1_2_1_58_1","volume-title":"Proceedings of the 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201912)","author":"Singla Ankit","unstructured":"Ankit Singla , Chi-Yao Hong , Lucian Popa , and P. Brighten Godfrey . 2012. Jellyfish: Networking data centers randomly . In Proceedings of the 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201912) . 225--238. Ankit Singla, Chi-Yao Hong, Lucian Popa, and P. Brighten Godfrey. 2012. Jellyfish: Networking data centers randomly. In Proceedings of the 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201912). 225--238."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2002.808407"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2999572.2999580"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1137\/110832458"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2003.818784"}],"container-title":["ACM Computing Surveys"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3397190","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3397190","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:31:37Z","timestamp":1750181497000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3397190"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,11]]},"references-count":62,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,7,31]]}},"alternative-id":["10.1145\/3397190"],"URL":"https:\/\/doi.org\/10.1145\/3397190","relation":{},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"value":"0360-0300","type":"print"},{"value":"1557-7341","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,11]]},"assertion":[{"value":"2019-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-07-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}