Jochen Seidel
email: seidelj@ethz.ch

Jara Uitto
email: juitto@ethz.ch

Roger Wattenhofer
email: wattenhofer@ethz.ch

Randomness vs. Time in Anonymous Networks

In an anonymous network, symmetry breaking tasks can only be solved if randomization is available. But how many random bits are required to solve any such task? As it turns out, the answer to this question depends on the desired runtime of the algorithm. Since any randomized anonymous network algorithm can be decomposed into a randomized 2-hop coloring stage and a deterministic stage, we tackle the question by focusing on the randomized stage. We establish that for any reasonable target function f , there is a randomized 2-hop coloring scheme running in O(f (n)) time. Our coloring scheme allows to trade an increase in runtime by a factor of d for a decrease by the d th root in the random bit complexity. To show that the achieved trade-off is asymptotically optimal for any choice of f , we establish a trade-off lower bound. Our bounds yield that it is sufficient to consider the cases when f is between Ω(log * n) and O(log log n). We obtain that for the two extreme cases, i.e., where f ∈ Θ(log * n) and f ∈ Θ(log log n), the random bit complexity is Θ( d √ n) and Θ(log n), respectively, for any constant d. The trade-off achieved by our scheme is asymptotically optimal for any f , i.e., reducing the runtime must lead to an increase in the random bit complexity.

Due to space constraints, in this extended abstract all proofs had to be omitted.

Introduction

We consider randomized algorithms running in a network of n communicating nodes. The network is anonymous, as opposed to identified networks in which nodes can be distinguished by their unique identifiers (IDs). The computational power of deterministic anonymous network algorithms has been found to be rather limited [START_REF] Naor | What can be computed locally?[END_REF]. When nodes have access to random bits however, many interesting tasks become solvable. But what is the amount of random bits, i.e., the random bit complexity, required to solve any such task?

Consider, for example, the fundamental symmetry breaking problem of graph coloring, where the goal is to assign colors to nodes so that every two neighbors get a different color. In a complete network, i.e., when every node is connected to all other nodes, a unique color must be used for every node. Therefore, for complete networks the answer is at least log n random bits. One result of our work is that in expectation Ω(log n) random bits are required even if every node in the network has at most 3 neighbors. Moreover, we establish that O(log n) random bits in expectation are also sufficient to solve all tasks in any network.

Alongside the random bit complexity, as a second efficiency measure, we consider the runtime required to solve such tasks. Increasing the runtime allows one to draw the random bits more carefully, thus reducing the number of unnecessarily drawn random bits. Conversely, it is true that drawing random bits more generously enables faster runtime. We study how exactly the random bit complexity relates to the runtime.

More precisely, we show that there is an efficiency trade-off between the runtime and the random bit complexity required to solve any task. Our contribution is to establish asymptotically tight lower and upper bounds on the achievable trade-off. Those bounds imply that using more than O(log log n) rounds to solve a task does not result in a better random bit complexity. Linial's local symmetry breaking lower bound, showing that one requires roughly log * n rounds [START_REF] Linial | Locality in Distributed Graph Algorithms[END_REF] to 3-color a ring, already hints that the interesting cases occur when the asymptotic runtime is between log * n and log log n. In the respective extreme cases, i.e., when the runtime is log * n or log log n, our lower bound states that the random bit complexity is Ω( d √ n) and Ω(log n), correspondingly, where d is a constant that depends on the runtime.

For the upper bound we devise a randomized scheme that produces sufficiently many random bits for any anonymous network algorithm. To this end we introduce the notion of a target function f which specifies the desired runtime of our scheme, and consider the cases where f (n) is asymptotically between log * n and log log n. The trade-off achieved by our scheme asymptotically matches the lower bound with high probability 1 and in expectation, also for all runtimes f that lie between the two extremes.

Our scheme is uniform: The algorithm does not require any knowledge about the network topology, such as its size or diameter. Note that this rules out the trivial approach of drawing a unique identifier with O(log n) bits, which would succeed with high probability. Being uniform, our scheme can be used to devise new uniform algorithms for classic sym-metry breaking problems by utilizing existing deterministic algorithms. This is due to the fact that those algorithms often assume IDs, but function correctly even if those IDs are only locally unique. As one example, consider the deterministic coloring algorithm from [START_REF] Schneider | A log-star distributed maximal independent set algorithm for growth-bounded graphs[END_REF] which runs in O(log * n) time on graphs with bounded growth. By applying our scheme, we obtain a uniform coloring algorithm for anonymous networks with the same runtime. Our lower bounds imply that an O(log * n) runtime is the best possible. This speed comes at the cost of a relatively high random bit complexity, which is Θ( d √ n). Note, however, that d is a freely selectable parameter of our scheme (a constant) that is hidden in the big-O notation. If one is willing to sacrifice the asymptotic runtime, on the other end of the spectrum, our approach allows to solve the same task in O(log log n) time using as little as O(log n) random bits. By tuning the f parameter, any trade-off between the two extremes can be achieved.

So how can we possibly bound the random bit complexity for any computable task? The answer to this complexity question can be based on a recent computability result by Emek et al. [START_REF] Dolev | Randomization adaptive self-stabilization[END_REF], where they showed that a 2-hop coloring2 is necessary and sufficient to replace access to random bits in any anonymous network algorithm. We therefore establish our upper bound by devising a 2-hop coloring algorithm whose runtime and random bit complexity are tuneable by a target function f and a constant d.

Related Work

The theory of distributed computability began with Angluin's insight that leader election is impossible in anonymous rings [START_REF] Angluin | Local and global properties in networks of processors (extended abstract)[END_REF]. A similar impossibility argument can be made for deterministic algorithms that solve local symmetry breaking tasks, e.g., coloring or MIS, and literally hundreds of more impossibilities are known [START_REF] Attiya | Impossibility Results for Distributed Computing[END_REF]. In short, the computational power of deterministic anonymous network algorithms is limited [START_REF] Naor | What can be computed locally?[END_REF].

