Chord

Overview

Nodes and keys are assigned an

m

{\displaystyle m}

-bit identifier using consistent hashing. The SHA-1 algorithm is the base hashing function for consistent hashing. Consistent hashing is integral to the robustness and performance of Chord because both keys and nodes (in fact, their IP addresses) are uniformly distributed in the same identifier space with a negligible possibility of collision. Thus, it also allows nodes to join and leave the network without disruption. In the protocol, the term node is used to refer to both a node itself and its identifier (ID) without ambiguity. So is the term key.

Using the Chord lookup protocol, nodes and keys are arranged in an identifier circle that has at most

2

m

{\displaystyle 2^{m}}

nodes, ranging from

0

{\displaystyle 0}

to

2

m

−

1

{\displaystyle 2^{m}-1}

. (

m

{\displaystyle m}

should be large enough to avoid collision.) Some of these nodes will map to machines or keys while others (most) will be empty.

Each node has a successor and a predecessor. The successor to a node is the next node in the identifier circle in a clockwise direction. The predecessor is counter-clockwise. If there is a node for each possible ID, the successor of node 0 is node 1, and the predecessor of node 0 is node

Protocol details

Basic query

The core usage of the Chord protocol is to query a key from a client (generally a node as well), i.e. to find

s

u

c

c

e

s

s

o

r

(

k

)

{\displaystyle successor(k)}

. The basic approach is to pass the query to a node's successor, if it cannot find the key locally. This will lead to a

O

(

N

)

{\displaystyle O(N)}

query time where

N

{\displaystyle N}

is the number of machines in the ring.

Finger table

To avoid the linear search above, Chord implements a faster search method by requiring each node to keep a finger table containing up to

m

{\displaystyle m}

entries, recall that

m

{\displaystyle m}

is the number of bits in the hash key. The

i

t

h

{\displaystyle i^{th}}

entry of node

n

{\displaystyle n}

will contain

s

u

c

c

e

s

s

o

r

(

(

n

+

2

i

−

1

)

Node join

Whenever a new node joins, three invariants should be maintained (the first two ensure correctness and the last one keeps querying fast):

Each node's successor points to its immediate successor correctly.

Each key

k

{\displaystyle k}

is stored in

s

u

c

c

e

s

s

o

r

(

k

)

{\displaystyle successor(k)}

.

Each node's finger table should be correct.

To satisfy these invariants, a predecessor field is maintained for each node. As the successor is the first entry of the finger table, we do not need to maintain this field separately any more. The following tasks should be done for a newly joined node

n

{\displaystyle n}

:

Initialize node

n

{\displaystyle n}

Stabilization

To ensure correct lookups, all successor pointers must be up to date. Therefore, a stabilization protocol is running periodically in the background which updates finger tables and successor pointers.

The stabilization protocol works as follows:

Stabilize(): n asks its successor for its predecessor p and decides whether p should be n's successor instead (this is the case if p recently joined the system).

Notify(): notifies n's successor of its existence, so it can change its predecessor to n

Fix_fingers(): updates finger tables

Potential uses

Cooperative Mirroring: A load balancing mechanism by a local network hosting information available to computers outside of the local network. This scheme could allow developers to balance the load between many computers instead of a central server to ensure availability of their product.

Time-shared storage: In a network, once a computer joins the network its available data is distributed throughout the network for retrieval when that computer disconnects from the network. As well as other computers' data is sent to the computer in question for offline retrieval when they are no longer connected to the network. Mainly for nodes without the ability to connect full-time to the network.

Distributed Indices: Retrieval of files over the network within a searchable database. e.g. P2P file transfer clients.

Large scale combinatorial searches: Keys being candidate solutions to a problem and each key mapping to the node, or computer, that is responsible for evaluating them as a solution or not. e.g. Code Breaking

Also used in wireless sensor networks for reliability

Proof sketches

With high probability, Chord contacts

O

(

log

⁡

N

)

{\displaystyle O(\log N)}

nodes to find a successor in an

N

{\displaystyle N}

-node network.

Suppose node

n

{\displaystyle n}

wishes to find the successor of key

k

{\displaystyle k}

. Let

p

{\displaystyle p}

be the predecessor of

k

{\displaystyle k}

. We wish to find an upper bound for the number of steps it takes for a message to be routed from

n

{\displaystyle n}

to

p

{\displaystyle p}

Pseudocode

Definitions for pseudocode

finger[k]

first node that succeeds

(

n

+

2

k

−

1

)

mod

2

m

,

1

≤

k

≤

m

{\displaystyle (n+2^{k-1}){\mbox{ mod }}2^{m},1\leq k\leq m}

successor

the next node from the node in question on the identifier ring

predecessor

the previous node from the node in question on the identifier ring

The pseudocode to find the successor node of an id is given below:

// ask node n to find the successor of id

n.find_successor(id)

// Yes, that should be a closing square bracket to match the opening parenthesis.