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. The 2001 Chord paper won a 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 formula_1-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 formula_2 nodes, ranging from formula_3 to  formula_4. (formula_1 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 formula_4; 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 formula_7 is the first node whose ID equals to formula_7 or follows formula_7 in the identifier circle, denoted by formula_10. Every key is assigned to (stored at) its successor node, so looking up a key formula_7 is to query formula_10. Since the successor (or predecessor) of a node may disappear from the network (because of failure or departure), each node records an  arc of formula_13 nodes in the middle of which it stands, i.e., the list of formula_14 nodes preceding it and formula_14 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 formula_10. 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 formula_17 query time where formula_18 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 formula_1 entries, recall that formula_1 is the number of bits in the hash key. The formula_21 entry of node formula_22 will contain formula_23. 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 formula_7, it will pass the query to the closest successor or predecessor (depending on the finger table) of formula_7 in its finger table (the "largest" one on the circle whose ID is smaller than formula_7), 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 formula_27. (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): To satisfy these invariants, a "predecessor" field is maintained for each node. As the successor is the first entry of the finger table, we do not need to maintain this field separately any more. The following tasks should be done for a newly joined node formula_22: The predecessor of formula_22 can be easily obtained from the predecessor of formula_32 (in the previous circle). As for its finger table, there are various initialization methods. The simplest one is to execute find successor queries for all formula_1 entries, resulting in formula_34 initialization time. A better method is to check whether formula_21  entry in the finger table is still correct for the formula_36 entry. This will lead to formula_37. The best method is to initialize the finger table from its immediate neighbours and make some updates, which is formula_27. Stabilization. To ensure correct lookups, all successor pointers must be up to date. Therefore, a stabilization protocol is running periodically in the background which updates finger tables and successor pointers. The stabilization protocol works as follows: Proof sketches. With high probability, Chord contacts formula_27 nodes to find a successor in an formula_18-node network. Suppose node formula_22 wishes to find the successor of  key formula_7. Let formula_43 be the predecessor of formula_7. We wish to find an upper bound for the number of steps it takes for a message to be routed from formula_22 to formula_43. Node formula_22 will examine its finger table and route the request to the closest predecessor of formula_7 that it has. Call this node formula_49. If formula_49 is the formula_21 entry in formula_22's finger table, then both formula_49 and formula_43 are at distances between formula_55 and formula_56 from formula_22 along the identifier circle. Hence, the distance between formula_49 and formula_43 along this circle is at most formula_55 . Thus the distance from formula_49 to formula_43 is less than the distance from formula_22 to formula_49: the new distance to formula_43 is at most half the initial distance. This process of halving the remaining distance repeats itself, so after formula_66 steps, the distance remaining to formula_43 is at most formula_68; in particular, after formula_69 steps, the remaining distance is at most formula_70. Because nodes are distributed uniformly at random along the identifier circle, the expected number of nodes falling within an interval of this length is 1, and with high probability, there are fewer than formula_69 such nodes. Because the  message always advances by at least one node, it takes at most formula_72 steps for a message to traverse this remaining distance. The total expected routing time is thus formula_27. If Chord keeps track of formula_74 predecessors/successors, then with high probability, if each node has probability of 1/4 of failing, find_successor (see below) and find_predecessor (see below) will return the correct nodes Simply, the probability that all formula_14 nodes fail is formula_76, which is a low probability; so with high probability at least one of them is alive and the node will have the correct pointer. Pseudocode. The pseudocode  to find the "successor" node of an id is given below: The pseudocode to stabilize the chord ring/circle after node joins and departures is as follows: