How is DHT different than regular hash tables in context to data/node lookup?

This (introduction, 3rd paragraph) paper says:

First, in addition to the insertion and deletion of items, DHTs must support the insertion and deletion of buckets: as machines join and leave the network, items must be migrated to other machines and the hash function revised to reflect their new location.

This problem is also in Hashtables (for example, if you implement a hashtable in C using LinkedList and Array, then if the size of the array increased (new node added) then the data needs to be redistributed to achieve good load factor)

Second, some kind of routing protocol is usually necessary: since it is not feasible in a P2P system for every node to maintain up-to-date knowledge of all other nodes in the system, an item is looked up (or inserted) by following a sequence of routing hops through the peer-to-peer network.

Is this point talking about routing mechanism, if yes, then is this done is normal hashtable?


1 Answer 1


Your question in the first sentence is a bit vague and open-ended. I'm guessing you want to know about routing and mutual node knowledge in the context of lookup.

Each node shouldn't have to know about every other node. Assuming a hash ring topology, the simplest approach is to have each node know about its two neighbors on the ring. This defines a circular linked list. Unfortunately, as with all linked lists, it only supports slow linear search. It's also very sensitive to node removal: if any two nodes go offline, it breaks the connectivity of the ring.

If you try to repair this idea by having nodes maintain knowledge of their longer-range relatives then you eventually wind up with the idea of a skip graph, a generalization of skip lists that can handle node disappearance robustly. Unlike skip lists they are not explicitly stratified, which is important due to the non-hierarchical peer-to-peer nature of the problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.