[chord] Correctness of finger table in simulator

[Ion Stoica]

Verdi,

I the followings I assume that you are refering to the old
Chord simulator, and not to the p2psim.

The Chord simulator combines the successor list, the
proper finger, and the cached nodes (i.e., nodes that contact
the current node but they are neither successors nor
proper fingers) in one data structure, fingerList.

However, the nodes in the successor list,
and the proper fingers are refreshed at a much higher
rate than the cached nodes. As a result, if size(fingerList)
 > num_fingers + num_successors,  the fingerList will
contain with a high probability (not in theoretical sense)
all nodes in the successor list and the proper fingers.

In summary, you are right that what you get from the
simulator is only an approximation of the stable condition.
But from our experience this approximation is very
good.

One way to "fix" this problem is to avoid inserting
nodes in the fingerList when you hear from other
nodes, and pick size(fingerList) = 2*logN + m,
where m is the number of bits of the identifier.
Let me know if you are interested in this approach.

Ion

PS. Also note that in most cases chosing
size(fingerList) = 3*logN is good enough
since the first log(2log(N)) proper fingers
will be shared with the 2*log(N) successors,
so in practice you can accommodate log(N) +
log(2log(N)) proper fingers.

Verdi March wrote:

>Hi,
>
>I need to check the correctness of node->fingerList. The reason is I
>need to simulate events (lookup, fail, etc.) in a stable Chord. Stable
>means a number of joins followed by a 'wait' period until all fingers in
>n->fingerList point to their proper finger. As defined in stabilize.c, a
>proper finger is the successor of n+2^{i-1}.
>
>My current approach is to periodically observe fingerList of every node:
>a. ensure that fingerList = num_fingers + num_successors
>b. for each finger, they must point to the proper successor
>
>Unfortunately, this approach does not work as I haven't fully understand
>how Chord simulator fills node->fingerList. 
>
>According to the paper, fingerList->size is fixed (with some duplicate
>entries). But in the simulator, fingerList->size varies depending on the
>total number of nodes.
>For instance, with num_finger = 16 and num_successor = 1, I expected 
>each node to have fingerList->size = 17.
>However, the simulation results are:
>1. With 5 nodes, nodes eventually have fingerList->size = 4.
>2. With 10 nodes, nodes eventually have fingerList->size = 9.
>
>Because it is possible that [fingerList->size < (num_fingers +
>num_successors)], my approach will fail (step a).
>
>I'm thinking whether I can assume that (after skipping num_successors 
>entries), the remaining fingers (say 3 more fingers) should points to
>n+1, n+2, and n+4 nodes?
>Which brings me another question: how do I know that 3 more fingers
>is the correct number? If I can't guarantee that 3 is the correct
>number, then my approach would only provides an approximation of stable
>condition.
>
>Any comments? TIA.
>
>
>Regards,
>Verdi
>
>_______________________________________________
>chord mailing list
>chord at amsterdam.lcs.mit.edu
>https://amsterdam.lcs.mit.edu/mailman/listinfo/chord
>  
>