Abstract
High scalability in Peer-to-Peer (P2P) systems has been achieved with the emergence of the networks based on Distributed Hash Table (DHT). Most of the DHTs can be regarded as exponential networks. Their network size evolves exponentially while the minimal distance between two nodes as well as the routing table size, i.e., the degree, at each node evolve linearly or remain constant. In this paper we present a model to better characterize most of the current logarithmic-degree DHTs. We express them in terms of absolute and relative exponential structured networks. In relative exponential networks, such as Chord, where all nodes are reachable in at most H hops, the number of paths of length inferior or equal to H between two nodes grows exponentially with the network size. We propose the Tango approach to reduce this redundancy and to improve other properties such as reducing the lookup path length. We analyze Tango and show that it is more scalable than the current logarithmic-degree DHTs. Given its scalability and structuring flexibility, we chose Tango to be the algorithm underlying our P2P middleware.
This work was funded at CETIC (www.cetic.be) by the Walloon Region (DGTRE) and the E.U. (ERDF and ESF), and at UCL by the Information Society Technologies programme of the European Commission, Future and Emerging Technologies under IST-2001-33234 PEPITO.
Chapter PDF
Similar content being viewed by others
References
Stoica, I., Morris, R., Karger, D., Kaashoek, F., Balakrishnan, H.: Chord: A Scalable Peer- To-Peer Lookup Service for Internet Applications. In: ACM SIGCOMM (August 2001)
Rowstron, A., Druschel, P.: Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems. In: ICDSP (November 2001)
Zhao, B., Kubiatowicz, J., Joseph, A.: Tapestry: An Infrastructure for Fault-tolerantWidearea Location and Routing. Technical Report CSD-011141, U.C. Berkeley (April 2001)
Kaashoek, F., Karger, D.: Koorde: A Simple Degree-optimal Hash Table. In: Kaashoek, M.F., Stoica, I. (eds.) IPTPS 2003. LNCS, vol. 2735, Springer, Heidelberg (2003)
Naor, M., Wieder, U.: Novel Architectures for P2P Applications: the Continous-Discrete Approach. In: ACM SPAA (June 2003)
El-Ansary, S., Onana, L., et al.: A Framework for Peer-to-Peer Lookup Services based on k-ary Search. Technical Report TR-2002-06, SICS (May 2002)
Onana, L., El-Ansary, S., et al.: DKS(N, k, f): A Family of Low Communication, Scalable and Fault-Tolerant Infrastructures for P2P Applications. In: CCGRID 2003 (May 2003)
Carton, B., Mesaros, V., Van Roy, P.: Improving the Scalability of Logarithmic-Degree Peer-to-Peer Networks. Technical Report RR-2004-01, UC-Louvain (January 2004)
Loguinov, D., Kumar, A., et al.: Graph-Theoretic Analysis of Structured Peer-to-Peer Systems: Routing Distances and Fault Resilience. In: SIGCOMM (August 2003)
P2PS v 1.0, Peer-to-Peer System Library, Universtité catholique de Louvain, and CETIC, Belgium (October 2003), http://www.mozart-oz.org/mogul/info/cetic_ucl/p2ps.html
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Carton, B., Mesaros, V. (2004). Improving the Scalability of Logarithmic-Degree DHT-Based Peer-to-Peer Networks. In: Danelutto, M., Vanneschi, M., Laforenza, D. (eds) Euro-Par 2004 Parallel Processing. Euro-Par 2004. Lecture Notes in Computer Science, vol 3149. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27866-5_143
Download citation
DOI: https://doi.org/10.1007/978-3-540-27866-5_143
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22924-7
Online ISBN: 978-3-540-27866-5
eBook Packages: Springer Book Archive