11

I can't quite wrap my brain around the joining process of Kademlia DHTs. I've seen a few tutorials and presentations online, but they all seem to say things the same way and all psedo code etc is the same in most (actual copy/paste).

Can somebody give a high level walk through on this?

Joshua Kissoon
  • 3,269
  • 6
  • 32
  • 58
JSON
  • 1,819
  • 20
  • 27

2 Answers2

25

I'm assuming you've read the Kademlia paper. Here's an excerpt from my article An Introduction to Kademlia DHT & How It Works

Some background information:

  1. When you have a Kademlia network running, there should always be a node that every other node knows about in order for them to join the network; lets call this the Bootstrap node BN.

  2. K is a Kademlia constant that determines the size of the Buckets in a node's routing table as well as the amount of nodes a piece of Data should be stored on.

Joining Process:

  1. A new Node NN is created with a NodeId (assigned by some method) and an IP Address (the IP of the computer it's hosted on).

  2. NN sends a LookupRequest(A.NodeId) to BN. A Lookup Request basically asks the receiving node for the K-Closest nodes it knows to a given NodeId. In this case, BN will return the K-Closest nodes it knows to NN.

  3. BN will now add NN to it's routing table, so NN is now in the network.

  4. NN receives the list of K-Closest nodes to itself from BN. NN adds BN to it's routing table.

  5. NN now pings these K nodes received from BN, and the ones that reply are added to it's Routing Table in the necessary buckets based on distance. By pinging these nodes, they also learn of NN existence and add NN to their Routing tables.

  6. NN is now connected to the network and is known by nodes on the network.

  7. NN now loops through each of it's K-Buckets

    foreach(K-Buckets as KB)         
    1. NN generates a random NodeId `RNID` // A NodeId that will be in KB 
    2. NN sends LookupRequest(RNID) to the K-Closest nodes it knows to RNID. 
    3. The response will be K nodes closest to RNID.
    4. NN now fills KB.

    NN does this for each of it's buckets to fill these buckets. After this operation, NN has a better idea of the nodes on the network at different distances away from itself.

    Note: This step is not mandatory, however I did it in My Implementation of Kademlia so that each node will have better knowledge of the network when they join.

I wrote a full introduction to Kademlia at An Introduction to Kademlia DHT & How It Works

gravetii
  • 9,273
  • 9
  • 56
  • 75
Joshua Kissoon
  • 3,269
  • 6
  • 32
  • 58
  • Is it possible to perhaps simplify this a bit? Step 2 could be NN adds BN into its own routing table and performs a lookup operation on itself. Thus, the k-neighbors would become aware of the new node and add it into their own routing tables. I think this approach would save us from performing additional pings – nz_21 Mar 29 '21 at 10:01
-3

My guess is it uses some super nodes and geospatial informations to compute a minimum spanning tree. It can also compute a voronoi-diagram or the dual delaunay triangulation from the super nodes and use it to run a proximity search. Here is an example: http://www.mathworks.de/de/help/matlab/math/spatial-searching.html.

Micromega
  • 12,486
  • 7
  • 35
  • 72
  • 1
    I'll mark your answer right since your the only one who answered and the bounty runs out in in hour, but more info would be awesome. I like the idea of using triangular proximity searches, can you provide links with info on this? – JSON Oct 24 '13 at 00:28
  • 1
    Alas, that bounty was wasted. The answer is incorrect and the link 404s. – the8472 Oct 27 '17 at 18:43
  • @the8472: Feel free to give a better answer! – Micromega Oct 28 '17 at 11:47