Chords

#cse6603

Introductory Paper

Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications

Theory

Chord is a protocol and algorithm for a peer-to-peer distributed hash table

Problem

In a peer-to-peer network, data is stored in different computers. A user needs to find out which computer the data is stored at before accessing it.

Solution

• Nodes (each computer in the network) and keys are assigned an m-bit identifier using Consistent Hashing.
  • There are $2^m$ Ids available
  • if m=8, total possible ids = $2^8$ = 256
• The SHA-1 algorithm is the base hashing function for consistent hashing
• Using the Chord lookup protocol, nodes and keys are arranged in an identifier circle that has at most $2^m(0$ to $2^m-1)$ nodes.

• Sites are then organized in a logical ring according to their IDs.
• Keys are also hashed into the same identifier space, and the key (and the corresponding value) is stored at its successor, i.e., the node with next higher ID.
• The expected number of hops is O(log n) where n is the number of nodes in the Chord ring.

Avoiding the linear $O(n)$ search --source

Implementation

Chord: Building a DHT (Distributed Hash Table) in Golang | by Farhan Ali Khan | techlog | Medium

GitHub - mitul227/Chord-DHT: Implementation of Chord P2P Distributed Hash Table

Further reading

Chord - Wikipedia

Key lookup in Chord with finger table | by Jing Yang | Medium