Chord: A Scalable Peertopeer Lookup Service for Internet
Applications

Ion Stoica \Lambda , Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan y
MIT Laboratory for Computer Science
chord@lcs.mit.edu
http://pdos.lcs.mit.edu/chord/

Abstract
A fundamental problem that confronts peertopeer 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.

9. References
[1] ANDERSEN, D. Resilient overlay networks. Master's thesis,
Department of EECS, MIT, May 2001.
http://nms.lcs.mit.edu/projects/ron/.
[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.
[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.
[4] CLARKE, I. A distributed decentralised information storage and
retrieval system. Master's thesis, University of Edinburgh, 1999.
[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.
[6] DABEK, F., BRUNSKILL, E., KAASHOEK, M. F., KARGER, D.,
MORRIS, R., STOICA, I., AND BALAKRISHNAN, H. Building
peertopeer systems with Chord, a distributed location service. In
Proceedings of the 8th IEEE Workshop on Hot Topics in Operating
Systems (HotOSVIII) (Elmau/Oberbayern, Germany, May 2001),
pp. 71--76.
[7] DABEK, F., KAASHOEK, M. F., KARGER, D., MORRIS, R., AND
STOICA, I. Widearea cooperative storage with CFS. In Proceedings
of the 18th ACM Symposium on Operating Systems Principles (SOSP
'01) (To appear; Banff, Canada, Oct. 2001).
[8] DRUSCHEL, P., AND ROWSTRON, A. Past: Persistent and
anonymous storage in a peertopeer 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.
[9] FIPS 1801. Secure Hash Standard. U.S. Department of
Commerce/NIST, National Technical Information Service,
Springfield, VA, Apr. 1995.
[10] Gnutella. http://gnutella.wego.com/.
[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.
[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 globalscale 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.
[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/.
[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.
[15] MOCKAPETRIS, P., AND DUNLAP, K. J. Development of the
Domain Name System. In Proc. ACM SIGCOMM (Stanford, CA,
1988), pp. 123--133.
[16] MOTWANI, R., AND RAGHAVAN, P. Randomized Algorithms.
Cambridge University Press, New York, NY, 1995.
[17] Napster. http://www.napster.com/.
[18] Ohaha, Smart decentralized peertopeer sharing.
http://www.ohaha.com/design.html.
[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.
[20] RATNASAMY, S., FRANCIS, P., HANDLEY, M., KARP, R., AND
SHENKER, S. A scalable contentaddressable network. In Proc. ACM
SIGCOMM (San Diego, CA, August 2001).
[21] STOICA, I., MORRIS, R., KARGER, D., KAASHOEK, M. F., AND
BALAKRISHNAN, H. Chord: A scalable peertopeer lookup service
for internet applications. Tech. Rep. TR819, MIT LCS, March 2001.
http://www.pdos.lcs.mit.edu/chord/papers/.
[22] VAN STEEN, M., HAUCK, F., BALLINTIJN, G., AND TANENBAUM,
A. Algorithmic design of the Globe widearea location service. The
Computer Journal 41, 5 (1998), 297--310.
