Why is Behavior::find_closest_local_peers() limited to the replication_factor instead of K_VALUE?

[mickvandijke]

When performing a FIND_NODE request, we expect a node to return up to K closest nodes to the key, as specified in the Kademlia protocol. However, Libp2p limits the number of returned nodes to the replication_factor:
https://github.com/libp2p/rust-libp2p/blob/master/protocols/kad/src/behaviour.rs#L773-L783 .

By default, replication_factor is set to K_VALUE:

rust-libp2p/protocols/kad/src/query.rs

Line 274 in f4322c5

replication_factor: NonZeroUsize::new(K_VALUE.get()).expect("K_VALUE > 0"),

.
However, it can be manually adjusted. For instance, our application sets the replication factor to 7 using this function here:

rust-libp2p/protocols/kad/src/behaviour.rs

Line 256 in f4322c5

pub fn set_replication_factor(&mut self, replication_factor: NonZeroUsize) -> &mut Self {

, meaning FIND_NODE returns only up to 7 nodes instead of K = 20, which seems unexpected.

Could someone clarify the reasoning behind limiting the results to replication_factor instead of K?

Thanks in advance!

[drHuangMHT]

cc @guillaumemichel since you are more familiar with Kadelima.

[guillaumemichel]

Thanks @drHuangMHT for the heads up!

---

AFAIK the Kademlia K has been used as the default value for 3 things:

1. Bucket size
2. Number of closest peers returned by a lookup request
3. Replication factor

There is no strict requirement that all 3 values should be the same. In your example, it is totally fine to set a replication factor lower than K.

I think the reason for which replication_factor is used instead of K is because K isn't present in the QueryConfig, but by default replication_factor is set to K, so it is correct as long as the replication factor isn't modified.

I would suggest to adapt the code to allow a replication factor distinct from K, and a proper use of both of them. Feel free to tag me to review the PR.

[mickvandijke]

Hey @guillaumemichel,

Thank you for the quick reply!

I think the reason for which replication_factor is used instead of K is because K isn't present in the QueryConfig, but by default replication_factor is set to K, so it is correct as long as the replication factor isn't modified.

Wouldn't it make more sense to limit the number of peers returned in FIND_NODE responses to the K_VALUE constant rather than using replication_factor? Also, when you call get_closest_peers() you will still get the K closest peers in the final result. But when you set the replication factor to something lower than K, say 7. Then only the 7 closest peers will be accurate. The remaining 13 peers (considering K = 20), will not necessarily be one of the K closest peers.

I was wondering if that cascades unexpected behaviour into other parts of the Kad logic, such as bootstrapping / bucket refreshing, because that also relies on get_closest_peers() / FIND_NODE?

[guillaumemichel]

Yes, you are right. I answered in #5971

[mickvandijke]

Example PR of the change that I want to propose: #5971

I don't understand why you would want the amount of results here to be different than K 🤔 .