Hicham Lakhlef
email: hicham.lakhlef@irisa.fr

Michel Raynal
email: raynal@irisa.fr

⋆ Franc

¸ois Taïani

Vertex Coloring with Communication and Local Memory Constraints in Synchronous Broadcast Networks

Keywords: Broadcast/receive communication, Bounded local memory, Collision-freedom, Conflictfreedom, Distributed algorithm, Message-passing, Multi-coloring, Network traversal, Scalability, Synchronous system, Tree network, Vertex coloring

The vertex coloring problem has received a lot of attention in the context of synchronous roundbased systems where, at each round, a process can send a message to all its neighbors, and receive a message from each of them. Hence, this communication model is particularly suited to point-topoint communication channels. Several vertex coloring algorithms suited to these systems have been proposed. They differ mainly in the number of rounds they require and the number of colors they use.

This paper considers a broadcast/receive communication model in which message collisions and message conflicts can occur (a collision occurs when, during the same round, messages are sent to the same process by too many neighbors; a conflict occurs when a process and one of its neighbors broadcast during the same round). This communication model is suited to systems where processes share communication bandwidths. More precisely, the paper considers the case where, during a round, a process may either broadcast a message to its neighbors or receive a message from at most m of them. This captures communication-related constraints or a local memory constraint stating that, whatever the number of neighbors of a process, its local memory allows it to receive and store at most m messages during each round. The paper defines first the corresponding generic vertex multicoloring problem (a vertex can have several colors). It focuses then on tree networks, for which it presents a lower bound on the number of colors K that are necessary (namely, K = ⌈ ∆ m ⌉ + 1, where ∆ is the maximal degree of the communication graph), and an associated coloring algorithm, which is optimal with respect to K.

Introduction

Distributed message-passing synchronous systems From a structural point of view, a messagepassing system can be represented by a graph, whose vertices are the processes, and whose edges are the communication channels. It is naturally assumed that the graph is connected.

Differently from asynchronous systems, where there is no notion of global time accessible to the processes, synchronous message-passing systems are characterized by upper bounds on message transfer delays and processing times. Algorithms for such systems are usually designed according to the round-based programming paradigm. The processes execute a sequence of synchronous rounds, such that, at every round, each process first sends a message to its neighbors, then receives messages from them, and finally executes a local computation, which depends on its local state and the messages it has received. The fundamental synchrony property of this model is that every message is received in the round in which it was sent. The progress from one round to the next is a built-in mechanism provided by the model. Algorithms suited to reliable synchronous systems can be found in several textbooks (e.g., [START_REF] Peleg | Distributed computing, a locally sensitive approach[END_REF][START_REF] Raynal | Distributed algorithms for message-passing systems[END_REF]) 1 . When considering reliable synchronous systems, an important issue is the notion of local algorithm. Those are the algorithms whose time complexity (measured by the number of rounds) is smaller than the graph diameter [START_REF] Angluin | Local and global properties in networks of processors[END_REF][START_REF] Linial | Locality in distributed graph algorithms[END_REF].

Distributed graph coloring in point-to-point synchronous systems One of the most studied graph problems in the context of an n-process reliable synchronous system is the vertex coloring problem, namely any process must obtain a color, such that neighbor processes must have different colors (distance-1 coloring), and the total number of colors is reasonably "small". More generally, the distance-k coloring problem requires that no two processes at distance less or equal to k, have the same color. When considering sequential computing, the optimal distance-1 coloring problem is NP-complete [START_REF] Garey | Computers and intractability: a guide to the theory of NP-completeness[END_REF].

When considering the distance-1 coloring problem in an n-process reliable synchronous system, it has been shown that, if the communication graph can be logically oriented such that each process has only one predecessor (e.g., a tree or a ring), O(log * n) rounds are necessary and sufficient to color the processes with at most three colors [START_REF] Cole | Deterministic coin tossing with applications to optimal parallel list ranking[END_REF][START_REF] Linial | Locality in distributed graph algorithms[END_REF] 2 . Other distance-1 coloring algorithms are described in several articles (e.g. [START_REF] Barenboim | Deterministic distributed vertex coloring in polylogarithmic time[END_REF][START_REF] Barenboim | Distributed (Delta+1)-coloring in linear (in Delta) time[END_REF][START_REF] Goldberg | Parallel symmetry-breaking in sparse graphs[END_REF][START_REF] Kuhn | On the complexity of distributed graph coloring[END_REF]). They differ in the number of rounds they need and in the number of colors they use to implement distance-1 coloring. Let ∆ be the maximal degree of the graph (the degree of a vertex is the number of its neighbors). Both algorithms in [START_REF] Barenboim | Deterministic distributed vertex coloring in polylogarithmic time[END_REF][START_REF] Barenboim | Distributed (Delta+1)-coloring in linear (in Delta) time[END_REF] color the vertices with (∆+1) colors. The first one requires O(∆ + log * n) rounds, while the second one uses O(log ∆) rounds. An algorithm is described in [START_REF] Goldberg | Parallel symmetry-breaking in sparse graphs[END_REF] for trees, which uses three colors and O(log * n) rounds. Another algorithm presented in the same paper addresses constant-degree graphs, and uses (∆ + 1) colors and O(log * n) rounds. The algorithm presented in [START_REF] Kuhn | On the complexity of distributed graph coloring[END_REF] requires O(∆ log ∆ + log * n) rounds. These algorithms assume that the processes have distinct identities 3 , which define their initial colors. They proceed iteratively, each round reducing the total number of colors. Distributed distance-2 and distance-3 coloring algorithms, suited to various synchronous models, are presented in [START_REF] Blair | An efficient self-stabilizing distance-2 coloring algorithm[END_REF][START_REF] Bozdag | A framework for scalable greedy coloring on distributed-memory parallel computers[END_REF][START_REF] Chipara | Dynamic conflict-free transmission scheduling for sensor network queries[END_REF][START_REF] Frey | Optimal collision/conflict-free distance-2 coloring in synchronous broadcast/receive tree networks[END_REF][START_REF] Gebremedhin | Parallel distance-k coloring algorithms for numerical optimization[END_REF][START_REF] Herman | A distributed TDMA slot assignment algorithm for wireless sensor networks[END_REF].

Motivation and content of the paper

The previous reliable synchronous system model assumes that there is a dedicated (e.g., wired) bi-directional communication channel between each pair of neighbor processes. By contrast, this paper considers a broadcast/receive communication model in which there is no dedicated communication medium between each pair of neighbor processes. This covers practical system deployments, such as wireless networks and sensor networks. In such networks, the prevention of collisions (several neighbors of the same process broadcast during the same round), or conflicts (a process and one of its neighbors issue a broadcast during the same round), does not come for free. In particular, round-based algorithms that seek to provide deterministic communication guarantees in these systems must be collision and conflict-free (C2-free in short).

We are interested in this paper to offer a programming model in which, at any round, a process can either broadcast a message to its neighbors (conflict-freedom), or receive messages from at most m of its neighbors (m-collision-freedom). This means that we want to give users a round-based programming abstraction guaranteeing conflict-freedom and a weakened form of collision-freedom, that we encapsulate under the name C2m-freedom (if m = 1, we have basic C2-freedom).

The ability to simultaneously receive messages from multiple neighbors can be realized in practice by exploiting multiple frequency channels 4 . The parameter m ≥ 1 is motivated by the following observations. While a process (e.g., a sensor) may have many neighbors, it can have constraints on the number of its reception channels, or constraints on its local memory, that, at each round, allow it to receive and store messages from only a bounded subset of its neighbors, namely m of them (m = 1, gives the classic C2-free model, while m ≥ ∆ assumes no collision can occur as in the classic broadcast/receive model presented previously). This "bounded memory" system parameter can be seen as a scalability parameter, which allows the degree of a process (number of its neighbors) to be decoupled from its local memory size.

C2m-freedom can be easily translated as a coloring problem, where any two neighbors must have different colors (conflict-freedom), and any process has at most m neighbors with the same color (mcollision-freedom). Once such a coloring is realized, message consistency is ensured by restricting the processes to broadcast messages only at the rounds associated with their color. While it is correct, such a solution can be improved, to allow more communication to occur during each round. More precisely, while guaranteeing C2m-freedom, it is possible to allow processes to broadcast at additional rounds, by allocating multiple colors to processes. From a graph coloring point of view, this means that, instead of only one color, a set of colors can be associated with each process, while obeying the following two constraints: (a) for any two neighbor processes, the intersection of their color sets must remain empty; and (b) given any process, no color must appear in the color sets of more than m of its neighbors.

We call Coloring with Communication/Memory Constraints (CCMC) the coloring problem described above. More precisely, this problem is denoted CCMC(n, m, K, ≥ 1), where n is the number of processes (vertices), m is the bound on each local memory (bound on the number of simultaneous communication from a reception point of view), and K the maximal number of colors that are allowed. "≥ 1" means that there is no constraint on the number of colors that that can be assigned to a process. CCMC(n, m, K, 1) denotes the problem instance where each process is assigned exactly one color. From a technical point of view, the paper focuses on tree networks. It presents a lower bound on the value of K for these communication graphs, and an algorithm, optimal with respect to K, which solves both instances of CCMC.