Under the assumption of uniform algorithms, the leader election impossibility result from [START_REF] Angluin | Local and global properties in networks of processors (extended abstract)[END_REF] extends to the case where randomization is available. In contrast to that, when randomization is available, there are well known algorithms that solve the local symmetry breaking problems coloring [START_REF] Linial | Locality in Distributed Graph Algorithms[END_REF] and MIS [START_REF] Alon | A fast and simple randomized parallel algorithm for the maximal independent set problem[END_REF][START_REF] Luby | A simple parallel algorithm for the maximal independent set problem[END_REF] also in anonymous networks. It is interesting to note that both randomized MIS algorithms are used to construct completely derandomized (deterministic) variants under the assumption that unique identifiers are available. How much randomization an anonymous network will ever need from a computability perspective can be characterized in terms of a 2-hop coloring [START_REF] Emek | Anonymous networks: randomization = 2-hop coloring[END_REF]. In this paper, based on that observation, we tackle the complexity question, i.e., the random bits and runtime necessary to obtain a 2-hop coloring. When unique IDs are available, runtime and messages (size and quantity) can be traded, e.g., in MIS and coloring algorithms [START_REF] Schneider | Trading bit, message, and time complexity of distributed algorithms[END_REF]. Focusing on anonymous algorithms, we trade runtime with a fourth complexity measure, namely the random bit complexity. Also outside of anonymous algorithms, randomization has many applications in distributed computing (cf. [START_REF] Attiya | Distributed Computing: Fundamentals, Simulations and Advanced Topics[END_REF]), e.g., in agreement [START_REF] Aspnes | Randomized consensus in expected o(n log 2 n) operations per processor[END_REF][START_REF] Attiya | Tight bounds for asynchronous randomized consensus[END_REF], self stabilization [START_REF] Dolev | Randomization adaptive self-stabilization[END_REF], and non-uniform leader election [START_REF] Alon | A fast and simple randomized parallel algorithm for the maximal independent set problem[END_REF].

Still, one of the most basic tasks to solve in a distributed setting remains coloring, and often coloring and MIS algorithms go hand in hand. As such, they were studied thoroughly (please refer to [START_REF] Barenboim | Distributed Graph Coloring: Fundamentals and Recent Developments[END_REF] for an extensive overview), usually aiming to use at most ∆ + 1 (or at least some small function of ∆) many colors. Perhaps surprisingly, when identifiers are available, deterministic coloring algorithms are among the fastest. A recent series of results by Barenboim, Elkin, and Kuhn [START_REF] Barenboim | Distributed (delta+1)-coloring in linear (in delta) time[END_REF][START_REF] Kuhn | Weak graph colorings: distributed algorithms and applications[END_REF][START_REF] Barenboim | Distributed (delta+1)-coloring in linear (in delta) time[END_REF] yields a ∆+1 coloring in O(∆+log * n) runtime by utilizing a new defective coloring technique. The picture is completed by the observation that colors can be traded for runtime [START_REF] Barenboim | Deterministic distributed vertex coloring in polylogarithmic time[END_REF], i.e., one can get

O(∆ ε + log * n) for O(∆) colors or O(log ∆ • log * n) for O(∆ 1+ε
) colors. These deterministic coloring algorithms have in common that they need to assume IDs. Also randomized algorithms (e.g. [START_REF] Schneider | A log-star distributed maximal independent set algorithm for growth-bounded graphs[END_REF][START_REF] Schneider | Symmetry breaking depending on the chromatic number or the neighborhood growth[END_REF]) often assume IDs and are not uniform, i.e., they assume knowledge about n or some other global network parameter. Relieving the algorithm from that knowledge, we focus on achieving a good random bit complexity instead of a low number of used colors, and refer to standard methods (e.g., the deterministic approach in [START_REF] Goldberg | Parallel symmetry-breaking in sparse graphs[END_REF]) to reduce this number. On the other hand, the O(log n) algorithms for MIS [START_REF] Alon | A fast and simple randomized parallel algorithm for the maximal independent set problem[END_REF][START_REF] Luby | A simple parallel algorithm for the maximal independent set problem[END_REF] and coloring [START_REF] Linial | Locality in Distributed Graph Algorithms[END_REF] are uniform, and can be formulated even in very restricted models [START_REF] Scott | Feedback from nature: an optimal distributed algorithm for maximal independent set selection[END_REF]. We improve on the runtime at the lowest possible price one needs to pay for that in terms of random bit complexity.

It is worth mentioning that in the context of self-stabilization [START_REF] Dolev | Self-Stabilization[END_REF], uniform MIS and (2-hop) coloring protocols were studied also for anonymous networks. For instance, [START_REF] Shukla | Developing self-stabilizing coloring algorithms via systematic randomization[END_REF] considers deterministic and randomized protocols that color paths and rings, and later [START_REF] Gradinariu | Self-stabilizing vertex coloration and arbitrary graphs[END_REF] obtain randomized protocols for MIS and coloring in arbitrary networks. The recent work [START_REF] Blair | An efficient self-stabilizing distance-2 coloring algorithm[END_REF] presents a 2-hop coloring protocol for graphs of bounded degree. In the self-stabilization context, the difficulty lies in dealing with faults. The random bit complexity is of no concern in the protocols mentioned above, and the runtime of [START_REF] Blair | An efficient self-stabilizing distance-2 coloring algorithm[END_REF] is necessarily much higher than in our non-faulty environment.

Sequential probabilistic computability was pioneered by Gill [START_REF] Gill | Computational complexity of probabilistic turing machines[END_REF], showing that, e.g., ZPP = RP ∩ co-RP, and Rabin [START_REF] Rabin | Probabilistic automata[END_REF], who reduced certain probabilistic automata to deterministic ones. Reducing the error probability using few additional random bits was studied, e.g., for the classes RP ( [START_REF] Karp | A time-randomness tradeoff[END_REF], cf. [START_REF] Vadhan | Pseudorandomness[END_REF]) and BPP (e.g., [START_REF] Andreev | Weak random sources, hitting sets, and BPP simulations[END_REF]), and [START_REF] Lautemann | BPP and the polynomial hierarchy[END_REF] relates BPP to the polynomial hierarchy. Derandomization [START_REF] Luby | Pairwise independence and derandomization[END_REF] is closely related to extracting randomness from low entropy sources [START_REF] Nisan | Extracting randomness: A survey and new constructions[END_REF][START_REF] Vadhan | Pseudorandomness[END_REF]. The field of randomized computability and complexity is covered in great detail in [START_REF] Motwani | Randomized Algorithms[END_REF]. A distributed version of BPP, so called (p, q)-deciders, and derandomization in this setting were studied in [START_REF] Fraigniaud | Randomized distributed decision[END_REF]. We characterize how many random bits are necessary to solve any anonymous network task with probability 1 depending on the desired runtime.

