{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T06:08:06Z","timestamp":1777615686444,"version":"3.51.4"},"reference-count":58,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2010,3,19]],"date-time":"2010-03-19T00:00:00Z","timestamp":1268956800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2010,5]]},"DOI":"10.1007\/s00446-010-0099-z","type":"journal-article","created":{"date-parts":[[2010,3,18]],"date-time":"2010-03-18T14:03:19Z","timestamp":1268920999000},"page":"249-267","source":"Crossref","is-referenced-by-count":33,"title":["Towards worst-case churn resistant peer-to-peer systems"],"prefix":"10.1007","volume":"22","author":[{"given":"Fabian","family":"Kuhn","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Schmid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roger","family":"Wattenhofer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,3,19]]},"reference":[{"key":"99_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Awerbuch, B., Azar, Y., Bartal, Y., Malkhi, D., Pavlov, E.: A generic scheme for building overlay networks in adversarial scenarios. In: Proceedings 17th International Symposium on Parallel and Distributed Processing (IPDPS) (2003)","DOI":"10.1109\/IPDPS.2003.1213125"},{"issue":"4","key":"99_CR2","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1109\/12.21148","volume":"38","author":"S.B. Akers","year":"1989","unstructured":"Akers S.B., Krishnamurthy B.: A group-theoretic model for symmetric interconnection networks. IEEE Trans. Comput. 38(4), 555\u2013566 (1989)","journal-title":"IEEE Trans. Comput."},{"key":"99_CR3","doi-asserted-by":"crossref","unstructured":"Albrecht, K., Arnold, R., G\u00e4hwiler, M., Wattenhofer, R.: Aggregating information in peer-to-peer systems for improved join and leave. In: Proceedings 4th IEEE International Conference on Peer-to-Peer Computing (P2P) (2004)","DOI":"10.1109\/PTP.2004.1334951"},{"issue":"3","key":"99_CR4","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1137\/0219037","volume":"19","author":"F. Annexstein","year":"1990","unstructured":"Annexstein F., Baumslag M., Rosenberg A.L.: Group action graphs and parallel architectures. SIAM J. Comput. 19(3), 544\u2013569 (1990)","journal-title":"SIAM J. Comput."},{"key":"99_CR5","unstructured":"Awerbuch, B., Scheideler, C.: The hyperring: a low-congestion deterministic data structure for distributed environments. In: Proceedings of 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 318\u2013327 (2004)"},{"key":"99_CR6","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Scheideler, C.: Robust random number generation for peer-to-peer systems. In: Proceedings of 10th International Conference on Principles of Distributed Systems (OPODIS) (2006)","DOI":"10.1007\/11945529_20"},{"key":"99_CR7","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Scheideler, C.: Towards a scalable and robust DHT. In: Proceedings of 18th ACM Symposium on Parallel Algorithms and Architectures (SPAA) (2006)","DOI":"10.1145\/1148109.1148163"},{"key":"99_CR8","doi-asserted-by":"crossref","unstructured":"Bhagwan, R., Savage, S., Voelker, G.: Understanding availability. In: Proceedings of 2nd International Workshop on Peer-to-Peer Systems (IPTPS) (2003)","DOI":"10.1007\/978-3-540-45172-3_24"},{"key":"99_CR9","doi-asserted-by":"crossref","unstructured":"Bhargava, A., Kothapalli, K., Riley, C., Scheideler, C., Thober, M.: Pagoda: a dynamic overlay network for routing, data management, and multicasting. In: Proceedings of 16th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 170\u2013179 (2004)","DOI":"10.1145\/1007912.1007938"},{"key":"99_CR10","doi-asserted-by":"crossref","unstructured":"Clouser, T., Nesterenko, M., Scheideler, C.: Tiara: A self-stabilizing deterministic skip list. In: Proceedings of SSS (2008)","DOI":"10.1007\/978-3-540-89335-6_12"},{"key":"99_CR11","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/0743-7315(89)90021-X","volume":"7","author":"G. Cybenko","year":"1989","unstructured":"Cybenko G.: Dynamic load balancing for distributed memory multiprocessors. J. Parallel Distrib. Comput. 7, 279\u2013301 (1989)","journal-title":"J. Parallel Distrib. Comput."},{"key":"99_CR12","unstructured":"Datta, A., Aberer, K.: Internet-scale storage systems under churn. In: Proceedings of 6th IEEE International Conference on Peer-to-Peer Computing (P2P) (2006)"},{"key":"99_CR13","unstructured":"Dweighter, H. (a.k.a. J. E. Goodman): Problem E2569. American Mathematical Monthly, vol. 82 (1975)"},{"key":"99_CR14","unstructured":"Fiat, A., Saia, J.: Censorship resistant peer-to-peer content addressable networks. In: Proceedings of 13th Symposium on Discrete Algorithms (SODA) (2002)"},{"key":"99_CR15","doi-asserted-by":"crossref","unstructured":"Fiat, A., Saia, J., Young, M.: Making chord Robust to byzantine attacks. In: Proceedings of European Symposium on Algorithms (ESA) (2005)","DOI":"10.1007\/11561071_71"},{"key":"99_CR16","doi-asserted-by":"crossref","unstructured":"Gall, D., Jacob, R., Richa, A., Scheideler, C., Schmid, S., T\u00e4ubig, H.: Brief announcement: on the time complexity of distributed topological self-stabilization. In: Proceedings of International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS) (2009)","DOI":"10.1007\/978-3-642-05118-0_58"},{"key":"99_CR17","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of books in the mathematical sciences). W.H. Freeman, San Francisco (1979)"},{"key":"99_CR18","doi-asserted-by":"crossref","unstructured":"Godfrey, P.B., Shenker, S., Stoica, I.: Minimizing churn in distributed systems. In: Proceedings of ACM SIGCOMM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (2006)","DOI":"10.1145\/1159913.1159931"},{"key":"99_CR19","unstructured":"Guha, S., Daswani, N., Jain, R.: An experimental study of the skype peer-to-peer VoIP system. In: Proceedings of 5th International Workshop on Peer-to-Peer Systems (IPTPS) (2006)"},{"key":"99_CR20","unstructured":"Haeberlen, A., Mislove, A., Post, A., Druschel, P.: Fallacies in evaluating decentralized systems. In: Proceedings 5th International Workshop on Peer-to-Peer Systems (IPTPS) (2006)"},{"issue":"4","key":"99_CR21","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/j.ipl.2004.01.019","volume":"90","author":"N. Harvey","year":"2004","unstructured":"Harvey N., Munro J.: Deterministic skipnet. Inf. Process. Lett. 90(4), 205\u2013208 (2004)","journal-title":"Inf. Process. Lett."},{"key":"99_CR22","doi-asserted-by":"crossref","unstructured":"Jacob, R., Richa, A., Scheideler, C., Schmid, S., T\u00e4ubig, H.: A distributed polylogarithmic time algorithm for self-stabilizing skip graphs. In: Proceedings of Annual ACM Symposium on Principles of Distributed Computing (PODC) (2009)","DOI":"10.1145\/1582716.1582741"},{"key":"99_CR23","doi-asserted-by":"crossref","unstructured":"Jacob, R., Ritscher, S., Scheideler, C., Schmid, S.: A self-stabilizing and local delaunay graph construction. In: Proceedings of 20th International Symposium on Algorithms and Computation (ISAAC) (2009)","DOI":"10.1007\/978-3-642-10631-6_78"},{"key":"99_CR24","doi-asserted-by":"crossref","unstructured":"Kempe, D., Dobra, A., Gehrke, J.: Gossip-based computation of aggregate information. In: Proceedings of 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS) (2003)","DOI":"10.1109\/SFCS.2003.1238221"},{"key":"99_CR25","doi-asserted-by":"crossref","unstructured":"Kothapalli, K., Scheideler, C.: Supervised peer-to-peer systems. In: Proceedings of International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN), pp. 188\u2013193 (2005)","DOI":"10.1109\/ISPAN.2005.81"},{"key":"99_CR26","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Locher, T., Wattenhofer, R.: Tight bounds for distributed selection. In: Proceedings of 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) (2007)","DOI":"10.1145\/1248377.1248401"},{"key":"99_CR27","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Schmid, S., Smit, J., Wattenhofer, R.: A blueprint for constructing peer-to-peer systems Robust to dynamic worst-case joins and leaves. In: Proceedings of 14th IEEE International Workshop on Quality of Service (IWQoS) (2006)","DOI":"10.1109\/IWQOS.2006.250446"},{"key":"99_CR28","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Schmid, S., Wattenhofer, R.: A self-repairing peer-to-peer system resilient to dynamic adversarial churn. In: Proceedings of 4th International Workshop on Peer-To-Peer Systems (IPTPS) (2005)","DOI":"10.1007\/11558989_2"},{"key":"99_CR29","unstructured":"Li, J., Stribling, J., Morris, R., Kaashoek, M.F., Gil, T.M.: A performance versus cost framework for evaluating DHT design tradeoffs under churn. In: Proceedings of 24th Annual IEEE Conference on Computer Communications (INFOCOM) (2005)"},{"key":"99_CR30","doi-asserted-by":"crossref","unstructured":"Li, X., Misra, J., Plaxton, C.G.: Active and concurrent topology maintenance. In: Proceedings of 18th Annual Conference on Distributed Computing (DISC) (2004)","DOI":"10.1007\/978-3-540-30186-8_23"},{"key":"99_CR31","doi-asserted-by":"crossref","unstructured":"Liben-Nowell, D., Balakrishnan, H., Karger, D.: Analysis of the evolution of peer-to-peer systems. In: Proceedings of 21st Annual Symposium on Principles of Distributed Computing (PODC), pp. 233\u2013242 (2002)","DOI":"10.1145\/571860.571863"},{"key":"99_CR32","unstructured":"Locher, T., Schmid, S., Wattenhofer, R.: eQuus: a provably Robust and locality-aware peer-to-peer system. In: Proceedings of 6th IEEE International Conference on Peer-to-Peer Computing (P2P) (2006)"},{"key":"99_CR33","unstructured":"Mitra, B., Ghose, S., Ganguly, N.: Effect of dynamicity on peer-to-peer networks. In: Proceedings of 14th International Conference on High Performance Computing (HiPC) (2007)"},{"key":"99_CR34","doi-asserted-by":"crossref","unstructured":"Mosk-Aoyama, D., Shah, D.: Computing separable functions via gossip. In: Proceedings of 25th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 113\u2013122 (2006)","DOI":"10.1145\/1146381.1146401"},{"key":"99_CR35","doi-asserted-by":"crossref","unstructured":"Naor, M., Wieder, U.: Novel architectures for P2P applications: the continuous-discrete approach. In: Proceedings of 15th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 50\u201359 (2003)","DOI":"10.1145\/777412.777421"},{"key":"99_CR36","doi-asserted-by":"crossref","unstructured":"Pandurangan, G., Raghavan, P., Upfal, E.: Building low-diameter P2P networks. In: Proceedings of 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS) (2001)","DOI":"10.1109\/SFCS.2001.959925"},{"issue":"1\u20133","key":"99_CR37","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/j.tcs.2006.10.032","volume":"370","author":"B. Patt-Shamir","year":"2007","unstructured":"Patt-Shamir B.: A note on efficient aggregate queries in sensor networks. Theor. Comput. Sci. 370(1\u20133), 254\u2013264 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"99_CR38","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing A Locality-sensitive Approach","author":"D. Peleg","year":"2000","unstructured":"Peleg D.: Distributed Computing A Locality-sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA (2000)"},{"issue":"2","key":"99_CR39","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1137\/0218015","volume":"18","author":"D. Peleg","year":"1989","unstructured":"Peleg D., Upfal E.: The token distribution problem. SIAM J. Comput. 18(2), 229\u2013243 (1989)","journal-title":"SIAM J. Comput."},{"key":"99_CR40","doi-asserted-by":"crossref","unstructured":"Plaxton, C.G.: Load Balancing, Selection and Sorting on the Hypercube. In: Proceedings of the 1st Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 64\u201373 (1989)","DOI":"10.1145\/72935.72943"},{"key":"99_CR41","unstructured":"Qiao, Y., Bustamante, F.E.: Structured and unstructured overlays under the microscope\u2014a measurement-based view of two P2P systems that people use. In: Proceedings of the USENIX Annual Technical Conference (2006)"},{"key":"99_CR42","doi-asserted-by":"crossref","unstructured":"Ratnasamy, S., Francis, P., Handley, M., Karp, R., Schenker, S.: A scalable content-addressable network. In: Proceedings of the ACM SIGCOMM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, pp. 161\u2013172 (2001)","DOI":"10.1145\/383059.383072"},{"key":"99_CR43","doi-asserted-by":"crossref","unstructured":"Rhea, S., Chun, B.-G., Kubiatowicz, J., Shenker, S.: Fixing the embarrassing slowness of openDHT on planetLab. In: Proceedings of the 2nd Conference on Real, Large Distributed Systems (WORLDS) (2005)","DOI":"10.1145\/1090191.1080102"},{"key":"99_CR44","unstructured":"Rhea, S., Geels, D., Roscoe, T., Kubiatowicz, J.: Handling churn in a DHT. In: Proceedings of the USENIX Annual Technical Conference (2004)"},{"key":"99_CR45","doi-asserted-by":"crossref","unstructured":"Rowstron, A., Druschel, P.: Pastry: scalable, decentralized object location and routing for large-scale peer-to-peer systems. In: Proceedings of the IFIP\/ACM International Conference on Distributed Systems Platforms (Middleware), pp. 329\u2013350 (2001)","DOI":"10.1007\/3-540-45518-3_18"},{"key":"99_CR46","doi-asserted-by":"crossref","unstructured":"Saia, J., Fiat, A., Gribble, S., Karlin, A., Saroiu, S.: Dynamically fault-tolerant content addressable networks. In: Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS) (2002)","DOI":"10.1007\/3-540-45748-8_26"},{"key":"99_CR47","doi-asserted-by":"crossref","unstructured":"Saroiu, S., Gummadi, P.K., Gribble, S.D.: A measurement study of peer-to-peer file sharing systems. In: Proceedings of the Multimedia Computing and Networking (MMCN) (2002)","DOI":"10.1117\/12.449977"},{"key":"99_CR48","doi-asserted-by":"crossref","unstructured":"Scheideler, C.: How to spread adversarial nodes? rotate! In: Proceedings of the 37th ACM Symposium on Theory of Computing (STOC) (2005)","DOI":"10.1145\/1060590.1060694"},{"key":"99_CR49","doi-asserted-by":"crossref","unstructured":"Scheideler, C., Schmid, S.: A distributed and oblivious heap. In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP) (2009)","DOI":"10.1007\/978-3-642-02930-1_47"},{"issue":"2","key":"99_CR50","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1109\/TNET.2004.826277","volume":"12","author":"S. Sen","year":"2003","unstructured":"Sen S., Wang J.: Analyzing peer-to-peer traffic across large networks. IEEE\/ACM Trans. Netw. 12(2), 219\u2013232 (2003)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"99_CR51","volume-title":"Scheduling and Load Balancing in Parallel and Distributed Systems","author":"B.A. Shirazi","year":"1995","unstructured":"Shirazi B.A., Kavi K.M., Hurson A.R.: Scheduling and Load Balancing in Parallel and Distributed Systems. IEEE Computer Science Press, Los Alamitos (1995)"},{"key":"99_CR52","unstructured":"Steiner, M., Biersack, E.W., Ennajjary, T.: Actively monitoring peers in KAD. In: Proceedings of the 6th International Workshop on Peer-to-Peer Systems (IPTPS) (2007)"},{"key":"99_CR53","doi-asserted-by":"crossref","unstructured":"Stutzbach, D., Rejaie, R.: Understanding churn in peer-to-peer networks. In: Proceedings of the 6th Internet Measurement Conference (IMC) (2006)","DOI":"10.1145\/1177080.1177105"},{"key":"99_CR54","unstructured":"Tian, J., Dai, Y.: Understanding the dynamic of peer-to-peer systems. In: Proceedings of the 6th International Workshop on Peer-to-Peer Systems (IPTPS) (2007)"},{"issue":"2","key":"99_CR55","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1145\/762483.762485","volume":"21","author":"R. Renesse Van","year":"2003","unstructured":"Van Renesse R., Birman K.P., Vogels W.: Astrolabe: a robust and scalable technology for distributed system monitoring, management, and data mining. ACM Trans. Comput. Syst. 21(2), 164\u2013206 (2003)","journal-title":"ACM Trans. Comput. Syst."},{"key":"99_CR56","doi-asserted-by":"crossref","unstructured":"Van Renesse, R., Bozdog, A.: Willow: DHT, aggregation, and publish\/subscribe in one protocol. In: Proceedings of the 3rd International Workshop on Peer-To-Peer Systems (IPTPS) (2004)","DOI":"10.1007\/978-3-540-30183-7_17"},{"key":"99_CR57","unstructured":"Yang, M., Chen, H., Zhao, B.Y., Dai, Y., Zhang, Z.: Deployment of a large scale peer-to-peer social network. In: Proceedings of the 1st Workshop on Real, Large Distributed Systems (2004)"},{"key":"99_CR58","unstructured":"Yusuke, K., Keiichi, K., Yuji, S.: Computing the diameter of the Pancake Graph. Joho Shori Gakkai Kenkyu Hokoku, 42 (2004)"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-010-0099-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-010-0099-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-010-0099-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,19]],"date-time":"2025-02-19T15:12:57Z","timestamp":1739977977000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-010-0099-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3,19]]},"references-count":58,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,5]]}},"alternative-id":["99"],"URL":"https:\/\/doi.org\/10.1007\/s00446-010-0099-z","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,3,19]]}}}