kelseyc18 / kademlia_vis Goto Github PK

join step 6 visualisation shows the same value for the nearest node as for the distance:

The following nodes are the k closest to Target ID 0b011100 (28):
    0b000001 (1) - distance 1
    0b001011 (11) - distance 11
    0b010101 (21) - distance 21
    0b011111 (31) - distance 31

Should be

The following nodes are the k closest to Target ID 0b011100 (28):
    0b000001 (1) - distance 29
    0b001011 (11) - distance 23
    0b010101 (21) - distance 9
    0b011111 (31) - distance 3

I traced it to displayFinalKContacts but I don't know JS well enough to figure out what's wrong.

Hello! Thanks for this visualization, it's great to have tools like this.

I was trying to verify my understanding and tried

Looking up ID 0b110010 (50) from Node 0b110001 (49).

We will use system-wide parameters k = 4 and alpha = 3.

These are almost neighbors, but the closest neighbors for 50 are:
red:

0b000001
(1)
0b000100
(4)
0b000101
(5)
0b000110
(6)

yellow:

0b100010
(34)
0b101011
(43)

green:

0b111100
(60)
0b111110
(62)

The simulation says:

Round 1 contacts are 0b000001 (1), 0b000100 (4), 0b000101 (5).

This seems incorrect intuitively to me, and the paper seems to be ambiguous so I'm not 100% sure. My intuition is that each hop should move closer to the destination node, backing up only if those nodes don't return closer nodes themselves. So in this case I'd expect it to select nodes from the green group, then yellow.

For reference, the paper says:

The lookup initiator starts by picking α nodes from its closest non-empty k-bucket (or, if that bucket has fewer than α entries, it just takes the α closest nodes it knows of).

I think "closest" must mean the k-bucket containing nodes the same distance from the initiator as the destination is from the initiator... which I think mathematically should be closer to the destination than any other node in any other bucket.

And then I guess it would try lower-k buckets, then higher-k buckets, because all lower-k buckets will be in the same subtree compared to higher k-buckets...

I tried

0b110111 (55) from Node 0b111100 (60)

too and it selects the neighbor in the closest k-bucket but then skips to red again and ignores yellow and pink which are both closer.