A concept related to that of randomization is non-determinism. Study of this concept's distributed notion, where often IDs are assumed, was initiated by Naor and Stockmeyer [START_REF] Naor | What can be computed locally?[END_REF], who studied what could be checked by deterministic constant-time algorithms if some labeling (non-determinism) is known in advance. Subsequently, the number of non-deterministic choices required to solve decision problems in this distributed manner was investigated [START_REF] Korman | Proof labeling schemes[END_REF]. A hierarchy of decidable problems depending on the necessary amount of non-determinism arises [START_REF] Göös | Locally checkable proofs[END_REF], also when the network is anonymous. Recently, it was found that in fact the combination of nondeterminism with randomization allows distributed algorithms to decide any language in constant time [START_REF] Fraigniaud | Towards a complexity theory for local distributed computing[END_REF].

Preliminaries

We model the network as a simple, undirected graph G = (V, E), where V and E denote the set of nodes and edges, respectively. The network size, i.e., the cardinality of V , is denoted by n. Furthermore, the exclusive

neighborhood of a node u ∈ V in G is the set Γ (u) = {v : (u, v) ∈ E}. Similarly, we denote by Γ 2 (u) = Γ (u) ∪ v∈Γ (u) {w : w = u, (v, w) ∈ E} the exclusive 2-hop neighborhood of u.
Note that throughout this paper, we assume that all logarithms are taken to base 2.

Uniform Randomized Algorithms. We consider randomized algorithms that always return a correct output and have finite expected runtime (Las Vegas algorithms). Our algorithms run under the synchronous broadcast model, i.e., the execution of an algorithm can be divided into discrete rounds starting from round 1. Furthermore, the execution of any round r + 1 for any node u begins only when every other node has finished executing round r. Round r executed by a node u is divided into 4 parts in the following manner. 1. Receive. Node u receives the messages sent by nodes in Γ (u) in round r -1. 2. Randomized Computation. Node u can perform arbitrary computations. During the computation u can draw a finite amount of random bits. The source of random bits for node u is independent from the source of random bits for any other node v ∈ V , and for the sake of simplicity we assume that each source is uniformly distributed. 3. Output. Node u can decide on an output value. An output is irrevocable, i.e., once u has decided on an output value, it cannot be changed. 4. Send. Node u sends a finite length broadcast message to all nodes in Γ (u). An algorithm A is called deterministic if A does not draw any random bits. When all nodes in the network have decided on an output value we say that A has terminated. We restrict ourselves to uniform algorithms, i.e., the nodes are unaware of any network parameter, e.g., the network size n, nor do they have unique identifiers (the network is anonymous).

We consider two complexity measures of an algorithm A.

(1) The runtime of A in some graph G is the number of rounds that are executed until all nodes terminate, and (2) the random bit complexity of A is the maximum number of random bits drawn by any node during the execution of A.

2-Hop Colorings. Throughout the paper, we study algorithms that aim to color the input graph. For a graph G, a k-coloring is a function γ : V → {1, . . . k} such that γ(v) = γ(u) for any (u, v) ∈ E, where k is the number of colors. When the number of colors is not of concern, γ is called simply a coloring. In other words, the color of u is different from the color of all v ∈ Γ (u). This definition naturally extends to multiple hops and in this paper, we are especially interested in the 2-hop version of coloring, where γ(u) = γ(w) for any u, v, w ∈ V such that w = u, (u, v) ∈ E and (v, w) ∈ E, i.e., the color of u is different from the color of any node w ∈ Γ 2 (u).

The Target Function f (n). A function f is called a target function if f is positive, strictly increasing, and continuous. Note that the properties of a target function f ensure that the inverse target function f -1 (n) of f (n) is well-defined. For easier readability, we denote the inverse function by

g f (n) = f -1 (n), or g(n) if f is clear from the context.
The purpose of a target function is to capture the runtime of some deterministic algorithm A. The runtime f * (n) of A is positive, but not necessarily strictly increasing in the input size n, nor continuous. However, for any ξ > 0, there is a target function

f such that f * (n) ≤ f (n) ≤ f * (n) + ξ, i.e., f "captures" f * at all integer values n ≥ 1.

Tailor-Made 2-Hop Coloring

Our technical contribution starts by presenting a 2-hop coloring algorithm, called Tailor-2-Hop-Coloring, with a customizable runtime. Specifically, our algorithm is parametrized by a target function f and two integers a > 2, d ≥ 2. As discussed before, we assume that f (n) is between log * n and log log n (see Section 4). Then, the algorithm finds a 2-hop coloring in 3d • f (n) rounds in expectation and with probability 1 -n 2-a .

The main difficulty is to choose how quickly random bits should be drawn, without knowledge of n. From the discussion above we know that in some round 3d • f (n), we should have drawn at least Ω(log n) bits. If we draw the bits too quickly, however, we might draw too many bits in the last round before the algorithm finishes. To deal with that, we design our bit drawing function b(i) for the target function f and the integer parameters a and d as follows. Let i be some positive integer, and write i = dp + s with 0 ≤ s ≤ d -1, i.e., p = i/d and s = i (mod d). The bit drawing function for i is defined as

b(i) = b(dp + s) = a • log g(p) (d-s)/d • log g(p + 1) s/d .
We describe Tailor-2-Hop-Coloring from the perspective of node u ∈ V (please refer to Algorithm 1 for a pseudo-code description). The algorithm progresses in phases p, starting from phase 1, and every phase consists of d sub-phases, which in turn consist of 3 rounds each.

