Ion Stoica
Robert Morris
David Karger
M. Frans Kaashoek
Abstract
A fundamental problem that confronts peer-to-peer applications is to efficiently locate the node that stores a particular data item. This paper presents Chord, a distributed lookup protocol that addresses this problem. Chord provides support for just one operation: given a key, it maps the key onto a node. Data location can be easily implemented on top of Chord by associating a key with each data item, and storing the key/data item pair at the node to which the key maps. Chord adapts efficiently as nodes join and leave the system, and can answer queries even if the system is continuously changing. Results from theoretical analysis, simulations, and experiments show that Chord is scalable, with communication cost and the state maintained by each node scaling logarithmically with the number of Chord nodes.
- 1 ANDERSEN, D. Resilient overlay networks. Master's thesis, Department of EECS, MIT, May 2001. http://nms.lcs.mit.edu/projects/ron/.Google Scholar
- 2 BAKKER, A., AMADE, E., BALLINTIJN, G., KUZ, I., VERKAIK, P. , VAN DER WIJK, I., VAN STEEN, M., AND TANENBAUM., A. The Globe distribution network. In Proc. 2000 USENIX Annual Conf. (FREENIX Track) (San Diego, CA, June 2000), pp. 141-152. Google ScholarDigital Library
- 3 CHEN,Y.,EDLER, J., GOLDBERG, A., GOTTLIEB, A., SOBTI, S., AND YIANILOS, P. A prototype implementation of archival intermemory. In Proceedings of the 4th ACM Conference on Digital libraries (Berkeley, CA, Aug. 1999), pp. 28-37. Google ScholarDigital Library
- 4 CLARKE, I. A distributed decentralised information storage and retrieval system. Master's thesis, University of Edinburgh, 1999.Google Scholar
- 5 CLARKE, I., SANDBERG, O., WILEY, B., AND HONG,T.W. Freenet: A distributed anonymous information storage and retrieval system. In Proceedings of the ICSI Workshop on Design Issues in Anonymity and Unobservability (Berkeley, California, June 2000). http://freenet.sourceforge.net.Google ScholarDigital Library
- 6 DABEK,F.,BRUNSKILL, E., KAASHOEK,M.F.,KARGER, D., MORRIS, R., STOICA, I., AND BALAKRISHNAN, H. Building peer-to-peer systems with Chord, a distributed location service. In Proceedings of the 8th IEEE Workshop on Hot Topics in Operating Systems (HotOS-VIII) (Elmau/Oberbayern, Germany, May 2001), pp. 71-76. Google ScholarDigital Library
- 7 DABEK,F.,KAASHOEK,M.F.,KARGER, D., MORRIS, R., AND STOICA, I. Wide-area cooperative storage with CFS. In Proceedings of the 18th ACM Symposium on Operating Systems Principles (SOSP '01) (To appear; Banff, Canada, Oct. 2001). Google ScholarDigital Library
- 8 DRUSCHEL,P.,AND ROWSTRON, A. Past: Persistent and anonymous storage in a peer-to-peer networking environment. In Proceedings of the 8th IEEE Workshop on Hot Topics in Operating Systems (HotOS 2001) (Elmau/Oberbayern, Germany, May 2001), pp. 65-70.Google ScholarCross Ref
- 9 FIPS 180-1. Secure Hash Standard. U.S. Department of Commerce/NIST, National Technical Information Service, Springfield, VA, Apr. 1995.Google Scholar
- 10 Gnutella. http://gnutella.wego.com/.Google Scholar
- 11 KARGER, D., LEHMAN, E., LEIGHTON,F.,LEVINE, M., LEWIN, D., AND PANIGRAHY, R. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (El Paso, TX, May 1997), pp. 654-663. Google ScholarDigital Library
- 12 KUBIATOWICZ, J., BINDEL, D., CHEN,Y.,CZERWINSKI, S., EATON,P.,GEELS, D., GUMMADI, R., RHEA, S., WEATHERSPOON, H., WEIMER,W.,WELLS, C., AND ZHAO,B. OceanStore: An architecture for global-scale persistent storage. In Proceeedings of the Ninth international Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2000) (Boston, MA, November 2000), pp. 190-201. Google ScholarDigital Library
- 13 LEWIN, D. Consistent hashing and random trees: Algorithms for caching in distributed networks. Master's thesis, Department of EECS, MIT, 1998. Available at the MIT Library, http://thesis.mit.edu/.Google Scholar
- 14 LI, J., JANNOTTI, J., DE COUTO, D., KARGER, D., AND MORRIS, R. A scalable location service for geographic ad hoc routing. In Proceedings of the 6th ACM International Conference on Mobile Computing and Networking (Boston, Massachusetts, August 2000), pp. 120-130. Google ScholarDigital Library
- 15 MOCKAPETRIS,P.,AND DUNLAP, K. J. Development of the Domain Name System. In Proc. ACM SIGCOMM (Stanford, CA, 1988), pp. 123-133. Google ScholarDigital Library
- 16 MOTWANI, R., AND RAGHAVAN,P.Randomized Algorithms. Cambridge University Press, New York, NY, 1995. Google ScholarDigital Library
- 17 Napster. http://www.napster.com/.Google Scholar
- 18 Ohaha, Smart decentralized peer-to-peer sharing. http://www.ohaha.com/design.html.Google Scholar
- 19 PLAXTON, C., RAJARAMAN, R., AND RICHA, A. Accessing nearby copies of replicated objects in a distributed environment. In Proceedings of the ACM SPAA (Newport, Rhode Island, June 1997), pp. 311-320. Google ScholarDigital Library
- 20 RATNASAMY, S., FRANCIS,P.,HANDLEY, M., KARP, R., AND SHENKER, S. A scalable content-addressable network. In Proc. ACM SIGCOMM (San Diego, CA, August 2001). Google ScholarDigital Library
- 21 STOICA, I., MORRIS, R., KARGER, D., KAASHOEK,M.F.,AND BALAKRISHNAN, H. Chord: A scalable peer-to-peer lookup service for internet applications. Tech. Rep. TR-819, MIT LCS, March 2001. http://www.pdos.lcs.mit.edu/chord/papers/.Google Scholar
- 22 VAN STEEN, M., HAUCK,F.,BALLINTIJN, G., AND TANENBAUM, A. Algorithmic design of the Globe wide-area location service. The Computer Journal 41, 5 (1998), 297-310.Google ScholarCross Ref
Index Terms
- Chord: A scalable peer-to-peer lookup service for internet applications
Recommendations
Chord: A scalable peer-to-peer lookup service for internet applications
SIGCOMM '01: Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communicationsA fundamental problem that confronts peer-to-peer applications is to efficiently locate the node that stores a particular data item. This paper presents Chord, a distributed lookup protocol that addresses this problem. Chord provides support for just ...
Chord: a scalable peer-to-peer lookup protocol for internet applications
A fundamental problem that confronts peer-to-peer applications is the efficient location of the node that stores a desired data item. This paper presents Chord, a distributed lookup protocol that addresses this problem. Chord provides support for just ...
Re-Chord: A Self-stabilizing Chord Overlay Network
The Chord peer-to-peer system is considered, together with CAN, Tapestry and Pastry, as one of the pioneering works on peer-to-peer distributed hash tables (DHT) that inspired a large volume of papers and projects on DHTs as well as peer-to-peer systems ...
Comments