Distributed load balancing over directed network topologies

In this paper we consider the problem of distributed load balancing over a directed graph that is not fully connected. We study the impact of network topology on the stability and balance of distributed computing. We furthermore propose informed load balancing (I-LB), an approach in which the nodes first reach an agreement over the balanced state, through using a consensus-seeking protocol, before proceeding to redistribute their tasks. We compare the performance of I-LB with that of the original load balancing (O-LB) approach in terms of speed of convergence and bandwidth usage. We prove that the O-LB approach can guarantee convergence to a balanced state as long as the underlying graph is strongly connected while I-LB may not converge. However, I-LB can increase the speed of convergence and/or reduce the bandwidth usage especially for low-connectivity graphs.