Node u maintains a variable x storing all random bits drawn in the course of the execution. In the first sub-phase of each phase, u appends bits to x until the length of x is b(dp). In the remaining d -1 sub-phases s = 1, . . . , d -1 of phase p, by appending bits to x, the number of used random bits is increased to b(dp + s). This process takes place in the first round of each sub-phase. After drawing bits in round 1 of sub-phase i, u sends its (preliminary) color x to all nodes v ∈ Γ (u). In the beginning of the second round of sub-phase i, node u receives the colors chosen by all nodes in Γ (u). The list consisting of u's own color x and all the received colors is then sent to all neighbors of u. In the beginning of the third round of sub-phase i node u receives such a list from each neighbor. If x occurs only once in each list, then u selects color x and terminates. Otherwise, if x was used by multiple nodes, the process continues.

The idea behind Tailor-2-Hop-Coloring is as follows. In the first sub-phase of each phase, every node u draws a random color x from the set {1, . . . , g(p) a }. Our choice of b ensures that the remaining sub-phases of phase p are used to interpolate between g(p) a and g(p+1) a if the chosen colors are not a valid 2-hop coloring. The interpolation is performed so that within each phase p, the multiplicative increase in the number of random bits used in each sub-phase is fixed. If, for instance, Tailor-2-Hop-Coloring is in the first sub-phase of some phase p = f (n) , then the number of bits used by u is at least a log n.

Please note that in round 3 of each sub-phase, a node chooses a color only if it does not violate the 2-hop coloring constraint. Thus, the output of Tailor-2-Hop-Coloring is always a valid 2-hop coloring. The remainder of this section is dedicated to establishing the following theorem.

Theorem 1. The runtime of Tailor-2-Hop-Coloring with high probability and in expectation is O(f (n)) rounds. The random bit complexity of Tailor-2-Hop-Coloring with high probability and in expectation is

O(h(f (n)) • log n) bits, where h(i) = d log g(i + 1)
log g(i) .

It will sometimes be convenient to express the bit drawing function in terms of h:

b(pd + s) = b(dp) • h(p) s , for 0 ≤ s ≤ d, and (1)
b(pd

+ s + 1) = b(dp + s) • h(p) , for 0 ≤ s ≤ d . (2)
Consider the last phase p and sub-phase s for which b(pd + s) < a log n.

In that case, b(pd + s + 1) ≥ a log n bits are drawn in the next step. Thus, due to the second expression, the essence of Theorem 1 is that Tailor-2-Hop-Coloring "overshoots" the necessary a log n bits by at most a factor of h(p).

Recall that the target function f can be thought of as the runtime function of any deterministic algorithm that relies on a 2-hop coloring. Before getting into the details of the analysis, let us briefly put Theorem 1 into perspective by considering the corner cases where f ∈ Θ(log log n) or f ∈ Θ(log * n). In the former case h(f (n)) is in O(1), whereas in the latter case h(f

(n)) is in O( d √ n)
. Thus, we obtain the following corollary from Theorem 1.

Corollary 1. Consider a target function f , and let R denote the random bit complexity of Tailor-2-Hop-Coloring.

1. If f (n) ∈ Θ(log * n), then R is O( d √ n • log n) ⊆ O( d-1 √ n) w.h.p. and in expectation. 2. If f (n) ∈ Θ(log log n), then R is O(log n) w.h.p.

and in expectation.

The analysis of Tailor-2-Hop-Coloring's runtime and random bit complexity are done separately. We first establish the high-probability results, beginning with the runtime. Lemma 1. Tailor-2-Hop-Coloring terminates after at most O(f (n)) rounds w.h.p.

We validate the claim by showing that all nodes terminate in phase f (n) with probability 1-n 2-a . This is sufficient, since each phase consists of exactly 3d rounds. The next lemma ensures the desired high probability result for the random bit complexity, and can be shown in a similar manner. However, this time our analysis takes the exact sub-phase in which Tailor-2-Hop-Coloring terminates (w.h.p.) into account.

Lemma 2. The random bit complexity of Tailor-2-Hop-Coloring is at most h(f (n)) • a log n with high probability.

Next, we establish the results for the expected values.

Lemma 3. The runtime of Tailor-2-Hop-Coloring is at most O(f (n)) in expectation.
Our proof of the above lemma again considers the phase in which Tailor-2-Hop-Coloring terminates. The idea is to split the summation of the expected value into two parts, namely before and including phase f (n), and after phase f (n). Both terms can then be bounded individually.

Lemma 4. If f (n) is at least log * n, then the random bit complexity of Tailor-2-Hop-Coloring is O(h(f (n)) • log n) in expectation.
The proof of Lemma 4, similar to that of Lemma 3, relies on carefully inspecting the round in which Tailor-2-Hop-Coloring terminates. However, due to the possibly large growth of g (which directly affects the growth of the bit drawing function), the analysis requires more attention. Instead of considering only the phase in which Tailor-2-Hop-Coloring terminates, we take the exact step in that phase into account. This yields a division of the expected value into 5 (instead of the previous 2) terms. Bounding each term individually leads to a rather lengthy proof. Theorem 1 is then established by combining Lemmas 1 to 4.

Trade-off Lower Bound

Our goal in this section is to show that the trade-off achieved by Tailor-2-Hop-Coloring's bit drawing function is asymptotically optimal. For this effort, it is sufficient to study lower bounds for the 1-hop variant of the coloring problem, since every 2-hop coloring is also a 1-hop coloring. More precisely, we are going to establish the following: Theorem 2. Let A be any randomized uniform anonymous coloring algorithm. If the expected runtime of A is asymptotically smaller than that of Tailor-2-Hop-Coloring, then A's expected random bit complexity is asymptotically larger than that of Tailor-2-Hop-Coloring. The rough idea is that in order to break symmetry, the nodes have to draw random bits according to some (possibly randomized) scheme. We distinguish two cases: In the first case, A may try to break symmetry quickly by using many random bits. We show that then, the expected random bit complexity of A needs to be large. For the second case, where A prevents this behavior, we show that the expected runtime of A is asymptotically as large as that of Tailor-2-Hop-Coloring.

