Chord Protocol
The Chord protocol is one solution for connecting the peers of a P2P network. Chord consistently maps a key onto a node. Both keys and nodes are assigned an -bit identifier. For nodes, this identifier is a hash of the node's IP address. For keys, this identifier is a hash of a keyword, such as a file name. It is not uncommon to use the words "nodes" and "keys" to refer to these identifiers, rather than actual nodes or keys. There are many other algorithms in use by P2P, but this is a simple and common approach.
A logical ring with positions numbered to is formed among nodes. Key k is assigned to node successor(k), which is the node whose identifier is equal to or follows the identifier of k. If there are N nodes and K keys, then each node is responsible for roughly keys.
When a new node joins or leaves the network, responsibility for keys changes hands.
If each node knows only the location of its successor, a linear search over the network could locate a particular key. This is a naive method for searching the network, since any given message could potentially have to be relayed through most of the network. Chord implements a faster search method.
Chord requires each node to keep a "finger table" containing up to entries. The entry of node will contain the address of successor .
With such a finger table, the number of nodes that must be contacted to find a successor in an N-node network is . (See proof below.)
Read more about this topic: Chord (peer-to-peer)
Famous quotes containing the word chord:
“Love took up the glass of Time, and turned it in his glowing hands;
Every moment, lightly shaken, ran itself in golden sands.
Love took up the harp of Life, and smote on all the chords with
might;
Smote the chord of Self, that, trembling, passed in music out of sight.”
—Alfred Tennyson (1809–1892)