=Paper= {{Paper |id=Vol-1949/ICTCSpaper09 |storemode=property |title= Distributed Beta-assignment on Graphs |pdfUrl=https://ceur-ws.org/Vol-1949/ICTCSpaper09.pdf |volume=Vol-1949 |authors=Mauro Leoncini,Gianluca De Marco,Lucia Mazzali,Manuela Montangero |dblpUrl=https://dblp.org/rec/conf/ictcs/LeonciniMMM17 }} == Distributed Beta-assignment on Graphs == https://ceur-ws.org/Vol-1949/ICTCSpaper09.pdf

Distributed β-assignment on graphs?

Gianluca De Marco1 , Mauro Leoncini2 , Lucia Mazzali2 , and Manuela
Montangero2 ??
1
Dipartimento di Informatica, Università di Salerno, Italy
gianluca.demarco@dia.unisa.it
2
Dipartimento di Scienze Fisiche, Informatiche e Matematiche,
Università di Modena e Reggio Emilia, Italy
leoncini@unimore.it, 168267@studenti.unimore.it,
manuela.montangero@unimore.it

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 efficient 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(max{n2 , D log q}) and message complexity O logn n · log q+m log m ,

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

Keywords: algorithms, distributed computing, assignment problems.

?
A preliminary version of this work appeared in Lucia Mazzali’s Master Thesis.
??
Work partially supported by the SUCCESS Project H2020-EU.3.4., G.A. 633338
1 Introduction
In this paper we consider the Balanced Color Assignment Problem and we pro-
pose a distributed algorithm to find an approximated solution for arbitrary com-
munication graphs. This problem was introduced in [3] for the ring topology.

1.1 The problem
Consider a set of items and a set of m colors, where each item is associated to
one color. There are n agents connected by a communication graph, and each
agent holds a subset of the colored items. A color assignment assigns each color
to exactly one agent, while a balanced color assignment is a color assignment
that minimizes the maximum, over all agents, of the number of different colors
assigned to the same agent.
Let’s say that the inital assignment of an item to an agent is invalid for a
certain color assignment if the color of the item is not assigned to the agent by
the color assignment.
Our goal is to search for a balanced color assignment that minimizes the
number of invalid initial assignments.
Fig. 1 shows an example of (a) an initial item distribution and (b-c) two
possible color assignments.

Fig. 1. Example for n = 4 agents and m = 5 colors. Items above the lines are invalid
initial assignments, their total number gives the cost of the assignment. (a) Initial item
distribution, (b) balanced color assignments of cost 22 (c) optimal assignment of cost
16.

The problem was fist introduced in [3], where an optimal message 3-
approximation distributed algorithm was given for the case of the ring topol-
ogy. Authors showed that the centralized version of the problem is equivalent
to a maximum weight perfect matching problem on complete bipartite graphs
when m = n, while it is equivalent to the weighted β-assignment [2] problem on
weighted bipartite graphs when m > n.

Definition 1 (Balanced color assignment [3]). Let A = {a0 , a1 , ..., an−1 }
be a set of n agents connected by a communication graph and let C =
{c0 , c1 , ..., cm−1 } be a set of m colors. Let Qj,i > 0 be the number of items of
color cj initially held by the agent ai , for j = 0, 1, ..., m − 1 and i = 0, 1, ..., n − 1.
A Balanced Coloring is an assignment
π : {0, 1, ...m − 1} → {0, 1, ...n − 1}
of the m colors to the n agents in such a way that:
i ) for every color cj there is exactly one agent ai such that π(j) = i;
ii ) for every agent ai we have

m m
6 |{cj : π(j) = i}| 6
n n
i.e., the number of colors assigned to agents is balanced. In particular b m
nc
colors are assigned to [(b m
n c + 1)n − m] agents and b m
n c + 1 colors to the
remaining (m − b mn cn) agents.
Definition 2 (Distributed balanced color assignment problem [3]). The
Distributed Balanced Color Assignment Problem aims at finding a balanced col-
oring of minimum cost in a distributed way, where the cost of a balanced coloring
π : {0, 1, ...m − 1} → {0, 1, ...n − 1} is defined as:
m−1
P n−1 P
Cost(π) = Qj,i .
j=0 i=0
i6=π(j)

Intuitively, the cost of the assignment is the total number of invalid initial
assignments.

