review of Chord

In a peer-to-peer system, each data item associates with a unique key. The
(key, value) pairs are stored in a node (peer) of the system. The problem
is, given a key, how to efficiently locate the node that stores the data
item related to the key.

In this paper, a scalable protocol called Chord is proposed to support the
lookup in a dynamic peer-to-peer system with frequent node arrivals and
departures. The key idea of Chord is using consistent hash to maintain an
identifier circle. Each Key is kept by its successor node on the ring. The
insertion of a node on the ring causes minimized changes of the ring and
the lookup on the ring is scalable. Chord also supports concurrent
insertion and failure recovery.

Consistent hash can minimize the changes when nodes join and leave the
ring. Each node and each key are assigned to a m-bit identifier using a
standard SHA-1 hash function. All identifiers are ordered in a circle mod
2m. Key k is assigned to its successor node whose identifier is equal to
or follows the identifier of k in the circle. Finger table is used to
speed up the lookup in the Chord ring. The finger table of a node n has m
entries. The ith entry contains the pointer that points to the successor
node of identifier (n+2i-1). When a node n does not know the successor of
k, it searches its finger table, finds node i whose identifier immediately
precedes k., and sends k to node i. Continue the searching until the node
is the successor of k. With finger tables, it does not linearly scan the
ring. The path lengths are O (log N). Information in finger tables should
be correct with respect to the dynamic node insertion and departure. The
successor list is used in Chord to support node failure recovery. Each
node maintains a successor lit of its first r nearest successors in the
ring. If node n’s successor failed, it can select the first live successor
from the list in order to continue the lookup.

The first assumption in this paper is that the length of m-bit identifier
must be long enough to ensure that the probability of two nodes or keys
hashing to the same identifier is very small. And the number of keys is
suitable for the size of the whole system. Another assumption is that
there is no malicious node sends incorrect information about which key is
stored in which node.

There is an unstable state in the ring when nodes join or fail in the
ring. Queries coming during the unstable state may fail to get the results
because of the inconsistent successor lists and finger tables. The failed
query needs to wait for retry. Since Chord is working in a dynamic system,
nodes may come and leave continuously and concurrently. At the same time,
each node runs stabilization function periodically. How to determine the
length of waiting for the retrying queries is not discussed in detail.
Another question comes along with the dynamic situation. The Chord ring
may be partitioned. A specific mechanism is needed to heal partitioned
rings.

Chord is one of the most famous lookup mechanisms in P2P systems. Another
one is content-addressable network (CAN), which routes messages in a
d-dimensional Cartesian coordinate space. Routing consists of forwarding
to a neighbor that is closer to the key. In CAN, each node has O (d)
neighbors and search path lengths are O (dN1/d).
Received on Sun Nov 06 2005 - 19:58:36 EST