We study a version of the beta-assignment problem (Chang and Lee, 1988) on asynchronous rings: 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 an asynchronous ring. Each agent holds a subset of the items, where initially different agents might hold items associated to the same color. We analyze the problem of distributively assigning colors to agents in such a way that (a) each color is assigned to one agent and (b) the number of different colors assigned to each agent is minimum. Since any color assignment requires that 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 on the ring requires a communication complexity of Omega(n middot m) and then we exhibit a polynomial time distributed algorithm with message complexity matching the bound, that determines a color assignment with cost at most (2 + eps) times the optimal cost, for any 0 < eps < 1.

Distributed Algorithm for a Color Assignment on Asynchronous Rings / G., DE MARCO; Leoncini, Mauro; Montangero, Manuela. - STAMPA. - (2006), pp. 1-10. ((Intervento presentato al convegno PARALLEL & DISTRIBUTED PROCESSING tenutosi a Rhodes Island, Greece nel 25-29 April 2006.

Distributed Algorithm for a Color Assignment on Asynchronous Rings

LEONCINI, Mauro;MONTANGERO, Manuela
2006

Abstract

We study a version of the beta-assignment problem (Chang and Lee, 1988) on asynchronous rings: 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 an asynchronous ring. Each agent holds a subset of the items, where initially different agents might hold items associated to the same color. We analyze the problem of distributively assigning colors to agents in such a way that (a) each color is assigned to one agent and (b) the number of different colors assigned to each agent is minimum. Since any color assignment requires that 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 on the ring requires a communication complexity of Omega(n middot m) and then we exhibit a polynomial time distributed algorithm with message complexity matching the bound, that determines a color assignment with cost at most (2 + eps) times the optimal cost, for any 0 < eps < 1.
PARALLEL & DISTRIBUTED PROCESSING
Rhodes Island, Greece
25-29 April 2006
1
10
G., DE MARCO; Leoncini, Mauro; Montangero, Manuela
Distributed Algorithm for a Color Assignment on Asynchronous Rings / G., DE MARCO; Leoncini, Mauro; Montangero, Manuela. - STAMPA. - (2006), pp. 1-10. ((Intervento presentato al convegno PARALLEL & DISTRIBUTED PROCESSING tenutosi a Rhodes Island, Greece nel 25-29 April 2006.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento 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: http://hdl.handle.net/11380/308115
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact