Distributed Beta-Assignment on graphs

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).