1.2 The model
We assume that the agents in A = {a0 , . . . , an−1 } are connected by a generic
graph and each agent can communicate only with its neighbors. We assume that
each agent knows n (the number of agents), and C (the set of colors).
We measure message complexity in the standard way (see for example [5]),
i.e., we assume that messages of bit length at most c log n, for some constant
c (called basic messages), can be transmitted at unit cost; that is, one basic
message can carry at most a constant number of agent ID’s. Non basic messages
of length L are allowed, and we charge a cost c0 dL/ log ne for their transmission,
for some constant c0 .
Brute force approach. Let q = maxi maxj Qj,i be the maximum number of
items of a given color initially assigned to agents. In a brute force algorithm, all
agents send all their color information to a designated leader agent which solves
the problem locally using the optimal algorithm for the maximum weight perfect
matching (if n = m), or for the weighted β-assignment problem (if m > n). The
leader then sends the solution back to all the other agents. With such an ap-
proach, each agent sends at most O(m) non basic messages, each one accounting
log q
for O( log n ) basic messages. Each message passes through O(D) channels, where
D is the diameter of the graph and, thus, the overall the message complexity is
log q
O(mnD log n ).
2 Lower bound on message complexity

To derive a lower bound we proceed in the following way: we describe two in-
stances of the problem, we pair agents and show that these two instances are
indistinguishable by one agent in the pair unless some communication is involved.
We start with the following lemma.

Lemma 1. Given a connected graph G with diameter D, we have Ω(D) disjoint
pairs of nodes at distance Ω(D).

Proof. Let P be a shortest path connecting two nodes x and y at distance D.
Arbitrarily number the nodes in P according to their distance from x. Then
the dD/2e pairs (i, i + d D+1
2 e) are disjoint and the distance between the node
components is d D+1
2 e, for i = 0, . . . , b D+1
2 c − 1. t
u

W.l.o.g., we consider instances of the problem in which the number agents n
is even and the number of colors m satisfies m = nt/2, for some even integer t.
By Lemma 1, we can form P ∈ Ω(D) disjoint pairs of nodes at distance
Ω(D). Since P ≤ n/2, we pair the remaining n − 2P agents arbitrarily. .
We then partition the set of colors C into n/2 subsets of cardinality t each;
i.e., {C0 , C1 , ...C n2 −1 } is a partition of the total set of colors C such that |Cj | = t
for all j = 0, 1, ..., n2 − 1.
We consider the set of instances I in which a pair (ai , ai0 ) of agents is initially
assigned only items whose colors are in the subset Ci = {ci1 , ..., cit }; i.e., no other
agent is initially assigned items of colors in Ci .
Now we define two specific instances I1 , I2 ∈ I. Fix an integer u > 1, we have
Instance I1 :
agent ai
Qj,i = u for j ∈ Ci
agent ai0
Qj,i0 = u for j = i1 , . . . i 2t
Qj,i0 = u + 1 for j = i 2t +1 , . . . it

Instance I2 :
agent ai
Qj,i = u for j ∈ Ci
agent ai0
Qj,i0 = u for j = i1 , . . . i 2t
Qj,i0 = u − 1 for j = i 2t +1 , . . . it
Observe that, from the point of view of ai the two instances are identical,
as the initial color assignment in the two instances are identical. On the other
hand, the optimal solutions for instances I1 and I2 are dual: in I1 agent ai has to
keep the colors with indices i1 , . . . i 2t , while in I2 agent ai has to keep the colors
with indices i 2t +1 , . . . it (an example can be found in Figure 2). Formal proofs
omitted here for lack of space can be found in an extended version of this work.
Instance I1 Optimal solution Instance I 2 Optimal solution

a a a a
i i i i

a i' a i' a i' a i'

Fig. 2. Example: Instances I1 , I2 , with t = 4 and u = 2. Agent ai has the same initial
item assignment, while ai0 has exactly 2 = t/2 colors for which the initial assignment
differs. The optimal solutions for instance I1 and I2 assign distinct set of colors to the
two agents.