Our proof relies on a graph construction consisting of several so-called (u, v)-gadgets. A (u, v)-gadget of length i (depicted in Figure 1) consists of 2i nodes, namely two paths p 1 , p 2 of length i -1 and two special nodes u and v, connected by an edge. Furthermore, nodes u and v are connected to one endpoint of both p 1 and p 2 . The other endpoints of p 1 and p 2 are referred to as x 1 and x 2 , respectively. We obtain the graph G(m, i) utilized in our lower bound proofs by connecting m (u, v)-gadgets of length i in a ring-like topology. This is done by simply chaining the m gadgets together by their endpoint nodes x 1 and x 2 -please refer to Figure 2 for an illustration. We note that G(m, i) consists of 2im nodes.

Consider, for example, the graph G = G(2 k , 3) for some arbitrarily large k. Since the graph G is symmetric from the perspective of each (u, v)-pair in any of the gadgets, every such pair can break symmetry only by their individual random coin tosses. Assume now for the sake of contradiction, that there is a coloring algorithm A with an expected bit complexity β ∈ o(log n). In that case, with arbitrarily large probability, at least one of the (u, v)-pairs tosses exactly the same sequence of random bits. This contradicts the claim that β ∈ o(log n), and thus we obtain the following result from our graph construction.

Corollary 2. Any coloring algorithm must have an expected random bit complexity in Ω(log n).

In our effort to prove the trade-off lower bound we would like to have a better grip than that on the random coin tosses made by the nodes. Specifically, for any algorithm A and (u, v)-gadget H, we denote by B A (i, H) the random variable taking on the maximum number of random bits drawn by nodes u and v in H until and including round i. Whenever A is clear from the context, we omit it in the notation and write B(i, H) instead. The following insight about those random variables in the graph G(m, i) is based on the observation that the length of the paths in the (u, v)-gadgets guarantee independence. We formally note this in the following Lemma 5, which will be helpful in our proof of Theorem 2. Lemma 5. Consider any algorithm A, and let H be a single (u, v)-gadget of length i. Let m ≥ 2 be an integer, and denote by H 1 , . . . , H m the m (u, v)-gadgets in the graph G(m, i). For any j ≤ i, all the random variables B(j, H k ), obtained from an execution of A in G(m, i), are independent and distributed like B(j, H).

As noted before, the proof for Theorem 2 is divided into two parts, depending on how A chooses to draw random bits (in expectation). For that, based on the bit drawing function b used by Tailor-2-Hop-Coloring (for fixed parameters f, a, and d), we introduce a threshold for the number of random bits drawn by some algorithm as follows.

Definition 1 (Drawing few/a lot of random bits). Fix a bit drawing function b, parametrized by a target function f and two constants a > 2 and d ≥ 2. Let H be a (u, v)-gadget of length i, and let A be a randomized algorithm. We say that A draws a lot of random bits if

∃i 0 ∀i ≥ i 0 E[B(i, H)] ≥ b(3i)/4 .
If A does not draw a lot of random bits, then we say that A draws few random bits.

Due to Lemma 5, properties of single (u, v)-gadgets can be lifted to instances of G(m, i). One such property we will use is encapsulated in the following technical lemma, which can be established using induction. We now have the essential tools to prove Theorem 2, and first consider the case where A draws a lot of random bits. In that case, for sure, the runtime of A can be better than that of Tailor-2-Hop-Coloring. Imagine for example a process that draws infinitely many random bits in the first round-one would immediately obtain a 2-hop coloring within a single round with probability 1, albeit at the cost of an infinite random bit complexity. The essential insight of the following Lemma 7 is that no matter how "smartly" one tries to draw a lot of random bits in hopes to get a better runtime, the expected bit complexity will be asymptotically worse than that of Tailor-2-Hop-Coloring. Lemma 7. Let A be any coloring algorithm. If A draws a lot of random bits, then A's expected random bit complexity is Ω(h(f (n)) 2 • log n).

In our proof, we carefully choose a gadget graph of a certain size. We then utilize Lemma 5 to "copy" the property obtained from Lemma 6 for a single (u, v)-gadget to all gadgets in the graph. Applying Markov's inequality twice, the choice of the gadget graph then allows us to derive the desired lower bound. With the next lemma we consider the opposite case where A draws only few random bits. Lemma 8. Let A be any coloring algorithm. If A draws few random bits, then the expected runtime of A is Ω(df (n)).

Our proof follows similar lines as that for Lemma 7. The key difference is how the size of the gadget graph is chosen. We obtain the desired optimality of Tailor-2-Hop-Coloring from Lemma 7 only if h(f (n)) 2 ∈ ω(h(f (n))). In the case where f ∈ O(log log n), however, h(f (n)) is bounded from above by a constant. It may thus appear that such an f is not covered by our lemmas.

To see that this is not an issue, observe that the constant 3 in the definition of drawing a lot of random bits was chosen arbitrarily. In other words, when h(f (n)) is bounded by some constant ρ, one may replace 3 in the above definition with ρ + 3. This way, we obtain that the coloring algorithm A draws "ρ-few" random bits. We can now apply the same reasoning as in the proof of Lemma 8 to obtain that the runtime of A is in the same order as that of Tailor-2-Hop-Coloring. This concludes our effort to establish Theorem 2.

Algorithm 1 : 1 :

 11 Tailor-2-Hop-Coloring(f, a, d) as executed by node u.Initialization: g(n) ← f -1 (n) x ←ε the empty bit string Phase p = 1, 2, . . . : For sub-phase s = 0, 1, 2, . . . , d -Round 1 of sub-phase s: Append random bits to x until |x| = b(pd + s) Send x to all neighbors Round 2 of sub-phase s: Receive x1, . . . , x δ from each non-terminated neighbor v1, . . . , v δ ∈ Γ (u) Send list x, x1, . . . , x δ to all neighbors Round 3 of sub-phase s: Receive lists L1, . . . , L δ from each neighbor if x appears exactly once in every list then Choose color x and terminate

Fig. 1 .Fig. 2 .

 12 Fig.1. A (u, v)-gadget of length i = 4, consisting of 2i nodes: The two special nodes u and v, and the two paths p1 and p2 of length i-1 with endpoints x1 and x2, respectively. Since the gadget is symmetric, symmetry between u and v can only be broken by their individual random coin tosses.

