Gossip-based fault-tolerant load balancing algorithm with low communication overhead. (January 2020)

• Record Type: Journal Article
• Authors: Chatterjee, Moumita; Mitra, Anirban; Setua, Sanjit Kumar; Roy, Sudipta
• Is Part Of: Computers & electrical engineering. Volume 81(2020)
• Publication Date: 2020-01
• Subjects: Load balancing -- Fault-tolerance -- Gossip protocol -- Expander graph -- Stability threshold -- Network optimization; Computer engineering -- Periodicals; Electrical engineering -- Periodicals; Electrical engineering -- Data processing -- Periodicals; Ordinateurs -- Conception et construction -- Périodiques; Électrotechnique -- Périodiques; Électrotechnique -- Informatique -- Périodiques; Computer engineering; Electrical engineering; Electrical engineering -- Data processing; Periodicals; Electronic journals; 621.302854
• DOI: 10.1016/j.compeleceng.2019.106517
• Languages: English
• ISSNs: 0045-7906

Abstract

Abstract: 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.