Advertisement

Chord project

From Academic Kids

"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 <math>log(N)<math> 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 <math>2^m<math> nodes. The ring can have ids/keys ranging from 0 to <math>2^m - 1<math>. In the above diagram <math>m = 3<math>.

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

// n' thinks it might be our predecessor.
n.notify(n')
 if (predecessor is nil or n'<math>\in<math>(predecessor, n))
  predecessor = n';

External links

Navigation

Academic Kids Menu

  • Art and Cultures
    • Art (http://www.academickids.com/encyclopedia/index.php/Art)
    • Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (http://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools