Kademlia & structured P2P overlays

Click through the three targets. The two "closest" nodes are a completely different pair each time — not because the nodes moved, but because XOR distance depends only on which bits differ, not on how far apart the numbers look.

Kademlia measures distance between two ids by XOR-ing them together and reading the result as a number:

Every node keeps its known peers in k-buckets: bucket $i$ holds peers at distance $[2^i,\, 2^{i+1})$ from itself. A lookup for target $t$ simply asks whichever known peers are currently closest to $t$, who in turn know peers even closer — narrowing in each round.

• $a \oplus b$ — bitwise XOR: a 1 in a bit position exactly where $a$ and $b$ differ there.
• bucket $i$ — holds peers at distance $2^i$ to $2^{i+1}-1$ from self; low $i$ means "very close."
• closest-$k$ — the $k$ known ids with the smallest $d(\cdot, t)$ to a target $t$; the contact list a lookup uses.

1. XOR ignores magnitude entirely

   $d(a,b)$ depends only on which bits differ, never on which number is "bigger" — ids $0$ and $15$ can be just as close as ids $6$ and $7$, if the right bits happen to match.

2. Distance is symmetric and zero only for identical ids

   $a \oplus b = b \oplus a$, and $a \oplus b = 0$ exactly when $a = b$ — so XOR behaves like a genuine distance, just not a familiar numeric one.

Drag the target id across the whole range and switch $k$ between 1, 2, and 3. The bars resort completely with every move — there's no "nearby" region of the number line the way there was on Chord's ring; closeness is purely bitwise.

Self is node $6$ (binary $0110$); other known nodes are $\{7, 4, 3, 0, 9, 13\}$:

1. Every node's k-bucket, by hand

   • $d(6,7)=6\oplus7=1$ (bucket 0)
   • $d(6,4)=6\oplus4=2$ (bucket 1)
   • $d(6,3)=6\oplus3=5$ (bucket 2, since $4 \le 5 < 8$)
   • $d(6,0)=6\oplus0=6$ (bucket 2, since $4 \le 6 < 8$)
   • $d(6,9)=6\oplus9=15$ (bucket 3, since $8 \le 15 < 16$)
   • $d(6,13)=6\oplus13=11$ (bucket 3, since $8 \le 11 < 16$)
2. Closest 3 to target 10

   • $d(9,10)=9\oplus10=3$
   • $d(13,10)=13\oplus10=7$
   • $d(3,10)=3\oplus10=9$
   • $d(0,10)=0\oplus10=10$
   • $d(7,10)=7\oplus10=13$
   • $d(4,10)=4\oplus10=14$

   Sorted ascending, the 3 nearest are $\{9, 13, 3\}$ — none of them is even in the same bucket as another.

3. Closest 2 to target 1

   • $d(0,1)=0\oplus1=1$
   • $d(3,1)=3\oplus1=2$
   • $d(4,1)=4\oplus1=5$
   • $d(7,1)=7\oplus1=6$
   • $d(9,1)=9\oplus1=8$
   • $d(13,1)=13\oplus1=12$

   The 2 nearest are $\{0, 3\}$ — the same pair that shares bucket 2 relative to self, because both happen to share their two lowest bits with target $1$.