Gossip based asynchronous and randomized distributed task assignment with guaranteed performance on heterogeneous networks
Franceschelli, Mauro
First
;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 | Size | Format | |
---|---|---|---|
NAHS2016_firstRevision.pdf open access
Description: articolo principale
Type: versione pre-print
Size 311.52 kB
Format Adobe PDF
|
311.52 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.