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 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 d guarantees a path length 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 Byzantine 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 worse parameters. Therefore, we expect that more distributed data structures could be designed and implemented in a dynamic environment.

REFERENCES

• 1: Ittai Abraham , Baruch Awerbuch , Yossi Azar , Yair Bartal , Dahlia Malkhi , Elan Pavlov, A Generic Scheme for Building Overlay Networks in Adversarial Scenarios, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.40.2, April 22-26, 2003
• 2: 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]
• 3: Alon, N., and Spencer, J. H. 2000. The Probabilistic Method, 2nd ed. John Wiley & Sons.
• 4: James Aspnes , Udi Wieder, The expansion and mixing time of skip graphs with applications, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073989]
• 5: John W. Byers , Michael Luby , Michael Mitzenmacher , Ashutosh Rege, A digital fountain approach to reliable distribution of bulk data, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.56-67, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 6: Cai, J. 2003. Essentially every unimodular matrix defines an expander. Theory Comput. Syst. 36, 2, 105--135.
• 7: Anawat Chankhunthod , Peter B. Danzig , Chuck Neerdaels , Michael F. Schwartz , Kurt J. Worrell, A hierarchical internet object cache, Proceedings of the 1996 annual conference on USENIX Annual Technical Conference, p.13-13, January 22-26, 1996, San Diego, CA
• 8: 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
• 9: Diks, K., and Pelc, A. 2000. Optimal adaptive broadcasting with a bounded fraction of faulty nodes. Algorithmica 28, 1, 36--50.
• 10: Dubhashi, D. P., and Panconesi, A. 2005. Concentration of Measure for the Analysis of Randomised Algorithms. Book draft.
• 11: Amos Fiat , Jared Saia, Censorship resistant peer-to-peer content addressable networks, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.94-103, January 06-08, 2002, San Francisco, California
• 12: Pierre Fraigniaud , Philippe Gauron, Brief announcement: an overview of the content-addressable network D2B, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.151-151, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872056]
• 13: Joel Friedman, A proof of alon's second eigenvalue conjecture, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780646]
• 14: Gabber, O., and Galil, Z. 1981. Explicit construction of linear-sized superconcentrators. J. Comput. Syst. Sci. 22, 407--420.
• 15: Gkantsidis, C., Mihail, M., and Saberi, A. 2004. Random walks in peer-to-peer networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM).
• 16: Hildrum, K., and Kubiatowicz, J. 2003. Asymptotically efficient approaches to fault-tolerance in peer-to-peer networks. In Proceedings of the International Symposium on Distributed Computing (DISC). 321--336.
• 17: Keren Horowitz , Dahlia Malkhi, Estimating network size from local information, Information Processing Letters, v.88 n.5, p.237-243, 16 December 2003 [doi>10.1016/j.ipl.2003.08.011]
• 18: Kaashoek, M. F., and Karger, D. R. 2003. Koorde: A simple degree-optimal distributed hash table. In Proceedings of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS). 98--107.
• 19: 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]
• 20: David R. Karger , Matthias Ruhl, Simple efficient load balancing algorithms for peer-to-peer systems, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007919]
• 21: Krishnaram Kenthapadi , Gurmeet Singh Manku, Decentralized algorithms using both local and random probes for P2P load balancing, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073990]
• 22: 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]
• 23: 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]
• 24: Larsen, M. 2003. Navigating the Cayley graph of SL₂(F_p). Int. Math. Res. Not. 27, 1465--1471.
• 25: Law, C., and Siu, K.-Y. 2003. Distributed construction of random expander graphs. In Proceedings of the Annual Joint Conference of the IEEE Computer Communications Societies (INFOCOM).
• 26: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 27: Leighton, F. T., and Maggs, B. 1989. Expanders might be practical: Fast algorithms for routing around faults in multibutterflies. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS). 384--389.
• 28: 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]
• 29: 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]
• 30: Gurmeet Singh Manku, Balanced binary trees for ID management and load balance in distributed hash tables, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011797]
• 31: Margulis, G. A. 1973. Explicit constructions of concentrators. Problemy Peredachi Inf. 9, 4 (Oct.-Dec.).
• 32: Petar Maymounkov , David Mazières, Kademlia: A Peer-to-Peer Information System Based on the XOR Metric, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.53-65, March 07-08, 2002
• 33: 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.
• 34: Nadav, U., and Naor, M. 2004. Fault-Tolerant storage in a dynamic environment. In Proceedings of the International Symposium on Distributed Computing (DISC). 390--404.
• 35: Moni Naor , Udi Wieder, Scalable and dynamic quorum systems, Distributed Computing, v.17 n.4, p.311-322, May 2005 [doi>10.1007/s00446-004-0114-3]
• 36: Moni Naor , Udi Wieder, Novel architectures for P2P applications: the continuous-discrete approach, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777421]
• 37: Naor, M., and Wieder, U. 2003b. A simple fault tolerant distributed hash table. In Proceedings of the 2nd International Workshop on Peer-to-Peer Systems. 88--97.
• 38: Atsuyuki Okabe , Barry Boots , Kokichi Sugihara, Spatial tessellations: concepts and applications of Voronoi diagrams, John Wiley & Sons, Inc., New York, NY, 1992
• 39: C. G. Plaxton , R. Rajaraman, Fast fault-tolerant concurrent access to shared objects, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.570, October 14-16, 1996
• 40: Abhiram G. Ranade, How to emulate shared memory, Journal of Computer and System Sciences, v.42 n.3, p.307-326, June 1991 [doi>10.1016/0022-0000(91)90005-P]
• 41: 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
• 42: 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
• 43: 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
• 44: Jared Saia , Amos Fiat , Steven D. Gribble , Anna R. Karlin , Stefan Saroiu, Dynamically Fault-Tolerant Content Addressable Networks, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.270-279, March 07-08, 2002
• 45: 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
• 46: Valiant, L. G. 1982. A scheme for fast parallel communication. SIAM J. Comput. 11, 2 (May), 350--361.
• 47: Hakim Weatherspoon , John Kubiatowicz, Erasure Coding Vs. Replication: A Quantitative Comparison, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.328-338, March 07-08, 2002
• 48: 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
      C.2.4 Distributed Systems

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES

Keywords:
Peer-to-peer networks, routing