●●●● ●●●● ●●●● ●●●● Idea: hash tables ●0●● ●●●● a hash table associates data with keys lookup(key)→data hash table insert(key, data) 0 Key is hashed to find bucket in hash table key hash function >pos 3 Each bucket is expected to Beatles" h(key) %N 1 hold #items/#buckets items hash bucket e In a distributed hash table (DHT), nodes are the hash buckets Key is hashed to find lookup(key)→data responsible peer node insert(key, data) Data and load are balanced key hash function >pos across nodes " Beatles h(key)%N N-1 node Peer-to-Peer Networks -P. FelberPeer-to-Peer Networks — P. Felber 6 Idea: Hash Tables ⚫ A hash table associates data with keys ⚫ Key is hashed to find bucket in hash table ⚫ Each bucket is expected to hold #items/#buckets items ⚫ In a Distributed Hash Table (DHT), nodes are the hash buckets ⚫ Key is hashed to find responsible peer node ⚫ Data and load are balanced across nodes key pos 0 hash function 1 2 N-1 3 ... x y z lookup (key) → data insert (key, data) “Beattles” 2 hash table hash bucket h(key)%N 0 1 2 ... node key hash function pos lookup (key) → data insert (key, data) “Beattles” 2 h(key)%N N-1