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, forming a peer-to-peer network of Node ...

networks, Koorde is a

distributed hash table A distributed hash table (DHT) is a Distributed computing, distributed system that provides a lookup service similar to a hash table. Key–value pairs are stored in a DHT, and any participating node (networking), node can efficiently retrieve the ...

(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 combinatorics, combinatorial mathematics, a de Bruijn sequence of order ''n'' on a size-''k'' alphabet (computer science), alphabet ''A'' is a cyclic sequence in which every possible length-''n'' String (computer science)#Formal theory, stri ...

). 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, person, physical countable object (or class thereof), or physical mass ...

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

ring (The) Ring(s) 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 Arts, entertainment, and media Film and TV * ''The Ring'' (franchise), a ...

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, each of which has a unique ID with

bit The bit is the most basic unit of information in computing and digital communication. 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 represented as ...

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 or between or across multiple networks. Broadly, routing is performed in many types of networks, including circuit-switched networks, such as the public switched telephone netw ...

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, points, people, or ideas are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two co ...

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 centre of the circle and whose endpoints lie on the circle. It can also be defined as the longest Chord (geometry), chord of the circle. Both definitions a ...

is reduced to . Koorde node maintains

pointers Pointer may refer to: People with the name * Pointer (surname), a surname (including a list of people with the name) * Pointer Williams (born 1974), American former basketball player Arts, entertainment, and media * ''Pointer'' (journal), the ...

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 description of the steps in an algorithm using a mix of conventions of programming languages (like assignment operator, conditional operator, loop) with informal, usually self-explanatory, notation of actio ...

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