# 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 [itex]log(N)[itex] 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

Missing image
Chord_ring.GIF
A Chord identifier circle

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

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 [itex]\in[itex] (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 [itex]\in[itex](n, successor))
successor = x;
successor.notify(n);

// n' thinks it might be our predecessor.
n.notify(n')
if (predecessor is nil or n'[itex]\in[itex](predecessor, n))
predecessor = n';


• Art and Cultures
• Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
• Space and Astronomy