Question

When using a Kademlia-based DHT for node discovery, what is the mathematical metric used to determine the &#x27;distance&#x27; between two node IDs for routing purposes?

Accepted Answer

The mathematical metric used to determine the distance between two node IDs in a Kademlia-based Distributed Hash Table is the bitwise exclusive or, commonly referred to as XOR. A node ID is a fixed-length sequence of bits, such as a 160-bit integer. The XOR operation compares these IDs bit by bit: it outputs a 1 if the corresponding bits are different and a 0 if they are the same. For example, if you XOR 0101 with 0011, you get 0110, where the resulting value represents the distance between those two nodes. Because XOR is symmetric, the distance from node A to node B is identical to the distance from node B to node A, which ensures consistent routing paths. Furthermore, XOR satisfies the triangle inequality, meaning the distance between two nodes is always less than or equal to the sum of the distances to a third node, which allows Kademlia to organize nodes into a logical structure called a binary tree. By using XOR, Kademlia defines distance based on the position of the first differing bit, which allows nodes to efficiently route queries toward a target ID by consistently halving the remaining distance in the ID space.

Home → All Courses → Engineering and Technology Courses → Blockchain Systems Development → Flashcard

When using a Kademlia-based DHT for node discovery, what is the mathematical metric used to determine the 'distance' between two node IDs for routing purposes?