There's also the [kademlia distributed hash table](https://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia...). The high level idea is that each node gets a random bit in the range [0, 2^m), and we define the distance to be XOR. We want to find a distributed algorithm to quickly get some information from X to Y, without knowing the whole network.
You can just look at the math and prove that it works, but my pet favorite visual interpretation of the algorithm is this:
Suppose you have a start node X, and it wants to find node k. Define the "X-distance tree" to be a binary tree, with leaf indices 0, 1, 2... But you put labels of X^leaf_index in each node, to represent the distance from a certain label to X. E.g. dist(x, x) = x^x = 0, so the label "X" (the original node) is put at the leftmost leaf (0).
The interval [2^i, 2^(i+1)) is some subtree of the X-distance tree. Let's say you know k's distance belongs in that interval, so you query some node Y in there as an approximate neighbor.
No matter what node Y you pick, the resulting prefix in the Y-distance tree will always be some permutation of the [2^i ,2^(i+1)) subtree we picked from the X-distance tree!
More specifically, my claim is that at the sets labels_of_leaves_of_X( [2^i, 2^(i+1)) ) == labels_of_leaves_of_Y( [0, 2^i) ). (recall that we index by distance, but the labels might be different).
There are far more rigorous comparisons to other DHT's like Chord, both mathematically and empircally. But to me, this visual intuition tells me what the "symmetry" of Kademlia means - sort of everybody's in their own local neighborhood, their own subtrees.
Whereas Chord, even if you implement it bi-directionally (which costs 2x memory! and seems even more treacherous to implement...), can't get this level of 'isolation' in some sense. The neighborhood sliding window of size S is always shifting: per bit, there's always 2^m distinct neighborhoods. Yea, even though most neighborhoods "look the same", it's just not pretty.
Kademlia has 1 + 2 + 4 ... + 2^m-1 neighborhoods, and it's all neat and tidy.
You can just look at the math and prove that it works, but my pet favorite visual interpretation of the algorithm is this:
Suppose you have a start node X, and it wants to find node k. Define the "X-distance tree" to be a binary tree, with leaf indices 0, 1, 2... But you put labels of X^leaf_index in each node, to represent the distance from a certain label to X. E.g. dist(x, x) = x^x = 0, so the label "X" (the original node) is put at the leftmost leaf (0).
The interval [2^i, 2^(i+1)) is some subtree of the X-distance tree. Let's say you know k's distance belongs in that interval, so you query some node Y in there as an approximate neighbor.
No matter what node Y you pick, the resulting prefix in the Y-distance tree will always be some permutation of the [2^i ,2^(i+1)) subtree we picked from the X-distance tree!
More specifically, my claim is that at the sets labels_of_leaves_of_X( [2^i, 2^(i+1)) ) == labels_of_leaves_of_Y( [0, 2^i) ). (recall that we index by distance, but the labels might be different).
There are far more rigorous comparisons to other DHT's like Chord, both mathematically and empircally. But to me, this visual intuition tells me what the "symmetry" of Kademlia means - sort of everybody's in their own local neighborhood, their own subtrees.
Whereas Chord, even if you implement it bi-directionally (which costs 2x memory! and seems even more treacherous to implement...), can't get this level of 'isolation' in some sense. The neighborhood sliding window of size S is always shifting: per bit, there's always 2^m distinct neighborhoods. Yea, even though most neighborhoods "look the same", it's just not pretty.
Kademlia has 1 + 2 + 4 ... + 2^m-1 neighborhoods, and it's all neat and tidy.