Koorde

A de Bruijn's 3-dimensional graph

Koorde is based on Chord but also on the De Bruijn graph (De Bruijn sequence). In a d-dimensional de Bruijn graph, there are 2^d nodes, each of which has a unique ID with d bits. The node with ID i is connected to nodes 2i mod 2^d and 2i + 1 mod 2^d. Thanks to this property, the routing algorithm can route to any destination in d hops by successively "shifting in" the bits of the destination ID but only if the dimensions of the distance between mod 1d and 3d are equal.

Routing a message from node m to node k is accomplished by taking the number m and shifting in the bits of k one at a time until the number has been replaced by k. Each shift corresponds to a routing hop to the next intermediate address; the hop is valid because each node's neighbors are the two possible outcomes of shifting a 0 or 1 onto its own address. Because of the structure of de Bruijn graphs, when the last bit of k has been shifted, the query will be at node k. Node k responds whether key k exists.

Example of the way Koorde routes from node 2 to node 6 using a 3-dimensional, binary graph

For example, when a message needs to be routed from node 2 (which is 010) to 6 (which is 110), the steps are following:

1. Node 2 routes the message to Node 5 (using its connection to 2i + 1 mod 8), shifts the bits left and puts 1 as the youngest bit (right side).
2. Node 5 routes the message to Node 3 (using its connection to 2i + 1 mod 8), shifts the bits left and puts 1 as the youngest bit (right side).
3. Node 3 routes the message to Node 6 (using its connection to 2i mod 8), shifts the bits left and puts 0 as the youngest bit (right side).

The d-dimensional de Bruijn can be generalized to base k, in which case node i is connected to nodes k • i + j mod kd, 0 ≤ j < k. The diameter is reduced to Θ(log_k n). Koorde node i maintains pointers to k consecutive nodes beginning at the predecessor of k • i mod kd. Each de Bruijn routing step can be emulated with an expected constant number of messages, so routing uses O(log_k n) expected hops- For k = Θ(log n), we get Θ(log n) degree and ${\displaystyle \Theta \left({\frac {\log n}{\log(\log n)}}\right)}$ diameter.

function n.lookup(k, shift, i)
{
    if k ∈ (n, s]
        return (s);
    else if i ∈ (n, s]
        return p.lookup(k, shift << 1, i ∘ topBit(shift));
    else
        return s.lookup(k, shift, i);
}

• "Internet Algorithms" by Greg Plaxton, Fall 2003:
• "Koorde: A simple degree-optimal distributed hash table" by M. Frans Kaashoek and David R. Karger:
• Chord and Koorde descriptions: