Chord project

"The Chord project aims to build a scalable, symmetric and robust distributed systems using peer-to-peer ideas. The basis for much of our work is the Chord distributed hash table lookup primitive. Chord is completely decentralized and can find data using only log(N) messages, where N is the number of nodes in the system. Chord's lookup mechanism is probably robust in the face of frequent node failures and re-joins."

Chord is being developed at MIT and the current Chord source code can be downloaded and used under the MIT license.

Overview

Using the Chord lookup protocol, node keys are arranged in a circle. The circle cannot have more than 2^m nodes. The ring can have ids/keys ranging from 0 to 2^m − 1. In the above diagram m = 3.

In the above diagram the green circles represent nodes. The black points represent keys. IDs and keys are assigned using what is known as consistent hashing. The SHA-1 algorithm is the base hashing function for consistent hashing.

Each node has a successor and a predecessor. The successor to a node or key is the next node in the identifier circle when you move clockwise. The predecessor of a node or key is the next node in the id circle when you move counter-clockwise. For example, the successor of node 1 is node 3, and the predecessor of node 1 is node 0.

The pseudocode to find the successor node of an id is given below:

 // ask node n to find the successor of id
 n.find_successor(id)
  if (id  (n, successor])
   return successor;
  else
   // forward the query around the circle
   return successor.find_successor(id);
 

The pseudocode to stabilize the chord ring/circle after node joins and departures is a follows:

 // create a new Chord ring.
 n.create()
  predecessor = nil;
  successor = n;
 
 // join a Chord ring containing node n0.
 n.join(n')
  predecessor = nil;
  successor = n'.find_successor(n);
 
 // called periodically. verifies n’s immediate
 // successor, and tells the successor about n.
 n.stabilize()
  x = successor.predecessor;
  if (x (n, successor))
   successor = x;
  successor.notify(n);
 
 // n' thinks it might be our predecessor.
 n.notify(n')
  if (predecessor is nil or n'(predecessor, n))
   predecessor = n';
 

External links

• The Chord Project
• Paper proposing Chord: "Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications"

See also: Chord project, Distributed hash table, Distributed system, MIT, MIT license, Peer-to-peer