Kademlia

Peer-to-peer networks are made of nodes, by design. The protocols that these nodes use to communicate, and locate information, have become more efficient over time. The first generation peer-to-peer file sharing networks, such as Napster, relied on a central database to co-ordinate lookups on the network. Second generation peer-to-peer networks, such as Gnutella, used flooding to locate files, searching every node on the network. Third generation peer-to-peer networks, such as Bittorrent, use distributed hash tables to look up files in the network. Distributed hash tables store resource locations throughout the network.

Kademlia uses a "distance" calculation between two nodes. This distance is computed as the exclusive or (XOR) of the two node IDs, taking the result as an unsigned integer number. Keys and node IDs have the same format and length, so distance can be calculated among them in exactly the same way. The node ID is typically a large random number that is chosen with the goal of being unique for a particular node (see UUID). It can and does happen that geographically far nodes – from Germany and Australia, for instance – can be "neighbors" if they have chosen similar random node IDs.

XOR was chosen because it acts as a distance function between all the node IDs. Specifically:

• the distance between a node and itself is zero
• it is symmetric: the "distances" calculated from A to B and from B to A are the same
• it follows the triangle inequality: given A, B and C are vertices (points) of a triangle, then the distance from A to B is shorter than (or equal to) the sum of both the distance from A to C and the distance from C to B.

These three conditions are enough to ensure that XOR captures all of the essential, important features of a "real" distance function, while being cheap and simple to calculate.[1]

Each Kademlia search iteration comes one bit closer to the target. A basic Kademlia search algorithm has complexity of O(log₂ (n)), that means for network with ${\textstyle 2^{n}}$ nodes it will take at most ${\displaystyle n}$ steps to find that node.

Fixed-size routing tables

This section is simplified to use a single bit; see #Accelerated lookups for more information on real routing tables.

Fixed-size routing tables were presented in the pre-proceedings version of the original paper[4] and are used in the later version only for some mathematical proofs. An actual Kademlia implementation does not have a fixed-size routing table, but a dynamically sized one.

Kademlia routing tables consist of a list for each bit of the node ID (e.g. if a node ID consists of 128 bits, a node will keep 128 such lists.) Every entry in a list holds the necessary data to locate another node. The data in each list entry is typically the IP address, port, and node ID of another node. Every list corresponds to a specific distance from the node. Nodes that can go in the n^th list must have a differing n^th bit from the node's ID; the first n-1 bits of the candidate ID must match those of the node's ID. This means that it is very easy to populate the first list as 1/2 of the nodes in the network are far away candidates. The next list can use only 1/4 of the nodes in the network (one bit closer than the first), etc.

With an ID of 128 bits, every node in the network will classify other nodes in one of 128 different distances, one specific distance per bit.

As nodes are encountered on the network, they are added to the lists. This includes store and retrieval operations and even helping other nodes to find a key. Every node encountered will be considered for inclusion in the lists. Therefore, the knowledge that a node has of the network is very dynamic. This keeps the network constantly updated and adds resilience to failures or attacks.

In the Kademlia literature, the lists are referred to as k-buckets. k is a system wide number, like 20. Every k-bucket is a list having up to k entries inside; i.e. for a network with k=20, each node will have lists containing up to 20 nodes for a particular bit (a particular distance from itself).

Since the possible nodes for each k-bucket decreases quickly (because there will be very few nodes that are that close), the lower bit k-buckets will fully map all nodes in that section of the network. Since the quantity of possible IDs is much larger than any node population can ever be, some of the k-buckets corresponding to very short distances will remain empty.

Network partition for node 110

Consider the simple network to the right. The network size is 2^3 or eight maximum keys and nodes. There are seven nodes participating; the small circles at the bottom. The node under consideration is node six (binary 110) in black. There are three k-buckets for each node in this network. Nodes zero, one and two (binary 000, 001, and 010) are candidates for the farthest k-bucket. Node three (binary 011, not shown) is not participating in the network. In the middle k-bucket, nodes four and five (binary 100 and 101) are placed. Finally, the third k-bucket can only contain node seven (binary 111). Each of the three k-buckets are enclosed in a gray circle. If the size of the k-bucket was two, then the farthest 2-bucket can only contain two of the three nodes. For example, if node six has node one and two in the farthest 2-bucket, it would have to request a node ID lookup to these nodes to find the location (ip address) of node zero. Each node knows its neighbourhood well and has contact with a few nodes far away which can help locate other nodes far away.

It is known that nodes that have been connected for a long time in a network will probably remain connected for a long time in the future.[5][6] Because of this statistical distribution, Kademlia selects long connected nodes to remain stored in the k-buckets. This increases the number of known valid nodes at some time in the future and provides for a more stable network.

When a k-bucket is full and a new node is discovered for that k-bucket, the least recently seen node in the k-bucket is PINGed. If the node is found to be still alive, the new node is placed in a secondary list, a replacement cache. The replacement cache is used only if a node in the k-bucket stops responding. In other words: new nodes are used only when older nodes disappear.

While the XOR metric is not needed to understand Kademlia, it is critical in the analysis of the protocol. The XOR arithmetic forms an abelian group allowing closed analysis. Other DHT protocols and algorithms require simulation or complicated formal analysis in order to predict network behavior and correctness. Using groups of bits as routing information also simplifies the algorithms.

