A power-law graph as a distributed hash table with quick search and small tables

We analyze the possibility of using an 'Internet-like' power-law graph as a basis for peer-to-peer distributed hash table applications. Our work is based on previous studies of power-law random graph models that showed emergence of a spontaneous hierarchy of nodes based on their degrees, called the 'soft hierarchy'. The soft hierarchy indicates very short paths, leading to the top of the hierarchy, where the top consists of a clique of highest degree nodes. Such paths have lengths that scale as log log N, with number of nodes N. Further, such paths can be found by a heuristic rule: 'the next hop to highest degree neighbor'. We suggest that these circumstances could be used as a basis of an efficient distributed hash table. The idea is that the hash-entries, needed to locate content, are stored at the periphery of the hierarchy, consisting of large enough set of nodes to guarantee small tables. It is required that any node, say, i in the hierarchy is aware which nodes are below it in the hierarchy, provided it is not in the periphery. The node i places its 'down-hill' neighbors in the hash-ring with equal intervals between them. When node i gets a request to store or search a given hash-entry, it uses some locally defined function that places the hash value on this ring and forwards it to the down-hill neighbor closest to this value. Our main result is a probabilistic estimate of the number of hash-values stored in a periphery node. It appears to be sub log log N and super log log log N, with N → ∞, and with probability tending to 1. Another contribution is a sketch of a novel algorithm that would create such topologies in a self-organizing manner.