Hi, guys:
I'm now learning Kademlia network by reading the classical paper Kademlia: A Peer-to-peer Information System Based on the XOR Metric. I want to understand the complexity of its operation but still cannot figure it out.
In the 3 Sketch of proof section, the paper gives two definitions:
1. Depth of a node (h): 160 − i, where i is the smallest index of a non-empty bucket
2. Node y’s bucket height in node x: the index of the bucket into which x would insert y minus the index of x’s least significant empty bucket.
And three conclusions:
1. With overwhelming probability the height of a any given node will be within a constant of log n for a system with n nodes.
2. The bucket height of the closest node to an ID in the kth-closest node will likely be within a constant of log k.
3. If none of this node’s h most significant k-buckets is empty, the lookup procedure will find a node half as close (or rather whose distance is one bit shorter) in each step, and thus turn up the node in h − log k steps.
So my questions are:
1. What is "least significant empty bucket" and "most significant k-buckets"?
2. How to explain the depth and bucket height in visual way?
3. How to understand the second and third conclusions, say, why log k and h - log k?
Thanks.
Page 1 of 1
Page 1 of 1