Consensus-based estimation protocol for decentralized dynamic load balancing over partially connected networks

A novel consensus-based protocol is developed for estimating the load information at nodes in a distributed computing system operating over a partially connected communication network. The challenge in such estimation process arises from the existence of tangible delays in the exchange of information, and the fact that loads are dynamic since nodes continue to execute their loads while the estimation process is ongoing. The protocol utilizes the concept of trust weight that each node has about any other node, based on the number of hops in between, to periodically form an updated estimate of the loads of the other nodes. The probability of consensus at any given time as well as the probability density function of the time to the first consensus are analytically characterized and used to determine the best instant for executing a dynamic load balancing (DLB) action. Detailed Monte-Carlo simulations of the average completion time of a workload by a distributed system under different system configurations are presented and discussed. The results suggest a range of time for executing the DLB over which satisfactory average completion time is achieved. The results also provide insight on the effects of network connectivity and the frequency of communication on the DLB performance.