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. The 2001 Chord paper won an ACM SIGCOMM Test of Time award in 2011.

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

Overview
Nodes and keys are assigned an -bit identifier using consistent hashing. The SHA-1 algorithm is the base hashing function for consistent hashing. Consistent hashing is integral to the robustness and performance of Chord because both keys and nodes (in fact, their IP addresses) are uniformly distributed in the same identifier space with a negligible possibility of collision. Thus, it also allows nodes to join and leave the network without disruption. In the protocol, the term node is used to refer to both a node itself and its identifier (ID) without ambiguity. So is the term key.

Using the Chord lookup protocol, nodes and keys are arranged in an identifier circle that has at most nodes, ranging from to . ( should be large enough to avoid collision.) Some of these nodes will map to machines or keys while others (most) will be empty.
Each node has a successor and a predecessor. The successor to a node is the next node in the identifier circle in a clockwise direction. The predecessor is counter-clockwise. If there is a node for each possible ID, the successor of node 0 is node 1, and the predecessor of node 0 is node ; however, normally there are "holes" in the sequence. For example, the successor of node 153 may be node 167 (and nodes from 154 to 166 do not exist); in this case, the predecessor of node 167 will be node 153.
The concept of successor can be used for keys as well. The successor node of a key is the first node whose ID equals to or follows in the identifier circle, denoted by . Every key is assigned to (stored at) its successor node, so looking up a key is to query .
Since the successor (or predecessor) of a node may disappear from the network (because of failure or departure), each node records an arc of nodes in the middle of which it stands, i.e., the list of nodes preceding it and nodes following it. This list results in a high probability that a node is able to correctly locate its successor or predecessor, even if the network in question suffers from a high failure rate.
Protocol details
Basic query
The core usage of the Chord protocol is to query a key from a client (generally a node as well), i.e. to find . The basic approach is to pass the query to a node's successor, if it cannot find the key locally. This will lead to a query time where is the number of machines in the ring.
Finger table
To avoid the linear search above, Chord implements a faster search method by requiring each node to keep a finger table containing up to entries, recall that is the number of bits in the hash key. The entry of node will contain . The first entry of finger table is actually the node's immediate successor (and therefore an extra successor field is not needed). Every time a node wants to look up a key , it will pass the query to the closest successor or predecessor (depending on the finger table) of in its finger table (the "largest" one on the circle whose ID is smaller than ), until a node finds out the key is stored in its immediate successor.
With such a finger table, the number of nodes that must be contacted to find a successor in an N-node network is . (See proof below.)
Node join
Whenever a new node joins, three invariants should be maintained (the first two ensure correctness and the last one keeps querying fast): Each node's successor points to its immediate successor correctly. Each key is stored in . Each node's finger table should be correct.