Lemma 6 .

 6 Let A be any coloring algorithm. If A draws a lot of random bits, then∃i 0 ∀i ≥ i 0 ∃j ≤ i E[B(j, H)] ≤ b(i)/4, and E[B(j + 1, H)] ≥ b(i + 2)/4 ,where H is a (u, v)-gadget of length i.

A 2-hop coloring is a coloring of the network in which every node's color is different from the colors used by any other node within distance 2 (see Section 2).


Chaleur Spécifique

J Kg -1 •k -1 E Epaisseur

K  Température

Conductivité

Nomenclature Symboles généraux c

thermique,W.m -2 .

Prototype expérimental pour l'identification de sources chauffantes se déplaçant sur une surface

Thanh Phong TRAN 1 , Alban VERGNAUD 1 , Laetitia PEREZ 2 1 LARIS, Université d'Angers 62 avenue notre dame du lac -49000 Angers -France 2 LTN-UMR CNRS 6607, Université de Nantes La Chantrerie, Rue Christian Pauc, BP50609 -44306 Nantes cedex 03 -France * (auteur correspondant : thanhphong.tran@etud.univ-angers.fr) Résumé -Le travail proposé dans cette étude s'articule au sein d'un projet visant à déplacer un ensemble de capteurs mobiles de manière optimale afin d'identifier la trajectoire et la puissance d'une (ou plusieurs) sources évoluant sur une plaque métallique fine. Cette expérimentation actuellement en cours de conception et de réalisation a pour objet de tester la validité de différentes stratégies de déplacements de capteurs. L'objectif principal est d'identifier en ligne le couple puissance & trajectoire de chaque source via une méthode de régularisation itérative basée sur la méthode du gradient conjugué. Cette communication vise à présenter la conception et la réalisation du dispositif expérimental. Les sources chauffantes sont embarquées sur des robots mobiles (Khepera III) qui évoluent sur une plaque d'aluminium fine de 4m² et d'épaisseur 2mm. La puissance des sources de chaleur est régulée de manière à décrire différents profils d'évolution. Sur cette même plaque, plusieurs robots mobiles sont équipés de pyromètres afin de mesurer la température de la plaque de manière quasi ponctuelle. Les températures mesurées ainsi que la position des points de mesures sont transmises à un calculateur central via une technologie sans fil (WIFI). Les problèmes inverses pour l'identification sont ensuite résolus quasi en ligne et simultanément, les prochaines trajectoires des pyromètres sont estimées et envoyées aux robots observateurs qui se déplacent alors vers leurs prochaines positions. La position absolue des robots étant nécessaire au bon fonctionnement du système (robustesse de la procédure d'identification), nous utilisons en complément de la mesure odométrique un système de localisation global par caméra. Cette dernière est positionnée au-dessus de la plaque ; les différentes mesures de position obtenues par vision sont synchronisées avec celles envoyées par les robots observateurs pour une éventuelle correction. Le dispositif présenté dans cette communication est schématisé Fig. 1.

Introduction

Dans le cadre de l'étude des problèmes inverses de conduction de la chaleur, il est usuel de chercher à minimiser un critère quadratique décrivant l'erreur de prédiction entre les observations et les températures prédites par un modèle mathématique valide [START_REF] Isakov | Inverse problems for Partial Differential Equations[END_REF]. De tels problèmes sont en général mal-posés du fait de la condition de stabilité [START_REF] Alifanov | Inverse heat transfer problems[END_REF] qui n'est pas satisfaite (d'importantes incertitudes sur le paramètre inconnu sont induites par de petites variations dans les mesures). Les méthodes permettant l'obtention de solutions stables sont dites de régularisation [START_REF] Morozov | Methods for solving incorrectly posed problems[END_REF]. La méthode de régularisation itérative basée sur un algorithme de descente de type gradient conjugué [START_REF] Minoux | Programmation mathématiquethéorie et algorithmes. Secondeédition[END_REF] est d'une efficacité reconnue en génie thermique [START_REF] Jarny | A general optimization method using adjoint equation for solving multidimensional inverse heat conduction[END_REF]. Une illustration de son effet régularisant est proposée dans [START_REF] Prud'homme | On the iterative regularization of inverse heat conduction problems by conjugate gradient method[END_REF] où il est montré que le nombre d'itération peut être considéré comme le paramètre de régularisation de ces méthodes, assurant que l'algorithme se comporte comme un filtre passe-bas capable de rejeter les perturbations des mesures qui sont à haute fréquence. Pour des procédés complexes (modèles non linéaires dans des géométries tri dimensionnelles faisant intervenir de très nombreux paramètres [START_REF] Beddiaf | Simultaneous determination of time-varying strength and location of a heating source in a three-dimensional domain[END_REF][START_REF] Beddiaf | Parametric identification of a heating mobile source in a three-dimensional geometry[END_REF]), le temps de calcul requis pour l'identification est rédhibitoire pour envisager un diagnostic en ligne. Il est toutefois possible d'envisager une adaptation quasi en ligne de la méthode régularisation itérative du gradient conjugué (une situation numérique est étudiée dans [START_REF] Vergnaud | On-line monitoring of surfacic mobile heating sources[END_REF]).Afin d'illustrer l'intérêt et la mise en oeuvre pratique de cette approche, un dispositif expérimental a été conçu pour l'identification de la trajectoire et de la puissance d'une (ou plusieurs) sources évoluant sur une plaque métallique fine. Cette expérimentation, actuellement en cours de conception et de réalisation, qui a pour objet de tester la validité de différentes stratégies de déplacements de capteurs est décrite ci-après. La problématique d'identification quasi en ligne est abordée dans une communication conjointe [START_REF] Vergnaud | Stratégie de sélection de capteurs pour une identification de flux thermique quasi en ligne[END_REF].

Dispositif expérimental

Description globale du système

