Networking

Non-Transitive Connectivity and DHTs

Date Added: Jan 2011
Format: PDF

The most basic functionality of a Distributed Hash Table, or DHT, is to partition a key space across the set of nodes in a distributed system such that all nodes agree on the partitioning. For example, the Chord DHT assigns each node a random identifier from the key space of integers modulo 2160 and maps each key to the node whose identifier most immediately follows it. Chord is thus said to implement the successor relation, and so long as each node in the network knows its predecessor in the key space, any node can compute which keys are mapped onto it.