Bilel Derbel

Local Maps: New Insights into Mobile Agent Algorithms

Keywords: Mobile agents, locality, local maps Mobile agents, locality, local maps

In this paper, we study the complexity of computing with mobile agents having small local knowledge. In particular, we show that the number of mobile agents and the amount of local information given initially to agents can significantly influence the time complexity of resolving a distributed problem. Our results are based on a generic scheme allowing to transform a message passing algorithm, running on an n-node graph G, into a mobile agent one. By generic, we mean that the scheme is independent of both the message passing algorithm and the graph G. Our scheme, coupled with a well-chosen clustered representation of the graph, induces O(1) † ratio between the time complexity of the obtained mobile agent algorithm and the time complexity of the original message passing counterpart, while using O(n) mobile agents. If only k agents are allowed (k is an integer parameter), then we show that the time ratio is O(n/ √ k). As a consequence, we show that any global labeling function of G can be computed by exactly n mobile agents knowing their n -neighborhood in O(D) time, D is the diameter of the graph and is an arbitrary small constant. We apply our generic results for the fundamental problem of computing a leader (resp. a BFS tree) under the additional restriction of O(1) (resp. O(n)) bit memory per agent, and obtain O(D) time algorithms.

Introduction 1.Motivation and goals

In a mobile agent algorithm, we are given a set of mobile entities (the mobile agents) equipped with a memory and able to move from a node to another in the network in order to do some computations. The time, the number of agent moves, the number of agents, and the memory size of agents, are the complexity measures that are used most often to evaluate the efficiency of a mobile agent algorithm. The general motivation of this paper is to understand the relationship of these complexity measures, especially the time complexity, to the the initial local view complexity measure.

In order to give an intuitive definition of the initial local view of a mobile agent, and to show how it can interfere with the way of resolving a distributed problem, let us consider the following example: take a non-anonymous graph that models a set of pairwise connected locations where some robots (mobile agents) are scattered. The robots can move from one location to a neighboring one and can communicate by leaving a message in the location where they pass. Suppose that initially each robot is given a map of its surrounding locations. Suppose that the robots have to agree on some location to meet, i.e., elect a location. It is obvious that if initially the robots know the whole map of the locations (that is the entire graph), then the robots can choose the location having the smallest name to meet there. The time needed to gather the robots is then dominated by the time needed to reach that elected location. Suppose now that initially each robot is given only an incomplete or a restricted map of its environment, say a map of only the very close locations. First, it is not obvious how the information provided by the local maps can help the robots to meet. Second, assuming that the information given by the local maps does so, it is not obvious that the robots can meet as fast as if they know the whole map of their environment.

Informally speaking, the initial local view of a mobile agent measures how small is the map given to it initially. More precisely, it measures the radius of the initial map given to the agent. The purpose of this paper is to show how small local maps do help providing good solutions to classical distributed problems such as computing a leader, computing a tree, and more generally computing some labeling of a graph.

To tackle this problem independently of the distributed task, we adopt a "simulation" based approach which allows to transform any message passing algorithm into a mobile agent one. On one hand, the initial local view of a mobile agent can be interpreted from a message passing perspective as the amount of knowledge that a node may have about its neighborhood. On the other hand, many distributed problems have been shown to have efficient local solutions in the message passing setting. Thus, providing a generic and efficient simulation method will also lead to design efficient local solutions using mobile agents.

Overview of related works

To the extent of our knowledge, the relation between the initial local view as defined in this paper and the complexity of mobile agent algorithms has not been studied in previous works. However, one can find many seemingly related concepts.

The concept of limited visibility [FPSW05, RDW05, San01, SDY06, KA02, IKK04, FS06, AOSY99, ASM95, FNS07] is perhaps the most closely related to the issues adressed in this paper. However, the computation models used to study that concept are different from ours. This is probably due to the nature of the problems studied tehrein. In fact, existing works about the impact of limited visibility concern autonomous robots moving most often in some space, i.e., the plane. In that context, a robot is said to have a limited visibility if it can sens its surrounding up to a fixed distance, i.e., it can look and see the positions of other robots in a ball of a fixed radius at any time of the execution of the algorithm.

Another related concept, called Oracles, arised recently for some specific problems, e.g., broadcast / wake-up [START_REF] Fraigniaud | Oracle size: a new measure of difficulty for communication tasks[END_REF], tree exploration [START_REF] Fraigniaud | Tree exploration with an oracle[END_REF]. The concept of oracles is also tightly related to the widely studied concepts of labeling schemes and advice schemes (see [START_REF] Fraigniaud | Local mst computation with short advice[END_REF][START_REF] Korman | Labeling schemes with queries[END_REF][START_REF] Korman | General compact labeling schemes for dynamic trees[END_REF]and the references there). These concepts aplly for the mobile agent model as well as for the message passing model. Informally speaking, an oracle with respect to a given problem P can be considered as an algorithm that, given a graph, outputs a labeling of the nodes in such a way solving P by a distributed algorithm becomes easier. The challenges in that context are (i) to design an oracle minimizing the number of bits used for the labeling of nodes, and (ii) to come out with a distributed algorithm that, using the information provided by the oracle (the labels), solves P efficiently. Although, studying oracles helps understanding the locality of a given problem, the issues addressed by oracles are different from those studied in this paper in many ways. In fact, paraphrasing the discussion made in [START_REF] Korman | Labeling schemes for dynamic tree networks[END_REF] for static labeling schemes, we can say that oracles "are centralized, in the sense that they are based on a sequential algorithm which given a description of the entire graph outputs the entire set of node labels1 . Hence while the resulting short labels reflect local knowledge and can be used locally, their generation process is still centralized and global". Moreover, oracles are problem specific, that is the output labels are function of a fixed problem and cannot be used to resolve another one. In many cases they are also topology specific (e.g., case of trees). In this paper, we are adressing the problem of resolving any distributed task, on any network, in a fully distributed way, provided that each node knowns its surrounding up to some small distance.

From a message passing perspective, the impact of local knowledge on resolving distributed tasks has been intensively studied over the last years yielding a huge variety of results (see e.g., the seminal papers [START_REF] Naor | What can be computed locally?[END_REF][START_REF] Linial | Locality in distributed graphs algorithms[END_REF]). The locality of distributively resolving many problems, e.g., trees, leader election, infromation dissemation, coloring, dominating sets, independent sets, partitions, tree covers, etc, can be found in the litterature. For instance, the results presented in [START_REF] Awerbuch | A trade-off between information and communication in broadcast protocols[END_REF] show that broadcasting in a network where each node knows its ρ-neighborhood can be done using Θ(min m, n 1+O(1)/ρ ) messages, where m (resp. n) is the number of links (resp. nodes) in the network. The lower bound given in [START_REF] Kuhn | What cannot be computed locally! In 23 rd[END_REF][START_REF] Kuhn | The price of being nearsighted[END_REF] shows, for instance, that in order to resolve the fundamental maximal independent set problem, a node must fetch some information in its Ω( log n/ log log n)-neighborhood while the best deterministic upper bound solves the problem in n O(1/ √ log n) . Reviewing all the existing results on the locality of message passing algorithms is beyond the scope of this paper. The reader is referred to [START_REF] Peleg | Distributed Computing: A Locality-Sensitive Approach[END_REF] and the pointers there for further results concerning the particulary rich state-of-the-art concerning the locality of distributed message passing algorithms. One goal of this paper is to provide a set of basic and general results that we hope will serve as a starting point to more problem specific studies of the locality level of mobile agent algorithms compared with message passing ones.

The relationship between mobile agent algorithms and message passing algorithms is studied in few works [CGMO06, BFFS03, DFSY07, FBDC99, PBD + 04]. In [START_REF] Chalopin | Mobile agent algorithms versus message passing algorithms[END_REF][START_REF] Barrière | Can we elect if we cannot compare? In 15[END_REF], a simulation based approach allows to provide equivalence results between tasks that can be computed with messages and those that can be computed with mobile agents. Roughly speaking, the research concern there is on determining what tasks can be computed by mobile agents and under what conditions, but not at what cost. More recently, [START_REF] Das | Faulttolerant simulation of message-passing algorithms by mobile agents[END_REF] shows how to simulate message passing algorithms with mobile agents under failures with a polynomial overhead in the number of moves per agent (for simulating one message sending). That paper focuses on agent fault issues. In [FBDC99, PBD + 04], the authors showed how mobile agents (from a system engineering point of view) can define a navigational programming style for distributed parallel computing which is competitive in many points compared with classical message passing and distributed shared memory systems.

