HotRoD: Load Balancing and Efficient Range Query Processing in Peer-to-Peer Data Networks

Abstract. We consider the conflicting problems of ensuring data-access load balancing and efficiently processing range queries on peer-to-peer data net-works maintained over Distributed Hash Tables (DHTs). Placing consecutive data values in neighboring peers is frequently used in DHTs since it accelerates range query processing. However, such a placement is highly susceptible to load imbalances, which are preferably handled by replicating data (since repli-cation also introduces fault tolerance benefits). In this paper, we present HotRoD, a DHT-based architecture that deals effectively with this combined problem through the use of a novel locality-preserving hash function, and a tun-able data replication mechanism which allows trading off replication costs for fair load distribution. Our detailed experimentation study shows strong gains in both range query processing efficiency and data-access load balancing, with low replication overhead. To our knowledge, this is the first work that concur-rently addresses the two conflicting problems using data replication.