Seminar - Load balancing with gossip-based distributed algorithms

Fri, 19/09/2008 (All day)
Abstract: In this talk we consider the problem of load balancing over heterogeneous networks, i.e. networks whose nodes have different speeds. Our goal is that of determining, using algorithms based on gossip, the solution that minimizes the maximum execution time. We discuss the discrete case, namely the case of finite (indivisible) tasks with different weights. We show that the convergence time of the proposed algorithm relies ultimately on the average meeting time between two agents performing a random walk on a graph. Finally, we suggest a way to significantly improve the performance assuming that an Hamiltonian cycle on the network exists and it is known.