Abstract
A well-known problem found in peer-to-peer systems is how to efficiently and scalably locate the peer that stores a particular data item. In a typical formulation of the problem solution, each data item is mapped to a key; every peer stores data items corresponding to a contiguous range of keys, and locating an item requires identifying the host that holds that item’s key. Here we describe Distributed Search Tree (DiST), a distributed lookup protocol based on a straightforward extension of the search tree concept. In DiST peers are assigned to groups, each group is responsible for a range of keys, and groups are located at the nodes of logical search tree. While our approach has comparable complexity to the best algorithms proposed so far (complexity is O(logN)), we show that its flexible design puts it at an advantage when it comes to the application of common performance enhancing techniques such as caching and replication. As an example of such advantage we describe the improvement in data lookup time and resilience obtained with key caching and table lookup replication.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
FIPS 180-1. Secure hash standard. U.S. Department of Commerce/NIST, National Technical Information Service, Springfield, VA (April 1995)
Balakrishnanand, H., et al.: Looking up data in p2p systems. Communications of the ACM 46(2) (February 2003)
FastTrack. Peer-to-peer technology company. In: Website (2001), http://www.fasttrack.nu/
Ganesan, P., Sun, Q., Garcia-Molina, H.: Yappers: A peer-to-peer lookup service over arbitrary topology. Stanford University
Liben-Nowell, D., et al.: Analysis of the evolution of peer-to-peer systems
Markatos, E.P.: Tracing a large-scale peer-to-peer system: An hour in the life of gnutella. Tech Report 298
Napster, http://www.napster.com
Ratnasamy, S., Francis, P., Handley, M., Karp, R., Shenker, S.: A scalable content addressable network. In: Proceedings of ACM SIGCOMM 2001 (2001)
Ripeanu, M., Foster, I.: Mapping the gnutella network: Macroscopic properties of large-scale peer-to-peer systems
Rowstron, A., Druschel, P.: Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems. Microsoft Research
Schlosser, M., Kamvar, S.D.: Modeling interactions in a p2p network. Stanford University
Stading, T., Maniatis, P., Baker, M.: Peer-to-peer caching schemes to address flash crowds. Stanford University
Stoica, I., Morris, R., Karger, D., Kaashoek, M.F., Balakrishnan, H.: Chord: A scalable peer-to-peer lookup protocol for internet applications. In: Proceedings of ACM SIGCOMM, San Diego, August 2001, pp. 160–177 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Krishnamoorthy, S., Vaidyanathan, K., Lauria, M. (2005). DiST: A Scalable, Efficient P2P Lookup Protocol. In: Moro, G., Bergamaschi, S., Aberer, K. (eds) Agents and Peer-to-Peer Computing. AP2PC 2004. Lecture Notes in Computer Science(), vol 3601. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11574781_4
Download citation
DOI: https://doi.org/10.1007/11574781_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29755-0
Online ISBN: 978-3-540-31657-2
eBook Packages: Computer ScienceComputer Science (R0)