{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T02:46:33Z","timestamp":1777689993152,"version":"3.51.4"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2014,12,17]],"date-time":"2014-12-17T00:00:00Z","timestamp":1418774400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0830704"],"award-info":[{"award-number":["CCF-0830704"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001736","name":"German-Israeli Foundation for Scientific Research and Development","doi-asserted-by":"publisher","award":["I-1245-407.6\/2014"],"award-info":[{"award-number":["I-1245-407.6\/2014"]}],"id":[{"id":"10.13039\/501100001736","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2014,12,17]]},"abstract":"<jats:p>\n            Peer-to-peer systems rely on a scalable overlay network that enables efficient routing between its members. Hypercubic topologies facilitate such operations while each node only needs to connect to a small number of other nodes. In contrast to static communication networks, peer-to-peer networks allow nodes to adapt their neighbor set over time in order to react to join and leave events and failures. This article shows how to maintain such networks in a robust manner. Concretely, we present a distributed and self-stabilizing algorithm that constructs a (slightly extended) skip graph, SKIP\n            <jats:sup>+<\/jats:sup>\n            , in polylogarithmic time from\n            <jats:italic>any given<\/jats:italic>\n            initial state in which the overlay network is still weakly connected. This is an exponential improvement compared to previously known self-stabilizing algorithms for overlay networks. In addition, our algorithm handles individual joins and leaves locally and efficiently.\n          <\/jats:p>","DOI":"10.1145\/2629695","type":"journal-article","created":{"date-parts":[[2014,12,19]],"date-time":"2014-12-19T13:38:51Z","timestamp":1418996331000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["SKIP\n            <sup>+<\/sup>"],"prefix":"10.1145","volume":"61","author":[{"given":"Riko","family":"Jacob","sequence":"first","affiliation":[{"name":"Eidgen\u00f6ssische Technische Hochschule Z\u00fcrich, Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrea","family":"Richa","sequence":"additional","affiliation":[{"name":"Arizona State University, Tempe, AZ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Scheideler","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Paderborn, Paderborn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Schmid","sequence":"additional","affiliation":[{"name":"T-Labs and Technische Universit\u00e4t Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hanjo","family":"T\u00e4ubig","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t M\u00fcnchen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,12,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.2001.1823"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073970.1073991"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA). 384--393","author":"Aspnes James","year":"2003","unstructured":"James Aspnes and Gauri Shah . 2003 . Skip graphs . In Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA). 384--393 . James Aspnes and Gauri Shah. 2003. Skip graphs. In Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA). 384--393."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290674"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073970.1073989"},{"key":"e_1_2_1_6_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the International Conference on Principles of Distributed Systems (OPODIS)","author":"Aspnes James","unstructured":"James Aspnes and Yinghua Wu. 2007. O(log n)-time overlay network construction from graphs with out-degree 1. In Proceedings of the International Conference on Principles of Distributed Systems (OPODIS) . Lecture Notes in Computer Science , vol. 4878 , Springer-Verlag , 286--300. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-540-77096-1_21 10.1007\/978-3-540-77096-1_21 James Aspnes and Yinghua Wu. 2007. O(log n)-time overlay network construction from graphs with out-degree 1. In Proceedings of the International Conference on Principles of Distributed Systems (OPODIS). Lecture Notes in Computer Science, vol. 4878, Springer-Verlag, 286--300. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-540-77096-1_21"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185378"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/645951.675485"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872053"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 318--327","author":"Awerbuch Baruch","year":"2004","unstructured":"Baruch Awerbuch and Christian Scheideler . 2004 . The hyperring: A low-congestion deterministic data structure for distributed environments . In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 318--327 . Baruch Awerbuch and Christian Scheideler. 2004. The hyperring: A low-congestion deterministic data structure for distributed environments. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 318--327."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185377"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2050613.2050620"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007912.1007938"},{"key":"e_1_2_1_14_1","first-page":"1","article-title":"Self-stabilization in distributed systems - A short survey","volume":"25","author":"Brzezinski J.","year":"2000","unstructured":"J. Brzezinski and M. Szychowiak . 2000 . Self-stabilization in distributed systems - A short survey . Found. Comput . Dec. Sci. 25 , 1 . J. Brzezinski and M. Szychowiak. 2000. Self-stabilization in distributed systems - A short survey. Found. Comput. Dec. Sci. 25, 1.","journal-title":"Found. Comput"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/SRDS.2008.18"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89335-6_12"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/248052.248056"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/361179.361202"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"S. Dolev. 2000. Self-Stabilization. MIT Press.   S. Dolev. 2000. Self-Stabilization. MIT Press.","DOI":"10.7551\/mitpress\/6156.001.0001"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4086\/cjtcs.1997.004"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 18th IFIP\/ACM International Conference on Distributed Systems Platforms (Middleware). 329--350","author":"Druschel Peter","year":"2001","unstructured":"Peter Druschel and Antony Rowstron . 2001 . Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems . In Proceedings of the 18th IFIP\/ACM International Conference on Distributed Systems Platforms (Middleware). 329--350 . See also http:\/\/research.microsoft.com\/&sim;antr\/Pastry. Peter Druschel and Antony Rowstron. 2001. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In Proceedings of the 18th IFIP\/ACM International Conference on Distributed Systems Platforms (Middleware). 329--350. See also http:\/\/research.microsoft.com\/&sim;antr\/Pastry."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12200-2_27"},{"key":"e_1_2_1_24_1","volume-title":"Sun","author":"Goodrich Michael T.","year":"2006","unstructured":"Michael T. Goodrich , Michael J. Nelson , and Jonathan Z . Sun . 2006 . The rainbow skip graph: A fault-tolerant constant-degree distributed data structure. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA). 384--393. Michael T. Goodrich, Michael J. Nelson, and Jonathan Z. Sun. 2006. The rainbow skip graph: A fault-tolerant constant-degree distributed data structure. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA). 384--393."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.01.019"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 4th USENIX Symposium on Internet Technologies and Systems (USITS). 113--126","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). 113--126 . 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). 113--126."},{"key":"e_1_2_1_27_1","volume-title":"Self-stabilization bibliography: Access guide","author":"Herman T.","unstructured":"T. Herman . 2002. Self-stabilization bibliography: Access guide . University of Iowa . (ftp:\/\/ftp.cs.uiowa.edu\/pub\/selfstab\/bibliography\/.) T. Herman. 2002. Self-stabilization bibliography: Access guide. University of Iowa. (ftp:\/\/ftp.cs.uiowa.edu\/pub\/selfstab\/bibliography\/.)"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1582716.1582741"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_78"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02278852"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989527"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/11558989_2"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/259380.259435"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/224964.224967"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-05118-0_2"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/571825.571857"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/646334.687801"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/777412.777421"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30183-7_26"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972870.10"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"David Peleg. 2000. Distributed computing: A Locality-Sensitive Approach. SIAM.   David Peleg. 2000. Distributed computing: A Locality-Sensitive Approach. SIAM.","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/383059.383072"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02930-1_47"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/P2P.2005.34"},{"key":"e_1_2_1_45_1","volume-title":"Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. Tech. Rep. MIT-LCS-TR-819. MIT.","author":"Stoica Ion","year":"2001","unstructured":"Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , and Hari Balakrishnan . 2001 . Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. Tech. Rep. MIT-LCS-TR-819. MIT. Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan. 2001. Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. Tech. Rep. MIT-LCS-TR-819. MIT."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/197917.198102"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629695","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629695","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:13:31Z","timestamp":1750227211000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629695"}},"subtitle":["A Self-Stabilizing Skip Graph"],"short-title":[],"issued":{"date-parts":[[2014,12,17]]},"references-count":45,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2014,12,17]]}},"alternative-id":["10.1145\/2629695"],"URL":"https:\/\/doi.org\/10.1145\/2629695","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12,17]]},"assertion":[{"value":"2012-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-12-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}