[chord] Correctness of finger table in simulator

[Ion Stoica]

Verdi March wrote:

>Hi Ion,
>
>On Tuesday June 8 2004 am 00:26, you wrote:
>  
>
>>One way to "fix" this problem is to avoid inserting
>>nodes in the fingerList when you hear from other
>>nodes,
>>    
>>
>
>This means I need to run the simulator by specifying
>num_location_cache = num_successors + num_finger - 1
>
>In addition, I need to change:
>n.process_request()
>begin
>  if (empty(request_list) == True)
>    return;
>
>  r = request_list.remove();
>
>  //finger_list.add(r.initiator);  //Don't insert cached node
>  //finger_list.add(r.sender);     //Don't insert cached node
>
>  ...
>end
>  
>
Yes, I think these are all the changes you need to do.

>  
>
>>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.
>>    
>>
>Is this under the assumption that num_successor = 2*logN ?
>  
>
yes.

>Some of my experiments do not involved node failure and node
>withdrawal -- only lookups on stable condition. For these
>experiments, I think it is sufficient to use only 1 successor
>(max. size of fingerList = m)?
>  
>
correct.

>  
>
>>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.
>>    
>>
>
>Ah, I forgot that fingerList only keep unique fingers. That's why,
>its size can be smaller than (max_successors + max_fingers - 1).
>
>However, I'm still confused about #shared_proper_finger, log(2log(N)).
>By "2log(N)" do you mean "2*log(N)" or "log_2 (N)"?
>  
>
I meant 2*log(N). Assuming that the successor list is 2*log(N), and the
nodes are uniformly distributed, then the expected number
of proper fingers in the successor list is log(2*log(N)).

Best,

Ion

PS. If you have more questions, you can send them directly
to me.