Object location in realistic networks

ABSTRACT

We devise an object location scheme that achieves a guaranteed low stretch in a wider and more realistic class of networks than previous schemes. The distinctive feature of our scheme is that it is inherently adaptive to the underlying topology. In particular, the system achieves 1+ε stretch (for arbitrarily fixed ε>0), with a neighbor list size that depends on the local density around the node (but not on the global growth rate bound). As a byproduct, our scheme has several advantages over existing ones, such as robustness to errors in network measurements, and simpler design choices of system builders, which may lead to improved and more robust deployments.

REFERENCES

• 1: Ittai Abraham , Dahlia Malkhi , Oren Dobzinski, LAND: stretch (1 + ε) locality-aware networks for DHTs, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 2: Marta Arias , Lenore J. Cowen , Kofi A. Laing, Compact roundtrip routing with topology-independent node names, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.43-52, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872042]
• 3: Marta Arias , Lenore J. Cowen , Kofi A. Laing , Rajmohan Rajaraman , Orjeta Taka, Compact routing with name independence, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777442]
• 4: Baruch Awerbuch , David Peleg, Concurrent online tracking of mobile users, Proceedings of the conference on Communications architecture & protocols, p.221-233, September 03-06, 1991, Zurich, Switzerland
• 5: Frank Dabek , M. Frans Kaashoek , David Karger , Robert Morris , Ion Stoica, Wide-area cooperative storage with CFS, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 6: F. Dabek, J. Li, E. Sit, J. Robertson, M. F. Kaashoek, and R. Morris. Designing a dht for low latency and high throughput. In Proceedings of the First Symposium on Networked Systems Design and Implementation, pages 85--98, Mar. 2004.
• 7: F. Dabek, B. Zhao, P. Druschel, J. Kubiatowicz, and I. . Stoica. Towards a common API for structured P2P overlays. In Proceedings of IPTPS, pages 33--44, 2003.
• 8: C. Gkantsidis, M. Mihail, and A. Saberi. Random walks in peer-to-peer networks. In Proceedings of IEEE INFOCOM, 2004.
• 9: K. Gummadi , R. Gummadi , S. Gribble , S. Ratnasamy , S. Shenker , I. Stoica, The impact of DHT routing geometry on resilience and proximity, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863998]
• 10: K. Hildrum and J. Kubiatowicz. Asymptotically efficient approaches to fault-tolerance in peer-to-peer networks. In 17th International Symposium on Distributed Computing, pages 321--336, 2003.
• 11: Kirsten Hildrum , John Kubiatowicz , Sean Ma , Satish Rao, A note on the nearest neighbor in growth-restricted metrics, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 12: K. Hildrum, J. Kubiatowicz, and S. Rao. Another way to find the nearest neighbor in growth-restricted metrics. Technical Report UCB/CSD-03-1267, UC Berkeley, 2003.
• 13: Kirsten Hildrum , John D. Kubiatowicz , Satish Rao , Ben Y. Zhao, Distributed object location in a dynamic network, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564877]
• 14: R. Huebsch, J. M. Hellerstein, N. L. Boon, T. Loo, S. Shenker, and I. Stoica. Querying the internet with pier. In Proceedings of 19th International Conference on Very Large Databases (VLDB), Sept. 2003.
• 15: David R. Karger , Matthias Ruhl, Finding nearest neighbors in growth-restricted metrics, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510013]
• 16: R. Krauthgamer and J. R. Lee. The black-box complexity of nearest neighbor search. In 31st International Colloquium on Automata, Languages and Programming. July 2004. To appear.
• 17: Robert Krauthgamer , James R. Lee, Navigating nets: simple algorithms for proximity search, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 18: John Kubiatowicz , David Bindel , Yan Chen , Steven Czerwinski , Patrick Eaton , Dennis Geels , Ramakrishna Gummadi , Sean Rhea , Hakim Weatherspoon , Chris Wells , Ben Zhao, OceanStore: an architecture for global-scale persistent storage, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.190-201, November 2000, Cambridge, Massachusetts, United States
• 19: C. Law and K.-Y. Siu. Distributed construction of random expander networks. In Proceedings of IEEE INFOCOM, 2003.
• 20: Xiaozhou Li , C. Greg Plaxton, On name resolution in peer-to-peer networks, Proceedings of the second ACM international workshop on Principles of mobile computing, October 30-31, 2002, Toulouse, France [doi>10.1145/584490.584507]
• 21: C. G. Plaxton, R. Rajaraman, and A. W. Richa. Accessing nearby copies of replicated objects in a distributed environment. Theory of Computing Systems, 32:241--280, 1999.
• 22: Rajmohan Rajaraman , Andreáa W. Richa , Berthold Vöcking , Gayathri Vuppuluri, A data tracking scheme for general networks, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.247-254, July 2001, Crete Island, Greece [doi>10.1145/378580.378670]
• 23: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 24: S. Rhea, D. Geels, T. Roscoe, and J. Kubiatowicz. Handling churn in a DHT. To appear in USENIX '04 Annual Technical Conference.
• 25: S. Rhea, D. Geels, T. Roscoe, and J. Kubiatowicz. Handling churn in a DHT. Technical Report UCB//CSD-03-1299, UC Berkeley, 2003.
• 26: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 27: Antony Rowstron , Peter Druschel, Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 28: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 29: Mikkel Thorup , Uri Zwick, Approximate distance oracles, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.183-192, July 2001, Hersonissos, Greece [doi>10.1145/380752.380798]
• 30: E. W. Zegura, K. L. Calvert, and S. Bhattacharjee. How to model an internetwork. In Proceedings of IEEE INFOCOM, pages 594--602, 1996.
• 31: B. Y. Zhao, L. Huang, S. C. Rhea, J. Stribling, A. D. Joseph, and J. Kubiatowicz. Tapestry: A global-scale overlay for rapid service deployment. IEEE Journal on Selected Areas in Communications, 2003. Special Issue on Service Overlay Networks, to appear.
• 32: Ben Y. Zhao , John D. Kubiatowicz , Anthony D. Joseph, Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and, University of California at Berkeley, Berkeley, CA, 2001

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Theory

Keywords:
DHT, DOLR, distributed hash table, distributed object location, locality, networking, overlay, peer-o-peer