Kademlia routing table and distance metric

Question

Its been the first time I read about Kademlia today, and some points I don't think I got them right.

The distance between nodes and keys is the xor of their values.

So, if I have key x and node y, the distance between them is x xor y.

But why what is the point to bucket the nodes I know about and order them by the prefix length ? That doesn't seem to be connected directly with the xor of node IDs to find closests nodes to me ?

When I get a request for a value I search in the nodes in the closests buckets to me, that is the nodes which have the largest shared prefix with me, ie the first few buckets of the 160 buckets ?

or instead I check all nodes I know about in all the buckets and I calculate the xor between the key I am looking for, and those nodes IDs, and then send my request to the top k matches based on the xoring results with the key ID ?

Sorry I am a bit new to DHTs, and found the explanations online a bit not clear.

Answer 1

I think I got it. The common prefix same bucket thing is indeed directly related to the xor values, so its indeed sorting them. I found those slides pretty helpful: http://heim.ifi.uio.no/michawe/teaching/p2p-ws08/p2p-5-6.pdf