Premium
A simpler load‐balancing algorithm for range‐partitioned data in peer‐to‐peer systems
Author(s) -
Chawachat Jakarin,
Fakcharoenphol Jittat
Publication year - 2015
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21627
Subject(s) - computer science , hash function , load balancing (electrical power) , hash table , consistent hashing , amortized analysis , perfect hash function , constant (computer programming) , algorithm , key (lock) , distributed hash table , range (aeronautics) , peer to peer , data structure , distributed computing , mathematics , materials science , geometry , computer security , double hashing , composite material , programming language , grid
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. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(3), 235–249 2015