Lemma 2. Given a pair of agents (ai , ai0 ) and instances I1 and I2 , agent ai
can distinguish instance I1 form instance I2 and compute the optimal solution
only if ai knows at least 2t colors initially held by ai0 .
Intuitively, as instances I1 and I2 are indistinguishable from ai ’s point of
view, the only way for ai to break this symmetry is to communicate with ai0 ,
and such communication must involve all the t/2 colors that might be assigned
to ai or ai0 , according to the initial item distribution.
Lemma 3. Given a pair of agents (ai , ai0 ) and instances I1 and I2 , in order to
compute the optimal solution, agents in the pair must exchange at least Ω( m n)
basic messages.
Proof. By Lemma 2, ai has to collect information about at least 2t = m
n different
colors held by ai0 . Using Shannon’s Entropy, the minimum number B of bits
needed to pin down m/n out of m colors is:

m m!

B = log m/n = log m !(m− m
)! n n

Stirling’s approximation gives us the following bound to the quantity log n!:
n−1 n−1
n log n − ≤ log n! ≤ n log n − + log n. (1)
ln 2 ln 2
Using Equation (1), some elementary algebra and the fact that m ≥ n, we
derive the following lower bound on B:

m 1 m m
B = log ≥− + log n − 2 log m + log n ∈ Ω log n .
m/n ln 2 n n
A basic message contains log n bits, therefore the pair needs to exchange at
least Ω( m
n ) basic messages.
t
u
m 2

Theorem 1. The distributed balance color assignment problem has Ω n ·D
message complexity.

Proof. At the end of the execution of any distributed algorithm running on
instance I1 or I2 , each process has to determine its own assignment of colors.
We now recall that in both instances there are P ∈ Ω(D) disjoint pairs at
a distance Ω(D), and, by Lemma 3 any algorithm must use, for each such pair,
Ω(m/n) basic messages to compute the optimal solution. Hence, we have the
following lower bound on message complexity:
m m
Ω(D) · Ω(D) · Ω =Ω · D2 .
n n
Corollary 1. Given a graph G with diameter D linear in the number of nodes
(i.e., D ∈ Ω(n)), then, the message complexity lower bound for the balanced color
assignment problem is Ω(m · n).

Corollary 2. Given a graph G with constant diameter D (i.e., D ∈ Θ(1)), then,
the message complexity lower bound for the balanced color assignment problem
is Ω(m).

Proof. If the graph is connected, there are Θ(n) disjoint pairs of agents at dis-
tance Θ(1), hence we have:
m
Ω(n) · Ω(1) · Ω = Ω (m) .
n
t
u

3 Algorithm Breadth-Balance

In this section we present the algorithm Breadth-Balance to find an approxi-
mate solution to the balanced color assignment on graph topology.
The algorithm works in three phases: (1) the algorithm elects a leader agent,
(2) it builds a breadth-first spanning tree rooted at the leader, and (3) it assigns
colors to agents in successive rounds, each round consisting of a convergecast
and a broadcast along the spanning tree.
Table 3 reports notation used in the description of the algorithm.

Algorithm Breadth-Balance.
Phase 1: To elect the leader, the algorithm uses the Mega-Merger [4] that works
in a decentralized way for arbitrary network and uses O(n log n + |E|) messages
on a graph with n nodes and |E| edges.
Phase 2: The algorithm builds a breadth-first spanning tree using the BFST
algorithm with centralized control [6], where the centralized control is done by
the leader agent elected in Phase 1. The message complexity of the algorithm is
O(n2 ).
C set of colors to be assigned
Qj,i number of items of color cj initially assigned to agent ai
Ki total number of colors to be assigned to agent ai
Ei number of colors already assigned to agent ai
Cr set of colors assigned by the end of round r
Ir interval of weights (number of items of the same color) in round r
Li,r list of colors requested by agent ai in round r
Li,r list of colors requested by agents in the subtree rooted at ai in round r
LIr flagged list of colors requested in round r

At the end of this phase each agent ai knows the identifier of its parent
(denoted with parenti ) and the identifiers of its children (stored in the list
childreni ), for i = 1, . . . , n.
Phase 3: The algorithm computes an approximate solution to the balanced
color assignment problem on graphs. The phase is in turn divided into two stages.

