# Koorde

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Koorde
> Markdown URL: https://mediated.wiki/source/Koorde.md
> Source: https://en.wikipedia.org/wiki/Koorde
> Source revision: 1163193878
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Distributed hash table system for peer-to-peer networks

In [peer-to-peer](/source/Peer-to-peer) networks, **Koorde** is a [distributed hash table](/source/Distributed_hash_table) (DHT) system based on the [Chord DHT](/source/Chord_(DHT)) and the [De Bruijn graph](/source/De_Bruijn_graph) ([De Bruijn sequence](/source/De_Bruijn_sequence)). Inheriting the simplicity of Chord, Koorde meets [*O*](/source/Big_O_notation)(log *n*) hops per [node](/source/Node_(networking)) (where n is the number of nodes in the DHT), and ⁠ O ( log ⁡ n log ⁡ ( log ⁡ n ) ) {\displaystyle O\left({\frac {\log n}{\log(\log n)}}\right)} ⁠ hops per lookup request with *O*(log *n*) neighbors per node.

The Chord concept is based on a wide range of [identifiers](/source/Network_address) (e.g. 2160) in a structure of a [ring](/source/Ring_network) where an identifier can stand for both node and data. Node-successor is responsible for the whole range of IDs between itself and its predecessor.

## De Bruijn's graphs

A de Bruijn's 3-dimensional graph

Koorde is based on Chord but also on the [De Bruijn graph](/source/De_Bruijn_graph) ([De Bruijn sequence](/source/De_Bruijn_sequence)). In a d-dimensional de Bruijn graph, there are 2*d* [nodes](/source/Vertex_(graph_theory)), each of which has a unique [ID](/source/Network_address) with d [bits](/source/Bit). The node with ID i is connected to nodes 2*i* [mod](/source/Modular_arithmetic) 2*d* and 2*i* + 1 mod 2*d*. Thanks to this property, the [routing algorithm](/source/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](/source/Distance_(graph_theory)) between mod 1*d* and 3*d* are equal.

Routing a message from node m to node k is accomplished by taking the number m and [shifting](/source/Bitwise_operation#Bit_shifts) 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.

## Routing example

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 2*i* + 1 mod 8), shifts the bits left and puts 1 as the youngest bit (right side).

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

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

## Non-constant degree Koorde

The d-dimensional de Bruijn can be generalized to [base](/source/Radix) k, in which case node i is connected to nodes *k* • *i* + *j* mod *kd*, 0 ≤ *j* < *k*. The [diameter](/source/Distance_(graph_theory)#Related_concepts) is reduced to [Θ](/source/Big_O_notation#Related_asymptotic_notations)(log*k* *n*). Koorde node i maintains [pointers](/source/Pointer_(computer_programming)) 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 ⁠ Θ ( log ⁡ n log ⁡ ( log ⁡ n ) ) {\displaystyle \Theta \left({\frac {\log n}{\log(\log n)}}\right)} ⁠ diameter.

### Lookup algorithm

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);
}

[Pseudocode](/source/Pseudocode) for the Koorde lookup algorithm at node n:

- k is the key

- I is the imaginary De Bruijn node

- p is the reference to the predecessor of 2n

- s is the reference to the successor of n

## References

- "Internet Algorithms" by Greg Plaxton, Fall 2003: [\[1\]](https://web.archive.org/web/20040929211835/http://www.cs.utexas.edu/users/plaxton/c/395t/slides/DynamicTopologies-2.pdf)

- "Koorde: A simple degree-optimal distributed hash table" by M. Frans Kaashoek and David R. Karger: [\[2\]](http://iptps03.cs.berkeley.edu/final-papers/koorde.ps)

- Chord and Koorde descriptions: [\[3\]](http://www.cs.jhu.edu/~scheideler/courses/600.348_F03/lecture_10.pdf)

---
Adapted from the Wikipedia article [Koorde](https://en.wikipedia.org/wiki/Koorde) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Koorde?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.