Abstract
Searching a file by its name is an essential problem of a large peer-to-peer file-sharing system. In this paper, we present a new scalable distributed data structure LinkNet for searching in a large peer-to-peer system. In LinkNet, all elements are stored in a sorted doubly linked list, and one node stores many elements. LinkNet uses virtual link to speed search and enhance fault tolerance. Because LinkNet is based on a sorted list, it benefits operations such as range query, bulk loading of data, and merging of two LinkNets.
The work was supported by the National Natural Science Foundation of China under Grant Nos. 60473069, 60496325 and the National High Technology Development 863 Program of China under Grant No. 2003AA4Z3030.
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
Balakrishnan, H., Frans Kaashoek, M., Karger, D., Morris, R., Stoica, I.: Looking Up Data in P2P Systems. Communications of the ACM 46(2) (February 2003)
Aspnes, J., Shah, G.: Skip Graphs. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (January 2003)
Harvey, N.J.A., Jones, M.B., Saroiu, S., Theimer, M., Wolman, A.: SkipNet: A Scalable Overlay Network with Practical Locality Properties. In: Proceedings of the 4th USENIX Symposium on Internet Technologies and Systems (USITS) (March 2003)
Pugh, W.: Skip Lists: A Probabilistic Alternative to Balanced Trees. Communications of the ACM 33(6), 668–676 (1990)
Pugh, W.: Concurrent Maintenance of Skip List. Technical Report CS-TR-2222, Department of Computer Science, University of Maryland (June 1990)
Napster, http://www.napster.com/
Gnutella, http://www.gnutelliums.com/
Ratnasamy, S., Francis, P., Handley, M., Karp, R., Shenker, S.: A Scalable Content- Addressable Network. In: Proceedings of the ACM Symposium on Communications Architectures and Protocols (SIGCOMM), San Diego, CA, USA (August 2001)
Stoica, I., Morris, R., Liben-Nowell, D., Karger, D., Frans Kaashoek, M., Dabek, F., Balakrishnan, H.: Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications. Tech. Rep. TR-819, MIT LCS (2001)
Rowstron, A., Druschel, P.: Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In: Proceedings of the 18th IFIP/ACM International Conference on Distributed Systems Platforms (November 2001)
Zhao, B., Kubiatowicz, J., Joseph, A.: Tapestry: An infrastructure for fault-tolerant wide-area location and routing. Tech. Rep. UCB/CSD-01-1141, Computer Science Division, U. C. Berkeley (Apr. 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
Zhang, K., Wang, S. (2005). LinkNet: A New Approach for Searching in a Large Peer-to-Peer System. In: Zhang, Y., Tanaka, K., Yu, J.X., Wang, S., Li, M. (eds) Web Technologies Research and Development - APWeb 2005. APWeb 2005. Lecture Notes in Computer Science, vol 3399. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-31849-1_24
Download citation
DOI: https://doi.org/10.1007/978-3-540-31849-1_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25207-8
Online ISBN: 978-3-540-31849-1
eBook Packages: Computer ScienceComputer Science (R0)