Kademlia is one implementation of a Distributed Hash Table.
The 3 parameters:
- Address space: a way to uniquely identify all the peers in a network.
- A metric to order the peers in the address space and therefore be able to visualize them along an ordered line.
- A projection that will take a record key and calculate a position in the address space where the peer(s) most ideally suited to store the record should be near.
- Peers can join (or leave) at any time hence it’s unstable.
- Each peer keeps links to the peers located at $2n$ of distance.
- For each multiple of 2, each peer keeps up to $K$ links.
- $K$ is determined based on the observed average churn in the network and the frequency with which the network republishes information.
- Computed to maximize the probability of keeping the network connected while maintaining good latency values for queries.
- Allow to search the network as if it was a sorted list.
- Allows for a lookup time of $O(\log(N))$ where $N$ is the size of the network.