[p2p-hackers] Errata in the Chord paper ?

[shudo at computer.org]

Hi all,

I have some doubt about a pseudocode in the Chord paper:

  I. Stoica, R. Morris, D. Karger, M. F. Kaashoek and H. Balakrishnan,
  Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications.
  In Proc. ACM SIGCOMM 2001, pp.149-160, Aug. 2001.

It is a pseudocode for a basic node join operation in the Fig. 6. The
paper presents another join algorithm in the Fig. 7 and the latter one
will be implemented usually because the basic algorithm in Fig. 6 is
not tolerate concurrent joins (and failures).

So, it's not a serious problem at all if there are errata in the basic
algorithm. And, of course, my interpretation of the paper is not
correct. Please give me a comment if you know the same possible errata
have been pointed out somewhere before.


(1) A finger table entry (finger[k].node) can be the node itself which
    have the finger table. But, the pseudocode in Fig. 6 does not allow it.

A finger table is initialized by a procedure init_finger_table(). The
init_finger_table() calls find_successor() on an existing node n'.
When the init_finger_table() is called on a joining node, no existing
node knows the joining node because existing nodes can notice the
joining node only by update_others() called just after init_finger_table().
As a result, a joining node cannot have itself in its finger table,
even if the joining node itself is the most appropriate node for a
finger table entry.


(2) A joining node calls find_predecessor(n - 2^(i-1)) in a procedure
    update_finger_others() to find out nodes which should have the joining
    node in their finger tables.  The argument for the call is not correct
    and it should be find_predecessor(n - 2^(i-1) + 1).

Let's consider the case of i = 1. Suppose n is the node ID of the
joining node. In this case, the joining node should find out a node
whose ID is n-1 (of course, mod 2^m) or prior to n-1. But
find_predecessor(n - 2^(i-1)) results in n-2 or prior to n-2 because
a procedure find_predecessor(id) in Fig. 4 returns id-1 or prior to id-1.


I appreciate any comment.

Cheers,

  Kazuyuki Shudo
  Grid Technology Research Center
  National Institute of Advanced Industrial Science and Technology (AIST)