Distributed balanced color assignment on arbitrary networks

Consider a scenario in which a set of n agents hold items, where each item can be of one out of m possible types (colors). The agents are connected by an arbitrary network and have to distributively find a repartition of the colors such that the amount of colors for each agent is as balanced as possible: in the particular case where m is a multiple of n, each agent must have exactly m/n colors. More formally, the goal is to let the agents agree on an assignment of colors to agents such that the following two conditions hold: (i) each color is assigned to exactly one agent; (ii) each agent has at least ⌊m/n⌋ and at most ⌈m/n⌉ colors. Among all possible such repartitions, we seek for the one that minimizes the number of “changes” (measured in terms of misplaced items) with respect to the initial configuration. In other words, our aim is to design a distributed algorithm that finds a balanced coloring of minimum cost, where the cost of a coloring is the number of items that need to be relocated. This kind of questions, usually modeled as generalized bipartite matching problems, have been studied in the distributed setting only on clusters of commodity nodes with the aim of copying with real-world massive instances, which may involve millions of agents and colors. Here we propose the first distributed algorithm designed to run on an arbitrary network with the agents as nodes. Our algorithm turns out to be efficient in terms of both time and message complexity for a large class of graphs. Our results can be outlined as follows. We prove a lower bound Ω(m/n⋅D2) on message complexity, where D is the diameter of the graph, that holds for any approximation algorithm whose solution has cost at most 2(α−2)/α times the cost of any optimal solution, for every constant α>2. We give a distributed deterministic algorithm with time complexity O(max⁡{n2,Dlog⁡q}) and message complexity?>O(nlog⁡n⋅(log⁡q+mlog⁡m)), where q is the maximum number of items of a given color held by any agent. We show that the cost of our solution for arbitrary graphs is at most (2+δ) times the optimal cost, for any δ>0. We finally observe that, for large diameter graphs (i.e., D=Ω(nϵ), ϵ>0), we get matching lower and upper bounds on message complexity for the vast majority of instances of potential interest, that is, instances with polynomial number of colors and (up to) super-exponential number of items.