Le dispositif a pour objet de valider une méthode d'identification quasi en ligne pour un problème inverse de conduction de la chaleur. Aussi, ce banc n'est pas dédié à un procédé thermique spécifique. Les sources chauffantes sont embarquées sur des robots mobiles qui évoluent sur une plaque d'aluminium fine d'environ 4m² et d'épaisseur 2mm. La puissance des sources de chaleur est régulée de manière à décrire différents profils d'évolution. Ces densités de flux pourront être continues ou non. La méthode d'identification quasi en ligne présentée dans [START_REF] Vergnaud | Stratégie de sélection de capteurs pour une identification de flux thermique quasi en ligne[END_REF] propose une stratégie de choix de capteurs ponctuels. Il ne s'agit pas ici de traiter des cartographies obtenues à l'aide de caméras infra-rouges. En effet, de manière plus générale, la problématique principale vise à maitriser le déplacement d'une meute de capteurs ponctuels dans un environnement de grande dimension (véhicules détectant des polluants se diffusant dans un milieu urbain contraint). Sur cette même plaque, plusieurs robots mobiles sont équipés de pyromètres afin de mesurer la température de la plaque de manière quasi ponctuelle. Les températures mesurées ainsi que la position des points de mesures sont transmises à un calculateur central via une technologie sans-fil (WiFi). Les problèmes inverses pour l'identification seront ensuite résolus quasi en ligne. Les trajectoires des pyromètres sont estimées tout au long du procédé et envoyées aux robots observateurs qui se déplacent alors vers leurs prochaines positions [START_REF] Vergnaud | DARC-EDP: Conception du prototype[END_REF]. La position absolue des robots étant nécessaire au bon fonctionnement du système (robustesse de la procédure d'identification), un système de localisation globale par vision est utilisé(en complément de la mesure odométrique). Une caméra est positionnée au-dessus de la plaque ; les différentes mesures de position obtenues par vision sont synchronisées avec celles envoyées par les robots observateurs pour une éventuelle correction. Le dispositif est schématisé figure 1.

Les capteurs

Pour les mesures de températures, les pyromètres Optris® CSlaser-LT-CF1 sont choisis afin de réaliser une acquisition sans contact sans perturber le milieu tout en facilitant le déplacement des capteurs. Leur géométrie est celle d'un cylindre d'environ 10cm de long et 5cm de diamètre (figure 3). La distance de mesure entre le pyromètre et la plaque est de 7cm et le diamètre du disque de mesure (correspondant à 90% du rayonnement émis) est de 1.4mm.Les pyromètres fournissent une température moyenne sur des zones d'environ 2mm 2 .

Les robots

Pour déplacer les sources et les pyromètres, les robots Khepera-III (figure 4) développés par la société K-Team de l'Ecole Polytechnique Fédérale de Lausanne ont été choisis [START_REF] Mondada | The Development of Khepera[END_REF]. Le diamètre de chaque robot est de 13cm pour une hauteur de 7cm. Ils sont capables de déplacer une charge inférieure à 2kg à une vitesse maximale de 50cm/s. L'autonomie affichée est de 8h (à vitesse constante et sans la plateforme embarquée Korebot-II) alors que la durée des campagnes expérimentales prévues est de l'ordre de 30 minutes. Une carte réseau WiFi (norme 802.11b/g) est intégrée à chaque robot afin de permettre sa connexion à l'ordinateur de gestion via un routeur WiFi grâce auquel ils peuvent échanger des informations sous la forme de trames de données en utilisant le protocole TCP/IP (serveur/client).

La caméra

Le logiciel SSL-vision [START_REF] Martinez-Gomez | Real Time Vision System for a Small Size League Team[END_REF][START_REF] Zickler | SSL-Vision: The Shared Vision System for the RoboCup Small Size League[END_REF] est utilisé afin de surveiller et corriger le déplacement des robots. Une caméra visible Stingray F-046C (Allied Vision Technologies) d'une résolution de 780x580 pixels et d'une fréquence d'acquisition de 55Hz a été choisie. Cette caméra (figure 4) est positionnée au-dessus de la plaque à 150cm de hauteur afin que tous les robots soient surveillés. Elle est câblée avec l'ordinateur de vision via le port FireWire 1394b.

Le routeur WiFi

Pour l'interconnexion entre les dispositifs en profitant de la technologie de communication sans-fils, un routeur WiFi a été choisi. Cet équipement de référence TL-WR740N de TP-LINK, combine les modes filaires et sans-fil. Ce routeur WiFi N est compatible avec la norme 802.11b/get peut permettre, à une distance d'interconnexion inférieure à 25m, une vitesse maximale de transfert jusqu'à 150 Mbps.

Protocole de communication

Le protocole de communication TCP/IP (Transmission Control Protocol/Internet Protocol) est actuellement le plus utilisé dans les réseaux locaux et Internet entre 2 programmes ou 2 machines (un client et un serveur). La couche TCP assure que les données envoyées sont toutes reçues par la machine destinataire. Le protocole d'échange de données entre le client et le serveur via les sockets (interfaces de connexion) réseaux TCP/IP est modélisé figure 5. Le routeur WIFI est l'élément central de cette expérimentation ; il est le seul lien entre l'ensemble des robots, le module de vision et le module de contrôle intelligent (voir figure 1). Il gère la connexion des robots au module de gestion (de l'ensemble des capteurs et des sources mobiles) et au module d'identification paramétrique. Ces différents éléments possèdent chacun une adresse IP unique permettant ainsi le dialogue entre eux. Ces éléments ouvrent une socket d'écoute et attendent une demande de connexion provenant d'une autre machine. Lorsqu'une tierce machine tente de se connecter à la machine hôte celle-ci active la connexion et le dialogue entre les deux machines est mis en place. Les données sont échangées sous forme de trames de données qui sont codées de manière spécifique.

Localisation basée sur la vision

Les robots Khepera III disposent de roues codeuses permettant de calculer le déplacement relatif effectué lors de la mise en marche des moteurs (mesure odométrique). Cependant, les frottements entre les roues du robot et la plaque engendrent des biais (en particulier lors des virages serrés). Afin de corriger ces erreurs, une vérification du positionnement robot est mise en place via le logiciel de traitement d'images (logiciel SSL-vision [START_REF] Martinez-Gomez | Real Time Vision System for a Small Size League Team[END_REF][START_REF] Zickler | SSL-Vision: The Shared Vision System for the RoboCup Small Size League[END_REF]). Ce logiciel utilise les images fournies par la caméra et détecte des marqueurs préalablement enregistré (figure 1). Ces marqueurs servent d'identifiant unique ; en apposant un marqueur sur chaque robot, il est possible de connaitre son positionnement   xy en évitant les obstacles (le cas échéant). A l'aide du logiciel SSL-vision, les positions des robots sont mises à jour chaque seconde afin de corriger les erreurs de déplacement et d'éviter d'accroitre l'imprécision sur les mesures de température.