Roadmap

The paper is made up of 7 sections. Section 2 presents the underlying system model. Section 3 formally defines the CCMC problem. Then, considering tree networks, whose roots are dynamically defined, Section 4 presents a lower bound on K for CCMC(n, m, K, 1) and CCMC(n, m, K, ≥ 1) to be solved. Section 5 presents then a K-optimal algorithm solving CCMC(n, m, K, ≥ 1). (from which a solution to CCMC(n, m, K, 1) can be easily obtained.) Section 6 presents a proof of the algorithm. Finally, Section 7 concludes the paper.

Synchronous Broadcast/Receive Model

Processes, initial knowledge, and the communication graph The system model consists of n sequential processes denoted p 1 , ..., p n , connected by a connected communication graph. When considering a process p i , 1 ≤ i ≤ n, the integer i is called its index. Indexes are not known by the processes. They are only a notation convenience used to distinguish processes and their local variables.

Each process p i has an identity id i , which is known only by itself and its neighbors (processes at distance 1 from it). The constant neighbors i is a local set, known only by p i , including the identities of its neighbors (and only them). In order for a process p i not to confuse its neighbors, it is assumed that no two processes at distance less than or equal to 2 have the same identity. Hence, any two processes at distance greater than 2 can have the very same identity.

∆ i denotes the degree of process p i (i.e. |neighbors i |) and ∆ denotes the maximal degree of the graph (max{∆ 1 , • • • , ∆ n }). While each process p i knows ∆ i , no process knows ∆ (a process p x such that ∆ x = ∆ does not know that ∆ x is ∆).

Timing model Processing durations are assumed equal to 0. This is justified by the following observations: (a) the duration of local computations is negligible with respect to message transfer delays, and (b) the processing duration of a message may be considered as a part of its transfer delay.

Communication is synchronous in the sense that there is an upper bound D on message transfer delays, and this bound is known by all the processes (global knowledge). From an algorithm design point of view, we consider that there is a global clock, denoted CLOCK , which is increased by 1, after each period of D physical time units. Each value of CLOCK defines what is usually called a time slot or a round.

Communication operations

The processes are provided with two operations denoted broadcast() and receive(). A process p i invokes broadcast TAG(m) to send the message m (whose type is TAG) to its neighbors. It is assumed that a process invokes broadcast() only at a beginning of a time slot (round). When a message TAG(m) arrives at a process p i , this process is immediately warned of it, which triggers the execution of the operation receive() to obtain and process the message. Hence, a message is always received and processed during the time slot -round-in which it was broadcast.

From a linguistic point of of view, we use the two following when notations when writing algorithms, where predicate is a predicate involving CLOCK and possibly local variables of the concerned process.

when TAG(m) is received do communication-free processing of the message. when predicate do code entailing at most one broadcast() invocation.

Message collision and message conflict in the m-bounded memory model As announced in the Introduction, there is no dedicated communication medium for each pair of communicating processes, and each process has local communication and memory constraints such that, at every round, it cannot receive messages from more than m of it neighbors. If communication is not controlled, "message clash" problems can occur, messages corrupting each other. Consider a process p i these problems are the following.

• If more than m neighbors of p i invoke the operation broadcast() during the same time slot (round), a message collision occurs. • If p i and one of its neighbors invoke broadcast() during the same time slot (round), a message conflict occurs.

As indicated in the introduction, an aim of coloring is to prevent message clashes from occurring, i.e., in our case, ensures C2m-freedom. Let us observe that a coloring algorithm must itself be C2m-free.

The Coloring with Communication/Memory Constraints Problem

Definition of the CCMC problem Let {p 1 , • • • , p n } be the n vertices of a connected undirected graph. As already indicated, neighbors i denotes the set of the neighbors of p i . Let the color domain be the set of non-negative integers, and m and K be two positive integers. The aim is to associate a set of colors, denoted colors i , with each vertex p i , such that the following properties are satisfied.

• Conflict-freedom. ∀i, j : (p i and p j are neighbors) ⇒ colors i ∩ colors j = ∅.

• m-Collision-freedom. ∀i, ∀c : |{j :

p j ∈ neighbors i ∧ c ∈ colors j }| ≤ m. • Efficiency. | ∪ 1≤i≤n colors i | ≤ K.
The first property states the fundamental property of vertex coloring, namely, any two neighbors are assigned distinct colors sets. The second property states the m-constraint coloring on the neighbors of every process, while the third property states an upper bound on the total number of colors that can be used.

As indicated in the Introduction, this problem is denoted CCMC(n, m, K, 1) if each color set is constrained to be a singleton, and CCMC(n, m, K, ≥ 1) if there is no such restriction.

Example An example of such a multi-coloring of a 21-process network, where ∆ = 10, and with the constraint m = 3, is given in Figure 1. Notice that K = ⌈ ∆ m ⌉ + 1 = 5 (the color set is {0, 1, 2, 3, 4}). Particular instances The problem instance CCMC(n, ∞, K, 1) is nothing other than the classical vertex coloring problem, where at most K different colors are allowed (m = ∞ states that no process imposes a constraint on the colors of its neighbors, except that they must be different from its own color). The problem instance CCMC(n, 1, K, 1) is nothing other than the classical distance-2 coloring problem (vertices at distance ≤ 2 have different colors).

Using the colors The reader can easily see that CCMC(n, m, K, ≥ 1) captures the general coloring problem informally stated in the introduction. Once a process p i has been assigned a set of colors colors i , at the application programming level, it is allowed to broadcast a message to neighbors at the rounds (time slots) corresponding to the values of CLOCK such that (CLOCK mod K) ∈ colors i .

4 CCMC(n, m, K, ≥ 1) in a Tree Network: Lower Bounds

An impossibility result

Considering tree networks, this section presents a lower bound on K: neither CCMC(n, m, K, 1), nor CCMC(n, m, K, ≥ 1), can be solved for K ≤ ⌈ ∆ m ⌉. The next sections will present an algorithm solving CCMC(n, m, K, ≥ 1) in the synchronous model described in Section 2, and a proof of it. As shown next, this algorithm is such K = ⌈ ∆ m ⌉ + 1, and is consequently optimal with respect to the total number of colors.

Theorem 1. Neither CCMC(n, m, K, 1), nor CCMC(n, m, K, ≥ 1) can be solved when K ≤ ⌈ ∆ m ⌉.

Proof Let us first show that there is no algorithm solving CCMC(n, m, K, 1) when K ≤ ⌈ ∆ m ⌉. To this end, let us consider a process p ℓ , which has ∆ neighbors (by the very definition of ∆, there is a such process). Let ∆ = m × x + y, where 0 ≤ y < m. Hence, x = ∆-y m = ⌊ ∆ m ⌋ colors are needed to color ∆y = m × x processes. Moreover, if y = 0, one more color is needed to color the y < m remaining processes. It follows that ⌈ ∆ m ⌉ is a lower bound to color the neighbors of p ℓ . As p ℓ cannot have the same color as any of its neighbors, it follows that at least ⌈ ∆ m ⌉ + 1 are necessary to color {p i } ∪ neighbors i , which proves the theorem for CCMC(n, m, K, ≥ 1).

Let us observe that an algorithm solving CCMC(n, m, K, 1) can be obtained from an algorithm solving CCMC(n, m, K, ≥ 1) by associating with each p i a single color of its set colors i . Hence, any algorithm solving CCMC(n, m, ⌈ ∆ m ⌉, ≥ 1) can be used to solve CCMC(n, m, ⌈ ∆ m ⌉, 1). As CCMC(n, m, ⌈ ∆ m ⌉, 1) is impossible to solve, it follows that CCMC(n, m, ⌈ ∆ m ⌉, ≥ 1) is also impossible to solve. 2 T heorem 1 4.2 A necessary and sufficient condition for multicoloring

Let CCMC(n, m, ⌈ ∆ m ⌉ + 1, > 1) denote the problem CCMC(n, m, ⌈ ∆ m ⌉ + 1, ≥ 1)
where at least one node obtains more than one color.

Theorem 2. CCMC(n, m, ⌈ ∆ m ⌉ + 1, > 1)
can be solved on a tree of maximal degree ∆, if and only if

∃i : ⌈ ∆ m ⌉ + 1 > max ∆ i m ∪ ∆ j m p j ∈ neighbors i + 1.
The proof of this theorem appears in Appendix A.

5 CCMC(n, m, K, ≥ 1) in a Tree Network: Algorithm

The algorithm presented in this section use as a skeleton a parallel traversal of a tree [START_REF] Raynal | Distributed algorithms for message-passing systems[END_REF]. Such a traversal is implemented by control messages that visit all the processes, followed by a control flow that returns at the process that launched the tree traversal. Algorithm 1 is a C2m-free algorithm that solves the CCMC(n, m, ⌈ ∆ m ⌉, ≥ 1) problem. It assumes that a single process initially receives an external message START(), which dynamically defines it as the root of the tree. This message and the fact that processes at distance smaller or equal to 2 do not have the same identity provide the initial asymmetry from which a deterministic coloring algorithm can be built. The reception of the message START() causes the receiving process (say p r ) to simulate the reception of a fictitious message COLOR(), which initiates the sequential traversal.

