{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T13:11:12Z","timestamp":1791119472854,"version":"4.1.0"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2008,2,1]],"date-time":"2008-02-01T00:00:00Z","timestamp":1201824000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2009,8]]},"DOI":"10.1007\/s00224-008-9099-9","type":"journal-article","created":{"date-parts":[[2008,1,31]],"date-time":"2008-01-31T14:29:57Z","timestamp":1201789797000},"page":"234-260","source":"Crossref","is-referenced-by-count":51,"title":["Towards a Scalable and Robust DHT"],"prefix":"10.1007","volume":"45","author":[{"given":"Baruch","family":"Awerbuch","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian","family":"Scheideler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2008,2,1]]},"reference":[{"key":"9099_CR1","doi-asserted-by":"crossref","first-page":"808","DOI":"10.1137\/0216053","volume":"16","author":"H. Alt","year":"1987","unstructured":"Alt, H., Hagerup, T., Mehlhorn, K., Preparata, F.P.: Deterministic simulation of idealized parallel computers on more realistic ones. SIAM J.\u00a0Comput. 16, 808\u2013835 (1987)","journal-title":"SIAM J.\u00a0Comput."},{"key":"9099_CR2","unstructured":"Aspnes, J., Shah, G.: Skip graphs. In: Proc. of the 14th ACM Symp. on Discrete Algorithms (SODA), pp. 384\u2013393 (2003)"},{"key":"9099_CR3","unstructured":"Awerbuch, B., Scheideler, C.: Group spreading: A protocol for provably secure distributed name service. In: Proc. of the 31st International Colloquium on Automata, Languages and Programming (ICALP), 2004"},{"key":"9099_CR4","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Scheideler, C.: Robust random number generation for peer-to-peer systems. In: 10th Int. Conference on Principles of Distributed Systems (OPODIS), pp. 275\u2013289 (2006)","DOI":"10.1007\/11945529_20"},{"key":"9099_CR5","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(85)90008-X","volume":"30","author":"A. Borodin","year":"1985","unstructured":"Borodin, A., Hopcroft, J.E.: Routing, merging, and sorting on parallel models of computation. J.\u00a0Comput. Syst. Sci. 30, 130\u2013145 (1985)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9099_CR6","doi-asserted-by":"crossref","unstructured":"Castro, M., Druschel, P., Ganesh, A., Rowstron, A., Wallach, D.: Security for structured peer-to-peer overlay networks. In: Proc. of the 5th Usenix Symp. on Operating Systems Design and Implementation (OSDI), 2002","DOI":"10.1145\/1060289.1060317"},{"key":"9099_CR7","unstructured":"Castro, M., Liskov, B.: Practical Byzantine fault tolerance. In: Proc. of the 2nd Usenix Symp. on Operating Systems Design and Implementation (OSDI), 1999"},{"key":"9099_CR8","unstructured":"Crosby, S., Wallach, D.: Denial of service via algorithmic complexity attacks. In: Usenix Security, 2003"},{"key":"9099_CR9","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Meyer auf der Heide, F.: Simple, efficient shared memory simulations. In: Proc. of the 5 ACM Symp. on Parallel Algorithms and Architectures (SPAA), pp. 110\u2013119 (1993)","DOI":"10.1145\/165231.165246"},{"key":"9099_CR10","doi-asserted-by":"crossref","unstructured":"Douceur, J.R.: The Sybil attack. In: Proc. of the 1st International Workshop on Peer-to-Peer Systems (IPTPS), 2002","DOI":"10.1007\/3-540-45748-8_24"},{"key":"9099_CR11","unstructured":"Druschel, P., Rowstron, A.: Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In: Proc. of the 18th IFIP\/ACM International Conference on Distributed Systems Platforms (Middleware 2001), 2001"},{"key":"9099_CR12","unstructured":"Dubhashi, D., Panconesi, A.: Concentration of measure for the analysis of randomized algorithms. Unpublished manuscript, accessible via http:\/\/www.cs.unibo.it\/~pancones\/papers.html (20 October 1998)"},{"key":"9099_CR13","unstructured":"Fiat, A., Saia, J., Young, M.: Making chord robust to Byzantine attacks. In: Proc. of the European Symposium on Algorithms (ESA), 2005"},{"key":"9099_CR14","doi-asserted-by":"crossref","unstructured":"Gennaro, R., Ishai, Y., Kushilevitz, E., Rabin, T.: The round complexity of verifiable secret sharing and secure multicast. In: Proc. of the 33rd ACM Symp. on Theory of Computing (STOC), pp. 580\u2013589 (2001)","DOI":"10.1145\/380752.380853"},{"key":"9099_CR15","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1137\/S0097539789164765","volume":"23","author":"K.T. Herley","year":"1994","unstructured":"Herley, K.T., Bilardi, G.: Deterministic simulations of PRAMs on bounded degree networks. SIAM J.\u00a0Comput. 23, 276\u2013292 (1994)","journal-title":"SIAM J.\u00a0Comput."},{"key":"9099_CR16","doi-asserted-by":"crossref","unstructured":"Karger, D., Lehman, E., Leighton, T., Levine, M., Lewin, D., Panigrahi, R.: Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web. In: Proc. of the 29th ACM Symp. on Theory of Computing (STOC), pp. 654\u2013663 (1997)","DOI":"10.1145\/258533.258660"},{"key":"9099_CR17","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Schmid, S., Wattenhofer, R.: A self-repairing peer-to-peer system resilient to dynamic adversarial churn. In: Proc. of the 4th International Workshop on Peer-to-Peer Systems (IPTPS), 2005","DOI":"10.1007\/11558989_2"},{"key":"9099_CR18","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1007\/BF01840402","volume":"5","author":"F. Luccio","year":"1990","unstructured":"Luccio, F., Pietracaprina, A., Pucci, G.: A new scheme for the deterministic simulation of PRAMs in VLSI. Algorithmica 5, 529\u2013544 (1990)","journal-title":"Algorithmica"},{"key":"9099_CR19","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/978-3-662-12788-9_6","volume-title":"Probabilistic Methods for Algorithmic Discrete Mathematics","author":"A. McDiarmid","year":"1998","unstructured":"McDiarmid, A.: Concentration. In: Habib, M., McDiarmid, C., Ramirez-Alfonsin, J., Reed, B. (eds.) Probabilistic Methods for Algorithmic Discrete Mathematics, pp. 195\u2013247. Springer, Berlin (1998)"},{"key":"9099_CR20","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/BF00264615","volume":"21","author":"K. Mehlhorn","year":"1984","unstructured":"Mehlhorn, K., Vishkin, U.: Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories. Acta Inf. 21, 339\u2013374 (1984)","journal-title":"Acta Inf."},{"key":"9099_CR21","unstructured":"Naor, M., Wieder, U.: Novel architectures for P2P applications: the continuous-discrete approach. In: Proc. of the 15th ACM Symp. on Parallel Algorithms and Architectures (SPAA), 2003"},{"key":"9099_CR22","unstructured":"Nielson, S., Crosby, S., Wallach, D.: Kill the messenger: A taxonomy of rational attacks. In: Proc. of the 4th International Workshop on Peer-to-Peer Systems (IPTPS), 2005"},{"key":"9099_CR23","doi-asserted-by":"crossref","unstructured":"Padmanabhan, V.N., Sripanidkulchai, K.: The case for cooperative networking. In: Proc. of the 1st International Workshop on Peer-to-Peer Systems (IPTPS), 2002","DOI":"10.1007\/3-540-45748-8_17"},{"key":"9099_CR24","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1016\/j.jalgor.2003.12.002","volume":"51","author":"R. Pagh","year":"2004","unstructured":"Pagh, R., Rodler, F.: Cuckoo hashing. J.\u00a0Algorithms 51, 122\u2013144 (2004)","journal-title":"J.\u00a0Algorithms"},{"key":"9099_CR25","doi-asserted-by":"crossref","unstructured":"Plaxton, G., Rajaraman, R., Richa, A.W.: Accessing nearby copies of replicated objects in a distributed environment. In: Proc. of the 9th ACM Symp. on Parallel Algorithms and Architectures (SPAA), pp. 311\u2013320 (1997)","DOI":"10.1145\/258492.258523"},{"key":"9099_CR26","doi-asserted-by":"crossref","unstructured":"Ratnasamy, S., Francis, P., Handley, M., Karp, R., Shenker, S.: A scalable content-addressable network. In: Proc. of the ACM SIGCOMM \u201901, 2001","DOI":"10.1145\/383059.383072"},{"key":"9099_CR27","unstructured":"Rhea, S., Geels, D., Roscoe, T., Kubiatowicz, J.: Handling churn in a DHT. In: USENIX Annual Technical Conference, 2004"},{"key":"9099_CR28","doi-asserted-by":"crossref","unstructured":"Saia, J., Fiat, A., Gribble, S., Karlin, A., Saroiu, S.: Dynamically fault-tolerant content addressable networks. In: Proc. of the 1st International Workshop on Peer-to-Peer Systems (IPTPS), 2002","DOI":"10.1007\/3-540-45748-8_26"},{"key":"9099_CR29","doi-asserted-by":"crossref","unstructured":"Scheideler, C.: How to spread adversarial nodes? Rotate! In: Proc. of the 37th ACM Symp. on Theory of Computing (STOC), pp. 704\u2013713 (2005)","DOI":"10.1145\/1060590.1060694"},{"key":"9099_CR30","doi-asserted-by":"crossref","unstructured":"Singh, A., Castro, M., Rowstron, A., Druschel, P.: Defending against Eclipse attacks on overlay networks. In: Proc. of the 11th ACM SIGOPS European Workshop, 2004","DOI":"10.1145\/1133572.1133613"},{"key":"9099_CR31","doi-asserted-by":"crossref","unstructured":"Sit, E., Morris, R.: Security considerations for peer-to-peer distributed hash tables. In: Proc. of 1st International Workshop on Peer-to-Peer Systems (IPTPS), 2002","DOI":"10.1007\/3-540-45748-8_25"},{"key":"9099_CR32","doi-asserted-by":"crossref","unstructured":"Srivatsa, M., Liu, L.: Vulnerabilities and security threats in structured overlay networks: A quantitative analysis. In: Proc. of the 20th IEEE Computer Security Applications Conference (ACSAC), 2004","DOI":"10.1109\/CSAC.2004.50"},{"key":"9099_CR33","doi-asserted-by":"crossref","unstructured":"Stading, T., Maniatis, P., Baker, M.: Peer-to-peer caching schemes to address flash crowds. In: Proc. of the 1st International Workshop on Peer-to-Peer Systems (IPTPS), 2002","DOI":"10.1007\/3-540-45748-8_19"},{"key":"9099_CR34","unstructured":"Stavron, A., Rubenstein, D., Sahn, S.: A lightweight robust P2P system to handle flash crowds. In: Proc. of the IEEE Int. Conf. on Network Protocols (ICNP), 2002"},{"key":"9099_CR35","unstructured":"Stoica, I., Morris, R., Karger, D., Kaashoek, M.F., Balakrishnan, H.: Chord: A scalable peer-to-peer lookup service for Internet applications. In: Proc. of the ACM SIGCOMM \u201901, 2001; see also http:\/\/www.pdos.lcs.mit.edu\/chord\/"},{"key":"9099_CR36","first-page":"116","volume":"34","author":"E. Upfal","year":"1987","unstructured":"Upfal, E., Wigderson, A.: How to share memory in a distributed system. J.\u00a0ACM 34, 116\u2013127 (1987)","journal-title":"J.\u00a0ACM"},{"issue":"11","key":"9099_CR37","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1137\/0211027","volume":"2","author":"L.G. Valiant","year":"1982","unstructured":"Valiant, L.G.: A scheme for fast parallel communication. SIAM J.\u00a0Comput. 2(11), 350\u2013361 (1982)","journal-title":"SIAM J.\u00a0Comput."},{"key":"9099_CR38","unstructured":"Zhao, B.Y., Kubiatowicz, J., Joseph, A.: Tapestry: An infrastructure for fault-tolerant wide-area location and routing. Technical report, UCB\/CSD-01-1141, University of California at Berkeley (2001); see also http:\/\/www.cs.berkeley.edu\/~ravenben\/tapestry"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9099-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-008-9099-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9099-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:51:35Z","timestamp":1558684295000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-008-9099-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,2,1]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["9099"],"URL":"https:\/\/doi.org\/10.1007\/s00224-008-9099-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,2,1]]}}}