Chord (peer-to-peer) - Pseudocode

Pseudocode

Definitions for pseudocode:

• finger: first node that succeeds
• successor: the next node from the node in question on the identifier ring
• predecessor: the previous node from the node in question on the identifier ring

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] ) // Yes, that should be a closing square bracket to match the opening parenthesis. It is a half closed interval. return successor; else // forward the query around the circle n0 = closest_preceding_node(id); return n0.find_successor(id); // search the local table for the highest predecessor of id n.closest_preceding_node(id) for i = m downto 1 if (finger(n,id)) return finger; return n;

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

// create a new Chord ring. n.create predecessor = nil; successor = n; // join a Chord ring containing node n'. n.join(n') predecessor = nil; successor = n'.find_successor(n); // called periodically. n asks the successor // about its predecessor, verifies if n's immediate // successor is consistent, 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'; // called periodically. refreshes finger table entries. // next stores the index of the finger to fix n.fix_fingers next = next + 1; if (next > m) next = 1; finger = find_successor(n+); // called periodically. checks whether predecessor has failed. n.check_predecessor if (predecessor has failed) predecessor = nil;