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

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

0.00 Avg rating0 Votes
Article ID: iaor201528819
Volume: 66
Issue: 3
Start Page Number: 235
End Page Number: 249
Publication Date: Oct 2015
Journal: Networks
Authors: ,
Keywords: load balancing, partitioning
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.