To analyze the algorithm, consider a Kademlia network of ${\displaystyle n}$ nodes with IDs ${\displaystyle x_{1},\ldots ,x_{n}}$, each of which is a string of length ${\displaystyle d}$ that consists of only ones and zeros. It can be modeled as a trie, in which each leaf represents a node, and the labeled path from the root to a leaf represents its ID. For a node ${\displaystyle x\in \{x_{1},\ldots ,x_{n}\}}$, let ${\displaystyle {\mathcal {D}}_{i}(x)}$ be the set of nodes (IDs) that share a prefix with ${\displaystyle x}$ of length ${\displaystyle d-i}$. Then filling the ${\displaystyle i}$-th bucket of ${\displaystyle x}$ can be modeled as adding pointers from the leaf ${\displaystyle x}$ to ${\displaystyle k}$ leaves (IDs) chosen uniformly at random from ${\displaystyle {\mathcal {D}}_{i}(x)}$. Thus routing can be seen as jumping among the leaves along these pointers such that each step goes towards the target ID as much as possible, i.e., in a greedy way.

Let ${\displaystyle T_{xy}}$ be number of jumps needed to go from the leaf ${\displaystyle x}$ to a target ID ${\displaystyle y}$. Assuming that ${\displaystyle x_{1},\ldots ,x_{n}}$ are chosen deterministically from ${\displaystyle \{0,1\}^{d}}$, it has been proved that

${\displaystyle \sup _{x_{1},\ldots ,x_{n}}\,\sup _{x\in \{x_{1},\ldots ,x_{n}\}}\,\sup _{y\in \{0,1\}^{d}}\mathbb {E} [T_{xy}]\leq (1+o(1)){\frac {\log n}{H_{k}}},}$

where ${\displaystyle H_{k}}$ is the ${\displaystyle k}$-th harmonic number. Since ${\displaystyle H_{k}/\log k\to 1}$ as ${\displaystyle k\to \infty }$, when ${\displaystyle k}$ is large ${\displaystyle \mathbb {E} T_{xy}}$ is bounded from above by about ${\displaystyle \log _{k}n}$, however the IDs and the target are chosen.[7] This justifies the intuition that in Kademlia only ${\displaystyle O(\log n)}$ nodes are contacted in searching for a target node.

To make the model closer to real Kademlia networks, ${\displaystyle x_{1},\ldots ,x_{n}}$ can also be assumed to be chosen uniformly at random without replacement from ${\displaystyle \{0,1\}^{d}}$. Then it can be proved that for all ${\displaystyle x\in \{x_{1},\ldots ,x_{n}\}}$ and ${\displaystyle y\in \{0,1\}^{d}}$,

${\displaystyle {\begin{aligned}&T_{xy}{\xrightarrow {p}}{\frac {\log n}{c_{k}}},\\&\mathbb {E} [T_{xy}]\to {\frac {\log n}{c_{k}}},\end{aligned}}}$

where ${\displaystyle c_{k}}$ is a constant depending only on ${\displaystyle k}$ with ${\displaystyle c_{k}/H_{k}\to 1}$ as ${\displaystyle k\to \infty }$. Thus for ${\displaystyle k}$ large, ${\displaystyle \mathbb {E} T_{xy}/\log _{k}n}$ converges to a constant close ${\displaystyle 1}$. This implies that the number of nodes need to be contact in searching for a target node is actually ${\displaystyle \Theta (\log n)}$ on average.[8]

Kademlia is used in file sharing networks. By making Kademlia keyword searches, one can find information in the file-sharing network so it can be downloaded. Since there is no central instance to store an index of existing files, this task is divided evenly among all clients: If a node wants to share a file, it processes the contents of the file, calculating from it a number (hash) that will identify this file within the file-sharing network. Since file hashes and node IDs have the same length, the client can use the XOR distance function to search for several nodes whose ID is close to the hash, and instructs those nodes to store the publisher's IP address in an implementation-defined manner. Nodes with IDs closest to the file hash will therefore have a list of IP addresses of peers/publishers of this file, from which a client may in an implementation-defined manner download the file.

Clients that wish to download the file from this publisher do not have to know the publisher's IP address (there can be many publishers), but only the hash of the file. A searching client will use Kademlia to search the network for the node whose ID has the smallest distance to the file hash, then will retrieve the sources list that is stored in that node.

Since a key can correspond to many values, e.g. many sources of the same file, every storing node may have different information. Then, the sources are requested from all k nodes close to the key, k being the size of the bucket.

The file hash is usually obtained from a specially formed Internet magnet link found elsewhere, or included within an indexing file obtained from other sources.

Filename searches are implemented using keywords. The filename is divided into its constituent words. Each of these keywords is hashed and stored in the network, together with the corresponding filename and file hash. A search involves choosing one of the keywords, contacting the node with an ID closest to that keyword hash, and retrieving the list of filenames that contain the keyword. Since every filename in the list has its hash attached, the chosen file can then be obtained in the normal way.

• Content-addressable network
• Chord (peer-to-peer)
• Tapestry (DHT)
• Pastry (DHT)
• Koorde

• Xlattice projects Kademlia Specification and definitions.