How can one find the value for a given a key in kademlia?

Question

Kademlia has 4 RPC messages:

1. ping
2. store
3. find_node
4. find_value

How does a Kademlia node find the value for a given key? Given an id, it is clear that it will take only $log(n)$ steps for a node in a network of size $n$ to find the node with that id. But how can a node efficiently find another node that has stored a given key-value pair? It would have to be of the order of $n$ nodes to retrieve the value for a key if one knew nothing about the node holds it.

Answer 1

Kademlia is a DHT, a distributed hash table. Retrieval is conceptually similar to a regular in-memory hash table. You first hash the key to find the place where in the table you would fine the ID and then you look at that location. In kademlia this means you do a targeted lookup towards the ID equals the hash of the key.

Answer 2

In Kademlia, each node contains a hash table of the form <key,value> where the key associated with each value is a node's ID. This <key,value> entry is then stored in the k-closest nodes to the key. The find_value RPC works similarly to a find_node. First query the k-closest nodes you know to that key, they return the value associated with the key (if they have it) or their k-closest nodes to the key.