peer-to-peer Peer-to-peer (P2P) computing or networking is a distributed application architecture that partitions tasks or workloads between peers. Peers are equally privileged, equipotent participants in the network. They are said to form a peer-to-peer n ...

networks, Koorde is a

distributed hash table A distributed hash table (DHT) is a distributed system that provides a lookup service similar to a hash table: key–value pairs are stored in a DHT, and any participating node can efficiently retrieve the value associated with a given key. The m ...

(DHT) system based on the Chord DHT and the

De Bruijn graph In graph theory, an -dimensional De Bruijn graph of symbols is a directed graph representing overlaps between sequences of symbols. It has vertices, consisting of all possible sequences of the given symbols; the same symbol may appear multiple ...

(

De Bruijn sequence In combinatorial mathematics, a de Bruijn sequence of order ''n'' on a size-''k'' alphabet ''A'' is a cyclic sequence in which every possible length-''n'' string on ''A'' occurs exactly once as a substring (i.e., as a ''contiguous'' subseq ...

). Inheriting the simplicity of Chord, Koorde meets hops per

node In general, a node is a localized swelling (a "knot") or a point of intersection (a vertex). Node may refer to: In mathematics *Vertex (graph theory), a vertex in a mathematical graph *Vertex (geometry), a point where two or more curves, lines, ...

(where is the number of nodes in the DHT), and hops per lookup request with neighbors per node. The Chord concept is based on a wide range of

identifiers An identifier is a name that identifies (that is, labels the identity of) either a unique object or a unique ''class'' of objects, where the "object" or class may be an idea, physical countable object (or class thereof), or physical noncountable ...

(e.g. 2) in a structure of a

ring Ring may refer to: * Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry * To make a sound with a bell, and the sound made by a bell :(hence) to initiate a telephone connection Arts, entertainment and media Film and ...

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

De bruijn graph-for binary sequence of order 4

Koorde is based on Chord but also on the

(

). In a -dimensional de Bruijn graph, there are

nodes In general, a node is a localized swelling (a "knot") or a point of intersection (a Vertex (graph theory), vertex). Node may refer to: In mathematics *Vertex (graph theory), a vertex in a mathematical graph *Vertex (geometry), a point where two ...

, each of which has a unique ID with

bit The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represente ...

s. The node with ID is connected to nodes and . Thanks to this property, the

routing algorithm Routing is the process of selecting a path for traffic in a Network theory, network or between or across multiple networks. Broadly, routing is performed in many types of networks, including circuit switching, circuit-switched networks, such as ...

can route to any destination in hops by successively "shifting in" the bits of the destination ID but only if the dimensions of the

distance Distance is a numerical or occasionally qualitative measurement of how far apart objects or points are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two counties over"). ...

between and are equal. Routing a message from node to node is accomplished by taking the number and shifting in the bits of one at a time until the number has been replaced by . 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 has been shifted, the query will be at node . Node responds whether key exists.

Routing example

For example, when a message needs to be routed from node 2 (which is ) to 6 (which is ), the steps are following: # Node 2 routes the message to Node 5 (using its connection to ), shifts the bits left and puts as the youngest bit (right side). # Node 5 routes the message to Node 3 (using its connection to ), shifts the bits left and puts as the youngest bit (right side). # Node 3 routes the message to Node 6 (using its connection to ), shifts the bits left and puts as the youngest bit (right side).

Non-constant degree Koorde

The -dimensional de Bruijn can be generalized to base , in which case node is connected to nodes , . The

diameter In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid for ...

is reduced to . Koorde node maintains

pointers Pointer may refer to: Places * Pointer, Kentucky * Pointers, New Jersey * Pointers Airport, Wasco County, Oregon, United States * The Pointers, a pair of rocks off Antarctica People with the name * Pointer (surname), a surname (including a l ...

to consecutive nodes beginning at the predecessor of . Each de Bruijn routing step can be emulated with an expected constant number of messages, so routing uses expected hops- For , we get degree and diameter.

Lookup algorithm

function n.lookup(k, shift, i)

Pseudocode In computer science, pseudocode is a plain language description of the steps in an algorithm or another system. Pseudocode often uses structural conventions of a normal programming language, but is intended for human reading rather than machine re ...

for the Koorde lookup algorithm at node : * is the key * is the imaginary De Bruijn node * is the reference to the predecessor of * is the reference to the successor of {{code, n

References

*"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

File sharing networks Distributed data storage Hash based data structures Hashing