Many other investigations assuming several mobile agent models (e.g., the anonymous model) exist for specific problems such as graph exploration [START_REF] Das | Distributed exploration of an unknown graph[END_REF][START_REF] Dessmark | Optimal graph exploration without good maps[END_REF], graph learning [ABRS99, BS94], graph searching [START_REF] Blin | Distributed chasing of network intruders[END_REF], decontamination [START_REF] Flocchini | Distributed security algorithms by mobile agents[END_REF], flocking [START_REF] Santoro | Distributed computations by autonomous mobile robots[END_REF], gathering [START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF][START_REF] Czyzowicz | Gathering few fat mobile robots in the plane[END_REF], election [START_REF] Barriere | Rendezvous and election of mobile agents: Impact of sense of direction[END_REF][START_REF] Das | Effective elections for anonymous mobile agents[END_REF], etc. Few of them have considered the impact of the initial local knowledge on the complexity of mobile agent algorithms.

Main contributions

Given a (synchronous) message passing algorithm, we describe a general scheme that allows to simulate a message passing algorithm in the (asynchronous) mobile agent model (See section 2 for a detailed definition of the distributed model). Our scheme is based on partitioning the graph into a set of clusters. Roughly speaking, each cluster is controlled by some agents that simulate the message passing algorithm in that cluster while collaborating with the other agents in neighboring clusters. The computations inside each cluster is almost for free, only computing at the border of each cluster costs high. 2We show that the properties of the partition, namely the number of clusters, the radius of clusters, and the inter-connexion between clusters, do influence the complexity of simulating a given message passing algorithm. In particular, we establish upper bound trade-offs between the initial local view, the number of agents and the time complexity. For instance, we show that using O(n 1+1/ ) mobile agents, the ratio between the time complexties of the original message passing algorithm and its mobile agent counterpart is O(1) (n is the size of the graph, is an integer parameter). If the number of agents is fixed to be k < n, then we show that the time ratio is at most O(n/ √ k). Upper bounds concerning the number of agent moves are also given. The latter results hold when the initial local view of agents is O(1) and O(n/ √ k) respectively. Based on our simulation scheme, we derive a universal distributed algorithm for computing in O(D) deterministic time any function of a given graph with initially one mobile agent per node knowing its n -neighborhood, > 0 is any arbitrary small constant and D is the diameter of the graph. Using mobile agents with no initial information at all, the time complexity of our algorithm becomes O(∆ + D) in expectation (∆ is the maximum degree of the graph). These results suggest that from a time complexity point of view, computing with mobile agents having small initial knowledge could be as powerful as message passing.

Finally, we investigate the time complexity of computing two classical and fundamental distributed problems with limited memory agents: the leader election and the Breadth First Spanning (BFS for short) tree. Using n mobile agents knowing their n -neighborhood, and having respectively O(1) and O(n) bit memory, we obtain O(D) time algorithms. The latter two results are obtained using general techniques that apply for as well for other classical tasks, e.g., the broadcast/convergecast. Thus, one could think of desgining other sophisticated (and efficient) algorithms using only limited memory agents.

Outline

In Section 2, we define the notations and the distributed models we will consider in this paper. In Section 3, we provide two basic techniques to simulate a message passing algorithm in a mobile agent environment. These two techniques are then combined in Section 4 to provide a generic and efficient simulation scheme. In Section 5, we show how to couple our simulation scheme with some clustered representations based on sparse partitions and small dominating sets in order to obtain complexity trade-offs. In section 6, a partition algorithm (of independent interest) allowing to efficiently initialize our simulation scheme is analyzed. In section 7, we apply our results for computing any function of a given graph, then for computing a leader and a BFS tree using agents having limited memory. In section 8, we conclude the paper and give some open problems.

Model and Definitions

We model a network by a connected undirected graph G = (V, E) where V is the set of nodes and E the set of edges. A labeled graph is a graph where nodes and edges are assigned labels.

We denote by n, m, ∆, and D respectively the number of nodes (n = |V |), the number of edges (m = |E|), the maximum degree, and the diameter of G. We assume that: Each node v of G is given a unique integer identifier of at most O(log n) bits.

The ports, that is the incident links, of a node v have distinct identifiers taken from 1 to deg v , where deg v is the degree of v. Notice that given an edge (u, v), the two port numbers assigned to this edge respectively for the u-leg and v-leg part are completely independent.

The size n of the graph G is known.

We define the radius of a subgraph H of G as following: Rad(H) = min u∈H {max v∈H {d G (u, v)}}, where d G (u, v) is the distance between the nodes u and v in G. Given a set of nodes C of G, we denote G[C] the subgraph of G induced by the nodes of C. Given a set C containing some sets of nodes, we denote Rad(C) = max C∈C {Rad(C)} where Rad(C) = Rad(G[C]). we denote G C = (V C , E C ) the graph induced by C, i.e., there is an edge between two nodes if their corresponding sets are neighbors in G. We denote by G t the graph obtained by adding an edge between every two nodes at distance at most t in G.

In the rest of this paper, we write

n instead of n O(1/ √ log n) . In fact, n O(1/ √ log n) = o(n )
for any arbitrary small constant > 0. Furthermore, since this is the first time where performance results concerning the amount of local knowledge of mobile agent algorithms are given, we omit precising the polylogarithmic overheads and use the

O notation ( O(f (n)) = log O(1) n • f (n)).

The message passing model

Each node of a graph G is an autonomous entity of computation that can communicate with its neighbors by sending and receiving messages. The output of a message passing algorithm is given by the final labeling of the graph. In the remainder, we write MsA to denote a message passing algorithm running on a graph G.

Unless stated explicitly, we concentrate on message passing algorithms that detect the local termination. More precisely, this assumption requires that each node can detect that it will not make any computations no more. For instance, we do not require a node to know that the result the algorithm is outputting was effectively computed, which is a stronger assumption. Also, we do not consider algorithms where a node knows that its label is final but it can not determine whether it will continue computing or not (for example by forwarding messages) which is a weaker assumption. Actually, our termination assumption is made only for the sake of simplicity and clarity, but fundamentally, it does not affect our results as we will point in Remarks 1, 2 and 3.

Unless stated explicitly, we consider the classical synchronous message passing model [START_REF] Peleg | Distributed Computing: A Locality-Sensitive Approach[END_REF]. In other words, we assume that there exists a global clock generating the same pulses for all nodes. At each pulse a node can process some messages, do some local computations and send messages to its neighbors. A message sent at a given pulse arrives before the next pulse. We denote by Time(MsA) the time complexity of algorithm MsA, that is the number of pulses from the beginning of the algorithm up to its termination. We denote by Message(MsA) the message complexity of the algorithm, that is the total number of messages exchanged by nodes.

One should remark that synchronous message passing algorithms are in general more efficient than their asynchronous counterparts. Thus, adapting them to the mobile agent setting is of particular interest. However, our mobile agent model is asynchronous as we will precise in the remainder. This is be motivated by the fact that our goal is to derive mobile agent algorithms which are both efficient and independent of the synchrony of the underlying network.

The mobile agent model

A mobile agent is a computation entity which is able to move from a node to another. We assume that:

A mobile agent is equipped with an internal memory. Unless stated explicitly, the memory of a mobile agent is assumed to have unlimited capacity.

Each node v has a whiteboard where agents can write and read information in a mutual exclusion manner. We assume that the whiteboards have unlimited capacity. Thus, a mobile agent can store any amount of information in a gievn whiteboard.

When an agent arrives at node v, it is able to distinguish the edge from which it has arrived to v among all other edges of v.

One should remark that our assumptions concerning the memory capacity of the whiteboards and the agents are introduced in order to focus on the high level locality issues. However, we will take a special care to derive algorithms for many distributed tasks while using bounded memory agents.

