Kademlia
Sign in to save<!-- see User_talk:Kinema. I User:Bpringlemeir had ask what additional material needs cited here. The entire article is a synopsis of the original paper by Maymounkov and Mazières. If people wish more references, please give a clue as to what in article does not have adequate references on the talk page.
~22 min read
Encyclopedic overview
15 sectionsContents
- System details
- Fixed-size routing tables
- Protocol messages
- Locating nodes
- Locating resources
- Joining the network
- Accelerated lookups
- Academic significance
- Mathematical analysis of the algorithm
- Use in file sharing networks
- Implementations
- Networks
- See also
- References
- External links
Kademlia is a distributed hash table for decentralized peer-to-peer computer networks designed by Petar Maymounkov and David Mazières in 2002. It specifies the structure of the network and the exchange of information through node lookups. Kademlia nodes communicate among themselves using UDP. A virtual or overlay network is formed by the participant nodes. Each node is identified by a number or node ID. The node ID serves not only as identification, but the Kademlia algorithm uses the node ID to locate values (usually file hashes or keywords).
In order to look up the value associated with a given key, the algorithm explores the network in several steps. Each step will find nodes that are closer to the key until the contacted node returns the value or no more closer nodes are found. This is very efficient: like many other s, Kademlia contacts only O(\log n) nodes during the search out of a total of n nodes in the system.
Excerpted from Wikipedia’s “Kademlia” article, available under the CC BY-SA 4.0 licence.