[chord] Chord queries relating to Initialisation and Join

[Emil Sit]

On Wed, May 19, 2010 at 2:30 PM, Aisling O' Driscoll
<odriscoll.aisling at gmail.com> wrote:
> 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.

I think node n can trigger stabilize as soon as it knows its
successor.  In Chord, all you need is a correct successor pointer in
order to do correct routing; the finger tables are just for
efficiency.

> 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?

Node n shouldn't be copying keys from p; it should be taking data from s.

The Chord protocol does not specify how to handle data transfers.  You
should probably not do a move on an item-by-item basis, but rather a
copy (which doesn't affect the ability to read data) and then,
optionally, once data movement is completed, a delete.  In the latest
NSDI paper (UsenetDHT, introducing Passing Tone), we recommend not
deleting unless you are disk constrained.

> 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?

In the implementation, it happens immediately because we store all
known nodes in a location_table object and dynamically figure out the
best fingers when they are needed.

> 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?

Well, I don't see how one could really have a new node proactively
update everyone else in a truly distributed and large scale system.
So, yes, it may take some time before everyone gets the fully updated
finger tables doing their own periodic fix_fingers.  But the idea
again is that Chord relies on successor pointers to route correctly
and finger tables to route efficiently.  Since a query should never
overshoot, you should never get the wrong answer.

> 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?

In the location_table approach, as soon as node m notifies node n that
it is a predecessor, node n will be in the table and be automatically
used as some fingers.

-- 
Emil Sit / http://www.emilsit.net/