Endless loop findSuccessor?

Question

I am currently dealing with the Chord protocol.

There are two functions for each node: findSuccessor and closestPrecedingNode , which are set as pseudocode.

findSuccessor :

 n.findSuccessor(id) if(id is.in (n, successor]) return successor; else n' = closestPrecedingNode(id); return n'.findSuccessor(id); 

closestPrecedingNode :

 n.closestPrecedingNode(id) for i = m downto 1 if(finger[i] is.in (n, id)) return finger[i]; return n; 

When a node is created, its successor is initially installed on the node itself, and its finger table is empty.

Now my question is what happens when there is only one node, and it is asked any identifier except its own id. findSuccessor then starts the else block and calls closestPrecedingNode . Since the finger table is empty, the node itself returns to findSuccessor . Therefore, n' then equals n .

Then findSuccessor is called on n' , which is a recursive call for itself.

And then we have an endless loop ... or am I missing something?

NOTE. The pseudo-code is taken from Chord: A Scalable Peer-to-Peer Search Protocol for Internet Applications , p. 5.

Answer 1

Apparently, the "jchord" developer agrees with you, as he adds the following code to findSuccessor :

 if (this == successor) { return this; } 

But there seems to be a more elegant solution with closer to pseudo-code. When checking whether the identifier is in the interval (n, successor) (excluded on the left, right on), make this check cyclical. JDHTUQ seems to do it like this (starting at line 75. Warning: Really ugly code):

http://jdhtuq.svn.sourceforge.net/viewvc/jdhtuq/source_code/distributed_lookup_service/LookupService/src/co/edu/uniquindio/utils/hashing/Key.java?revision=63&view=markupup

IMHO performing loop checking of intervals seems to be correct. The document you indicated says (on page 4):

The designation (a; b] denotes the segment of the chord ring obtained by moving clockwise from (but not including) a until reaching (and turning on) b.

In the case of a single node, you should check

 id is.in (n, n] 

which should give true , since id is inside the ring, which begins immediately after n and ends with n .