Load balancing on networks with gossip-based distributed algorithms

We study the distributed and decentralized load balancing problem on arbitrary connected graphs, representing an homogeneous network. The network contains several tasks, represented by possibly different integer numbers, to be processed at nodes. We propose a randomized algorithm based on gossip that achieves consensus on the load distribution within fixed bounds of the optimal one; we also show by simulations that in most cases the achieved consensus is optimal. We finally present a computationally convenient heuristic and show that it ensures the same bounds: simulation results, however, show that the heuristic performs worse.