DChord: An Efficient and Robust Peer to Peer Lookup System

Abstract

Dynamic Hash Tables (DHTs) are distributed systems that maintain key-value pairs and provide efficient lookup services. Traditional DHTs usually rely on a random ID distribution of the keys to achieve such efficiency. Uniformly random hash functions are typically used to create uniformly random ID distributions from non-random key distributions. However, there are many cases where such random hash functions cannot be applied. For example, those systems that provide range queries over the keys cannot apply random hash functions on the keys, otherwise, the range query is very difficult to support. In this paper, we present a new lookup system called DChord, which does not depend on the randomness assumption to achieve its performance. To show the performance of the proposed system, we provide mathematical analysis and extensive simulation results in a highly non-random USN (Ubiquitous Sensor Network) metadata identifier space. To be specific, we show that DChord has high regularity in terms of in-degree and out-degree distributions. Thus, the system is robust against random node failures. We also show that query processing load is well balanced among nodes and the lookup speed is deterministic in such a way that the number of nodes to visit for a query is at most log2(N).