Where does sqrt come from? Shouldn't it be log? I don't know much about DHTs, but Kademila (BitTorrent's DHT) has query complexity of around O(log n), with n being the total number of nodes in the network. Kademila also uses random node IDs and XOR disrance metric.
BitTorrent's mainline DHT is O(log n). Base 2. However you can usually skip 2-3 bits per round of queries. This means you can locate any of the 20 million nodes in BitTorrent in about 7 hops. In practice it's about 20 queries and takes about 3-5s. No persistent connections. Barely a few KB of memory for every client. No other real world implementation is that good.
Co-author here. If you look into the R5N paper (link in draft), you can find this term. If you assume a routing performance of O(log n) and O(sqrt (n)) number of lookups to find the value, you get O (sqrt (n) * log n) as overall complexity (last section in paper).
For the argument of the sqrt (n) itself, see the paper.
Edit 1: Quote: "Assuming that T [random path length] is chosen large enough to achieve perfect mixing, sqrt (n / (c−1)) replicas would need to be created in order for a GET request to succeed with about 50% probability according
to the birthday paradox."
Edit 2: In a world without local minima the term itself will be 1 (you only need a single lookup and will find the value with 100% probability.
In the restricted route scenario you will have to so O(sqrt(n)) lookups.
Aha, thanks for that, the paper seems to reason better at first glance, I'll read it.
You mention sybil attacks on Kademlia, especially those that arise because nodes may set their ID and "camp around" some known key in the hash table. How is this addressed here? By glancing over the standard draft, I see the identifier is just a SHA-512 of the pubkey. Wouldn't it be feasible to bruteforce the first some bits of the key and "camp around" some keys a malicious sybil actor wants to deny service to?
