0

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.

codewario
  • 19,553
  • 20
  • 90
  • 159
Marlo
  • 207
  • 1
  • 4
  • 12

2 Answers2

0

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.

the8472
  • 40,999
  • 5
  • 70
  • 122
0

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.

marxum
  • 13
  • 3
  • Thanks @marxum. What I don't understand is that any node can then either only store one value, accessible from the key that coincides with the node's Id, or it may store multiple values but all accessible from the same key, namely its node Id??? Both options seem to me very sub-optimal. – Marlo May 29 '22 at 10:22
  • Actually this post kindof solves my problem https://stackoverflow.com/questions/59657964/what-does-it-mean-by-kademlia-keys-are-used-to-identify-nodes-as-well-as-data?rq=1 – Marlo May 29 '22 at 10:40