Novel architectures for P2P applications: the continuous-discrete approach

ABSTRACT

We propose a new approach for constructing P2P networks based on a dynamic decomposition of a continuous space into cells corresponding to processors. We demonstrate the power of these design rules by suggesting two new architectures, one for DHT (Distributed Hash Table) and the other for dynamic expander networks. The DHT network, which we call Distance Halving allows logarithmic routing and load, while preserving constant degrees. It offers an optimal tradeoff between the degree and the dilation in the sense that degree d guarantees a dilation of O(log _d 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 faults. Finally we show that, using our approach, it is possible to construct any family of constant degree graphs in a dynamic environment, though with worst parameters. Therefore we expect that more distributed data structures could be designed and implemented in a dynamic environment.

REFERENCES

• 1: William Aiello , Baruch Awerbuch , Bruce Maggs , Satish Rao, Approximate load balancing on dynamic and asynchronous networks, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.632-641, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167250]
• 2: N. Alon and J. H. Spencer. The Probabilistic Method. John Wiley & Sons, 2000.
• 3: A. Chankhunthod, P. B. Danzig, C. Neerdaels, M. F. Schwartz, and K. J. Worrell. A hierarchical Internet object cache. In Proceedings of the USENIX 1996 annual technical conference, pages 153--163.
• 4: Edith Cohen , Haim Kaplan, Balanced-Replication Algorithms for Distribution Trees, Proceedings of the 10th Annual European Symposium on Algorithms, p.297-309, September 17-21, 2002
• 5: Emma Brunskill, Building Peer-to-Peer Systems with Chord, a Distributed Lookup Service, Proceedings of the Eighth Workshop on Hot Topics in Operating Systems, p.81, May 20-22, 2001
• 6: P. Fraigniaud and P. Gauron. The content-addressable network d2b. Technical Report LRI 1349, Univ. Paris-Sud, 2003.
• 7: O. Gabber and Z. Galil. Explicit construction of linear-sized superconcentrators. Journal of Computer and System Science, 22:407--420, 1981.
• 8: F. Kaashoek and D. Karger. Koorde, a simple degree-optimal hash table. In 2nd International Workshop on Peer-to-Peer Systems (IPTPS), 2003.
• 9: David Karger , Eric Lehman , Tom Leighton , Rina Panigrahy , Matthew Levine , Daniel Lewin, Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.654-663, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258660]
• 10: Jon Kleinberg, The small-world phenomenon: an algorithm perspective, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.163-170, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335325]
• 11: Richard R. Koch , F. T. Leighton , Bruce M. Maggs , Satish B. Rao , Arnold L. Rosenberg , Eric J. Schwabe, Work-preserving emulations of fixed-connection networks, Journal of the ACM (JACM), v.44 n.1, p.104-147, Jan. 1997 [doi>10.1145/256292.256299]
• 12: Ching Law and Kai-Yeung Siu. Distributed construction of random expander graphs. In INFOCOM, 2003.
• 13: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 14: David Liben-Nowell , Hari Balakrishnan , David Karger, Analysis of the evolution of peer-to-peer systems, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571863]
• 15: Bruce M. Maggs , Eric J. Schwabe, Real-time emulations of bounded-degree networks, Information Processing Letters, v.66 n.5, p.269-276, June 16, 1998 [doi>10.1016/S0020-0190(98)00064-7 ]
• 16: Dahlia Malkhi , Moni Naor , David Ratajczak, Viceroy: a scalable and dynamic emulation of the butterfly, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571857]
• 17: Dahlia Malkhi , Michael Reiter , Rebecca Wright, Probabilistic quorum systems, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.267-273, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259458]
• 18: G. A. Margulis. Explicit constructions of concentrators. Problemy Peredachi Informatsii, (9(4)):325--332, 1973.
• 19: M. Mitzenmacher, A. Richa, and R. Sitaraman. The power of two random choices: A survey of the techniques and results. In Handbook of Randomized Computing. P. Pardalos, S. Rajasekaran, J. Rolim, and Eds. Kluwer, editors, 2000.
• 20: Moni Naor , Udi Wieder, Scalable and dynamic quorum systems, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.114-122, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872052]
• 21: M. Naor and U. Wieder. A simple fault tolerant distributed hash table. In Second International Workshop on Peer-to-Peer Systems, February 2003.
• 22: Atsuyuki Okabe , Barry Boots , Kokichi Sugihara, Spatial tessellations: concepts and applications of Voronoi diagrams, John Wiley & Sons, Inc., New York, NY, 1992
• 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: Sylvia Ratnasamy , Ion Stoica , Scott Shenker, Routing Algorithms for DHTs: Some Open Questions, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.45-52, March 07-08, 2002
• 25: 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
• 26: 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
• 27: L. G. Valiant. A scheme for fast parallel communication. SIAM Journal on Computing, 11(2):350--361, 1982.
• 28: 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:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Algorithms

Keywords:
distributed systems, fault tolerance, hash tables, peer-to-peer