Koorde

In peer-to-peer networks, Koorde is a distributed hash table (DHT) system based on the Chord DHT and the De Bruijn graph (De Bruijn sequence).

In a d-dimensional de Bruijn graph, there are 2d nodes, each of which has a unique ID with d bits.

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.

Each de Bruijn routing step can be emulated with an expected constant number of messages, so routing uses O(logk n) expected hops- For k = Θ(log n), we get Θ(log n) degree and ⁠