Messages The algorithm uses two types of messages, denoted COLOR() and TERM().

• The messages COLOR() implement a control flow visiting in parallel the processes of the tree from the root to the leaves. Each of them carries three values, denoted sender, cl map, and max cl.

sender is the identity of the sender of the message. If it is the first message COLOR() received by a process p i , sender defines the parent of p i in the tree. -cl map is a dictionary data structure with one entry for each element in neighbors x ∪ {id x }, where p x is the sender of the message COLOR(). cl map[id x ] is the set of colors currently assigned to the sender and, for each id j ∈ neighbor x , cl map[id j ] is the set of colors that p x proposes for p j . -max cl is an integer defining the color domain used by the sender, namely the color set {0, 1, . . . , (max cl -1)}. Each child p i of the message sender will use the color domain defined by max(max cl, σ i ) to propose colors to its own children (σ i is defined below). Moreover, all the children of the sender will use the same slot span {0, 1, . . . , (max cl -1)} to broadcast their messages. This ensures that their message broadcasts will be collisionfree 5 .

• The messages TERM() propagate the return of the control flow from the leaves to the root. Each message TERM() carries two values: the identity of the destination process (as this message is broadcast, this allows any receiver to know if the message is for it), and the identity of the sender.

Local variables Each process p i manages the following local variables. The constant

∆ i = |neighbors i | is the degree of p i , while the constant σ i = ⌈ ∆ i m ⌉ + 1
is the number of colors needed to color the star graph made up of p i and its neighbors.

• state i (initialized to 0) is used by p i to manage the progress of the tree traversal. Each process traverses five different states during the execution of the algorithm. States 1 and 3 are active states: a process in state 1 broadcasts a COLOR() message for its neighbors, while a process in state 3 broadcasts a message TERM() which has a meaning only for its parent. States 0 and 2 are waiting states in which a process listens on the broadcast channels but cannot send any message. Finally, state 4 identifies local termination. • parent i stores the identity of the process p j from which p i receives a message COLOR() for the first time (hence p j is the parent of p i in the tree). The root p r of the tree, defined by the reception of the external message START(), is the only process such that parent r = id r . • colored i is a set containing the identities of the neighbors of p i that have been colored.

• to color i is the set of neighbors to which p i must propagate the coloring (network traversal).

• color map i [neighbors i ∪ {id i }] is a dictionary data structure where p i stores colors of its neighbors in color map i [neighbors i ], and its own colors in color map i [id i ]; colors i is used as a synonym of color map i [id i ]. • max cl i defines both the color domain from which p i can color its children, and the time slots (rounds) at which its children will be allowed to broadcast. • slot span i is set to the value max cl carried by the message COLOR() received by p i from its parent. As this value is the same for all the children of its parent, they will use the same slot span to define the slots during which each child will be allowed to broadcast messages.

Initial state

In its initial state (state i = 0), a process p i waits for a message COLOR(). As already indicated, a single process receives the external message START(), which defines it at the root process.