We consider the fully asynchronous mobile agent model. More precisely, the mobile agent algorithms that we will describe do not exploit any assumptions on time such as the existence of a global clock or an upper bound on the time needed to do some actions, etc. We assume that the output result computed by a mobile agent algorithm is encoded by mean of the whiteboards of the nodes. In other words, the output is a labeling of the graph.

In the following definitions, we denote by AgA a mobile agent algorithm computing some labeling of a graph G.

Definition 1 We say that a node is in a final state if its whiteboard will not be changed by any mobile agent. We say that a mobile agent algorithm terminates, if the algorithm ends up with all nodes in a final state.

Definition 2

The size of algorithm AgA, denoted by Size(AgA), is the number of agents used by the algorithm.

In the next defintion, we define the time complexity of a mobile agent algorithm in the asynchronous setting. We remark that time units in the above definition are with regard to a global, external clock, which is not avalaible to the agents. Hence time is observed by an "outside" observer and time units are used purely for the sake of analysis, i.e., the agent do not use any global clock to make decisions.

Definition 3

The time complexity of algorithm AgA, denoted by Time(AgA), is the total number of time units from the beginning of the algorithm up to its termination, assuming that an agent move induces a delay of one time unit and that the computations done by agents are time negligible.

Definition 4

The cost of algorithm AgA, denoted by Cost(AgA), is the total number of agent moves from the beginning of the algorithm up to its termination.

In the following, we will define the initial local view complexity measure. Let A be the set of mobile agents used by algorithm AgA. For every mobile agent A ∈ A, we call h A the homebase of agent A if at the beginning of the algorithm, agent A is at node h A .

Definition 5 We say that an agent A ∈ A has an initial local view H A , if at the beginning of the algorithm the agent A knows a labeled connected subgraph H A of G containing its homebase h A . The initial local view of algorithm AgA, denoted ILV(AgA), is then defined as the maximum radius of the initial local views of its agents. More formally,

ILV(AgA) = max A∈A {Rad(H A )}
We say that agent A has no initial local view if its initial local view H A satisfies:

H A = ∅.
We remark that the latter definition formalizes the intuitive notion of local maps discussed in the introduction. However, our definition does not say whether the local maps should be stored in the memory of agents or in the memory of nodes, i.e., the whiteboards. In the rest of this paper, we will suppose that these maps are stored in the whiteboards of nodes.

In the rest of the paper, given a problem P , a message passing algorithm MsA solving P , and a mobile agent algorithm AgA sovling P , we will term time ratio the ratio: Time(AgA)/Time(MsA). We omit precising P , MsA and AgA when they are clear from the context.

Basic simulation techniques

In the remainder, we suppose that we are given a message passing algorithm MsA computing some labeling of a graph G. Our goal is to provide a mobile agent algorithm AgA that computes the same labeling.

Agents with a full initial local view

Suppose that we have only one mobile agent knowing the whole graph G, i.e., its initial local view is D. Then, algorithm MsA can be simulated in O(n) time as following: First, the agent simulates algorithm MsA for each node of the graph locally at its homebase and it computes a copy of the output labeling. Second, the agent explores the graph in order to assign the final state of each node. According to our model assumptions, only the graph exploration is time consuming. Exploring a known graph can be done in O(n) time, with a depth first traversal for example. Thus, any message passing algorithm can be simulated by one agent knowing the whole graph in O(n) time.

Since the time complexity of the previous technique depends only on the time needed to explore the graph and mark the final states of nodes, one may ask whether we can go faster by allowing more than one agent. The answer is positive. In fact, an efficient graph structure was given in [START_REF] Cooper | Searching for black-hole faults in a network using multiple agents[END_REF] in order to explore a graph searching for black holes. That data structure represents the graph using a forest of k trees (spanning the whole graph), each tree has at most O(n/k) nodes. Thus, using k mobile agents, the agents can mark the nodes of the graph in parallel, i.e., each agent is assigned one tree, each agent traverses the graph using a shortest path leading to that tree, and each agent traverses the assigned tree to mark its nodes with their final states.

Using the "balanced tree" structure of [START_REF] Cooper | Searching for black-hole faults in a network using multiple agents[END_REF], the following holds:

Theorem 1 Given an integer parameter k 1, any labeling function of G can be computed by an asynchronous mobile agent algorithm AgA such that:

ILV(AgA) D Size(AgA) k Time(AgA) O(n/k + D) Cost(AgA) O(n + k • D)

Agents with no initial local view

The one-node-one-agent technique: Suppose that each node is assigned a mobile agent having no initial local view. Then, a simple idea to simulate algorithm MsA is to make each agent simulate the instructions that the algorithm would have done at his homebase. For that purpose, we classify the instructions of algorithm MsA into two types: (i) A send instruction: a node u sends a message to a neighbor v.

(ii) A compute instruction: a node u makes some computation, e.g., it checks whether it has received a message, it updates the value of its variables, it waits until the reception of a message from a given neighbor.

In order to simulate the instructions of algorithm MsA in node u by the mobile agent A u assigned to u, let us first consider the following technique:

Using the whiteboard of u, agent A u creates deg u receive-buffers corresponding to the ports of u. Each receive-buffer is identified by its corresponding port.

To simulate a send instruction of a message from node u to a node v, agent A u stores the message in its internal memory. Then, it crosses the edge connecting u to node v. Once at node v, it writes the message in the corresponding receive-buffer of the whiteboard of v. After that, the agent goes back to u.

To simulate a compute instruction, agent A u makes the same computation using the whiteboard of u.

Clearly, the previous technique is correct when algorithm MsA is asynchronous. However, it may fail when the algorithm is synchronous. Typically, that may happen if the decisions made by the algorithm are based on the pulse numbers of the global clock. Furthermore, the previous technique may fail even if we assume that the mobile agent model is synchronous.

A solution that solves the problems due to synchrony is to use a synchronizer-α like algorithm [START_REF] Moran | Simple and efficient network decomposition and synchronization[END_REF][START_REF] Awerbuch | Complexity of network synchronization[END_REF] in order to "synchronize" an agent A u with the other agents in the neighborhood of u. More precisely, in order to simulate the send instructions of a given pulse p, each agent A u proceeds in two stages. At the first stage, agent A u simulates the send instructions as explained before. At the second stage, the agent moves sequentially to each node v in its neighborhood and it writes a special <IamSafe in p> message in the corresponding receive buffer of v saying that it has finished simulating the instructions of pulse p. When the agent A u learns that all the agents in its neighborhood are also safe, then it can proceed with pulse p + 1 and so on. Clearly, simulating one pulse is at most O(∆) time consuming, and requires the agents to move O(m) times.

The master/worker technique: Now, suppose that at each node u there is initially deg u + 1 agents. Among these agents, suppose that there is a distinguished agent called master and deg u agents called workers. Thus, to simulate a send instruction, the master can delegate this work to one worker. The communication between the masters and their workers can be easily implemented using the whiteboards of nodes. One can see that the time ratio is then reduced to O(1). This simple technique is efficient from a time complexity point of view but it is agent consuming, i.e., we need O(m) agents. In the next section we will show how to exploit the master/worker technique to get better performances.

The performances of the previous techniques are resumed by the following theorem:

Theorem 2 Any synchronous message passing algorithm MsA can be simulated by an asynchronous mobile agent algorithm AgA such that:

ILV(AgA) 0 Size(AgA) n O(m) Time(AgA) O(∆ • Time(MsA)) O(Time(MsA)) Cost(AgA) O(m • Time(MsA))

A generic simulation scheme

In this section, we give a generalization of the basic simulation techniques described in the previous section. The idea of the generalization is to combine those techniques with a clustered representation of the graph. We will see that our generalization leads to new trade-offs between the complexity measures.

In the reaminder of this section, we will consider the following hypothesis:

H(C):
We are given a precomputed partition C of the graph G into disjoint regions. Each region C has a distinguished node r C called the center and a precomputed spanning tree T C rooted at the center. At node r C , there is a mobile agent called the master, together with some other workers (eventually none). Each master knows a labeled copy of the neighborhood of its region. In particular, he knows the edges leading to different regions.