3.1 Agents compute the value q = maxi maxj Qj,i (i.e. the maximum number
of items of the same color initially held by any agent), with a convergecast
followed by a broadcast:
– Convergecast: each agent ai computes qi = maxj Qj,i and collects all
the values qi0 , qi1 , . . . , qiki −1 from its ki ≥ 0 children. Then it sends
max{qi , qi0 , qi1 , . . . , qiki −1 } to its parent.
– Broadcast: the leader computes the exact value q and broadcasts it back
down the tree.
log q
Phase 3.1 is accomplished with O(n · log n ) basic messages.
3.2 Agents actually assigns colors to themselves. After an initialization stage,
the second stage proceeds in rounds.
Initialization: Each agent ai computes g = (b m n c)n − m and stores in the
variable Ki the number of colors it will assign to itself according to the
following rule:
(
bmnc if i < g
Ki = m
b n c + 1 otherwise
A counter variable Ei is used by ai to store the number of colors that agent
ai has already assigned to itself: it is initially set to zero and it is incremented
after each assignment.
Round r: The actual color assignment is done in dlog qe + 1 rounds.3 In
each round a (possibly empty) subset of colors is assigned to agents (each
color to exactly one agent). At the beginning of a generic round r, for r =
0, 1, ..., dlog qe, Cr−1 is the set of colors that has already been assigned in
previous rounds and is known by all agents, Initially C−1 is the empty set,
while at the end Clog q = C, the set of all colors.
3
The way in which rounds are defined is analogous to the one in [3]
In round r, r = 0, . . . , dlog qe, agents consider only colors whose weight Qi,j
falls in the interval Ir = [lr , ur [ defined as:
 q
I0 = 2 , +∞

q
Ir = 2r+1 , 2qr for 1 ≤ r ≤ dlog qe -1

Idlog qe = [0, 1[


Observe that each agent is able to compute Ir , for each r, independently and
consistently.
Each agent ai computes Li,r = {cj ∈ C : cj ∈ / Cr−1 and Qi,j ∈ Ir }, i.e.
the set of not yet assigned colors whose weight falls in the interval Ir . If the
cardinality of Li,r is larger than Ki −Ei (i.e., the maximum number of colors
still assignable to the agent) then agents ai selects the Ki − Ei colors in Li,r
with greatest weight.
Each round r ≤ dlog qe consists of a convergecast followed by a broadcast:
– Convergecast: Leaves send a message containing their Li,r s to their par-
ents. Internal node ai waits for messages from all its children, then it
composes the message Li,r containing the union of the sets of requested
colors in the sub-tree rooted in ai and sends this message to its parent.
Finally, the root (leader) computes the list LIr of colors to be assigned
in the current round.
– Broadcast: The leader a` assigns to itself the colors in L`,r (i.e., the colors
requested in the current round), updates the list of assigned colors (Cr =
Cr−1 ∪ LIr ) and prepares the messages to be delivered to its children.
Each such message contains the complete list of requested colors LIr
together with a binary flag associated to each color. Flag value 1 means
that the color is available, while 0 means that the color has been assigned
to some agent in the current round.
For each child aj , the leader set flags according to the following rules:
(1) all flags of colors in L`,r are set to 0;
(2) the flag for color cz ∈ LIr is set to 0 if cz 6∈ Lz,r ; i.e., if the color cz
has not been requested by any agent in the subtree rooted in aj .
(3) the flag for color cz ∈ LIr is set to 1 only if cz ∈ Lz,r (i.e., if the
color cz has been requested by some agent in the subtree rooted in
aj ). If the color appears in the request lists of two or more children,
then the flag of color cz is set to 1 in exactly one message (arbitrarily
chosen) and to 0 in all the others.
Upon receiving the message from their parents, all other agents act as
the leader, starting from the received message.

Lemma 4. Stage 3.2 of Algorithm Breadth-Balance can be completed using
O(nm · log m
log n ) basic messages.

Proof. Assume that Ar colors are assigned in round r = 0, 1, ..., dlog qe. In a
generic round r we have:
Message

List of colors L i,r
1 0 1 1 1 0
Agent

Colors

1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0

Convergecast Broadcast
(a) (b)

Fig. 3. Example of round r in stage 3.2. (a) Convergecast: each leaf agent sends to its
parent the list of desired colors for the current round. Internal nodes merge their list of
desired colors with those received by their children. (b) Broadcast: each node receives
from its parent the list of all colors required in the round. Flags tell the agent if a color
is available for choosing. Each agent prepares messages for its children in such a way
that the flag for one color is set to one only in one message.

– n − 1 non basic messages are sent to perform the convergecast. Each message
contains at most Ar color identifiers, for a maximum of Ar log m bits per
message. Hence, convergecast uses O(n · Ar log m/ log n) basic messages.
– n − 1 non basic messages are sent to perform the broadcast. Each message
contains Ar color identifiers plus Ar bit for flags. Hence, also broadcast uses
O(n · Ar log m/ log n) basic messages.
Plog q
Summing up for all rounds, as we have r=0 Ar = m, we get:

   
dlog qe dlog qe

X Ar log m  log m log m
X
O n· = O n · · Ar  = O n · ·m ,
r=0
log n log n r=0 log n
t
u
Theorem 2. The Breadth-Balance algorithm finds a feasible solution to the
balanced color assignment problem using O logn n · log q + m log m basic mes-

sages.
Proof. First we prove that the algorithm works correctly, i.e. (a) one color is
assigned to exactly one agent, (b) each color is assigned to at least one agent,
and (c) the assignment is balanced.
a) Two agents cannot assign themselves the same color. Assume two agents
requested the same (still available) color cz in the same round r. Then, if
one is ancestor of the other in the spanning tree, then the ancestor is the first
to have the possibility to assign itself the color (if the flag associated to the
color is 1). When it does, then it will set the flag to 0, and the descendant will
not be able to select the color. Otherwise, if the two agents belong to different
subtrees, then a common ancestor will decide in which of the subtrees the
color can be assigned and the flag is set to 1 in the message going down one
(and only one) subtree.
b) In the last round (r = dlog qe), colors whose Qj,i s fall in the interval Idlog qe =
[0, 1[ are assigned. Thus, it is possible that an agent is assigned a color even
it initially held no item of that color. Hence, If a color is not taken before,
it is eventually assigned in round log q.
c) All colors are assigned, and each color is assigned to exactly one agent. Since
each agent ai assigns itself no more that Ki colors, by a counting argument,
the assignment must be balanced.
Now we concentrate on the message complexity of the algorithm Breadth-
Balance. The first phase requires O(n log n + |E|) basic messages, but |E| ∈
O(n2 ), hence O(n log n + |E|) ⊂ O(n2 ). The second phase requires O(n2 ) basic
log q
messages. Phase 3.1 requires O(n log n ) basic message and phase 3.2 requires
O(nm log m
log n ) basic messages, by Lemma 4. Summing up upper bounds for single
phases, and remembering that m ≥ n, we get:
log q log m n
O(n2 ) + O n + O nm =O · log q + m log m .
log n log n log n
t
u
Corollary 3. Assuming m ∈ O(nc ), for some constant c, and q ∈ O(mm ),
Breadth-Balance algorithm finds a solution to the balanced color assignment
problem using Θ(m · n) message complexity.
We conclude this analysis with two observations. Under the hypothesis of
Corollary 3, we have that:

1. if the diameter of the graph is linear in the number of nodes (i.e., D ∈
Ω(n)), then the algorithm Breadth-Balance has optimal message complexity
Θ(m · n);
log q
2. the upper bound of the brute force approach becomes O(mnD log n) =
2 2
O(m n ), the square of the lower bound.

Synchronous case. The algorithm can be used also for the synchronous case and
we have the following results:
Theorem 3. The Breadth-Balance algorithm finds a feasible solution to the
balanced color assignment problem in time O(max{n2 , D log q}).
Proof. The first phase, that uses the Mega-Merger algorithm, requires O(n) time
units [1]. The second phase, that uses the BFST algorithm with centralized
control, requires O(n2 ) time units [6]. Phase 3.1 requires O(D) time units for
each broadcast and each convergecast. Phase 3.2 requires O(D log q) time units,
as it performs one convergecast and one broadcast in each of the dlog qe + 1
rounds. Summing up upper bounds for single phases we get:

O(n) + O(n2 ) + O(D) + O(D log q) = O(max{n2 , D log q}).
3.1 Approximation factor
The analysis of [3] can be applied to the Breadth- Balance algorithm, giving
the following result:
Theorem 4. Breadth-Balance is a 3-approximation algorithm for the dis-
tributed balanced color assignment problem.
Proof. For lack of space, the proof is omitted here and given in an extended
version of this work.

We now show that the above results is tight by defining a particular family
of input instances whose approximation ratios get arbitrarily close to 3. To this
end, it is sufficient to assume m = n.
Fix q > 30 and let T be the spanning tree computed in Phase 2 of the
algorithm. We form as many disjoint pairs (ai , ak ) as possible, with the constraint
that ai is an ancestor of ak in T , and let A denote the set of remaining nodes,
i.e., ones that are not involved in any pair. We now consider the specific initial
assignment of items to agents described below.
(i) Each agent aj ∈ A has q items colored with cj and none of other colors. No
other agent has items colored
with cj , initially.
q
(ii) Let x = x(r) = 2r+1 − 1, for an arbitrary r ∈ [2..dlog qe − 1]; then, the
paired agents (ai , ak ), have the following initial item assignment:
agent ai : Qi,i = x + 3 i.e., x + 3 items of color ci
Qk,i = x i.e., x items of color ck
Qj,i = 0 ∀j 6= i, k i.e., 0 items of any other color
agent ak : Qi,k = 2x − 3 i.e., 2x − 3 items of color ci
Qk,k = 0 i.e., 0 items of color ck
Qj,k = 0 ∀j 6= i, k i.e., 0 items of any other color
Since m = n, each agent is assigned exactly one color.
Let us now consider the characteristics of any optimal solution.

(i) For each aj ∈ A, optimal solutions assign color cj to agent aj , since it is
the only one with that color. There are no invalid assignments for these items,
hence the contribution of cj to the cost of the optimal assignment is 0.
(ii) Consider now a pair (ai , ak ): agents ai and ak are the only ones holding items
of color ci initially; on the other hand, ai is the only agent with items of color
ck . Hence, an optimal solution may assign color ci to agent ak and color ck to
ai . In this way, the number of invalid assignments for this pair is x + 3.
It turns out the cost of an optimal solution is then equal to (x + 3) times the
number of pairs formed, which is (n − |A|)/2.
Let us now consider a possible solution computed by algorithm
Breadth-Balance. Agent aj ∈ A will be the only one to ask for color cj , in a
proper round of stage 3.2, and will succeed in self assigning the color. As before,
this assignment will give a zero contribution to the total cost of the solution.
Consider the pair (ai , ak ), by the choice of x we have that
q q
x< ≤ x + 3 ≤ 2x − 3 ≤ ,
2r+1 2r
hence, both ai and ak will ask for color ci in round r of stage 3.2. As ai is
ancestor of ak , ai it will self assign color ci , while ak will self assign one of the
colors for which it has zero items and some other agent x items. For the sake of
presentation, let us assume that this color is ck .
The total number of invalid assignments for the pair is (2x − 3) (due to the
assignment of ci to ai ) plus x (due to the assignment of ck to ak ). Hence, the cost
of the solution found by algorithm Breadth-Balance is equal to n−|A| 2 · (3x − 3).
It follows that the ratio between the cost of the approximated solution and
the cost of optimal solution is 3x−3
x+3 which can be made arbitrarily close to 3.

4 Conclusions and further work

In this paper we studied the distributed balanced color assignment problem [3] in
general graph topologies. We presented a lower bound on the message complexity
of the problem, described a distributed algorithm and showed that the algorithm
has optimal message complexity for graphs with diameter linear in the number
of nodes. Finally, we show that the algorithm finds an approximated solution to
the problem, with tight approximation factor equal to three.
Future research will involve experiments to investigate, in practice, how far
the computed solution is from the optimal one, and the study of the specific case
of graphs with constant diameter.

References
1. B. Awerbuch, Optimal Distributed Algorithm for Minimum Weight Spanning Tree,
Counting, Leader Election and Other Problems, SIAM Journal on Computing,
1987.
2. C. J. Chang and P. H. Ho, The β-assignment problems, European Journal of Op-
erational Research 104, 1998.
3. Gianluca De Marco, Mauro Leoncini and Manuela Montangero, Distributed al-
gorithm for a color assignment on asynchronous rings, Proc. 20th International
Parallel and Distributed Processing Symposium (IPDPS06), 2006.
4. R. G. Gallager , P. A. Humblet and P. M. Spira, A Distributed Algorithm for
Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages
and Systems (TOPLAS), v.5 n.1, p.66-77, Jan. 1983.
5. D. Peleg, Distributed Computing: A Locality-Sensitive Approach, SIAM, Philadel-
phia, PA, 2000.
6. Y. Zhu and T.Y. Cheung, A new distributed breadth-first search algorithm. Infor-
mation Processing Letters, 25: 239-333, 1987.