How is DHT different than regular hash tables in context to data/node lookup? 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?
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.