For the clarity of the presentation, distributed methods to cope with hypothesis H(C) will be presented later in sections 5 and 6. In particular, we will show how to construct a partition C and how to initialize the masters and the workers by efficient distributed algorithms. For now, we concentrate on describing and analysing our generic simulation scheme under the hypothesis H(C).

Description of the scheme

Provided that H(C) is true, any synchronous message passing algorithm MsA can be simulated by the generic scheme described in Fig. 1 below.

There are two key points in our scheme:

The messages sent by nodes in a region C to nodes in a region C (C = C ) are concatenated into only one message M C→C (Step 1.c). The message M C→C is delivered to the master in center node r C by one worker at once, thus avoiding to deliver the messages one by one.

The pulses of algorithm MsA are simulated using a combination of a synchronizer-γ like [MS00, Awe85] algorithm and a synchronizer-α like algorithm. Roughly speaking, the master synchronizes the nodes in its region by itself (This is made possible since the master knows the entire topology of its region). Then the master (using its workers) synchronizes its region with neighboring ones using the <IamSafe> messages.

Hereafter, we give more details about the low level (yet important) distributed problems raised by our high level description and the way to resolve them: How a worker agent at node r C knows the route leading to a center node r C (Steps 1.b and 1.c)? This can be solved using the spanning trees T C and T C (remember that our scheme assumes that H(C) is satisfied). In fact, the master knows an inter-region edge leading to C . Hence, the master can tell the worker which path in T C leads to that edge. Once arrived in C the worker uses the rooted tree T C to reach the center r C . It also uses its internal memory to remember the route it took to reach r C and thus to go back home to r C .

How the concatenated messages are delivered (Step 1.c)? This is done by adding the identifiers of the sender and the receiver to each message. How a master simulates a compute instruction in the form: "wait upon the reception of a message from ..."? This type of instruction is transformed in the form: "while no message has been received from ... then check for the message at next pulse". Thus, a master agent is never blocked. (c) If some nodes in C send some messages in algorithm MsA to some other nodes belonging to a region C = C, then the master concatenates those messages into only one message. Then, one worker is chosen to deliver that message to r C . The worker returns to r C once its job is finished.

(d) If a node u ∈ C makes some computations in algorithm MsA, then the master of C makes the same computations using the withebord of r C .

(e) Once the master finish simulating the sending of messages of pulse p, the master synchronizes with other masters in neighboring region: the workers move to neighboring regions and deliver a special <IamSafe (C, p)> message.

(f) Once the master is safe and learns that all the neighboring masters are safe, then it proceeds with the next pulse p + 1.

2. Once a master and its workers have finished simulating the instructions of algorithm MsA in C:

(a) They inform other masters in neighboring regions that the simulation is terminated for region C by delivering an <IamDone C > message.

(b) They continue synchronizing with a neighboring master in region C until an <IamDone C > message is delivered by that master.

(c) They mark every node in C with its final state computed in Step 1. (Once an <IamDone> message is delivered by each neighboring master).

Figure 1: The simulation scheme.

What is the <IamDone> messages in Step 2? These messages allow us to terminate the mobile agent algorithm correctly. In fact, if we allow a master agent to stop computing just after the simulation of algorithm MsA is finished in its regions, then it may happen that a neighboring master waiting for a synchronization message get blocked. Remark that in our scheme a master agent continues synchronizing until all the neighboring masters terminate the simulation in Step 1.

When the simulation of algorithm MsA does terminate (Step 2)? Because we only consider message passing algorithm that detect the local termination, the master can detect the local termination of each node in its region and thus it knows when to execute the last step of Fig 1 . The case of weaker message passing termination assumptions is treated in Remarks 1, 2 and 3.

Complexity analysis

Clearly, the simulation of a send instruction between two nodes not in the same region dominates the overall time complexity per pulse. The concatenation mechanism of our scheme allows to deliver the messages exchanged by nodes in a region C and nodes in a different region C at once. Therefore, assuming that each master agent has as many workers as neighboring regions, it takes at most 2Rad(C) + 2Rad(C ) + 1 time to simulate all the send instructions of a given pulse of algorithm MsA. Thus, by using at most |C| master agents plus 2 |E C | workers, each pulse can be simulated in O(Rad(C)) time. As for the cost complexity, one can see that simulating each pulse requires the workers to deliver the messages of the original algorithm and to synchronize with neighboring masters. Thus, the cost complexity is O(Rad(C)

• |E C |) per pulse.
After finishing the simulation of the pulses of algorithm MsA, the nodes must be marked with their final states (Step 2.c). This step has also a time and a cost complexity. In the following, we denote by τ (C) the maximum time needed for each master agent (and its workers) to mark the whiteboards of nodes in its region with their final states. We also denote by η(C) the cost complexity of marking the nodes with their final states, that is the total number of moves that all agents make in order to mark the whiteboards of all nodes in the graph. The analysis of τ (C) and η(C) is delayed to section 5.

Lemma 1 Under the hypothesis H(C), any synchronous message passing algorithm MsA can be simulated by an asynchronous mobile agent algorithm AgA such that:

ILV(AgA) Rad(C) Size(AgA) O(|C| + |E C |) Time(AgA) O(Rad(C) • Time(MsA)) + τ (C) Cost(AgA) O (Rad(C) • |E C | • Time(MsA)) + η(C)
Remark 1 Suppose that we have a message passing algorithm that does not detect the local termination, e.g., at least one node can not say whether it has finished the computations. Then, we can modify our simulation scheme so that, at each round a master and its workers mark the nodes in their region with the labels computed by the message passing algorithm, instead of waiting the end of the simulation. Thus, at each round, the labeling of nodes will be the same than in the message passing algorithm. This simple modification allows to obtain a termination property for our mobile agent scheme which is 'similar' to that of the original message passing algorithm. Of course, this is achieved at the price of increasing the time and the cost complexities, i.e., the overhead will be order of τ (C) and η(C) (respectively) at each round. As we will discuss in Remarks 2 and 3, the overhead can be made negligible compared to the complexity of the simulation itself.

Synchrony issues

First, remark that if we consider the synchronous mobile agent model, then we can prove that the cost complexity is at most

O(Rad(C) • Message(MsA)) or O(Rad(C) • |E C | • Time(MsA)), plus η(C), without time penality.
Second, we remark that a correct asynchronous message passing algorithm should work when the delay induced by a message is arbitrary. In other words, the only assumption we made is that the messages sent by a node arrive to destination. Therefore, by simply removing the synchronization mechanism from the previous synchronous simulation scheme, we can obtain a new simulation scheme for asynchronous message passing algorithms. Of course, such an asynchronous scheme will have different performance measures. One can prove that the cost complexity is at most O(Rad(C) • Message(MsA)). The best upper bound on the time complexity we can obtain is also O(Rad(C) • Message(MsA)). In fact, in the general case of any asynchronous message passing algorithm, it is no longer possible to avoid delivering the messages of the algorithm one by one using the concatenation mechanism. Nevertheless, we can prove that for many classes of asynchronous message passing algorithms, the concatenation mechanism will work efficiently and leads to the same time ratio as in the synchronous case. Since we are essentially interested in the time complexity, we omit the detailed analysis.

Coupling our scheme with efficient clustered representations

The efficiency of our simulation scheme depends on the properties of the partition C we are given.

For instance, in order to reduce the number of agents, we should use a partition of the network into few regions connected by few edges. If we want to reduce the time ratio, then we should use a partition having a small radius. If we want to reduce the cost complexity, then we should use a partition minimizing the radius and the inter-region edges. Finding a partition having a good compromise between the three criteria, radius, inter-region edges, and number of regions is difficult. However, there exist partitions with a good compromise between only two criteria. Furthermore, we can construct these partitions distributively by efficient algorithms.

Sparse partition based scheme

Sparse decompositions [START_REF] Awerbuch | Sparse partitions[END_REF] allow to represent a graph by a set of clusters with a good compromise between the radius of the clusters and the number of inter-cluster edges. In Section 6, we will prove the following lemma:

Lemma 2 In the message passing model, there exists a deterministic (resp. randomized) distributed algorithm that given an n-node graph G and an integer parameter k, constructs a partition structure

