In a decentralized peer-to-peer network, it is often difficult to guarantee the location and retrieval of documents that exist on the network. Chord is a scalable search protocol designed to be the basis of a network that solves this problem, where queries return a definitive response whether a document exists or not.

Chord uses consistent-hashing, a method that evenly distributes hash keys to nodes and values (or documents). Nodes are organized in a ring topology, maintaining keys of values that are less than or equal to the assigned node value and greater than the value of the node’s predecessor. Figure 1 shows how keys are mapped to respective nodes. The green circles labelled N# are the nodes on the Chord ring and the boxes labelled with K# represent keys and point to the nodes which they are assigned.

Figure 1 - Chord Key/Node mapping.

For querying, each node contains a finger table containing Chord identifiers and IP addresses of its neighbors. This finger table allows each node to only track on the order of log(N) neighboring nodes, where N is the number of nodes in the network. Using the Chord identifiers in their finger tables, nodes can determine the possible location of keys on the network. Figure 2 below shows the finger tables of a simple network. If a key is beyond the scope of a node's finger table, the query will be forwarded around the ring to the furthest node on the table (the node with the highest Chord identifier).

Figure 2

When a new node enters the network, it randomly assigns itself a Chord identifier, locates its position on the ring, announces itself to the successor nodes and moves any appropriate keys. The successor is now aware that the new node is its predecessor but other nodes on the network are unaware of its existence. The problem is resolved when the network stabilizes itself on a periodic basis, where each node queries the first entry in its finger table to identify its predecessor. If the finger tables are properly configured, the result should be the Chord identifier of the querying node. If this is not the case, the finger table is updated accordingly. Figures 3 and 4 show how the Chord network updates itself when new nodes join.

Figure 3

Figure 4

A proposed method to increase the reliability of Chord suggests that the values (documents) associated with keys are replicated a configurable number (r) times on the r nodes following the node possessing the associated key. Preceding nodes pointing to the key would also aware that there are r duplicates of the value beyond the key-holding node. If a node associated with a key were to drop from the network, the request would be forwarded to the next node on the ring. The scheme would require all r nodes to drop from the network in order for a document to be lost.