In this paper we consider the problem of load balancing over heterogeneous networks, i.e. networks whose nodes have different speeds. We assume that tasks are indivisible and with different weights. Our goal is that of minimizing the maximum execution time over nodes. We provide a gossip-based distributed algorithm whose convergence to a bounded set is guaranteed. 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.

Load balancing over heterogeneous networks with gossip-based algorithms

FRANCESCHELLI, MAURO;GIUA, ALESSANDRO;SEATZU, CARLA
2009

Abstract

In this paper we consider the problem of load balancing over heterogeneous networks, i.e. networks whose nodes have different speeds. We assume that tasks are indivisible and with different weights. Our goal is that of minimizing the maximum execution time over nodes. We provide a gossip-based distributed algorithm whose convergence to a bounded set is guaranteed. 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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11584/103926
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 18
  • ???jsp.display-item.citation.isi??? 14
social impact