A tree-based DHT Approach to scalable weakly consistent peer-to-peer data management

Second generation peer-to-peer systems employ a distributed hashtable (DHT) to locate data efficiently in their network. But when peers fail, the DHT algorithm needs to route around them, which, in many cases, reduces its efficiency. We propose to separate the data lookup from the data storing concerns. Thus we can guarantee a search cost proportional to the logarithm of the number of peers in the network despite a high change rate, i.e., many peers join or leave the network concurrently. To demonstrate our approach, we use a simple DHT based on a binary tree whose leaves are associated with collections of peers that are responsible for a range of data values associated with search keys. Peers of a group collaborate to form redundant data storage and thus ensure high availability of their data. This means, however, only weak data, consistency can be guaranteed when an insertion or update takes place.