A simpler load-balancing algorithm for range-partitioned data in peer-to-peer systems

Random hashing is a standard method to balance loads among nodes in Peer-to-Peer networks. However, hashing destroys locality properties of object keys, the critical properties to many applications, more specifically, those that require range searching. To preserve a key order while keeping loads balanced, Ganesan, Bawa, and Garcia-Molina proposed a load-balancing algorithm that supports both object's key insertion and deletion with a guaranteed max-min load ratio, the imbalance ratio, of 4.237 using constant amortized costs. Nonetheless, the algorithm is not straightforward to implement in real networks because of its recursiveness. The algorithm mostly uses local operations with global max-min load information. In this work, we present a simple nonrecursive algorithm using essentially the same primitive operations as in Ganesan et al.'s work. For insertions and deletions, our algorithm guarantees a proven constant imbalance ratio of 7.464 with constant amortized costs. (c) 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(3), 235-249 2015