Bucket splitting exception in Kademlia

Question

In the section "Routing" in the original paper, the problem of the normal bucket splitting rule is described as follows:

Every node with prefix 001 would have an empty k-bucket into which u should be inserted, yet u's bucket refresh would only notify [$ k]of the node.

I don't understand why it is a problem. Why does every node with prefix 001 needs to receive u's bucket refresh?

I have read the original paper and have spent quite amount of time researching the bucket splitting, but I couldn't figure out. Can any one explain?

Thank you

Answer 1

That's the highly unbalanced tree case. For kademlia to work properly it must have nearly-exact view of its neighborhood while only needing a subsampled views of more remote portions of the keyspace.

The initially described bucket splitting algorithm would only split a bucket when its ID-range covers the node's own ID. But if a node's nearest neighbors don't fall into this bucket then maintaining an exhaustive view of the neighborhood requires a non-covering bucket to be split (or in S/Kademlia: an explicit neighborhood list to be maintained).