{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:10:08Z","timestamp":1763467808401,"version":"3.41.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2007,8,1]],"date-time":"2007-08-01T00:00:00Z","timestamp":1185926400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2007,8]]},"abstract":"<jats:p>\n            We propose a new approach for constructing P2P networks based on a dynamic decomposition of a continuous space into cells corresponding to servers. We demonstrate the power of this approach by suggesting two new P2P architectures and various algorithms for them. The first serves as a DHT (distributed hash table) and the other is a dynamic expander network. The DHT network, which we call Distance Halving, allows logarithmic routing and load while preserving constant degrees. It offers an optimal tradeoff between degree and path length in the sense that degree\n            <jats:italic>d<\/jats:italic>\n            guarantees a path length of\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sub>\n              <jats:italic>d<\/jats:italic>\n            <\/jats:sub>\n            <jats:italic>n<\/jats:italic>\n            ). Another advantage over previous constructions is its relative simplicity. A major new contribution of this construction is a dynamic caching technique that maintains low load and storage, even under the occurrence of hot spots. Our second construction builds a network that is guaranteed to be an expander. The resulting topologies are simple to maintain and implement. Their simplicity makes it easy to modify and add protocols. A small variation yields a DHT which is robust against random Byzantine faults. Finally we show that, using our approach, it is possible to construct\n            <jats:italic>any<\/jats:italic>\n            family of constant degree graphs in a dynamic environment, though with worse parameters. Therefore, we expect that more distributed data structures could be designed and implemented in a dynamic environment.\n          <\/jats:p>","DOI":"10.1145\/1273340.1273350","type":"journal-article","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T13:44:55Z","timestamp":1189777495000},"page":"34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":52,"title":["Novel architectures for P2P applications"],"prefix":"10.1145","volume":"3","author":[{"given":"Moni","family":"Naor","sequence":"first","affiliation":[{"name":"The Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Udi","family":"Wieder","sequence":"additional","affiliation":[{"name":"Microsoft Research, Mountain View, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,8]]},"reference":[{"volume-title":"Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS). 40","author":"Abraham I.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167250"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Alon N. and Spencer J. H. 2000. The Probabilistic Method 2nd ed. John Wiley &amp; Sons.  Alon N. and Spencer J. H. 2000. The Probabilistic Method 2nd ed. John Wiley &amp; Sons.","DOI":"10.1002\/0471722154"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073970.1073989"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/285237.285258"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-002-1017-y"},{"volume-title":"Proceedings of the USENIX Annual Technical Conference. 153--163","author":"Chankhunthod A.","key":"e_1_2_1_7_1"},{"volume-title":"Proceedings of the European Symposium on Algorithms (ESA). 297--309","author":"Cohen E.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010030"},{"key":"e_1_2_1_10_1","unstructured":"Dubhashi D. P. and Panconesi A. 2005. Concentration of Measure for the Analysis of Randomised Algorithms. Book draft.  Dubhashi D. P. and Panconesi A. 2005. Concentration of Measure for the Analysis of Randomised Algorithms. Book draft."},{"volume-title":"Proceedings of the Symposium on Discrete Algorithms (SODA). 94--103","author":"Fiat A.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872056"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780646"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90040-4"},{"volume-title":"Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM).","author":"Gkantsidis C.","key":"e_1_2_1_15_1"},{"volume-title":"Proceedings of the International Symposium on Distributed Computing (DISC). 321--336","author":"Hildrum K.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2003.08.011"},{"volume-title":"Proceedings of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS). 98--107","author":"Kaashoek M. F.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258660"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007912.1007919"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073970.1073990"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335325"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/256292.256299"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1155\/S1073792803130383"},{"volume-title":"Proceedings of the Annual Joint Conference of the IEEE Computer Communications Societies (INFOCOM).","author":"Law C.","key":"e_1_2_1_25_1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Leighton F. T. 1992. Introduction to Parallel Algorithms and Architectures: Arrays Trees Hypercubes. Morgan Kaufmann San Mateo CA.   Leighton F. T. 1992. Introduction to Parallel Algorithms and Architectures: Arrays Trees Hypercubes. Morgan Kaufmann San Mateo CA.","DOI":"10.1016\/B978-1-4832-0772-8.50005-4"},{"volume-title":"Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS). 384--389","author":"Leighton F. T.","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00064-7"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/571825.571857"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011797"},{"key":"e_1_2_1_31_1","first-page":"4","article-title":"Explicit constructions of concentrators","volume":"9","author":"Margulis G. A.","year":"1973","journal-title":"Problemy Peredachi Inf."},{"volume-title":"Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS). 53--65","author":"Maymounkov P.","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Mitzenmacher M. Richa A. and Sitaraman R. 2000. The power of two random choices: A survey of the techniques and results. In Handbook of Randomized Computing P. Pardalos et al. eds. Kluwer Hingham MA.  Mitzenmacher M. Richa A. and Sitaraman R. 2000. The power of two random choices: A survey of the techniques and results. In Handbook of Randomized Computing P. Pardalos et al. eds. Kluwer Hingham MA.","DOI":"10.1007\/978-1-4615-0013-1_9"},{"volume-title":"Proceedings of the International Symposium on Distributed Computing (DISC). 390--404","author":"Nadav U.","key":"e_1_2_1_34_1"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-004-0114-3"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/777412.777421"},{"volume-title":"Proceedings of the 2nd International Workshop on Peer-to-Peer Systems. 88--97","author":"Naor M.","key":"e_1_2_1_37_1"},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Okabe A. Boots B. Sugihara K. and Chiu S. N. 2000. Spatial Tessellations---Concepts and Applications of Voronoi Diagrams 2nd ed. Wiley Chichester UK.   Okabe A. Boots B. Sugihara K. and Chiu S. N. 2000. Spatial Tessellations---Concepts and Applications of Voronoi Diagrams 2nd ed. Wiley Chichester UK.","DOI":"10.1002\/9780470317013"},{"volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science. 570--579","author":"Plaxton C. G.","key":"e_1_2_1_39_1"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90005-P"},{"volume-title":"Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS). 45--52","author":"Ratnasamy S.","key":"e_1_2_1_41_1"},{"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.5555\/646591.697650"},{"volume-title":"Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS). 270--279","author":"Saia J.","key":"e_1_2_1_44_1"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/383059.383071"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211027"},{"volume-title":"Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS). 328--338","author":"Weatherspoon H.","key":"e_1_2_1_47_1"},{"volume-title":"Tapestry: An infrastructure for fault-tolerant wide-area location and routing. Tech. Rep. UCB CSD 01-1141","year":"2001","author":"Zhao B. Y.","key":"e_1_2_1_48_1"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1273340.1273350","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1273340.1273350","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:57:55Z","timestamp":1750258675000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1273340.1273350"}},"subtitle":["The continuous-discrete approach"],"short-title":[],"issued":{"date-parts":[[2007,8]]},"references-count":48,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,8]]}},"alternative-id":["10.1145\/1273340.1273350"],"URL":"https:\/\/doi.org\/10.1145\/1273340.1273350","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2007,8]]},"assertion":[{"value":"2007-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}