Gossip based asynchronous and randomized distributed task assignment with guaranteed performance on heterogeneous networks
Franceschelli, Mauro
Primo
;Giua, Alessandro;Seatzu, Carla
2017-01-01
Abstract
The main contribution of this paper is a novel distributed algorithm based on asynchronous and randomized local interactions, i.e., gossip based, for task assignment on heterogeneous networks. We consider a set of tasks with heterogeneous cost to be assigned to a set of nodes with heterogeneous execution speed and interconnected by a network with unknown topology represented by an undirected graph. Our objective is to minimize the execution time of the set of tasks by the networked system. We propose a local interaction rule which allows the nodes of a network to cooperatively assign tasks among themselves with a guaranteed performance with respect to the optimal assignment exploiting a gossip based randomized interaction scheme. We first characterize the convergence properties of the proposed approach, then we propose an edge selection process and a distributed embedded stop criterion to terminate communications, not only task exchanges, while keeping the performance guarantee. Numerical simulations are finally presented to corroborate the theoretical results.File | Dimensione | Formato | |
---|---|---|---|
NAHS2016_firstRevision.pdf accesso aperto
Descrizione: articolo principale
Tipologia: versione pre-print
Dimensione 311.52 kB
Formato Adobe PDF
|
311.52 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.