[chord] Chord queries relating to Initialisation and Join

[Aisling O' Driscoll]

Hi,

I am currently implementing chord in opnet and would greatly appreciate if
two main points could be clarified to ensure my implementation is correct.

I have read differing accounts as to the order in which the steps should
occur for a node join so if the logic of the following sequence could be
verified that would be great:


    1. I assume a chord ring is already formed.
      2. Node n wishes to join the ring.
      3. Node n contacts a known node in the chord ring (node q) and queries
      q for its successor. Node p replies that its successor is node s.
      4. Node n sets its successor = s and its predecessor = nil.
      5. Node n then begins to build its finger table by getting node q to
      do lookups for each of its finger table entries (according to
the algorithm
      as specified in the paper, n – 2^i-1).
      6. Does node n then trigger the stabilize function or do I set a timer
      for node n and wait for stabilize to occur at the next interval? If it is
      triggered, then node n will inform node s of its existence so that it can
      update its predecessor pointer.
      7. Node p, who was previously the predecessor of node s, then sends
      it’s periodic notify message querying node s’ predecessor. When node s
      replies saying its predecessor is node n, node p updates its
successor and
      notifies node n that it is its new predecessor.
      8. Am I correct in saying that *only now* does node n copy the keys
      it’s responsible for i.e. only after all the above steps have
occurred? And
      if so, does the predecessor node p initiate this transfer upon
learning that
      it has a new successor just after it sends the notify message?
      9. Furthermore when does the predecessor node p update its finger
      tables to reflect node s? Is it immediately, when it learns that it has a
      new successor and immediately recalculates every entry in its
finger table
      or is it done gradually according to the fix_fingers algorithm?
      10. Finally I have read differing accounts as to how other nodes in
      the ring update their finger table entries. I think according to
the default
      Chord algorithm this is done lazily i.e. every node periodically does a
      lookup on a random finger table entry i.e. fix_fingers. Therefore it will
      take O(log N) intervals to update the entire table. I have read others
      accounts such as the attached that claim all nodes whose finger tables
      previously referred to node s must be updated. They reference the Chord
      SIGCOMM paper so I am unsure which approach to take? Also, if a proactive
      approach is taken how does joining node n know which nodes should be
      updated?

 My seconds question relates to how nodes join when the network is first
initialised (as opposed to later on when the Chord ring is functioning – as
per above).

   1.  So node n joins the network. It is the first node in the Chord ring.
   It sets successor = n and predecessor = nil. It creates every entry in its
   finger table so that every entry finger_table [i] = n. It is now the
   bootstrap node for the network.
   2. Now node m joins the network. This is where I’m confused. Node m
   contacts node n (its equivalent of a bootstrap node). It queries its
   successor. Node n will reference its finger table and deduce that node n
   itself is the successor for joining node m. Node m will then query node n
   for its finger table entries but based on the previous step all the answers
   will be set to that of node n. So both nodes will now have finger tables
   only containing entries for node n. Is this correct behaviour? And if so how
   will these nodes ever have build correct finger table entries?

 Many thanks in advance.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://amsterdam.lcs.mit.edu/pipermail/chord/attachments/20100519/75beef01/attachment.htm