It is assumed that CLOCK = 0 when a process receives this message. When it receives it, the corresponding process p i simulates the reception of the message COLOR(id i , cl map, σ i ) where cl map[id i ] defines its color, namely, (CLOCK + 1) mod σ i (lines 01-02). Hence, at round number 1, the root will send a message COLOR() to its children (lines [START_REF] Peleg | Distributed computing, a locally sensitive approach[END_REF][START_REF] Raynal | Fault-tolerant agreement in synchronous message-passing systems[END_REF].

Initialization: σi = ⌈ ∆ i m ⌉ + 1; statei ← 0; colorsi ← ∅; colorsi is a synonym of color mapi[idi]. (
else statei ← 3 % pi is a leaf % (23) end if (24) else color mapi[idi] ← color mapi[idi] ∩ cl map[idi] (25) end if.
(26) when (CLOCK mod slot spani) ∈ colorsi) ∧ (statei ∈ {1, 3}) do (27) case (statei = 1) then broadcast COLOR(idi, color mapi, max cli); statei ← 2 (28) (statei = 3) then broadcast TERM(parenti, idi); statei ← 4 % pi's subtree is colored % (29) end case.

(30) when TERM(dest, id) is received do (31) if (dest = idi) then discard the message (do not execute lines 25-28) end if;

(32) coloredi ← coloredi ∪ {id}; (33) if (coloredi = neighbors i ) (34) then if (parenti = idi) then the root pi claims termination else statei ← 3 end if (35) end if. Algorithm 1: C2m-free algorithm solving CCMC(n, m, ⌈ ∆ m ⌉ + 1, ≥ 1) in tree networks (code for p i )
Algorithm: reception of a message COLOR() When a process p i receives a message COLOR() for the first time, it is visited by the network traversal, and must consequently (a) obtain an initial color set, and (b) propagate the the network traversal, if it has children. The processing by p i of this first message COLOR(sender, cl map, max cl) is done at lines 05-23. First, p i saves the identity of its parent (the sender of the message) and its proposed color set (line 05), initializes colored i to {sender}, and to color i to its other neighbors (line 06). Then p i obtains a color set proposal from the dictionary cl map carried by the message (line 07), computes the value max cl i from which its color palette will be defined, and saves the value max cl carried by the message COLOR() in the local variable slot span i (line 08). Let us remind that the value max cl i allows it to know the color domain used up to now, and the rounds at which it will be able to broadcast messages (during the execution of the algorithm) in a collision-free way.

Then, the behavior of p i depends on the value of to color i . If to color i is empty, p i is a leaf, and there is no more process to color from it. Hence, p i proceeds to state 3 (line 22).

If to color i is not empty, p i has children. It has consequently to propose a set of colors for each of them, and save these proposals in its local dictionary color map i [neighbors i ]. To this end, p i computes first the domain of colors it can use, namely, the set {0, 1, . . . , (max cl i -1)}, and considers that each of these colors c is represented by m tokens colored c. Then, it computes the multiset 6 , denoted tokens i , containing all the colored tokens it can use to build a color set proposal for each of its children (line 10). The multiset tokens i is initially made up of all possible colored tokens, from which are suppressed (a) all tokens associated with the colors of p i itself, and, (b) one colored token for each color in color map i [parent i ] (this is because, from a coloring point of view, its parent was allocated one such colored token for each of its colors).

Then, p i checks if it has enough colored tokens to allocate at least one colored token to each of its children (assigning thereby the color of the token to the corresponding child). If the predicate |tokens i | ≥ |to color i | is satisfied, p i has enough colored tokens and can proceed to assign set of colors to its children (lines [START_REF] Peleg | Distributed computing, a locally sensitive approach[END_REF][START_REF] Raynal | Fault-tolerant agreement in synchronous message-passing systems[END_REF]. Differently, if the predicate |tokens i | < |to color i | is satisfied, p i has more children than colored tokens. Hence, it must find more colored tokens. For that, if colors i (i.e., color map i [id i ]) has more than one color, p i suppresses one color from colors i , adds the m associated colored tokens to the multiset tokens i (lines 12-13), and re-enters the "while" loop (line 11).

If colors i has a single color, this color cannot be suppressed from colors i . In this case, p i considers the color set of its parent (color map i [parent i ]), takes the maximal color of this set, suppresses it from color map i [parent i ], adds the associated colored token to the multiset tokens i , and -as before-reenters the "while" loop (line 15). Only one token colored cl is available because the (m -1) other tokens colored cl were already added into the multiset tokens i during its initialization at line 10.

As already said, when the predicate |tokens i | < |to color i | (line 11) becomes false, tokens i contains enough colored tokens to assign to its children. This assignment is done at lines 19-20. Let ch = |to color i | (number of children of p i ); p i extracts ch pairwise disjoint and non-empty subsets of the multiset tokens i , and assigns each of them to a different neighbor. "Non-empty non-intersecting multisets" used at line 19 means that, if each of z multisets tk[id x ] contains a token with the same color, this colored token appears at least z times in the multiset tokens i .

If the message COLOR(sender, cl map, -) received by p i is not the first one, it was sent by one of its children. In this case, p i keeps in its color set color map i [id i ] (colors i ) only colors allowed by its child sender (line 24). Hence, when p i has received a message COLOR() from each of its children, its color set colors i has its final value.

Algorithm: broadcast of a message A process p i is allowed to broadcast a message only at the rounds corresponding to a color it obtained (a color in colors i = color map i [id i ] computed at lines 07, 12, and 24), provided that its current local state is 1 or 3 (line 26).

If state i = 1, p i received previously a message COLOR(), which entailed its initial coloring and a proposal to color its children (lines 09-21). In this case, p i propagates the tree traversal by broadcasting a message COLOR() (line 27), which will provide each of its children with a coloring proposal. Process p i then progresses to the local waiting state 2.

If state i = 3, the coloring of the tree rooted at p i is terminated. Process p i consequently broadcasts the message TERM(parent i , id i ) to inform its parent of it. It also progresses from state 3 to state 4, which indicates its local termination (line 28).

Algorithm: reception of a message TERM() When a process p i receives such a message it discards it if it is not the intended destination process (line 31). If the message is for it, p i adds the sender identity to the set colored i (line 32). Finally, if colored i = neighbors i , p i learns that the subtree rooted at it is colored (line 33). It follows that, if p i is the root (parent i = i), it learns that the algorithm terminated. Otherwise, it enters state 3, that will direct it to report to its parent the termination of the coloring of the subtree rooted at it.

Solving CCMC(n, m, K, 1) in a tree Algorithm 1 can be easily modified to solve CCMC(n, m, K, 1). When a process enters state 3 (at line 22 or line 34), it reduces color map i [id i ] (i.e., colors i ) to obtain a singleton.

6 CCMC(n, m, K, ≥ 1) in a Tree Network: Cost and Proof

The proof assumes n > 1. Let us remember that colors i and color map i [id i ] are the same local variable of p i , and p r denotes the dynamically defined root process.

Cost of the algorithm Each non-leaf process broadcasts one message COLOR(), and each non-root process broadcasts one message TERM(). Let x be the number of leaves. There are consequently (2n -(x + 1)) broadcasts. As ∆ ≤ x + 1 (7 ), the number of broadcast is upper bounded by 2n -∆.

Given an execution whose dynamically defined root is the process p r , let d be the height of the corresponding tree. The root computes the colors defining the slots (rounds) at which its children can broadcast the messages COLOR() and TERM(). These colors span the interval [0..⌈ ∆r m ⌉], which means that the broadcasts of messages COLOR() by the processes at the first level of the tree span at most ⌈ ∆r m ⌉ + 1 rounds. The same broadcast pattern occurs at each level of the tree. It follows that the visit of the tree by the messages COLOR() requires at most d⌈ ∆ m ⌉ rounds. As the same occurs for the the messages TERM(), returning from the leaves to the root, it follows that the time complexity of the algorithm is O(d⌈ ∆ m ⌉).

Lemma 1. Algorithm 1 is conflict-free.

Proof The algorithm uses two types of messages: COLOR() and TERM(). We first show conflictfreedom for COLOR() messages (if a process broadcasts a message COLOR(), none of its neighbors is broadcasting any message in the same round). Let us first notice that a process p i broadcasts at most one message COLOR(), and one message TERM() (this is due to the guard state i ∈ {1, 3}, line 26, and the fact that the broadcast of a message makes its sender progress to the waiting state 2 or 4). Moreover, let us make the following observations.

• Observation 1: The first message sent by any node is of type COLOR() (line 27).

• Observation 2: Except for the root process, a message COLOR() is always broadcast by a process after it received a message COLOR() (which triggers the execution of lines 03-25). • Observation 3: Except for leaf processes, a message TERM() is always broadcast by a process after it received a message TERM() from each of its children (lines 30-35 and line 28.).

Observations 1 and 2 imply that when the root process broadcasts its COLOR() message, none of its neighbors is broadcasting a message, and they all receive the root's COLOR() message without conflict.

Let us now consider a process p i , different from the root, which receives its first message COLOR k () (from its parent p k ). Because there is no cycle in the communication graph (a tree), all the children of p i (neighbors i \ {p k }) are in state 0, waiting for their COLOR() message. Moreover, due to Observations 1 and 2, they will receive from p i their message COLOR() without conflict. After sending its COLOR() message, p i 's parent p k remains in the waiting state 2 until it receives a TERM() message from all its children (lines 32-33), which include p i . As a consequence, p k is not broadcasting any message in the round in which it receives p i 's COLOR() message, which is consequently received without conflict by all its neighbors. As far the messages TERM() are concerned we have the following. Initially, only a leaf process can broadcast a message, and when it does it, its parent is in the waiting state 2 (since it broadcast a message COLOR() at line 27 and it must receive messages TERM() to proceed to state 3). Hence a message TERM() broadcast by a leaf cannot entail conflict. Let us now consider a non-leaf process p i . It follows from Observation 3 that p i can broadcast a message TERM() only when its children are in state 4 (in which they cannot broadcast), and its parent (because it has not yet received a message TERM() from each of its children) is in the waiting state 2. Hence, we conclude that the broadcast of a message TERM() by a non-leaf process is conflict-free, which concludes the proof of the lemma.

2 Lemma 1

Definition A message COLOR(sender, cl map, max cl) is well-formed if its content satisfies the following properties. Let sender = id i . M1 The keys of the dictionary data structure cl map are the identities in neighbors i ∪ {id i }.

M2 ∀ id ∈ (neighbors i ∪ {id i }) : cl map[id] = ∅. M3 ∀ id ∈ neighbors i : cl map[id] ∩ cl map[id i ] = ∅. M4 ∀c : |{j : (id j ∈ neighbors i ) ∧ (c ∈ cl map[id j ])}| ≤ m. M5 1 < max cl ≤ ⌈ ∆ m ⌉ + 1. M6 ∀ id ∈ (neighbors i ∪ {id i }) : cl map[id] ⊆ [0..max cl -1].
Once established in Lemma 3, not all properties M1-M6 will be explicitly used in the lemmas that follow. They are used by induction to proceed from one well-formed message to another one. Lemma 2. If a message COLOR(sender, cl map, max cl) received by a process p i = p r is well-formed and entails the execution of lines 05-23, the while loop (lines 11-18) terminates, and, when p i exits the loop, the sets colors i and color map i [parent i ] are not empty, and their intersection is empty.

Proof Let us consider a process p i = p r that receives a well-formed COLOR j (sender, cl map, max cl) message from p j . Let us assume COLOR() causes p i to start executing the lines 05-23, i.e., COLOR() is the first such message received by p i . The body of the while loop contains two lines (lines 12 and 14) that select elements from two sets, colors i and color map i [parent i ] respectively.

Before discussing the termination of the while loop, we show that lines 12 and 14 are well-defined, i.e. the sets from which the elements are selected are non-empty. To this aim, we prove by induction that the following invariant holds in each iteration of the loop:

color map i [parent i ] = ∅, (1)
colors i = ∅, (2)
|tokens i | = m × max cl i -m × |colors i | -|color map i [parent i ]|. (3)
Just before the loop (i.e., before line 11), Assertion (1) follows from the assignment to color map i [parent i ] at line 05 and the property M2 of COLOR j () (id j = parent i ). Assertion (2) also follows from M2 (colors i is synonym of color map i [id i ]). Assertion (3) follows from M3, M6, and the initialization of max cl i at line 08.

Let us now assume that Assertion (1) holds at the start of a loop iteration (i.e., just before lines 12). There are two cases. This concludes the proof that the three assertions (1)-( 3) are a loop invariant. Hence, Assertion (1) and Assertion (2) imply that lines 12 and 14 are well-defined.

|color map i [parent i ]| > m × max cl i -m × |colors i | -|to colors i |, > m × max cl i -m × |colors i | -(∆ i -1) (because of line 06), > m × σ i -m × |colors i | -(∆ i -1) (because of line 08), > m × (⌈ ∆ i m ⌉ + 1) -m × |colors i | -(∆ i -1) (by definition), > ∆ i + m -m × |colors i | -(∆ i -1) (arithmetic), > m × (1 -|colors i |) + 1.

Hence, because |colors

i | ≤ 1, we obtain |color map i [parent i ]| > 1,
Let us now observe that, in each iteration of the loop, new colored tokens are added to tokens i , and thus |tokens i | is strictly increasing. Because |to color i | remains unchanged, the condition |tokens i | < |to color i | necessarily becomes false at some point, which proves that the loop terminates.

Just after the loop, the invariant is still true. In particular Assertion (1) and Assertion [START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF] show that both the sets colors i and color map i [parent i ] are not empty when p i exits the while loop.

Finally, due to to the fact that the message COLOR j () is well-formed, it follows from M3 that we have colors i ∩ color map i [parent i ] = ∅ after line 07. As colors are added neither to colors i , nor to color map i [parent i ] in the loop, their intersection remains empty, which concludes the proof of the lemma.

2 Lemma 2 Lemma 3. All messages COLOR() broadcast at line 27 are well-formed.

Proof To broadcast a message COLOR(), a process p i must be in local state 1 (line 27). This means that p i executed line 21, and consequently previously received a message COLOR(sender, cl map, max cl) that caused p i to execute lines 05-23.

Let us first assume that COLOR() is well-formed. It then follows from Lemma 2 that p i exits the while loop, and each of colors i and color map i [parent i ] is not empty (A), and they have an empty intersection (B). When considering the message COLOR(id i , color map i , max cl i ) broadcast by p i we have the following.

• M1 follows from the fact that the entries of the dictionary data structure created by p i are: color map i [parent i ] (line 05), color map i [id i ] (line 07), and color map i [id] for each id ∈ to colors i = neighbors i \ {parent i } (lines 06 and 20), and the observation that no entry is ever removed from color map i is the rest of the code. • M2 follows from (A) for color map i [parent i ] and color map i [id i ], from line 19 for the identities in to colors i = neighbors i \ {parent i } (due to |tokens i | ≥ |to colors i | when line 19 is executed, and the non-intersection requirement of the tk[id] sets, no tk[id] is empty), and from the observation that color map i is not modified between the end of line 20 and the broadcast of line 27. This last claim is derived from the fact that color map i is only modified when messages are received, and that neither p i 's parent nor p i 's children are in states that allow them to send messages while p i is transitioning from line 20 to line 27. • Similarly M3 follows for id = parent i : from (B) and the fact that color map i [parent i ] never increases, for id ∈ to color i = neighbors i \ {parent i }: from the fact that, due to lines 10 and 12, at line 19 tokens i contains no token whose color belongs to colors i , from which we have tk[id] ∩ color map i [id i ] = ∅ for any id ∈ to color i .

• M4 follows from the construction of tokens i . This construction ensures that, for any color c, tokens i contains at most m tokens with color c (line 10, 13, and 15). • M5 is an immediate consequence of the assignment max cl i ← max(max cl, σ i ) at line 15.

• M6 follows from the following observations:

for id ∈ {id i , parent i }: from max cl ≤ max cl i (line 08) and the fact that the message COLOR() received by p i is well-formed (hence

color map i [id i ] ∪ color map i [parent i ] ⊆ [0..(max cl -1)]
), for id ∈ to color i = neighbors i \ {parent i }: from the fact that tokens i contains only tokens whose color is in [0..(max cl i -1)] (line 10).

The previous reasoning showed that, if a process receives a well-formed message COLOR(), executes lines 05-23 and line 27, the message COLOR(id i , color map i , max cl i ) it will broadcast at this line is well-formed. Hence, to show that all messages broadcast at line 27 are well-formed, it only remains to show that the message COLOR(id r , color map r , max cl r ) broadcast by the root p r is well-formed. Let us remember that neighbors r is a constant defined by the structure of the tree, and parent r = id r / ∈ neighbors r .

Let us notice that the message COLOR(id, cl map, max cl), that p r sends to itself at line 02,is not well-formed. This is because, cl map[id] is not defined for id ∈ neighbors i . When p r receives this message we have the following after line 10:

|tokens r | = m × |σ r | -m = m × (|σ r | -1) = m⌈ ∆r m ⌉ ≥ ∆ r , from which we conclude |tokens r | ≥ ∆ r = |to colors r | = |neighbors i |.
Hence, p r does not execute the loop body, and proceeds to lines 19-20 where it defines the entries color map r [id] for id ∈ to colors r = neighbors r . A reasoning similar to the previous one shows that the message COLOR(id r , color map r , max cl r ) broadcast by p r at line 27 satisfies the properties M1-M6, and is consequently well-formed. (The difference with the previous reasoning lies in the definition of the set to colors i which is equal to neighbors i \ {parent i } for p i = p r , and equal to neighbors r for p r .)

2 Lemma 3

Lemma 4. If a process p i computes a color set (colors i ), this set is not empty.

A each child p j of p i adopts cl map[id j ] as its initial color set and assigns it to color map j [id j ];

B p i 's parent p k uses cl map[id k ] to update color map k [id k ] at line 24 such that color map k [id k ] ⊆ cl map[id k ].
(A), (B), and M4 imply that just after p i 's neighbors have processed p i 's message, the lemma holds. As already seen in the proof of other lemmas, color map j [id j ] may subsequently decrease, but never increases: colors can be suppressed from color map j [id j ] (line 24) but never added to it. And the same is true at p i for its set of colors color map i [id i ], and at its parent p k for color map k [id k ]. It then follows that |{j : j ∈ neighbors i ∧ c ∈ colors j }| ≤ m throughout the execution of the algorithm, which concludes the proof of the lemma.

2 Lemma 6

Lemma 7. Algorithm 1 is collision-free.

Proof We have to show that no process can have more than m of its neighbors that broadcast during the same round. Initially, all processes are in state 0. Let us consider a process p i and assume that one of its neighbors p j is broadcasting a message. Let us further assume that this message is of type COLOR().

• If p j is p i 's parent, p j 's COLOR() message is the first message received by p i , and both p i and its children (p i 's remaining neighbors) are in state 0, and hence silent. There is no collision at p i . • If p j is one of p i 's children, the value slot span j used by p j at line 26 is equal to max cl contained in the message COLOR(-, -, max cl) first received by p j from p i . Because of Lemma 3, this message is well-formed, and consequently satisfies property M6. Any other child p ℓ of p i broadcasting during this round will have received the same first message, and will therefore be using the same slot span ℓ = max cl value. It follows from Property M6, the assignment of line 07 executed by any child p ℓ (of p i ) that received the message, and the fact that its set colors ℓ can only decrease after being first assigned, that colors ℓ ⊆ [0..slot span ℓ -1] for any child p ℓ of p i (C).

Lemma 6, Property (C), and the CLOCK -based predicate defining the rounds at which a process is allowed to broadcast (line 26), imply that at most m children of p i can broadcast during the same round. If p i has a parent p k (i.e. p i is not the root), both p i and p k are in state 2, and hence p k is silent, proving the lemma. If p i is the root, all its neighbors are its children, and the lemma also holds.

The same reasoning applies to the messages TERM() broadcast by the children of p i and its parent.

2 Lemma 7
Lemma 8. Each process computes a set of colors, and the root process knows when coloring is terminated.

Proof Let us first observe that, due to Lemmas 2 and 3, no process p i = p r can loop forever inside the while loop (lines 11-18), when it receives its first message COLOR(). The same was proved for the root p r at the end of the proof of Lemma 4. Moreover, a process cannot block at line 24 when it receives other messages COLOR() (one from each of its children). Hence, no reception of a message COLOR() can prevent processes from terminating the processing of the message. The same is trivially true for the processing of a message TERM().

Let us first show that each process obtains a non-empty set of colors. To this end, we show that each non-leaf process broadcasts a message COLOR().

• When the root process p r receives the external message START(), it "simulates the sending to itself" of the message COLOR(id r , color map r , σ r ), where the dictionary data structure color map r has a single element, namely, color map r [id r ] = {1}. The root p r executes consequently the lines 25-23, during which it obtains a color (color map r [id r ] = {1}, line 07), and computes a set of proposed colors color map r [id j ] for each of its children p j (lines [START_REF] Peleg | Distributed computing, a locally sensitive approach[END_REF][START_REF] Raynal | Fault-tolerant agreement in synchronous message-passing systems[END_REF]. It then progresses to the local non-waiting state 1 (line 21). Hence, during the first round, it broadcasts to its neighbors the message COLOR(id r , color map r , σ r ).Because the algorithm is conflict-and collision-free (Lemmas 1 and 5), this message is received by all the root's neighbors. • Let us now consider a process p i that receives a message COLOR(sender, color map, max cl)

for the first time. It follows from Lemma 4 that p i starts computing a non-empty set colors i and enters the waiting state 1 (line 21). Finally, as colors i ⊆ [0..slot span i -1], and CLOCK never stops increasing, the predicate of line 26 is eventually satisfied. It follows p i broadcasts the messageCOLOR(id i , color map i , max cl i ). As above all of p i 's neighbors will receive this message.

It follows that COLOR() messages flood the tree from the root to the leaves.

Moreover, when a process p i has received a message COLOR() from each of its neighbors (children and parent), it has obtained the final value of its color set color map i [id i ] = colors i . Due to lemma 4, this set is not empty, which concludes the first part of the proof.

Let us now show that the root learns coloring termination. This relies on the messages TERM(). As previously, due to Lemma 1 and Lemma 7, these messages entail neither message conflicts nor message collisions.

Let us observe that each leaf process enters the non-waiting state 3. When the predicate of line 26 is satisfied at a leaf p ℓ (this inevitably occurs), this process broadcasts the message TERM() to its parent p i . Then, when p i has received a message TERM() from each of its children, it broadcasts TERM() to its own parent. This sequence repeats itself on each path from a leaf to the root. When the root has received a message TERM() from each of its children, it learns termination (line 34), which concludes the proof of the lemma.

2 Lemma 8

Lemma 9.

| 1≤i≤n colors i | = ⌈ ∆ m ⌉ + 1.
Proof Let p r , p a , • • • , p ℓ be a path in the tree starting at the root p r and ending at a leaf p ℓ . It follows from

• the content of the parameter max cl of the messages COLOR(sender, cl map, max cl) broadcast along this path of the tree (broadcast at line 27 and received at line 03), and • the assignment of max(max cl, σ i ) to max cl i at line 08, that max cl ℓ = max(σ r , σ a , • • • , σ ℓ ). Let p ℓ1 , ..., p ℓx be the set of leaves of the tree. It follows that max(max cl ℓ1 , • • • , max cl ℓx ) = max(σ 1 , • • • , σ n ), i.e., the value max cl carried by any message is

≤ ⌈ ∆ m ⌉ + 1.
The fact that a process p i uses only colors in [0..(max cl i -1)], combined with Theorem 1 implies the lemma. The algorithm is consequently optimal with respect to the number of colors.

2 Lemma 9

Theorem 3.

Let K = ⌈ ∆ m ⌉ + 1.
Algorithm 1 is a C2m-free algorithm, which solves CCMC(n, m, K, ≥ 1) in tree networks. Moreover, it is optimal with respect to the value of K.

Proof The proof that Algorithm 1 is C2m-free follows from Lemma 1 and Lemma 7. The proof that it satisfies the Conflict-freedom, Collision-freedom, and Efficiency properties defining the CCMC(n, m, K, ≥ 1) problem follows from Lemmas 2-6, and Lemma 8. The proof of its optimality with respect to K follows from Lemma 9.

2 T heorem 3

Conclusion

The paper first introduced a new vertex coloring problem (called CCMC), in which a process may be assigned several colors in such a way that no two neighbors share colors, and for any color c, at most m neighbors of any vertex share the color c. This coloring problem is particularly suited to assign rounds (slots) to processes (nodes) in broadcast/receive synchronous communication systems with communication or local memory constraints. Then, the paper presented a distributed algorithm which solve this vertex coloring problem for tree networks in a round-based programming model with conflicts and (multi-frequency) collisions. This algorithm is optimal with respect to the total number of colors that can be used, namely it uses only K = ⌈ ∆ m ⌉ + 1 different colors, where ∆ is the maximal degree of the graph.

It is possible to easily modify the coloring problem CCMC to express constraints specific broadcast/receive communication systems. As an example, suppressing the conflict-freedom constraint and weakening the collision-freedom constraint into ∀i, ∀c

: |{j : (id j ∈ neighbors i ∪ {id i }) ∧ (c ∈ colors j )}| ≤ m, (4)
captures bi-directional communication structures encountered in some practical systems in which nodes may send and receive on distinct channels during the same round. Interestingly, solving the coloring problem captured by ( 4) is equivalent to solving distance-2 coloring in the sense that a purely local procedure (i.e., a procedure involving no communication between nodes) executed on each node can transform a classical distance-2 coloring into a multi-coloring satisfying (4). More precisely, assuming a coloring col : V → [0..(K * m) -1] providing a distance-2 coloring with K * m colors on a graph G = (V, E), it is easy to show that the coloring (with one color per vertex)

col ′ : V → [0 .. K -1] x → col(x) mod K, (5)
fulfills (4) on G (8 ). Since the distance-2 problem with K * m colors is captured by CCMC(n, 1, K * m, 1) (as discussed in Section 3), the proposed algorithm can also solve the coloring condition captured by [START_REF] Barenboim | Distributed graph coloring, fundamental and recent developments[END_REF] on trees in our computing model. Moreover, from an algorithmic point of view, the proposed algorithm is versatile, making it an attractive starting point to address other related problems. For instance, in an heterogeneous network, lines 19-20 could be modified to take into account additional constraints arising from the capacities of individual nodes, such as their ability to use only certain frequencies.

Last but not least, a major challenge for future work consists in solving the CCMC problem in general graphs. The new difficulty is then to take into account cycles.

Proof The terms "process" and "vertex" are considered here as synonyms. To simplify notation, we consider in the following that id i = i. Let us first notice that if follows from its definition that K ≥ 2.

Proof of the "if direction". The proof of this direction consists in a sequential algorithm that associates two colors to a process p i whose position in the tree satisfies the previous predicate.

Algorithm 2 is a sequential algorithm solving CCMC(n, m, ⌈ ∆ m ⌉ + 1, 1). Using the control flow defined by a simple depth-first tree traversal algorithm, it takes two input parameters, a process p j , and its color. Then, assuming a coloring of both p j and its parent, it recursively colors the vertices of the tree rooted at p j . The initial call is DF MColoring(i, 0) where p i is a vertex satisfying the predicate stated in the theorem, and 0 the color assigned to it. The function parent color(j) returns the color of the parent of p j if p j = p i and returns no value if p j = p i . Let us notice that, except for p j = p i , parent color(j) is called only after the parent of p j obtained a color. Algorithm 2: Sequential multi-coloring of a tree with a depth-first traversal algorithm (code for p i ) A call to DF MColoring(j, c) works as follows. First, color c is assigned to p j . If p j has a single neighbor (its parent, which issued this call), the current procedure call terminates. Otherwise, the current invocation computes the multiset of colored tokens which includes (a) m identical tokens for each possible color, except the colors of p j and its parent, and (b) (m -1) identical tokens with the color of parent j (line 03). Let us notice that all the colored tokens are ordered by their color number, hence the notion of a "token with a smallest color" is well-defined. Then, for each of p j 's neighbor p k (except its parent), taken one after the other (line 04), a token with a smallest color is selected for p k (which will inherit the corresponding color) and withdrawn from the multiset tokens (hence, this token can no longer be used to associate a color to another neighbor of p j , line 04). Due to line 03, the multiset tokens used to assign colors to p j 's neighbors, is such that |tokens| = (K -2) × m + (m -1) = (K -1) × m -1 (Property P1). (The factor (K -2) comes from the fact the colors are in the color set {0, 1, • • • , (K -1)} \ {color j , parent color(j)}. The term (m -1) comes from the fact that color i = 0 is already used once for the neighbor p i .) It follows that the loop is well-defined. The subtree rooted at p k is then depth-first recursively colored (line 05).

procedure DF MColoring(j, c) is (01) colori ← c; (02) if |neighbors j | > 1 then (03) tokens ← { m colored tokens for each color in {0, 1, • • • , (K -1)} \ {colorj , parent color(j)} } ∪ { (m -
It follows that (a) no two neighbors can be assigned the same color (line 03), (b) each process is assigned a color as small as possible (line 04), and (c) at most m neighbors of a process can be assigned the same color (lines 02 and 05).

We now show that, given the previous coloring, it is possible to assign (at least) one more color to (at least) the root p i . The set of K colors used in Algorithm 2 is the set {0, 1, • • • , (K -1)}. Let us consider any vertex p j , which is a neighbor of p i . Due to the property stated in the theorem, we have K > ⌊ ∆ j m ⌋ + 1, which, due to Lemma 10 translates as (K -1) × m > ∆ j (P2). As color i = 0 and K ≥ 2, we have color i = K -1. Moreover, we also have color j = K -1. This follows from the assumption K > ⌈ ∆ i m ⌉ + 1, and the fact that, to color p i and its neighbors, Algorithm 2 uses ⌈ ∆ i m ⌉ + 1 ≤ K -1 colors, namely the color set {0, • • • , (K -2)}. When executing DF MColoring(j, c) for a neighbor p j of p i , Algorithm 2 executes (∆ j -1) times the body of the "for" loop (lines 04-06), (once for each neighbor of p j , except p i , which has already been assigned a color). It follows from (P2) that (K -1) × m -1 > ∆ j -1. Combined with (P1) we obtain |tokens| > ∆ j -1, from which we conclude that tokens = ∅ is always true. It is consequently a loop invariant in each call related to a neighbor p j of p i . It follows that tokens always contains a colored token with the highest color, namely (K -1). This color can consequently be assigned to p i , in addition of color 0, without violating the conflict-freedom, m-collision-freedom, and efficiency defining the CCMC problem solved by Algorithm 2. This concludes the proof of the "if" part of the theorem.

Proof of the "only if direction". In the following we use the following notations, where M is a multi-set.

• |M | is the size of M (in the following all sets and multisets are finite),

• set(M ) is the underlying set of M , the set of elements present at least once in M ,

• 1 M (x) is the multiplicity of an element x in M . By construction we have

1 M (x) ≥ 1 ⇐⇒ x ∈ set(M ) and |M | = x∈set(M ) 1 M (x). (6)
If A and B are two multisets, A ⊎ B is the multiset union of A and B. In particular we have:

|A ⊎ B| = |A| + |B| and 1 A⊎B (x) = 1 A (x) + 1 B (x). (7)
We consider a set S as a special case of a multi-set in which all elements of S have a multiplicity of 1:

x ∈ S ⇐⇒ 1 S (x) = 1.

Let us assume that CCMC(n, m, K, > 1) can be solved on a tree, such that at least one process, i.e. p i , is allocated more than one color:

|colors i | ≥ 2. ( 8
)
For ease of exposition, and without loss of generality, we assume all other processes are allocated only one color: ∀j = i :

|colors j | = 1. (9)
Let C neighbors i denote the multiset of colored tokens allocated to the neighbors of p i :

C neighbors i = p j ∈neighbors i colors j . (10)
From ( 9) and [START_REF] Cole | Deterministic coin tossing with applications to optimal parallel list ranking[END_REF] we derive (by way of ( 7))

|C neighbors i | = | p j ∈neighbors i colors j | = p j ∈neighbors i |colors j | = |neighbors i | = ∆ i . (11)
This means that ∆ i colored tokens are needed to color the neighbors of p i . Because the coloring solves CCMC(n, m, K, > 1), m-Collision-freedom means that ∀c ∈ set(C neighbors i ) :

1 C neighbors i (c) ≤ m. (12)
Using ( 12) in (6) applied to C neighbors i gives us

|C neighbors i | = c∈set(C neighbors i ) 1 C neighbors i (c) ≤ |set(C neighbors i )| × m, (13)
which yields, with [START_REF] Frey | Optimal collision/conflict-free distance-2 coloring in synchronous broadcast/receive tree networks[END_REF]

K > ∆ i m + 1 (20)
which concludes the first part of the proof on the "only if" direction.

Let us now turn to the neighbors of p i . For p j ∈ neighbors i we consider similarly to p i the set of colored tokens allocated to p j 's neighbors (which include p i ):

C neighbors j = p k ∈neighbors j colors k . (21)
Hence (as for p i ) we have:

|C neighbors j | = p k ∈neighbors j |colors k |. (22)
Contrary to p i however, all of p j 's neighbors do not have only one color allocated: p i has at least two, by assumption. This yields

|C neighbors j | = |colors i | + p k ∈neighbors j \{p i } |colors k |, (23)
≥ 2 + |neighbors j -1| × 1 using ( 8) and ( 9), (24)

≥ 2 + ∆ j -1 ≥ ∆ j + 1. (25)
As for p i , m-Collision-freedom means that

≥ |set(C neighbors j )| + 1 because of ( 9), (31)

K -1 ≥ |set(C neighbors j )|. (32)
Injecting (32) into (27) gives us

(K -1) × m ≥ ∆ j + 1, ( 33
) (K -1) × m > ∆ j , (34)
K -1 > ∆ j m ≥ ∆ j m because of Lemma 10, (35)
K > ∆ j m + 1. (36)
(36) concludes the proof of necessary condition to solve CCMC(n, m, K, > 1). 2 T heorem 2

B Defining the slots of the upper layer programming level

When the root process claims termination, the other processes are in their local state 4, but cannot exploit the multi-coloring assignment. As indicated in the paragraph "Using the colors" (just before Section 4), to do that, they need to know the value K = ⌈ ∆ m ⌉ + 1. The knowledge of K can be brought to the root process by the messages TERM(), and then disseminated from the root to all the processes. Algorithm 1 is slightly modified and enriched with Algorithm 3 to allow all processes to know the value of K. Modified lines are postfixed by a "prime", and new lines are numbered Nxy.

Each process p i manages a new local variable ak i (approximate k), initialized to σ i = ⌈ ∆ i m ⌉ + 1, and whose final value will be K. The additional behavior of p i is now as follows.

• First, when a non-root process informs its parent of its local termination, it now broadcasts the message TERM(parent i , id i , ak i ) (line 28'). Hence, the values ak of the leaves will be the first to be known by their parent. • When a process receives a message TERM(dest, id, ak) (line 30'), in addition to its previous statements, it updates ak i to max(ak i , ak) (line N1). It follows that the root learns the value of K (which is the maximal value ak it receives). When it learns it, the root progresses to the local state 5 (line 34'). • Starting from the root, when a non-leaf process is in state 5 and allowed to broadcast (predicate of line N2), it broadcasts the message END(id i , ak) and progresses to the final state 6 (line N3). • Finally, when a process p i , in state 4, receives a message END(sender, ak) from its parent, it updates ak i to max(ak i , ak) and progresses to state 5 (line N6). It will then forward the message END(sender, ak) to its children if it has some, and in all cases will enter local state 6 (line N3).

After the local state of a process p i became 6, we have ak i = K. Hence, all processes are provided with a round-based programming level in which each process p i can C2m-freely broadcast messages at all the rounds such that (CLOCK mod ak i ) ∈ colors i .

Figure 1 :

 1 Figure 1: Multi-coloring of a 21-process 10-degree tree with the constraint m = 3 (5 colors)

|C

  neighbors j | ≤ |set(C neighbors j )| × m. (26) (25) and (26) yield|set(C neighbors j )| × m ≥ ∆ j + 1.(27)As for p i we have (Conflict-freedom)set(C neighbors j ) ∩ colors j = ∅,(28)leading toK ≥ |set(C neighbors j ) ∪ colors j | by definition,(29)≥ |set(C neighbors j )| + |colors j | because of (28),

  01) when START() is received do % a single process pi receives this external message % (02) pi executes lines 04-25 as if it received the message COLOR(idi, cl map, σi) where cl map [idi] = {(CLOCK + 1) mod σi} . then tokens i ← { m tokens with color x, for each x ∈ [0..(max cli -1)] \ colors i } \ { one token with color z, for each z ∈ color mapi[parenti] }; (11) while (|tokens i| < |to colorsi|) do (12) if (|colorsi| > 1) then let cl ∈ colors i; suppress cl from colors i

	(03) when COLOR(sender, cl map, max cl) is received do
	(04) if (first message COLOR() received)
	(05) then parenti ← sender; color mapi[parenti] ← cl map[sender];
	(06)	coloredi ← {sender}; to colori ← neighborsi \ {sender};
	(07)	color mapi[idi] ← cl map[idi]; % Synonym of colorsi %
	(08)	max cli ← max(max cl, σi); slot spani ← max cl;
	(09)	if (to colori = ∅)	% next lines: tokens i is a multiset %
	(10)
	(13)		add m tokens colored cl to tokens i
	(14)		else let cl be the maximal color in color mapi[parenti];
	(15)		add one token colored cl to tokens i;
	(16)		color mapi[parenti] ← color mapi[parenti] \ {cl}
	(17)	end if
	(18)	end while;
	(19)

Extract |to colorsi| non-empty non-intersecting multisets tk[id] (where id ∈ to colori) from tokens i such that no tk[id] contains several tokens with the the same color;

[START_REF] Raynal | Fault-tolerant agreement in synchronous message-passing systems[END_REF]

for each id ∈ to colori do color mapi[id] ← {colors of the tokens in tk[id]} end for;

[START_REF] Raynal | Distributed algorithms for message-passing systems[END_REF]

statei ← 1 % pi has children % (22)

•

  If |colors i | > 1, lines 14-16 are not executed, and consequently color map i [parent i ] is not modified. It follows from the induction assumption that Assertion (1) still holds. • If |colors i | ≤ 1, we have the following. Because we are in the while loop, we have |tokens i | < |to colors i |, which, combined with Assertion (3), implies |to colors i | > m × max cl im × |colors i | -|color map i [parent i ]|, from which we derive

  which means that p i 's local variable color map i [parent i ] contains at least two elements before the execution of line 12. Because only one color is removed from color map i [parent i ], this local variable remains nonempty after line 16, thus proving Assertion (1).Let us now assume that both Assertion (2) and Assertion (3) hold at the start of a loop iteration (i.e., just before line 12). There are two cases.

• Case |colors i | > 1. In this case we have: (i) one color is removed from colors i , (ii) m colored tokens are added to tokens i , and (iii) color map i [parent i ] remains unchanged. |colors i | > 1 and (i) imply that Assertion (2) remains true; and (i) and (ii) mean that Assertion (3) is preserved. • Case |colors i | ≤ 1. In this case we have: (i) one color is removed from color map i [parent i ], and one colored token added to tokens i , and (ii) colors i stays unchanged. (i) implies that Assertion (3) remains true, and (ii) ensures Assertion (2) by assumption.

  (required number of colors for p i 's neighbors): Because |set(C neighbors i )| is an integer,[START_REF] Goldberg | Parallel symmetry-breaking in sparse graphs[END_REF] implies that Because the coloring solves CCMC(n, m, K, > 1), it respects Conflict-freedom, implying thatset(C neighbors i ) ∩ colors i = ∅,(16)and hence|set(C neighbors i ) ∪ colors i | = |set(C neighbors i )| + |colors i |, By definition K ≥ |set(C neighbors i ) ∪ colors i |, which yields

	|set(C neighbors i )| ≥	|C neighbors i | m	≥	∆ i m	.	(14)
	|set(C neighbors i )| ≥	∆ i m	.	(15)
								(17)
	≥ |set(C neighbors i )| + 2	using (8),	(18)
	≥	∆ i m	+ 2 >	∆ i m	+ 1.	using (15)	(19)

The case where processes may exhibit faulty behaviors (such as crashes or Byzantine failures) is addressed in several books (e.g.,[2, 18, 19,

[START_REF] Raynal | Fault-tolerant agreement in synchronous message-passing systems[END_REF]).[START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF] log * n is the number of times the function log needs to be iteratively applied in log(log(log(...(log n)))) to obtain a value ≤ 2. As an example, if n is the number of atoms in the universe, log * n ⋍ 5.3 Some initial asymmetry is necessary to solve breaking symmetry problems with a deterministic algorithm.

Depending on the underlying hardware (e.g., multi-frequency bandwidth, duplexer, diplexer), variants of this broadcast/receive communication pattern can be envisaged. The algorithms presented in this paper can be modified to take them into account.

As we will see, conflicts are prevented by the message exchange pattern imposed by the algorithm.

Differently from a set, a multiset (also called a a bag), can contain several times the same element. Hence, while {a, b, c} and {a, b, a, c, c, c} are the same set, they are different multisets.

Let pi be the process that has ∆ as degree. If pi is the root of the tree, the tree contains at least ∆ leaf processes. This is because each neighbor of pi is either a leaf or the root of a subtree that has at least one leaf process. And if pi is not the root of the tree, pi possesses ∆ -1 children, and the number of leaf processes is at least ∆ -1 following a similar reasoning.

This is because (a) distance-2 coloring ensures that any vertex and its neighbors have different colors, and (b) there are at most m colors c1, ..., cx ∈ [0..(K * m) -1] (hence x ≤ m), such that (c1 mod K) = • • • = (cx mod K) = c ∈ [0..(K -1)].

Proof Let us first observe that, if a process p i = p r receives a message COLOR(-, cl map, -), the previous lemma means that this message is well-formed, and due to property M2, its field cl map[id i ] is not empty, from which follows that the initial assignment of a value to color map i [id i ] ≡ colors i is a non-empty set. Let us also observe, that, even if it is not well-formed the message COLOR(-, cl map, -) received by the root satisfies this property. Hence, any process that receives a message COLOR() assigns first a non-empty value to color map i [id i ] ≡ colors i .

Subsequently, a color can only be suppressed from color map i [id i ] ≡ colors i at line 24 when p i receives a message COLOR() from one of its children. If p i is a leaf, it has no children, and consequently never executes line 24. So, let us assume that p i is not a leaf and receives a message COLOR(id j , cl map, -) from one of its children p j . In this case p i previously broadcast at line 27 a message COLOR(id i , color map i , -) that was received by p j and this message is well-formed (Lemma 3).

A color c that is suppressed at line 24 when p i processes COLOR(id j , cl map, -) is such that c ∈ colors i and c / ∈ cl map[id i ]. cl map[id i ] can be traced back to the local variable color map j [id i ] used by p j to broadcast COLOR() at line 27. Tracing the control flow further back, color map j [id i ] was initialized by p j to color map i [id i ] (line 05) when p j received the well-formed message COLOR() from p i .When processing COLOR() received from p i , process p j can suppress colors from color map j [id i ] only at line 16, where it suppresses colors starting from the greatest remaining color. We have the following.

• If p i is not the root, the message COLOR() it received was well-formed (Lemma 3). In this case, it follows from the proof of Lemma 2 that it always remains at least one color in color map j [id i ]. • If p i = p r , its set colors r is a singleton (it "received" COLOR(id r , cl map r , -) where cl map r has a single entry, namely cl map r [id r ] = {1}). When p j computes tokens j (line 10) we have

Hence, p j does not execute the loop, and consequently does not modify color map j [id r ].

Consequently, the smallest color of colors i ≡ color map i [id i ] is never withdrawn from color map j [id i ]. It follows that, at line 24, p i never withdraws its smallest color from the set color map i [id i ]. 2 Lemma 4 Lemma 5. If p i and p j are neighbors colors i ∩ colors j = ∅.

Proof As all color sets are initialized to ∅, the property is initially true. We show that, if a process receives a message COLOR(), the property remains true. As TERM() messages do not modify the coloring-lines 30-35-they do not need to be considered.

Let us consider two neighbor processes p i and p j , which computes their color sets (if none or only one of p i and p j computes its color set, the lemma is trivially satisfied). As the network is a tree, one of them is the parent of the other. Let p i be the parent of p j .

Process p i broadcast a message COLOR(-, cl map, -) at line 27 in which the set cl map[id j ] is color map i [id j ], as computed at line 19. If this message is received by p j , this set will in turn be assigned to color map i [id j ] at p j . As this message is well-formed (Lemma 3), we therefore have color map i [id i ] ∩ color map j [id j ] = ∅ (Property M3 of a well-formed message). Then, while p i can be directed to suppress colors from color map i [id i ] at line 24, it never adds a color to this set. The same is true for p j and color map j [id j ]. It follows that the predicate color map i [id i ] ∩ color map j [id j ] = ∅ can never be invalidated.

2 Lemma 5 Lemma 6. ∀i, ∀c : |{j : j ∈ neighbors i ∧ c ∈ colors j }| ≤ m.

Proof The property is initially true. We show that it remains true when processes receive messages.

Let us consider a process p i that broadcasts a message COLOR(). Due to the fact that such messages are broadcast only at line 27, it follows from Lemma 3 that the message COLOR(id i , cl map, -) broadcast by p i is well-formed. Hence it satisfies property M4. When processing this message


Anna Loddo Stéphanie

Loddo

Compte

come

Dans le but d'éclairer comment les opérations-martyre sont formulées, performées et intégrées culturellement dans la société palestinienne et plus largement dans la sphère régionale, Abufarha propose une analyse historique de la construction et de la transformation de la relation à l'État israélien en expansion, et des conditions de production d'un discours palestinien de résistance autour notamment de la notion d'istishhadi (martyr). L'auteur examine ensuite des données aussi diverses que des interviews de membres des factions résistantes et des familles de martyrs, les histoires de vie de martyrs et l'organisation de leurs opérations, ainsi que la production et la circulation de discours et matériaux culturels.

Abufarha met ainsi en évidence l'absence d'un profi l-type du candidat au martyre, ce dernier pouvant être motivé par une diversité d'expériences personnelles, de conceptions de la souffrance, de la résistance et du sacrifi ce. En revanche, la performance du martyre s'inscrit à l'intérieur d'un discours culturel de résistance, cadre dans lequel émerge la motivation de passer à l'acte. Construit en relation avec l'expérience de la violence israélienne contre les Palestiniens, ce discours vise à affi rmer l'enracinement des Palestiniens et leur unité alors qu'ils ont perdu « la capacité de naviguer dans le temps et l'espace » (p. 105). Abufarha décrit longuement les « conditions ontologiques » de la rencontre avec l'État d'Israël et sa politique d'expansion, caractérisée par la restriction de mouvement, le confi nement et la fragmentation spatiale, la violence et la peur qu'elle engendre.

Le martyre inverse cet ordre politique et ontologique. L'exercice d'une « violence mimétique » dans l'espace civil israélien dont les Palestiniens sont exclus pervertit le sens de la normalité et de la sécurité des Israéliens dans une performance où les barrières sont forcées et détruites par le corps du martyr qui explose. L'analyse de la vie sociale de ce dernier après sa mort révèle comment mourir en martyr est « mourir pour vivre » ; le mort devient un héros national et son sacrifi ce génère la production et la circulation de matériaux culturels. Par la création d'un rapport d'homologie entre le corps du martyr et le paysage palestinien, son sacrifi ce apparait comme une performance culturelle visant à affi rmer la liberté, l'enracinement et l'unité territoriale palestinienne.

Cet ouvrage aborde les attentats-suicide sous l'angle jusque-là peu exploré de leur dimension culturelle. Abufarha démontre de manière convaincante que le succès des opérationsmartyre auprès des organisations de résistance et de la société palestinienne ne peut s'expliquer sans tenir compte des conditions d'occupation de la Palestine et des signifi cations culturelles que les Palestiniens et les acteurs régionaux accordent aux opérations. Tout en fournissant une base solide à son argumentation, sa description ethnographique détaillée des conditions de vie sous occupation introduit les lecteurs à l'expérience particulière de la spatialité en Palestine occupée. Cependant, la majeure partie de l'ouvrage est un compte-rendu historique et ethnographique de l'occupation israélienne, alors que le thème des opérations-martyre n'est abordé que dans les deux derniers chapitres. Cette structure refl ète l'argument de l'auteur, mais celui-ci aurait pu être plus amplement étoffé par la présentation de davantage de matériaux culturels, notamment ceux produits par le candidat au martyre. Une attention portée à la perception des opérationsmartyre parmi la population palestinienne aurait également enrichi son propos. L'ouvrage n'en est pas moins une contribution importante à la recherche sur la violence politique. Dans sa démarche exigeante d'explorer le phénomène à différentes échelles, Abufarha apporte un éclairage important sur les conditions locales et globales de la formulation des modes de résistance en Palestine.

Stéphanie Loddo Institut de recherche interdisciplinaire sur les enjeux sociaux CNRS-INSERM-EHESS, Paris, France

  Anthropologie et Sociétés, vol. 34, 2010 ABUFARHA Nasser, 2009, The Making of a Human Bomb. An Ethnography of Palestinian Resistance. Durham, Duke University Press, 288 p., bibliogr., index (Stephanie Loddo) Dans cette analyse anthropologique des attentats-suicide dans le contexte de la Palestine occupée, Nasser Abufarha livre les résultats d'une enquête menée en 2003 à Jénine, sa ville d'origine. Le phénomène des 'amaliyyat istishhadiyya (opérations-martyre) organisées par le Hamas durant la période d'Oslo s'est intensifi é et généralisé parmi toutes les factions comme mode de résistance lors de la deuxième Intifada. Depuis les attentats du 11 septembre 2001, l'intérêt académique pour le terrorisme et en particulier les attentats-suicide s'est manifesté principalement dans des approches politiques, stratégiques et psychologiques. Cet ouvrage s'en démarque par l'attention portée à la construction historique et sociale de ce type de violence. Il se concentre sur les conditions selon lesquelles un individu choisit son corps comme site de la violence et comment celle-ci devient une ressource politique et identitaire pour les Palestiniens.