C such that Rad(C) = O (k c ) and |E C | = O(n 1+1/k ) in k c • n time (resp. O(k c • log n) expected time) where c is a constant (c = log 2 5).
Suppose we use the partition of the previous lemma at the bottleneck of our generic scheme. What upper bounds can we give for τ (C) and η(C) ? Using at most O(n) agents, it is easy to see that τ (C) and η(C) can be bounded by O(Rad(C)) and O(Rad(C) • n) respectively (Remember that the masters know the topology of their regions). Now, applying Theorem 2 in the context of the sparse partition algorithm given by Lemma 2, one can derive a preprocessing mobile agent algorithm constructing the required partition. In the following, we will denote by Preprocess Part such an algorithm.

From the discussion above, and combining Lemma 2 and Lemma 1, the following holds:

Theorem 3 Given an integer parameter k, any graph G can be preprocessed by an asynchronous mobile agent algorithm Preprocess Part verifying3 :

ILV(Preprocess Part) 0 Size(Preprocess Part) n Time(Preprocess Part) k c • ∆ • n E (Time(Preprocess Part)) k c • ∆ • log n
such that after the preprocessing phase, any synchronous message passing algorithm MsA can be simulated by an asynchronous mobile agent algorithm AgA verifying:

ILV(AgA) O(k c ) Size(AgA) O(n 1+1/k ) Time(AgA) O(k c • Time(MsA)) Cost(AgA) O k c • n 1+1/k • Time(MsA)
Remark 2 Using Remark 1, the time (resp. cost) overhead needed to handle other termination assumptions on algorithm MsA can be proved to be O(k c ) (resp. O(k c • n)) per round which is negligible.

Dominating set based scheme

In this section, we want to fix the number of agents used by our simulation scheme to be a parameter k < n. For that purpose, we use a graph structure based on small dominating sets. A ρ-dominating set S of G is a set of nodes verifying: ∀v ∈ V , ∃s ∈ S such that d G (v, s) ρ. Given a ρ-dominating set of G, a partition of G can be obtained by clustering the nodes of the graph around the nodes of the dominating set. Based on the results presented in [START_REF] Kutten | Fast distributed construction of small k-dominating sets and applications[END_REF], we have:

Lemma 3 ([KP98])
In the message passing model, there exists a deterministic distributed algorithm that given an n-node graph G and a parameter ρ

(< n) constructs a partition structure C such that Rad(C) = O(ρ) and |C| = O(n/ρ) in O(ρ • log * n) time.
Applying Lemma 1 in the case of a dominating set based partition is less straightforward. First, the best upper bound we can give to

|E C | is O(|C| 2 )
. Hence, to obtain a total of k agents, we use at most √ k master agents, each one has at most √ k workers, i.e., we have to chose parameter ρ = n/ √ k. Second, when the number of agents is fixed, we have to bound τ (C) and η(C). Using a trivial traversal to mark the final states of nodes will lead to upper bounds that dominate the complexity of the simulation itself. An efficient solution is to use the algorithms of Theorem 1. In other words, we use the balanced tree structure of [START_REF] Cooper | Searching for black-hole faults in a network using multiple agents[END_REF] inside each region of the partition. Thus, using only √ k agents per region of radius O(n/ √ k) each, we can bound τ (C) and η(C) by O(n/ √ k) and O(n) respectively. By applying Theorem 2 to the partition given by Lemma 3 we can to derive a preprocessing algorithm called Preprocess Dom, such that the following holds:

Theorem 4 Given an integer parameter k < n, any graph G can be preprocessed by an asynchronous mobile agent algorithm Preprocess d verifying:

ILV(Preprocess Dom) 0 Size(Preprocess Dom) n Time(Preprocess Dom) O ∆ • n/ √ k • log * n
such that after the preprocessing phase, any synchronous message passing algorithm MsA can be simulated by an asynchronous mobile agent algorithm AgA verifying:

ILV(AgA) O n/ √ k Size(AgA) k Time(AgA) O n/ √ k • Time(MsA) Cost(AgA) O √ k • n • Time(MsA)
Remark 3 Based on Remark 1, one can prove that the time/cost overhead needed to handle other termination assumptions is negligible when using only k mobile agents.

6 Efficient distributed initialization of the simulation scheme

In the previous section, we did not care about how the agents are initialized distributively after the preprocessing phase, i.e., how the masters and the workers are initialized distributively. In the following paragraphs, we will give efficient distributed algorithms proving that the complexity of initializing the agents is negligible.

Input: An n-node graph G, and an integer k 1.

Output: a partition C and a set of preferred edges -→ P .

1.

C := ∅; R := V ; ∀v ∈ V , R(v) := {v}, - → P = ∅.
2. For i = 1 to log k + 1 do:

(a) Let L := R ∈ R, |N G R (R)| n 1/k |R| , where |N G R (R)| is the number of the neighboring regions of R in the graph G R induced by the regions in R.. (b) Let X := MIS((G R ) 2 [R \ L]).
(c) If a region R ∈ R \ X is at distance at most 2 from a region of set X in the graph G R , then merge R with its closest region X ∈ X breaking ties using region identifiers (the identifier of a region is the identifier of its center. The center of the new merged region is the center of X.) 3. ∀R ∈ C, construct a BFS tree rooted at its center.

Figure 2: Algorithm Part the region R to outside R. For instance, take an outgoing edge -→ e ∈ -→ P with respect to R that leads to R . Consider the endpoints u ∈ R and v ∈ R of that edge. Then, the edge (u, v) may also correspond to an outgoing edge -→ e with respect to R . But in this case, -→ e and -→ e define two different edges in set -→ P . Also, we remark that if -→ e is an outgoing edge with respect to R that leads to R then, it does not necessarily mean that there exists an outgoing edge with respect to R that leads to R.

Lemma 6 The set of preferred outgoing edges -→ P computed by algorithm Part satisfies:

For every region R ∈ C, there are at most n 1/k |R| outgoing edges with respect to R.

For every region R ∈ C, and for every two outgoing edges with respect to R and leading to regions R and R , we have R = R .

For every R, R ∈ C, there exists at least one edge - → e ∈ -→ P connecting R and R . Remark 4 We remark that the correctness of Lemma 2 is a straightforward consequence of the two previous lemmas.

Let A u be the set of mobile agents that are initially in a node u. Then, using algorithm Part, we can initialize the masters and the workers as following:

If node u is a center of a region R, then one agent from the set A u becomes the master of R. The others become workers in R.

If a node u is not a center, then u must belong to a region R with center v. Hence, all the agents of the set A u join the master at node v using the BFS tree of R and become workers in R. Once arrived at v, they also inform the master about the outgoing edges with respect to R that are incident to their homebase u.

For each outgoing edge -→ e with respect to a region R and leading to a region R , the master of R asks one worker to join the master of R and to be worker there.

By Lemmas 4 and 6, and using the previous initialilzation technique, 2n 1/k + 1 agents per node are sufficient to initialize the masters and the workers in k O(1) time (and cost) after the preprocessing of Theorem 3, which is negligible.

Applications

In this section we will concentrate on the time complexity and omit discussing the cost complexity.

On computing any labeling of a graph

First, any labeling function of G can be computed by a message passing algorithm in O(D) time in the message passing model (by collecting the topology of G at one node, computing the labeling locally and broadcasting the result).

Second, if we have a task which can be computed by a deterministic message passing model in t time, then all the information used by a node is in its t-neighborhood. Thus, if we have a mobile agent per node, and if the mobile agents know the O(t)-neighborhood of their homebases, then each mobile agent can construct in O(1) time a labeled copy of its O(t)-neighborhood where the labels assigned to nodes and edges of that neighborhood copy correspond to the final labeling computed by the message passing algorithm.

For k = log n, we have n 1/k = O(1). Hence, using O(1) agents per node allows us to run algorithm Part and also to initialize the masters and the workers efficiently. Thus, from the previous discussion we can derive an efficient algorithm for computing any labeling of a graph using O(1) agents per node. In the following, we will argue that assuming that initially there is exactly one agent per node leads to essentially the same complexity trade-offs.

Theorem 5 Given any graph G with one mobile agent assigned to each node, any labeling function of G can be distributively computed by a deterministic (resp. randomized) asynchronous mobile agent algorithm Det AgA (resp. Rand AgA)4 verifying:

ILV(Det AgA) 0 n Time(Det AgA) n • ∆ + O(D) O(D) ILV(Rand AgA) 0 E(Time(Rand AgA)) O(∆ + D) Proof.
(i) R ∈ - → R and R / ∈ -→ R , or (ii) R / ∈ - → R and R ∈ -→ R , or (iii) R ∈ - → R and R ∈ -→ R .
Remark that at each pulse (of the original message passing algorithm), at most one concatenated message must be delivered from R to R , and symmetrically at most one concatenated message must be received by R from R .

Thus, to simulate the instructions of a message passing algorithm at a given pulse, the idea is to make the workers of each region R deliver the concatenated messages to the regions in -→ R in at most O(1) stages. Each stage requires that the |R| -1 workers traverse their region R, plus an additional neighboring region. Once arrived at the center of a neighboring region, a worker delivers a concatenated message, and it also asks the master there whether any concatenated message must be delivered to R. If any, then the worker goes back home with that concatenated message. If none, then the worker also goes back home. However, by using only this technique we may miss delivering some concatenated messages. In fact, take two regions R and R satisfying: R ∈ -→ R and R / ∈ -→ R , and suppose that at a given pulse, there exists no concatenated message to deliver from R to R but there do exist a concatenated message M R →R to deliver from R to R. Since, no worker will move to the center of R , the concatenated message M R →R is missed. Note also that this is the only case where a concatenated message may be missed. To handle this case, we make the workers systematically move to all the neighboring regions defined by -→ R and ask whether a concatenated message has to be delivered back to R. Thus, each pulse of the original algorithm is simulated in at most O(1) stages, each stage lasts at most O(1) time.

Synchronizing the masters in neighboring regions can also be handled using the same technique.

Remark 5 The previous results should be compared with the fact that for any graph G, there exists a labeling function of G that can not be distributively computed by an algorithm using O(n) agents having no initial local views in time better than Ω(D) (e.g., compute a tree, a leader) and Ω(m/n) (e.g., compute a copy of the graph).

On computing with small memory agents

In previous sections, we have always considered that agents are equipped with enough memory when simulating the instructions of a given message passing algorithm. Actually, only the workers need to have enough internal memory to simulate message sending from a region to another. In fact, since a master never moves from its center node, then it can use the memory provided by the whiteboard to store the information needed for the simulation. However, a worker has to (i) store the concatenated messages (and the synchronization messages), (ii) store the route used to go from a center node to another one, and (iii) store the information needed to mark nodes with their final labeling at the end of the simulation:

The size of the concatenated messages depends both on the size of the messages in the original algorithm to simulate and on the number of edges connecting the nodes of two neighboring regions. In the worst case, O(m • b) bits of memory per agent are needed, where b is the maximum size (in bits) of a message sent by the original algorithm. The synchronization process requires only O(1) bit memory.

Using Theorem 3 for k = log n, two center nodes are at distance at most O(1). Thus, the memory needed by a worker to store a shortest path between two center nodes is at most O(1) bits. Actually, this memory overhead can be avoided by labeling the paths leading to neighboring regions in the preprocessing phase without time penalty. Since the overhead is negligible we omit the details.

Seeing that each worker in Theorem 3 has to store the final state of only one node in its region, it is not difficult to prove that the memory size needed for marking the nodes is O( ) bits, where is the maximum size (in bits) of the output labels.

Thus, assuming that is small compared to m (which is the case of many distributed algorithms), the memory size needed by a worker is dominated by the size of concatenated messages. Nevertheless, we remark that if a node in the original message passing algorithm sends the same message to all its neighbors then a worker can store only one message for that node in its internal memory, i.e., it does not need to store the same message many times. More generally, the memory size can be drastically improved for algorithms having particular behaviors. For instance, consider a message passing algorithm such that at each round a node (i) sends the same message M 1 to a bounded number of neighbors and (ii) the same message M 2 to the other neighbors. Then, it is not difficult to see that we can modify our concatenation mechanism so that the memory size needed by a worker is at most O(n • b) bits. In particular, we have Theorem 6 For any n-node graph G, using n mobile agents with n initial local view and having O(n) bit memory, a BFS tree with respect to a given node can be computed by a deterministic algorithm in O(D) time.

Proof. Consider the following flood-like (message passing) algorithm: initially a root node begins the BFS computation by sending a <Wave> message to its neighbors. Each node not yet in the tree waits upon the reception of <Wave> messages. Whenever some <Wave> messages are received for the first time at a given pulse, a node (i) chooses its parent in the tree, (ii) sends a <Wave> message to all its neighbors, and (iii) terminates. Clearly, this is a correct synchronous BFS tree algorithm detecting the local termination. Furthermore, a node always sends the same message to all its neighbors. Thus the previous discussion concerning the memory size needed by the agents applies for this algorithm.

Nevertheless, the agents simulating the above BFS tree algorithm will terminate without knowing that the tree was effectively computed. One solution is to add a convergecast stage from the leaves of the tree to the root and a broadcast stage from the root to the leaves. One can see that the convergecast stage requires that each node sends one message to its father in the tree at a given pulse. Thus, the memory size needed by the agents is O(n) bits. As for the broadcast stage, a node v may send the same message to an unbounded number of children requiring more than O(n) bits per agent. However, we remark that a master agent in a region containing some neighbors of node v, say (u 1 • • • u d ), can determine that v is the father of (u 1 • • • u d ). Thus, the only information that must be delivered to the master is: "v is broadcasting a message". Thus, one can prove that the memory size required by agents to detect that the tree was computed is still O(n) bits.

Theorem 7 For any n-node graph G, using n mobile agents with n initial local view and having O(1) bit memory, a leader can be computed in O(D) time.

Proof.(sketch) Actually, one can apply the following algorithm: (i) simulate algorithm Part (ii) compute the region having the highest identifier (iii) the center of that region is elected leader. Computing the highest region is then proved to need O(1) bit memory per agent. This can be done using a 'wave-like' algorithm on the graph induced by the regions and started in parallel by the master of each region.

Using the leader election, the BFS tree, the broadcast/convergecast process as basic procedures, one can think of other applications to more sophisticated algorithms.

Open problems

The results presented in this paper aim at understanding the power of computing with mobile agents having a small amount of knowledge. We believe that these results are a first step and an opening door towards new challenging problems in mobile agent computing. Hereafter, we give some open challenging questions:

1. Is a O(1) initial local view for the agents sufficient to compute as fast as with message passing? As regards to our randomized universal algorithm, this seems to be true (up to polylogarithmic factor) for many topologies and for many distributed tasks even when agents have no initial local view at all.

2. What lower bounds on the time ratio can we provide in the case of k mobile agents equipped with some limited initial local view? In particular, it is still not clear whether there is a √ k gap to close in our upper bound.

3. Is there any non trivial upper bound (or lower bound) on the time complexity if we constrain both the agent memory and the whiteboards to have limited capacity ? Actually, some of our techniques may help deriving new results concerning the memory of agents. However, it seems that new techniques have to be derived for studying computation models where the capacity of the whiteboards are limited.

  Input: a graph G with H(C) satisfied; a synchronous message passing algorithm MsA.Output: algorithm AgA in a region C. 1. For each pulse p in algorithm MsA, the master agent of a region C simulates the instructions of pulse p for all nodes in C (locally in r C ): (a) For every node in C, the master creates a collection of receive-buffers in the whiteboard of r C . (b) To simulate a send instruction from node u ∈ C to node v ∈ C, the master writes the message in the corresponding receive-buffer created in r C .

  (d) Let M be the set of new merged regions, and U the set of unmerged regions. (e) ∀R ∈ U, if R has a neighboring region R in M or in U then R selects one preferred edge -→ e leading to R . The preferred edge -→ e is called an outgoing edge with respect to R. ∀R ∈ C, if R has a neighboring region R ∈ M then let E(R → R ) = { -→ e 1 , ..., -→ e } be the subset of outgoing edges with respect to R that lead to R . If 2, then update the set -→ P by removing all but one edge from E(R → R ). (g) Update R := M and C := C ∪ U.

  Proof.(sketch) The outgoing edges with respect to a region R are added only at one iteration where R falls into set U (Step 2.e). The first claim of the lemma follows by remarking that U ⊂ L, and the number of neighbors of R in set M or set U is at most the number of neighbors of R before the merge process of Step 2.c.The two other claims follow by construction from Step 2.c. and Step 2.f.

  Assume that there is one agent per node and take k = log n in algorithm Part. Every agent simulates algorithm Part locally. If the homebase is not a center, then the agent becomes a worker in its region, otherwise it is a master. Thus the master of a region R owns |R| -1 workers.Consider two neighboring regions R and R computed by algorithm Part. By Lemma 6, one can see that we have three cases:

	Let Lemma 6, we have | -→ R be the set of regions that are incident to the outgoing edges with respect to R. By -→ R| = O(1) • |R|. Notice that the set -→ R does not define all the neighboring
	region of R.

RR n°6511

Exceptions exist for labeling schemes but they are problem specific or topology specific, see for example[START_REF] Korman | Labeling schemes for dynamic tree networks[END_REF] INRIA

One should note that using clustered representations is not new in distributed computing. For instance, they have been used successfully in [PS96, AR93, AGLP89, KP98, Awe85, DG06, BBCD02] to find efficient distributed protocols in the message passing setting. What is new is to show how these representations can be used for studying and designing efficient mobile agent algorithms.RR n°6511

The constant c in the following tables is the same than in Lemma 2.RR n°6511

We have given the names Det AgA and Rand AgA to detyerministic and randomized algorithms in order to clarify the presentation and to ease the comparaison with previous results. However, these two algorithms are not explicitly described in the paper as they can be implicitly derived from the generic simulation technique and the proof of the theorem.RR n°6511

http://www.inria.fr ISSN 0249-6399

Basic observations

Suppose that initially we have one agent per node. After the preprocessing of Theorem 3 or Theorem 4, each mobile agent can say whether it is a center of a region or not. Thus, it is easy to initialize the master agents: Each mobile agent who identifies its homebase as the center of a region becomes the master of its region. A trivial solution to initialize the workers is to allow the master to create as many workers as needed (such a clone like [START_REF] Abbas | Distributed computation of a spanning tree in a dynamic graph by mobile agents[END_REF][START_REF] Flocchini | Distributed security algorithms by mobile agents[END_REF] solution may be acceptable in practice). In the following, we will not make such an assumption.

A first idea to initialize the workers is to let an agent whose homebase is not a center of a region be a worker in its region. This idea will work in the case of Theorem 4. In fact, the ρdominating set algorithm of [START_REF] Kutten | Fast distributed construction of small k-dominating sets and applications[END_REF] also allows to partition the graph into regions having at least n/ρ nodes (This non trivial property is proved in [START_REF] Kutten | Fast distributed construction of small k-dominating sets and applications[END_REF]). Hence, if each agent in a non-center node becomes worker and joins his master (at distance ρ = n/ √ k), then each master agent will have the required number of workers assumed implicitly in Theorem 4 (The hypothesis H(C) is handled using the labeling computed by workers). Thus, the complexity of initializing the agents is negligible compared to the preprocessing.

The same idea will not work in the case of Theorem 3 since the number of required workers could be Θ(n 1+1/k ). One could think that if initially there are Θ(n 1/k ) mobile agents per node, then the previous initialization technique would hold. This is not true since the maximum degree of the graph G C , where C is the partition constructed in Lemma 2, is not bounded by O(n 1/k ). Partitions having small maximum degree exist. But, to our knowledge, there are no efficient distributed algorithms to construct them (By efficient here we mean having running time n ).

Hence, the question is : assume that we have Θ(n 1/k ) agent per node, how can we initialize the workers needed for Theorem 3 efficiently ? In the following, we give an answer to this question using algorithm Part described and analyzed in the next paragraphs.

Algorithm Part

Algorithm Part is given in Fig. 2 (The MIS procedure of Step 2.c denotes a Maximal Independent Set procedure [START_REF] Peleg | Distributed Computing: A Locality-Sensitive Approach[END_REF]).

The idea of algorithm Part is to construct the partition of Lemma 2 and at the same time to chose some particular edges, called preferred edges, that will help us initializing the workers. We remark that algorithm Part is an adaptation of algorithm Srategy 2 of [START_REF] Derbel | Fast deterministic distributed algorithms for sparse spanners[END_REF] (algorithm Part allows to improve the size of the spanners constructed there by a log k factor which could be of independent interest).

The proofs of the two following lemmas are essentially the same than the correctness proof of algorithm Srategy 2 of [START_REF] Derbel | Fast deterministic distributed algorithms for sparse spanners[END_REF]. Hence, we will only give a sketch. Proof.(sketch) Remark that the size of a merged region increases exponentially each iteration. Thus, after at most log k iterations all the regions will satisfy the sparsity condition of Step 2.a. The lemma is now proved by showing that at each iteration the radius of each new merged region increases by at most a multiplicative factor O(1).

Lemma 5 In the message passing model, algorithm Part can be implemented by a deterministic (resp. randomized) distributed algorithm in k

Proof.(sketch) Use the best known MIS algorithms [START_REF] Peleg | Distributed Computing: A Locality-Sensitive Approach[END_REF] In the next lemma, we will state some properties concerning the set of preferred edges contructed by algorithm Part.

First, let us remark that the definition of "an outgoing edge with respect to" a region R is given in Step 2.e of algorithm Part. Roughly speaking, it means that the edge is oriented from


est destinée au dépôt

Effects of high ambient temperature on responses of pigs to an inflammatory challenge

incrcased daily avera geel RT and VT at bath physiological stages (P<O.OOO 1) but these increases were higher in lactating than in dry cows ( + 1. 1 vs. 0.15 oc for RT in lactating and dry eows, and + 1.05 vs. +0.1 oc for VT). In ali situations, RT dropped at the times of the meals (-1.6 °C for the 08:30 h meal) and leveled off at a maximal value during the night. For lactaling cows at l-IT. VT followed a parallel pattern to thal of RT with post-pnmdial drop of -1 °C, whereas for lactating cows at TN and dry cows at both HT and TN, the hourly variation of VT was inferior to 0.3 °C. The hu ge infra-day variation of core temperature rel at cd to RT thal was observed in lactating cows at HT clearly showed thal the rumen can be a heat sink for the body when cow thermoregulation is impaired by high ambient temperature.

436

EAAP-641h An nuai Meeting, Nantes 2013

  Paulo Henrique Reis Furtado Campos, Elodie Merlot, Marie M. Damon, Jean Noblet, Nathalie Le Floc'H To cite this version: Paulo Henrique Reis Furtado Campos, Elodie Merlot, Marie M. Damon, Jean Noblet, Nathalie Le Floc'H. Effects of high ambient temperature on responses of pigs to an inflammatory challenge. 64. Annual Meeting of the European Federation of Animal Science (EAAP), Aug 2013, Nantes, France. hal-02747227 Session 32 Effects of high aml>ient temperature on res1Jonses of pigs to an inflammatory challenge P. H.R. F Campos, E. Meriot, M. Dam on, J. Noble! and N. Le Floc'h INRA, Ui\-fR 13./8 PEGASE. 35590 Sai lit-Gilles. France; paulo.campos@,remzes.illrafi• Theatre 5i\lthough the eff ects of heat stress on pig performance are weil descrihed in the litera\ ure. little is known about how am bien\ temperature could afl èct the ir ability to resist, cope with or recover from an inflammatOI)' challenge associated with heat stress. The aim of the study was to evaluate the effects of heat stress on performance and physiological rcsponscs of growing pigs submitted to repcated injections of Eschericlzia coli lipopolysaccharide lLPS). Cathetcrized and individually housed 48 kg gwwing pigs wcrc assigncd to thenno neutra) (TN: 24 °C; n=16) or heat S\Tess (HS: 30 °C; n=14) environmental conditions. Within each condition, pigs were submitted to 14 days of adaptation and th en to a 17-d experimental period divided in a period without LPS (P 1, from cl -7 to -1) and a subsequent peri ml with LPS administration (P2, from d 1 to 1 0). During P2, LPS was administered each 48 h (i.e. on d 1, 3, 5. 7 and 9) and the initial dosage of 30 �tg/kg of B W wns incrcascd by 12% at each subsequent injection. Dry matter intake decreased during P2 and this dccrease was greater in TN than in HS pigs (-28 vs. -19%, respectively; P<0.05). Average daily gain and feed efficiency were lower during P2 compared to P 1 in TN pigs (P<O.O 1 ), wh ile no differences (P>0.05) were observee! in HS pigs. Rectal temperature and plasma haptoglobin and cortisol concentrations were higher (P<O.OO 1) du ring P2 campa red to P 1. Total thyroxine levels were lower (P<O.OO 1) during P2 than during P 1. Plasma total triiodothyronine (T3) decreased (P<0.05) 24 h after the first LPS administration (LPSI) and thcn rcturncd to pre LPS levcls by d 6. A similar pattern of response was obscrvcd for frcc T3 but HS pigs rcturned to pre LPS levels earlicr (d 6: P<O.OI ) than TN pigs (d 10). Plasma intcrleukin-6 1evels were markedly inereased (P<O.O 1) a fier LPS 1 and this increase was twice higher (P<O.O 1) in TN th an in HS pigs. In conclusion. the eiTects of an innammatory challenge seem to be attenuated in heat-stressed pigs.Session 32Theatre 6lncrease in aml>ient temperature changes the relationship ruminai-core temperatures in lactating cows A. Boudon l . 2 , H. Khelif-A1ja l . 2 and P Faverdin / . 2 1 Agrocampus Ouest, UM/?13./8 PEGASE, 35000 Re11nes, France, 2 /NRA, UMR1348 PEGASE. 35590 Saim-Gilles, France; anne.boudo11@ren11es. i11ra,(l• Aulomatic monitoring of ruminai temperature is a promising tool for identification of hcat stress or other physiological disorders in dai1y cows. However, the relationship between ruminai and body core temperature has to be established in situation of high ambient temperatures. Daily dynamics of ruminai temperature (RT) and vaginal temperatures (VT) wcre compared in 4 dry and 4 lactating Holstein cows submitted to 2 ambient tempemtures (15 oc i.e. thermoneutrality (TN) or 28 oc i.e. high temperature (HT)) maintained constant throughout the day and 2 diet sodium contents (0.15 or 0.55 g/kg DM). RT and VT were re.corded every 15 min with indwelling autonomous monitoring systems (MEDRI/\ S./\.). Drinking and feeding behaviors were continuously recorded. The treatments were compared during 4 periods of 15 d, according to a Latin square design for each physiological stage. Diet consisted on a total mixed ration based on maize silage. Dry cows were offercd I4 kg Dl'vt/d while lactating cows wcre fed ad /ibiwm. At TN, average RT was 38.9 oc (SEM=O.II) and VT was 38.4 °C (SEM=0.15), whatever the physiological stage lP>0.15). HT


Lamia Krichen

Apricot core collection assessment using morphological characterization

teaching and research institutions in France or abroad, or from public or private research centers.


Joël Daroussin

A Python script to produce datasets to support GlobalSoilMap mapping of soil properties

Some tools have been built to fulfill the requirements of the GlobalSoilMap specifications for products to support the display and distribution of the Tiered soil properties. These tools can still be improved in particular to overcome some limitations in the management of the unique identifier that is attributed to each point/cell.

Introduction

To support the delivery of derived soil properties, the specifications of the GlobalSoilMap.net project (Science Committee 2013) suggest two types of spatial entities. Tier 1 is defined as point data describing soils down to 2 m depth at each location in a similar way to what a pedon would. Tier 2 is defined as volume data shaped as square cells down to the same 2 m depth in a similar way to what soil mapping units would. Both points and cells are regularly spaced by 3 arc seconds (~100 m). Points in the Tier 1 product correspond to the cell centers in the Tier 2 product. Soil properties are stored as attributes of these entity types. Each point/cell is given a unique identifier (ID) on a common global scheme to allow attachment of soil descriptions.

Ref: Science Committee of the GloBalSoilMap.net project, 2013. Specifications Tiered GlobalSoilMap products, Release 2.3, 05/2/2013. http://www.globalsoilmap.net

Tiling and numbering scheme

The goal is to build point and raster products at nested levels of resolution one of which is 3 arc seconds that follow the 1x1 degree SRTM tiling schema while avoiding tiles overlap and with coincident cell centers and boundaries.

Each point/cell is given a unique identifier using a hierarchical numbering system by appending characters to an ID to refine its precision (shown for levels 1 and 2).

To each level corresponds a resolution both in geographic and projected units.

Products Tools

GSM_id: for a given longitude/latitude and level, returns ID and residual.

GSM_id_reverse: for a given ID returns longitude/latitude and level.

GSM_id_tile: for a given 1 degree tile and level writes a text file containing IDs and their longitude/latitude.

version 2.7

Produces the data for a whole study area -not just a tile -, in projected coordinates -in addition to geographic coordinates -, and in an ESRI File Geodatabase® as well as in text files.

Points and cells produced for France at level 7 in geographic coordinates.

Notice that the points do not necessarily correspond to 1 degree tile limits illustrated by the graticule.

A close view on the nested set of points at levels 7, 8 and 9 and the corresponding numbering scheme for the Global Soil Map unique IDs. As a consequence one should be aware not to project the raster. Rather, one should use the point feature class product. Thus the following flowchart for usage of the products is proposed: Use GenerateGSM.py to produce a point feature class , the corresponding raster in geographic coordinates and a projected version of the point product . Perform analysis and modeling with needed covariates. These must be available in a common spatial reference (projected coordinate system). Transfer results to the projected points, but if the analysis involves the points (e.g. points carry some information from say a soil monitoring network) then transfer the covariates as well. Other analysis tasks may be run. Any of the point attributes, whether initial covariate values or analysis results, may be transferred to either one or both of the unprojected geographic coordinates point and raster products for visualization and/or data distribution.

5a 5b

Products usage needs caution

Due to distortion, projecting a raster introduces some artifacts because raster cells have to remain square whichever projection system is used.

The main effect that is of concern to our purpose is on GSM IDs.

Projecting the raster loss of uniqueness of the GSM IDs.

Rasterizing the projected points loss of GSM ID and loss of sense of the GSM ID.

  NB: If a covariate carries nominal or ordinal values, it must be transferred by simple point-in-cell spatial join. If it carries quantitative values it may rather be transferred by interpolation techniques.


Stephane Pezennec

Said Bouhallab

Pascaline Hamon

Anne Renault

Sylvie Beaufils

The bulk association

est destinée au dépôt

14th International Conference on Organized Molecular Films ICOMF14 (LB14) Paris July 10-13, 2012

The Bulk Association Mechanism between Lysozyme and alpha-Lactalbumine Is Revealed by Interfacial Measurements

Stephane Pezennec 1,2 , Saïd Bouhallab 1,2 , Pascaline Hamon Controlled interactions and assembly of proteins with one another promise to be a powerful approach for generating novel supramolecular architectures. In this study, we report on two oppositely charged proteins, Lysozyme (LYS) and alpha-Lactalbumine (ALA) which self-assemble into well-defined micrometer-sized spherical particles under specific physicochemical conditions. These particles are spontaneously built following two main steps: first the formation of oligomers constituting the elementary pieces of the final assembly, second the growth of the particles by assembly of these oligomers (1-3). We hypothezised that the adsorption steps at the air water interface would reflects the assembly mechanism leading to the micro-spheres. To test this hypothesis, we have recorded adsorption kinetics at the air-water interface, of LYS and ALA in conditions where microspheres were formed and in conditions where microspheres could not grow up (i.e. at high ionic strength). Our results show that the adsorption of the mixture LYS-ALA at the air-water interface is governed by the same rules that govern the first steps of formation of micro-spheres.

Fig. 1 :

 1 Fig. 1: In condition of formation of micro-spheres, the mixture LYS-ALA forms multilayers at the air-water interface. At high ionic force, micro-spheres does not grow and the mixture LYS-ALA forms a monolayer at the air-water interface

Acknowledgements: This work was supported by ANR