Official eMule-Board: How To Understand The Time Complexity Of Kademlia Node Operation? - Official eMule-Board

Jump to content


Page 1 of 1

How To Understand The Time Complexity Of Kademlia Node Operation?

#1 User is offline   Darkgeek 

  • Newbie
  • Pip
  • Group: Members
  • Posts: 1
  • Joined: 12-March 15

Posted 13 March 2015 - 01:33 AM

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. :bounce:
1

  • Member Options

Page 1 of 1

1 User(s) are reading this topic
0 members, 1 guests, 0 anonymous users