Chord (peer-to-peer)

In computing, Chord is a protocol and algorithm for a peer-to-peer distributed hash table. A distributed hash table stores key-value pairs by assigning keys to different computers (known as "nodes"); a node will store the values for all the keys for which it is responsible. Chord specifies how keys are assigned to nodes, and how a node can discover the value for a given key by first locating the node responsible for that key.

Chord is one of the four original distributed hash table protocols, along with CAN, Tapestry, and Pastry. It was introduced in 2001 by Ion Stoica, Robert Morris, David Karger, Frans Kaashoek, and Hari Balakrishnan, and was developed at MIT.[1] The 2001 Chord paper[1] won an ACM SIGCOMM Test of Time award in 2011.[2]

Subsequent research by Pamela Zave has shown that the original Chord algorithm (as specified in the 2001 SIGCOMM paper,[1] the 2001 Technical report,[3] the 2002 PODC paper,[4] and the 2003 TON paper [5]) can mis-order the ring, produce several rings, and break the ring.[6]

  1. ^ a b c Stoica, I.; Morris, R.; Kaashoek, M. F.; Balakrishnan, H. (2001). "Chord: A scalable peer-to-peer lookup service for internet applications" (PDF). ACM SIGCOMM Computer Communication Review. 31 (4): 149. doi:10.1145/964723.383071.
  2. ^ "ACM SIGCOMM Test of Time Paper Award". Retrieved 16 January 2022.
  3. ^ Stoica, I.; Morris, R.; Liben-Nowell, D.; Karger, D.; Kaashoek, M. F.; Dabek, F.; Balakrishnan, H. (2001). Chord: A scalable peer-to-peer lookup service for internet applications (PDF) (Technical report). MIT LCS. MIT. 819. Archived from the original (PDF) on 22 July 2012.
  4. ^ Liben-Nowell, David; Balakrishnan, Hari; Karger, David (July 2002). Analysis of the evolution of peer-to-peer systems (PDF). PODC '02: Proceedings of the twenty-first annual symposium on Principles of distributed computing. pp. 233–242. doi:10.1145/571825.571863.
  5. ^ Stoica, I.; Morris, R.; Liben-Nowell, D.; Karger, D.; Kaashoek, M. F.; Dabek, F.; Balakrishnan, H. (25 February 2003). "Chord: a scalable peer-to-peer lookup protocol for Internet applications". IEEE/ACM Transactions on Networking. 11 (1): 17–32. doi:10.1109/TNET.2002.808407. S2CID 221276912.
  6. ^ Zave, Pamela (2012). "Using lightweight modeling to understand chord" (PDF). ACM SIGCOMM Computer Communication Review. 42 (2): 49–57. doi:10.1145/2185376.2185383. S2CID 11727788.