[chord] Correctness of finger table in simulator

[Verdi March]

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

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

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

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

Using different approach, I also arrived at the same calculation (size
of fingerList is bounded by 3*log(N)):
with s successor there will be (log(s) + 1) successors shared with the 
proper fingers. Since s = 2*log(N) and max_fingers = log(N), then the
maximum size of fingerList will be log(N) + s - log(s) + 1, which is
3*log(N) - log(log(N)) + 1.


Regards,
Verdi