undefined | Better HN

0 pointsjesprenj1y ago0 comments

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.

0 comments

3 comments · 1 top-level

anacrolix1y ago· 2 in thread

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.

jesprenjOP1y ago

Yes, but where did sqrt come from that the parent commenter mentioned?

schanzen1y ago

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.

1 more reply

j / k navigate · click thread line to collapse