Identification de sources chauffantes

Dans le paragraphe précédent, l'ensemble du prototype expérimental a été décrit. Celui-ci étant relativement ambitieux, de nombreux aspects techniques ont été abordés. Compte tenu de la place limitée pour cette communication, il est impossible de détailler la procédure d'identification quasi en ligne. Celle-ci est décrite dans la communication conjointe intitulée « Stratégie de sélection de capteurs pour une identification de flux thermique quasi en ligne » [START_REF] Vergnaud | Stratégie de sélection de capteurs pour une identification de flux thermique quasi en ligne[END_REF].Les points principaux sont toutefois décrits ci-après. Chaque source chauffante est considérée uniforme sur un disque dont le centre est en mouvement. La plaque d'aluminium (posée sur un isolant) est fine et les transferts dans l'épaisseur sont négligés. Une étude préalable a démontré la validation d'un modèle 2D décrit par le système d'équations suivant :

                    0 0 , ; 2 , ; ,; , ; , ; 0, , ;0 , ,; 0 ,
                                          (1)
Le terme   ,; x y t  contient à la fois les informations sur les trajectoires et sur les densités de flux. Il s'agit donc d'identifier   ,; x y t  à partir des mesures de températures considérées ponctuelles et mobiles. Le problème inverse pour l'identification des flux de chauffe (puissance variable et trajectoire) est résolu en minimisant un critère quadratique. Celui-ci est évalué à chaque itération de l'algorithme du gradient conjugué par la résolution du problème direct [START_REF] Isakov | Inverse problems for Partial Differential Equations[END_REF]. Ce dernier, décrit par un système d'équations aux dérivées partielles, est résolu numériquement à l'aide de la méthode éléments finis implantée numériquement par le code Comsol interfacé avec Matlab. Afin d'estimer la direction de descente à chaque itération, un problème adjoint (issu d'une formulation Lagrangienne) est résolue par la même méthode numérique. Il permet le calcul du gradient du critère à minimiser et donc de la direction de descente (voir [START_REF] Minoux | Programmation mathématiquethéorie et algorithmes. Secondeédition[END_REF]). La profondeur de descente (optimale dans la direction de descente) est estimée à partir de la résolution du problème de sensibilité. Il est important de noter qu'à chaque itération de l'algorithme d'identification, trois problèmes décrits par des équations aux dérivées partielles sont résolus par la même méthode numérique. Il est ainsi judicieux de conserver le même maillage et les mêmes matrices d'assemblage afin de réduire les temps de calculs. Ces trois problèmes sont bien posés au sens d'Hadamard [START_REF] Isakov | Inverse problems for Partial Differential Equations[END_REF][START_REF] Alifanov | Inverse heat transfer problems[END_REF][START_REF] Morozov | Methods for solving incorrectly posed problems[END_REF]. Le critère d'arrêt de l'algorithme est lié aux incertitudes sur les mesures supposées prédominantes par rapport aux erreurs de modèle [START_REF] Alifanov | Inverse heat transfer problems[END_REF]. La procédure itérative d'identification est ainsi stoppée avant de chercher à donner une signification erronée au bruit de mesures (qui présente une fréquence élevée par rapport à la dynamique des transferts thermiques étudiés).

L'identification quasi en ligne est réalisée en considérant un intervalle temporel d'observations « glissant » durant le procédé. Cela signifie que la procédure d'identification est lancée dès que des mesures sont disponibles et avant la fin du procédé (ce qui serait hors ligne). Au fur et à mesure que la minimisation se poursuit en parallèle, des nouvelles observations sont disponibles et différentes stratégies peuvent être mises en oeuvre : ajout en ligne de nouvelles mesures, longueur variable de l'horizon glissant, superposition des intervalles d'observations, facteur d'oubli, … Ces différentes méthodes sont actuellement testées et des retards de l'ordre d'une minute pour un procédé de trente minutes peuvent être atteints.

En ce qui concerne le déplacement optimal des robots de mesure, celui-ci est réalisé en optimisant un critère issu des fonctions de sensibilité et des températures prédites quasi en ligne lors de la procédure d'identification.

Conclusions

Dans cette communication, le dispositif expérimental développé dans notre institut a été présenté. Il a pour objectif d'étudier des stratégies d'identification de sources chauffantes mobiles et de déplacement (ou de choix) de capteurs sur une géométrie 2D. Différents éléments techniques ont été brièvement décrits alors que la méthode d'identification actuellement testée est présentée dans la communication intitulée « Stratégie de sélection de capteurs pour une identification de flux thermique quasi en ligne ». A moyen terme, la configuration suivante est retenue : 2 robots mobiles chauffants, 6 robots mobiles observateurs. Toutes les 10 secondes, les 6 robots mobiles fournissent la mise à jour des mesures collectées, l'algorithme d'identification (puissance et trajectoire des 2 robots chauffants) fournit des résultats en un maximum de 10 secondes, les stratégies de déplacements de capteurs sont aussitôt évaluées et les 6 robots mobiles se redéploient à nouveau.

Figure 1 :

 1 Figure 1 : Prototype du système de vision

Figure 2 :

 2 Figure 2 : Les sources chauffantes

Figure 3 :

 3 Figure 3 : Le pyromètre Optris® CSlaser-LT-CF1

Figure 4 :

 4 Figure 4 : Robot Khepera-III équipé d'un pyromètre et Caméra Stingray F-046C

Figure 5 :

 5 Figure 5 : Protocole d'échanges TCP/IP



  repère Oxy . Une fois les nouvelles coordonnées calculées, celles-ci sont comparées avec les mesures odométriques des robots afin d'estimer au mieux les coordonnées des robots sur la plaque. Après traitement des mesures et procédure d'identification quasi en ligne, chaque robot reçoit une trame de données qui contient ses coordonnées actuelles   et la position désirée   11 , xy . Il calcule alors une trajectoire pour se déplacer de la position actuelle   00 ,, o xy à la position désirée   11 ,