Gossip-based fault-tolerant load balancing algorithm with low communication overhead

In large-scale distributed-computing environments, numerous factors may affect the predictable performance of load balancing policies causing variable load distribution in the network and bottlenecks. This paper presents a two-level load balancing algorithm for solving the dynamic load balancing problem considering the loss of processors and connectivity of the network. The proposed method privileges local load balancing over global load balancing thus reduces the communication cost over the global network. To further minimize communication costs and to handle loss of connectivity, the algorithm proposes a new communication model for global communication among the processors. The performance, correctness, and scalability of the algorithm are analyzed which show that our algorithm requires O(log m) rounds and O(m log m) messages for m clusters and achieves minimum cluster and global load deviation. Simulation results also support our analytical studies. (C) 2019 Elsevier Ltd. All rights reserved.