5

I read the paper about Kademlia available here.

I don't understand how the number k is chosen (for the k-bucket).

I don't understand this sentence: "k is chosen such that any given k nodes are very unlikely to fail within an hour of each other."

I don't understand how a node failing?

2 Answers 2

2

Kademlia is an abstract algorithm.

Individual implementations can choose their own k based on expected characteristics of the nodes in the network.

For example if you wanted to form a small overlay of a few hundred nodes in a highly reliable datacenter then k = 2 may be sufficient.

Bittorrent uses k = 8 with lots of domestic (read: quite unreliable) nodes scattered over the whole internet and it does its job, but its job is not particularly demanding. So one can't infer that that's the upper practical limit from that alone.

I don't understand how a node failing?

Computers crash, go offline, change internet connections, reboot, are put into hibernation. All those are things that effectively are node failures from the perspective of the network.

4
  • So what are the exact criteria for selecting k-bucket size? If I understood your answer correctly, you say: "if your network is expected to be unreliable, choose bigger k". That's understandable: bigger k means more nodes I store contact information about. But why would I want to keep k value low? What stops me to set k to infinite, which would mean: do not reject anyone, just save all contact info. Wouldn't it be better? Even more reliable? What am I missing here?
    – Piotrek
    May 11, 2022 at 9:05
  • Quote from the question "k is chosen such that any given k nodes are very unlikely to fail within an hour of each other.". Once k is high enough to achieve that goal going further would only create inefficiencies such as excessive routing table maintenance traffic. Remember that kademlia's goal is to provide O(log(n)) behavior. k = ∞ would mean keeping the whole network in memory which would be O(n).
    – the8472
    May 11, 2022 at 16:35
  • And what exactly is "excessive routing table maintenance traffic"? Do I need to send ping messages periodically to each of nodes stored in k-buckets? Or only the one that might be replaced while some other new node requests to be added to k-bucket list?
    – Piotrek
    May 11, 2022 at 16:51
  • That starts to sound like a separate question to me, somthing about how kademlia routing table maintenance works?
    – the8472
    May 12, 2022 at 11:35
0

Here is what I've managed to find about significance of k-bucket value on Kademlia network behavior:

Based on Improving Community Management Performance with Two-Level Hierarchical DHT Overlays paper:

  • Low k means more fragmented network
  • High k means lower number of hops during lookup, but higher maintenance traffic

The value of k (referring to bucket size, a Kademlia-specific parameter) has a major impact for the operation of the Kademlia DHT. On the first hand, the value should not be set too low; otherwise the network could become fragmented, complicating or even preventing the routing of messages between some peers. On the second hand, the value should not be set too high or a significant amount of unnecessary load from maintenance traffic would be inflicted on the network.

What should be the exact amount (tested on networks with size 100 and 500):

The measurements indicated that k values of 1 and 2 were insufficient to prevent the fragmentation of the network. The chosen k value of 3 was enough to achieve a consistent network structure in both of the network sizes. With the k value of 4 and larger, the nodes’ knowledge of the network develops further, but at the cost of increased maintenance traffic. Even though the average hop count decreases, the larger routing table induces more KeepAlive messaging.

The "maintanance traffic" is amount of KeepAlive messages being sent. KeepAlive messages are being sent to all devices in k-buckets to ensure that connections are alive. If we didn't send them, we could one day end up with no connections, unable to participate in network. Although in this paper, they are sending several such messages per minute, I'm not sure that that much is in real life necessary.

The other use-case of k-buckets was in paper linked in this question: Kademlia: A Peer-to-peer Information System Based on the XOR Metric. I ommitted it at first, as I thought it was an original Kademlia paper. Although authors here are the same, it turns out it's content is different and they are actually talking about significance of k-buckets:

  • They promote being in network longer (the more stable node you are, the more significance in network you have)
  • They prevent DoS attacks. Flooding network with new nodes won't be destructive, since old nodes will still take place in k-buckets

A second benefit of k-buckets is that they provide resistance to certain DoS attacks. One cannot flush nodes’ routing state by flooding the system with new nodes. Kademlia nodes will only insert the new nodes in the k-buckets when old nodes leave the system

So I guess it's the second factor when choosing k value: higher k means your network is easier to hijack due to Sybil/Eclipse attack

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.