Consider a set of items and a set of m colors, where each item is associated to one color. Consider also n computational agents connected by a ring. Each agent holds a subset of the items and items of the same color can be held by different agents. We analyze the problem of distributively assigning colors to agents in such a way that (a) each color is assigned to one agent only and (b) the number of different colors assigned to each agent is minimum. Since any color assignment requires the items be distributed according to it (e.g. all items of the same color are to be held by only one agent), we define the cost of a color assignment as the amount of items that need to be moved, given an initial allocation. We first show that any distributed algorithm for this problem requires a message complexity of Ω(n⋅m) and then we exhibit an optimal message complexity algorithm for synchronous and asynchronous rings that in polynomial time determines a color assignment with cost at most three times the optimal. We show that the approximation is tight and how to get a better cost solution at the expenses of either the message or the time complexity. Finally, we present some experiments showing that, in practice, our algorithm performs much better than the theatrical worst case scenario.

A distributed message-optimal assignment on rings / De Marco, G.; Leoncini, M.; Montangero, M.. - In: JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING. - ISSN 0743-7315. - 132:(2019), pp. 284-298. [10.1016/j.jpdc.2019.05.007]

A distributed message-optimal assignment on rings

Leoncini M.;Montangero M.
2019

Abstract

Consider a set of items and a set of m colors, where each item is associated to one color. Consider also n computational agents connected by a ring. Each agent holds a subset of the items and items of the same color can be held by different agents. We analyze the problem of distributively assigning colors to agents in such a way that (a) each color is assigned to one agent only and (b) the number of different colors assigned to each agent is minimum. Since any color assignment requires the items be distributed according to it (e.g. all items of the same color are to be held by only one agent), we define the cost of a color assignment as the amount of items that need to be moved, given an initial allocation. We first show that any distributed algorithm for this problem requires a message complexity of Ω(n⋅m) and then we exhibit an optimal message complexity algorithm for synchronous and asynchronous rings that in polynomial time determines a color assignment with cost at most three times the optimal. We show that the approximation is tight and how to get a better cost solution at the expenses of either the message or the time complexity. Finally, we present some experiments showing that, in practice, our algorithm performs much better than the theatrical worst case scenario.
2019
132
284
298
A distributed message-optimal assignment on rings / De Marco, G.; Leoncini, M.; Montangero, M.. - In: JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING. - ISSN 0743-7315. - 132:(2019), pp. 284-298. [10.1016/j.jpdc.2019.05.007]
De Marco, G.; Leoncini, M.; Montangero, M.
File in questo prodotto:
File Dimensione Formato  
Revision2_JPDC-beta-assignment.pdf

Accesso riservato

Tipologia: Versione dell'autore revisionata e accettata per la pubblicazione
Dimensione 741.8 kB
Formato Adobe PDF
741.8 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1188508
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact