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 arbitrary graph. Each agent initially holds a subset of the items. 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 (c) the number of items initially assigned to agents that are not consistent with the assignment of colors is minimum. This problem, known in the centralized setting as a matching problem, has been introduced in the distributed setting in [3] for the simple ring topology. Here, we generalize the problem to arbitrary graphs, by solving it with a distributed algorithm which is eficient both in terms of time complexity and message complexity for a large class of graphs. Namely, our results can be outlined as follows. We prove a lower bound on the message complexity ofω (m/n D2), where D is the diameter of the graph. We give a distributed deterministic algorithm with time complexity O(maxn2;Dlog qg) and message complexity O (n/log n) (log q+mlogm) , where q is the maximum number of items of a given color held by an agent. It can be noticed that for a large class of instances of practical interest, namely for m O(nc), for some constant c, and q € O(mm), our algorithm exhibits a message complexity of O(m n), which turns out to be optimal, in view of our lower bound, for graphs with diameter linear in the number of nodes. We finally show that the cost of our solution for arbitrary graphs is at most three times the optimal cost (found by a centralized algorithm).

Distributed Beta-Assignment on graphs / DE MARCO, Gianluca; Leoncini, Mauro; Mazzali, Lucia; Montangero, Manuela. - 1949:(2017), pp. 109-120. ((Intervento presentato al convegno 18th Italian Conference on Theoretical Computer Science ICTCS 2017 tenutosi a ita nel 2017.

Distributed Beta-Assignment on graphs

DE MARCO, GIANLUCA;Leoncini, Mauro;MAZZALI, LUCIA;Montangero, Manuela
2017

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 an arbitrary graph. Each agent initially holds a subset of the items. 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 (c) the number of items initially assigned to agents that are not consistent with the assignment of colors is minimum. This problem, known in the centralized setting as a matching problem, has been introduced in the distributed setting in [3] for the simple ring topology. Here, we generalize the problem to arbitrary graphs, by solving it with a distributed algorithm which is eficient both in terms of time complexity and message complexity for a large class of graphs. Namely, our results can be outlined as follows. We prove a lower bound on the message complexity ofω (m/n D2), where D is the diameter of the graph. We give a distributed deterministic algorithm with time complexity O(maxn2;Dlog qg) and message complexity O (n/log n) (log q+mlogm) , where q is the maximum number of items of a given color held by an agent. It can be noticed that for a large class of instances of practical interest, namely for m O(nc), for some constant c, and q € O(mm), our algorithm exhibits a message complexity of O(m n), which turns out to be optimal, in view of our lower bound, for graphs with diameter linear in the number of nodes. We finally show that the cost of our solution for arbitrary graphs is at most three times the optimal cost (found by a centralized algorithm).
18th Italian Conference on Theoretical Computer Science ICTCS 2017
ita
2017
1949
109
120
DE MARCO, Gianluca; Leoncini, Mauro; Mazzali, Lucia; Montangero, Manuela
Distributed Beta-Assignment on graphs / DE MARCO, Gianluca; Leoncini, Mauro; Mazzali, Lucia; Montangero, Manuela. - 1949:(2017), pp. 109-120. ((Intervento presentato al convegno 18th Italian Conference on Theoretical Computer Science ICTCS 2017 tenutosi a ita nel 2017.
File in questo prodotto:
File Dimensione Formato  
general_graphs_final.pdf

non disponibili

Tipologia: Post-print dell'autore (bozza post referaggio)
Dimensione 389.18 kB
Formato Adobe PDF
389.18 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
ICTCSpaper09.pdf

accesso aperto

Tipologia: Versione dell'editore (versione pubblicata)
Dimensione 389.18 kB
Formato Adobe PDF
389.18 kB Adobe PDF Visualizza/Apri
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: https://hdl.handle.net/11380/1151333
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact