| • Science | • People | • Locations | • Timeline |
Over an existing LAN/ WAN (like the Internet) a new, virtual network , is created in which each network node is identified by a number ("Node ID"). This number serves not only as its identification, but the Kademlia algorithm uses it for further purposes.
A node, which would like to join the net, must first go through a bootstrap process: In this phase, the node needs to know the IP address of another node (obtained from the user, or from a stored list), which is already participating in the Kademlia network. If the bootstrapping node has not participated before in the network, it computes a random ID number that is not already assigned to any other node. It uses this ID until leaving the network.
The Kademlia algorithm is based on the calculation of the "distance" between two nodes. This distance is computed as the exclusive or of the two node IDs, taking the result as an integer number.
This "distance" does not have anything to do with geographical conditions, but designates the distance within the ID range. Thus it can and does happen that e.g. a node from Germany and one from Australia are "neighbours".
Information within Kademlia is stored in so called "values", every value being attached to a "key".
When searching for some key, the algorithm explores the network in several steps, each step approaching closer to the searched-for key, until the contacted node returns the value, or no more closer nodes are found. The number of nodes contacted during the search is only marginally dependent on the size of the network: If the number of participants in the net doubles in number, then a user's node must query only one more node per search, not twice as many.
Further advantages are found particularly in the decentralized structure, which clearly increases the resistance against a denial of service attack. Even if a whole set of nodes are flooded, this will have limited effect on network availability, which will recover itself by knitting the network around these "holes".
Kademlia has been used for file sharingFile sharing is the activity of making files available to other users for download over the Internet, but also over smaller networks. Usually file sharing follows the peer-to-peer (P2P) model, where the files are stored on and served by personal computers. 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: The node that possesses a file it wants to share, processes the contents of the file, calculating from it a number ( hashA hash function is a function that converts an input from a (typically) large domain into an output in a (typically) smaller range (the hash value often a subset of the integers). Hash functions vary in the domain of their inputs and the range of their ou) that will identify this file within the file-sharing network. The hashes and the node IDs must be of the same length. The searching client will use Kademlia to search the network for the node whose ID has the smallest distance to the filehash, then will retrieve the contacts list that is stored in that node. The contacts stored in the network are under constant change as nodes connect and disconnect. Due to built-in redundancyRedundancy in general terms, refers to the quality or state of being redundant that is: exceeding what is necessary or normal, containing an excess. This can have a negative connotation, superfluous, but also positive, serving as a duplicate for preventin, these contacts are replicated in several nodes.
Public clients using the Kademlia algorithm (networks are incompatible with one another):