Julian Anaya
email: ingjuliananaya@gmail.com

Jérémie Chalopin
email: jeremie.chalopin@lif.univ-mrs.fr

Jurek Czyzowicz

Arnaud Labourel
email: arnaud.labourel@lif.univ-mrs.fr

Andrzej Pelc
email: pelc@uqo.ca

Yann Vaxès
email: yann.vaxes@lif.univ-mrs.fr

Con

Convergecast and Broadcast by Power-Aware Mobile Agents

scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

1 Introduction

The model and the problem

A set of agents is deployed in a network represented by a weighted graph G. An edge weight is a positive real representing the length of the edge, i.e., the distance between its endpoints along the edge. The agents start simultaneously at different nodes of G. Every agent has a battery: a power source allowing it to move in a continuous way along the network edges. An agent may stop at any point of a network edge (i.e. at any distance from the edge endpoints, up to the edge weight). The movements of an agent use its battery proportionally to the distance traveled. We assume that all agents move at the same speed that is equal to one, i.e., we can interchange the notions of the distance traveled and the time spent while traveling. In the beginning, the agents start with the same amount of power noted P , allowing all agents to travel the same distance P .

We consider two tasks: convergecast, in which at the beginning, each agent has some initial piece of information, and information of all agents has to be collected by some agent, not necessarily predetermined; and broadcast in which information of one specified agent has to be made available to all other agents. In both tasks, agents notice when they meet (at a node or inside an edge) and they exchange the currently held information at every meeting.

The task of convergecast is important, e.g., when agents have partial information about the topology of the network and the aggregate information can be used to construct a map of it, or when individual agents hold measurements performed by sensors located at their initial positions and collected information serves to make some global decision based on all measurements. The task of broadcast is used, e.g., when a preselected leader has to share some information with others agents in order to organize their collaboration in future tasks.

Agents try to cooperate so that convergecast (respectively broadcast) is achieved with the smallest possible agent's initial battery power P c OP T (respectively P b OP T ), i.e., minimizing the maximum distance traveled by an agent. We investigate these two problems in two possible settings, centralized and distributed.

In the centralized setting, the optimization problems must be solved by a central authority knowing the network and the initial positions of all the agents. We call strategy a finite sequence of movements executed by the agents. During each movement, starting at a specific time, an agent walks between two points belonging to the same network edge. A strategy is a convergecast strategy if the sequence of movements results in one agent getting the initial information of every agent. A strategy is a broadcast strategy if the sequence of movements results in all agents getting the initial information of the source agent. We consider two different versions of the problem : the decision problem, i.e., deciding if there exists a convergecast strategy or a broadcast strategy using power P (where P is the input of the problem) and the optimization problem, i.e., computing the smallest amount of power that is sufficient to achieve convergecast or broadcast.

In the distributed setting, the task of convergecast or broadcast must be approached individually by each agent. Each agent is unaware of the network, of its position in the network and of the positions (or even the presence) of any other agents. The agents are anonymous and they execute the same deterministic algorithm. Each agent has a very simple sensing device allowing it to detect the presence of other agents at its current location in the network. Each agent is also aware of the degree of the node at which it is located, as well as the port through which it enters a node, called an entry port. We assume that the ports of a node of degree d are represented by integers 1, 2, . . . , d. Agents can meet at a node or inside an edge. When two or more agents meet at a node, each of them is aware of the direction from which the other agent is coming, i.e., the last entry port of each agent.

Since the measure of efficiency in this paper is the battery power (or the maximum distance traveled by an agent, which is proportional to the battery power used) we do not try to optimize the other resources (e.g. global execution time, local computation time, memory size of the agents, communication bandwidth, etc.). In particular, we conservatively suppose that, whenever two agents meet, they automatically exchange the entire information they hold (rather than the new information only). This information exchange procedure is never explicitly mentioned in our algorithms, supposing, by default, that it always takes place when a meeting occurs. The efficiency of a distributed solution is expressed by the competitive ratio, which is the worst-case ratio of the amount of power necessary to solve the convergecast or the broadcast problem by the distributed algorithm with respect to the amount of power computed by the optimal centralized algorithm, which is executed for the same agents' initial positions.

It is easy to see, that in the optimal centralized solution for the case of the line and the tree, the original network may be truncated by removing some portions and leaving only the connected part of it containing all the agents (this way all leaves of the remaining tree contain initial positions of agents). We make this assumption also in the distributed setting, since no finite competitive ratio is achievable if this condition is dropped. Indeed, two nearby anonymous agents inside a long line need to travel, in the worst case, a long distance to one of its endpoints in order to meet.

Related work

Rapidly developing network and computer industry fueled the research interest in mobile agents computing. Mobile agents are often interpreted as software agents, i.e., programs migrating from host to host in a network, performing some specific tasks. However, the recent developments in computer technology bring up problems related to physical mobile devices. These include robots or motor vehicles and various wireless gadgets. Examples of agents also include living beings: humans (e.g. soldiers in the battlefield or disaster relief personnel) or animals (e.g. birds, swarms of insects).

In many applications the involved mobile agents are small and have to be produced at low cost in massive numbers. Consequently, in many papers, the computational power of mobile agents is assumed to be very limited and feasibility of some important distributed tasks for such collections of agents is investigated. For example [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF] introduced population protocols, modeling wireless sensor networks by extremely limited finite-state computational devices. The agents of population protocols move according to some mobility pattern totally out of their control and they interact randomly in pairs. This is called passive mobility, intended to model, e.g., some unstable environment, like a flow of water, chemical solution, human blood, wind or unpredictable mobility of agents' carriers (e.g. vehicles or flocks of birds). On the other hand, [START_REF] Suzuki | Distributed anonymous mobile robots: Formation of geometric patterns[END_REF] introduced anonymous, oblivious, asynchronous, mobile agents which cannot directly communicate, but they can occasionally observe the environment. Gathering and convergence [START_REF] Ando | Distributed memoryless point convergence algorithm for mobile robots with limited visibility[END_REF][START_REF] Cieliebak | Solving the robots gathering problem[END_REF][START_REF] Cohen | Convergence properties of the gravitational algorithm in asynchronous robot systems[END_REF][START_REF] Cord-Landwehr | A new approach for analyzing convergence algorithms for mobile robots[END_REF], as well as pattern formation [START_REF] Das | On the computational power of oblivious robots: Forming a series of geometric patterns[END_REF][START_REF] Flocchini | Gathering of asynchronous robots with limited visibility[END_REF][START_REF] Suzuki | Distributed anonymous mobile robots: Formation of geometric patterns[END_REF][START_REF] Yamashita | Characterizing geometric patterns formable by oblivious anonymous mobile robots[END_REF] were studied for such agents.

Apart from the feasibility questions for limited agents, the optimization problems related to the efficient usage of agents' resources have been also investigated. Energy management of (not necessarily mobile) computational devices has been a major concern in recent research papers (cf. [START_REF] Albers | Energy-efficient algorithms[END_REF]). Fundamental techniques proposed to reduce power consumption of computer systems include power-down strategies (see [START_REF] Albers | Energy-efficient algorithms[END_REF][START_REF] Augustine | Optimal power-down strategies[END_REF][START_REF] Irani | Algorithms for power savings[END_REF]) and speed scaling (introduced in [START_REF] Yao | A scheduling model for reduced cpu energy[END_REF]). Several papers proposed centralized [START_REF] Bunde | Power-aware scheduling for makespan and flow[END_REF][START_REF] Stojmenovic | Power-aware localized routing in wireless networks[END_REF][START_REF] Yao | A scheduling model for reduced cpu energy[END_REF] or distributed [START_REF] Albers | Energy-efficient algorithms[END_REF][START_REF] Ambühl | An optimal bound for the mst algorithm to compute energy efficient broadcast trees in wireless networks[END_REF][START_REF] Augustine | Optimal power-down strategies[END_REF][START_REF] Irani | Algorithms for power savings[END_REF] algorithms. However, most of this research on power efficiency concerned optimization of overall power used. Similar to our setting, assignment of charges to the system components in order to minimize the maximal charge has a flavor of another important optimization problem which is load balancing (cf. [START_REF] Azar | On-line load balancing[END_REF]).

In wireless sensor and ad hoc networks the power awareness has been often related to the data communication via efficient routing protocols (e.g. [START_REF] Ambühl | An optimal bound for the mst algorithm to compute energy efficient broadcast trees in wireless networks[END_REF][START_REF] Stojmenovic | Power-aware localized routing in wireless networks[END_REF]. However in many applications of mobile agents (e.g. those involving actively mobile, physical agents) the agent's energy is mostly used for it's mobility purpose rather than communication, since active moving often requires running some mechanical components, while communication mostly involves (less energy-prone) electronic devices. Consequently, in most tasks involving moving agents, like exploration, searching or pattern formation, the distance traveled is the main optimization criterion (cf. [START_REF] Albers | Exploring unknown environments[END_REF][START_REF] Alpern | The theory of search games and rendezvous[END_REF][START_REF] Awerbuch | Piecemeal graph exploration by a mobile robot[END_REF][START_REF] Baezayates | Searching in the plane[END_REF][START_REF] Betke | Piecemeal learning of an unknown environment[END_REF][START_REF] Blum | Navigating in unfamiliar geometric terrain[END_REF][START_REF] Deng | Exploring an unknown graph[END_REF][START_REF] Dynia | Power-aware collective tree exploration[END_REF][START_REF] Fraigniaud | Collective tree exploration[END_REF][START_REF] Megow | Online graph exploration: New results on old and new algorithms[END_REF]). Single agent exploration of an unknown environment has been studied for graphs, e.g. [START_REF] Albers | Exploring unknown environments[END_REF][START_REF] Deng | Exploring an unknown graph[END_REF], or geometric terrains, [START_REF] Baezayates | Searching in the plane[END_REF][START_REF] Blum | Navigating in unfamiliar geometric terrain[END_REF].

While a single agent cannot explore a graph of unknown size unless pebble (landmark) usage is permitted (see [START_REF] Bender | The power of a pebble: Exploring and mapping directed graphs[END_REF]), a pair of robots are able to explore and map a directed graph of maximal degree d in O(d 2 n 5 ) time with high probability (cf. [START_REF] Bender | The power of team exploration: two robots can learn unlabeled directed graphs[END_REF]). In the case of a team of collaborating mobile agents, the challenge is to balance the workload among the agents so that the time to achieve the required goal is minimized. However this task is often hard (cf. [START_REF] Frederickson | Approximation algorithms for some routing problems[END_REF]), even in the case of two agents in a tree, [START_REF] Averbakh | A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree[END_REF]. On the other hand, the authors of [START_REF] Fraigniaud | Collective tree exploration[END_REF] study the problem of agents exploring a tree, showing O(k/ log k) competitive ratio of their distributed algorithm provided that writing (and reading) at tree nodes is permitted.

Assumptions similar to our paper have been made in [START_REF] Awerbuch | Piecemeal graph exploration by a mobile robot[END_REF][START_REF] Blum | Navigating in unfamiliar geometric terrain[END_REF][START_REF] Dynia | Power-aware collective tree exploration[END_REF] where the mobile agents are constrained to travel a fixed distance to explore an unknown graph [START_REF] Awerbuch | Piecemeal graph exploration by a mobile robot[END_REF][START_REF] Blum | Navigating in unfamiliar geometric terrain[END_REF], or tree [START_REF] Dynia | Power-aware collective tree exploration[END_REF]. In [START_REF] Awerbuch | Piecemeal graph exploration by a mobile robot[END_REF][START_REF] Blum | Navigating in unfamiliar geometric terrain[END_REF] a mobile agent has to return to its home base to refuel (or recharge its battery) so that the same maximal distance may repeatedly be traversed. [START_REF] Dynia | Power-aware collective tree exploration[END_REF] gives an 8-competitive distributed algorithm for a set of agents with the same amount of power exploring the tree starting at the same node.

The convergecast problem is sometimes viewed as a special case of the data aggregation question (e.g. [START_REF] Krishnamachari | The impact of data aggregation in wireless sensor networks[END_REF][START_REF] Rajagopalan | Data-aggregation techniques in sensor networks: a survey[END_REF]) and it has been studied mainly for wireless and sensor networks, where the battery power usage is an important issue (cf. [START_REF] Kesselman | Fast distributed algorithm for convergecast in ad hoc geometric radio networks[END_REF][START_REF] Annamalai | On tree-based convergecasting in wireless sensor networks[END_REF]). Recently [START_REF] Chen | when, where: Timeslot assignment to mobile clients[END_REF] considered the online and offline settings of the scheduling problem when data has to be delivered to mobile clients while they travel within the communication range of wireless stations. [START_REF] Kesselman | Fast distributed algorithm for convergecast in ad hoc geometric radio networks[END_REF] presents a randomized distributed convergecast algorithm for geometric ad-hoc networks and study the trade-off between the energy used and the latency of convergecast. The broadcast problem for stationary processors has been extensively studied both for the message passing model, see e.g. [START_REF] Awerbuch | A trade-off between information and communication in broadcast protocols[END_REF], and for the wireless model, see e.g. [START_REF] Bar-Yehuda | On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization[END_REF]. To the best of our knowledge, the problem of the present paper, when the mobile agents perform convergecast or broadcast by exchanging the held information when meeting, while optimizing the maximal power used by a mobile agent, has never been investigated before.

Our results

In the centralized setting, we give a linear-time algorithm to compute the optimal battery power and the strategy using it, both for convergecast and for broadcast, when agents are on the line. We also show that finding the optimal battery power for convergecast or for broadcast is NP-hard for the class of trees. In fact, the respective decision problem is strongly NP-complete. On the other hand, we give a polynomial algorithm that finds a 2-approximation for convergecast and a 4-approximation for broadcast, for arbitrary graphs.

In the distributed setting, we give a 2-competitive algorithm for convergecast in trees and a 4-competitive algorithm for broadcast in trees. The competitive ratio of 2 is proved to be the best for the problem of convergecast, even if we only consider line networks. Indeed, we show that there is no (2 -)-competitive algorithm for convergecast or for broadcast in the class of lines, for any > 0.

The following table gives the summary of our results.

Setting Problems

Convergecast Broadcast

Centralized

• linear-time algorithm to compute optimal battery power and strategy on lines • proof that the above problem is NP-hard on trees

Roadmap

In Section 2, we show that we can restrict the search for the optimal strategy for convergecast or broadcast on the line to some smaller subclass of strategies called regular strategies. In Section 3, we present our centralized algorithms for convergecast and broadcast on lines. Section 4 is devoted to centralized convergecast and broadcast on trees and graphs. In Section 5, we investigate convergecast and broadcast in the distributed setting. Section 6 contains conclusions and open problems.

Regular strategies for convergecast and broadcast on lines

In this section, we show that if we are given a convergecast (respectively broadcast) strategy for some initial positions of agents in the line, then we can always modify it in order to get another convergecast (respectively broadcast) strategy, using the same amount of maximal power for every agent, satisfying some simple properties. Such strategies will be called regular. These observations permit to restrict the search for the optimal strategy to some smaller and easier to handle subclass of strategies.

We order agents according to their positions on the line. Hence we can assume w.l.o.g., that agent a i , for 1 ≤ i ≤ n is initially positioned at point P os[i] of the line of length and that 0 ≤ P os [START_REF] Albers | Energy-efficient algorithms[END_REF] < P os[2] < . . . < P os[n] ≤ . The set P os[1 : n] will be called a configuration for the line of length .

Regular carry strategies

Given a configuration P os[1 : n], a starting point s, a target point t (s < t), and an amount of power P , we want to know if there exists a strategy S for the agents enabling them to move the information from s to t so that the amount of power spent by each agent is at most P . Strategies that move information from point s to point t will be called carry strategies for (P os[1 : n], s, t, P ). We restrict attention to configurations P os[1 : n] such that |s -P os [START_REF] Albers | Energy-efficient algorithms[END_REF]| < P and |t -P os[n]| < P because otherwise either P os [START_REF] Albers | Energy-efficient algorithms[END_REF] (respectively P os [n]) is useless or it is impossible to carry information from s to t. A regular carry strategy for (P os[1 : n], s, t, P ) is the set of moves for agents a 1 , a 2 , . . . , a n defined as follows: agent a i first goes back to a point b i ≤ P os[i], getting there the information from the previous agent (except a 1 that has to go to s), then it goes forward to a point f i ≥ b i . Moreover, we require that each agent travels the maximal possible distance, i.e., it spends all its power. Lemma 1. If there exists a carry strategy for (P os[1 : n], s, t, P ), then there exist the following two regular carry strategies.

The pull strategy that can be computed iteratively (in linear time) starting with the last agent:

1. b 1 ≤ s, f n = t, 2. b i = f i-1 , ∀2 ≤ i ≤ n, 3. f i = P + 2b i -P os[i] ≥ b i , ∀1 ≤ i ≤ n.
The push strategy that can be computed iteratively (in linear time) starting with the first agent:

1. b 1 = min{P os[1], s}, f n ≥ t, 2. b i = min(f i-1 , P os[i]), ∀2 ≤ i ≤ n, 3. f i = P + 2b i -P os[i] ≥ b i , ∀1 ≤ i ≤ n.
Proof. We first show that there exists a pull strategy. Consider (P os[1 : n], s, t, P ) with the minimum number of agents such that there exists a carry strategy, but no pull strategy. We consider the smallest value s such that (P os[1 : n], s, t, P ) admits a carry strategy but no pull strategy. If P os [START_REF] Albers | Energy-efficient algorithms[END_REF] < s, then either P os[1] + P < s, or P os[1] + P ≥ s. In the first case, a 1 cannot move the information between s and t, and then (P os[2 : n], s, t, P ) admits a carry strategy but not a pull strategy and has fewer agents. In the second case, S is also a carry strategy for (P os[1 : n], P os [START_REF] Albers | Energy-efficient algorithms[END_REF], t, P ) and there is no pull strategy for (P os[1 : n], P os [START_REF] Albers | Energy-efficient algorithms[END_REF], t, P ), contradicting our choice of s.

Hence, we may suppose that P os [START_REF] Albers | Energy-efficient algorithms[END_REF] ≥ s. Since there exists a carry strategy S, let a i be the first agent that reaches s. The rightmost point where a i can move the information from s is s = 2s + P -P os[i]. Since S is a carry strategy, when considering all the agents except i, S is a carry strategy for (P os[S \ {i}], s , t, P ). By minimality of the number of agents, the pull strategy solves the subproblem on (P os[S \ {i}], s , t, P ). Consequently, we can assume that S is a pull strategy on (P os[S \ {i}], s , t, P ). If i = 1, by minimality of s, we have s = b 2 and thus S is a pull strategy which is a contradiction. Hence, suppose that i > 1. Note that if P os[i] = P os [START_REF] Albers | Energy-efficient algorithms[END_REF], we can exchange the roles of a i and a 1 and we are in the previous case. Hence, suppose that P os[i] > P os [START_REF] Albers | Energy-efficient algorithms[END_REF] and let [b 1 , f 1 ] be the interval that a 1 traverses with the information when S is applied; by minimality of s, b 1 = s and consequently we have P = P os[i] + b 1 -2s = P os [START_REF] Albers | Energy-efficient algorithms[END_REF] + f 1 -2b 1 , and thus s = (2P os[i]+P os [START_REF] Albers | Energy-efficient algorithms[END_REF]+f 1 -3P )/4. Consider now the strategy where we exchange the roles of a 1 and a i : a 1 gets the information from s, gives it to a i , and a i goes to f 1 . More formally, let

f i = f 1 , b i = (P os[i] + f i -P )/2, f 1 = b i and b 1 = (P os[1] + f 1 -P )/2.
From our definition of f 1 and s 1 and the first part of the proof, there exists a carry strategy for (P os[1 : n], b 1 , t, P ). However, b 1 = (2P os [START_REF] Albers | Energy-efficient algorithms[END_REF] + P os[i] + f 1 -3P )/4 = s + (P os [START_REF] Albers | Energy-efficient algorithms[END_REF] -P os[i])/4 < s, contradicting the minimality of s.

Consequently, if there exists a carry strategy S for (P os[1 : n], s, t, P ), then there exists a pull strategy on (P os[1 : n], s, t, P ). Now suppose that (P os[1 : n], s, t, P ) admits a carry strategy. From the first part of the proof, we know that it admits a pull strategy. The push strategy for (P os[1 : n], s, t, P ) can be obtained inductively from the pull strategy. Let [b i , f i ] for i = 1, ..., n be the set of intervals that induces the pull strategy for (P os[1 : n], s, t, P ). Notice that [b i , f i ] for i = 1, ..., n -1 induces the pull strategy for (P os[1 : n -1], s, b n , P ). By induction, there exists a set of intervals [b i , f i ] that induces a push strategy for (P os[1 : n-1], s, b n , P ) with f n-1 ≥ b n . We define b n = min{P os[n], f n-1 } and f n = P + 2b n -P os [n]. Since b n ≥ f n-1 ≥ b n , we deduce that f n ≥ f n ≥ t and therefore the set of intervals [b i , f i ] induces a push strategy for (P os[1 : n], s, t, P ).

Remark 1. Note that the pull strategy is uniquely defined by a configuration P os[1 : n], a target point t, and an amount of power P and enables to compute the smallest s such that (P os[1 : n], s, t, P ) admits a carry strategy.

Similarly, the push strategy is uniquely defined by a configuration P os[1 : n], a starting point s, and an amount of power P and enables to compute the largest t such that (P os[1 : n], s, t, P ) admits a carry strategy.

Note that carry strategies are defined for the target t larger than the starting point s. A carry strategy will be called reverse if the target t is smaller than s and all moves to the right are replaced by moves to the left and vice-versa.

Regular convergecast strategies

We now define the notion of a regular convergecast strategy for P os[1 : n] on the segment [0, ], using power at most P . Without loss of generality, we suppose that P os [START_REF] Albers | Energy-efficient algorithms[END_REF] = 0 and P os[n] = . Intuitively, a regular convergecast strategy divides the set of all agents into the set of left agents and the set of right agents such that left agents execute a push strategy from P os [START_REF] Albers | Energy-efficient algorithms[END_REF] and right agents execute a reverse push strategy from P os [n].

More formally, a regular convergecast strategy is given by a partition of the agents into two sets LR = {a i | i ≤ p} and RL = {a i | i > p} for some p, and by two points b i , f i of segment [0, ] for each agent a i , such that (1) if a i ∈ LR, b i = min{f i-1 , P os[i]} and f i = 2b i + P -P os[i],

(2) if a i ∈ RL, b i = max{f i+1 , P os[i]} and f i = 2b i -P -P os[i],

(3)

F LR = max{f i | a i ∈ LR} ≥ F RL = min{f i | a i ∈ RL}.
Suppose that we are given a partition of the agents into two disjoint sets LR and RL and values b i , f i for each agent a i satisfying conditions (1)- [START_REF] Alpern | The theory of search games and rendezvous[END_REF]. Then the following moves define a regular convergecast strategy: first, every agent a i ∈ LR ∪ RL moves to b i ; subsequently, every agent in LR moves to f i once it learns the initial information of a 1 ; then, every agent in RL moves to f i once it learns the initial information of a n . Let a k be an agent from LR such that f k is maximum. Once a k has moved to f k , it knows the initial information of all the agents a i such that b

i ≤ f k . If f k ≥ , convergecast is achieved. Otherwise, since f k = max{f i | a i ∈ LR} ≥ min{f i | a i ∈ RL},
we know that there exists an agent a j ∈ RL such that f j ≤ f k < b j . When a j reaches f k it knows the initial information of all the agents such that b i ≥ f k and thus, a j and a k know the initial information of all agents, which accomplishes convergecast.

The following lemma shows that we can restrict attention to regular convergecast strategies.

Lemma 2. If there exists a convergecast strategy for a configuration P os[1 : n] using power at most P then there exists a regular convergecast strategy for the configuration P os[1 : n] using power at most P .

Proof. Consider a convergecast strategy S for a configuration P os[1 : n] using power at most P . Suppose that convergecast occurred at time t at some point q. If an agent a i does not get the initial information of a 1 , then at time t it must have been in the segment [q, P os[n]]. Hence, by time t, it must have learned the initial information of a n . It follows that every agent a i , for 1 < i < n, must learn either the initial information of agent a 1 or of a n . Therefore, we can partition the set of agents performing a convergecast strategy into two subsets LR and RL, such that each agent a i ∈ LR learns the initial information of agent a 1 before learning the initial information of agent a n (or not learning at all the information of a n ). All other agents belong to RL. We denote by [b i , f i ] the interval of all points visited by a i ∈ LR and by [f j , b j ] the interval of points visited by a j ∈ RL.

Let F LR = max{f i | a i ∈ LR} and F RL = min{f j | a j ∈ RL}.
Since S is a convergecast strategy, we have F LR > F RL . Observe that the agents in LR move the initial information of a 1 from P os [START_REF] Albers | Energy-efficient algorithms[END_REF] to F LR and that the agents in RL move the initial information of a n from P os[n] to F RL . From Lemma 1, we can assume that the agents in LR (resp. RL) execute a push strategy (resp. a reverse push strategy) and thus conditions (1)-(3) hold.

Suppose now that there exists an agent a i ∈ RL such that a i+1 ∈ LR. Let f RL (i) = min{f j | a j ∈ RL, j > i} and f LR (i + 1) = max{f j | a j ∈ LR, j < i}; note that b i = max{f RL (i), P os[i]} and b i+1 = min{f LR (i + 1), P os[i + 1]}. Consider the strategy where we exchange the roles of a i and a i+1 , i.e., we put a i ∈ LR and

a i+1 ∈ RL. Let b i = min{f LR (i + 1), P os[i]}, b i+1 = max{f RL (i), P os[i + 1]}, f i = 2b i + P -P os[i] and f i+1 = 2b i+1 -P -P os[i + 1]. If f RL (i) ≤ P os[i + 1], then f i+1 = P os[i + 1] -P ≤ b i+1 ≤ f LR (i + 1). If f LR (i + 1) ≥ P os[i], then f i = P os[i] + P ≥ b i ≥ f RL (i).
In both cases, we still have a convergecast strategy.

If

f RL (i) ≥ P os[i + 1] and f LR (i + 1) ≤ P os[i], then f i = 2f LR (i + 1) + P -P os[i] > 2f LR (i + 1) + P - P os[i + 1] = f i+1 , and f i+1 = 2f RL (i) -P -P os[i + 1] < 2f RL (i) -P -P os[i] = f i . Consequently, we still have a convergecast strategy.
Applying this exchange a finite number of times, we get a regular convergecast strategy.

Regular broadcast strategies

We now define the notion of a regular broadcast strategy for P os [1 : n] where the source agent is a k , on the segment [0, ], using power at most P . Without loss of generality, we suppose that P os [START_REF] Albers | Energy-efficient algorithms[END_REF] = 0 and P os[n] = . Intuitively, a regular broadcast strategy divides the set of all agents into the set of left agents and the set of right agents such that left agents execute a reverse pull strategy from P os[k] and right agents execute a pull strategy from P os[k].

More formally, a regular broadcast strategy is given by points b i , f i of segment [0, ] defined for each agent a i such that

1. b 1 = f 1 = P os[1] + P , b n = f n = P os[n] -P , 2. if 1 < i < k, f i = b i-1 and b i = (f i + P os[i] + P )/2, 3. if k < i < n, f i = b i+1 and b i = (f i + P os[i] -P )/2, 4. {b k , f k } = {b k-1 , b k+1 } and |2b k -P os[k] -f k | ≤ P
Suppose that we are given points b i , f i for each agent a i , satisfying conditions (1)-(4). Then the following moves define a regular broadcast strategy: initially every agent a i moves to b i . Once a i learns the source information, a i moves to f i . Since (1)-(4) hold, this is a broadcast strategy and the maximum amount of power spent is at most P .

Before proving that it is enough to only consider regular broadcast strategies, we need to prove the following technical lemma. Lemma 3. There exists a broadcast strategy S for a configuration (P os[1 : n], k, P ) if and only if for every i, there exist positions l i , x i , r i such that [START_REF] Albers | Energy-efficient algorithms[END_REF]

for each i, l i ≤ x i ≤ r i (2) x k = P os[k]; (3) for each i, |x i -P os[i]| + min(x i + r i -2l i , 2r i -x i -l i ) ≤ P . (4) for each i, if x i < P os[k] (resp. x i > P os[k]
), there exists j such that x i ∈ [l j , r j ] and x j > x i (resp.

x j < x i ).

Proof. Consider a broadcast strategy S where the maximum amount of power spent is P . For every agent a i , let x i be the position where a i learns the information that has to be broadcast, and let l i (resp. r i ) be the leftmost (resp. rightmost) position reached by a i once it got the information. By definition of l i , x i , r i , ( 1) and ( 2) hold. Since the maximum amount of power spent by an agent is at most P , and since the agent has to go from P os[i] to x i and then to r i and l i , (3) holds. Since every agent learns the information, for every agent a i , either

x i = P os[k],
or a i meets an agent a j in x i such that a j already has the information. Assume that x i < P os[k] (the other case is symmetric). If x i < x j , then (4) holds for i. Suppose now that x j ≤ x i ≤ P os[k] and let A be the non-empty set of agents a j such that x j ≤ x i and a j learns the information before a i . Let a j ∈ A be the agent that is first to learn the information. Since x j ≤ x i < P os[k], a j learns the information from an agent a j that does not belong to A. Consequently, x j > x i ≥ x j and thus

x i ∈ [x j , x j ] ⊆ [l j , r j ]. Thus (4) holds for i.
Conversely, if we are given values x i , l i , r i satisfying ( 1)-( 4), we can exhibit a strategy for broadcast: initially every agent a i moves to x i . Once a i learns the information, if x i + r i -2l i ≤ 2r ix il i , then a i moves to l i and to r i and if x i + r i -2l i > 2r ix il i , then a i moves to r i and to l i . Since (4) holds, this is a broadcast strategy and since (3) holds, the maximum amount of power spent is at most P .

The following lemma shows that we can restrict attention to regular broadcast strategies. Lemma 4. If there exists a broadcast strategy for a configuration P os[1 : n] with source agent a k , using power at most P , then there exists a regular broadcast strategy for the configuration P os[1 : n] with source agent a k , using power at most P .

Proof. Suppose that there exists a broadcast strategy for (P os[1 : n], k, P ). For every agent a i , i = k we define b i , f i as in the definition of a regular broadcast strategy. Note that the agents {a i | 1 < i < k} execute a reverse pull strategy between b k-1 and P os [START_REF] Albers | Energy-efficient algorithms[END_REF] + P . Similarly, the agents {a i | k < i < n} execute a pull strategy between b k+1 and P os[n] -P . By Remark 1, it means that there exists i > k (resp. i < k) such that a i reaches b k-1 (resp. b k+1 ) with the information from a k . Moreover, since the agents execute either a reverse pull strategy or a pull strategy, we have P os

[k -1] ≤ b k-1 , and P os[k + 1] ≥ b k+1 .
Suppose the lemma does not hold. This means that 2b k+1 -P os[k]-b k-1 > P , and b k+1 +P os[k]-2b k-1 > P . Consequently, a k cannot reach both b k-1 and b k+1 , i.e., there exists i < k such that a i reaches b k+1 , or there exists i > k such that a i reaches b k-1 . If P os[k] ≤ b k-1 , it implies that b k+1 > P os[k] + P , and consequently, there cannot exist a broadcast strategy since there is no carry strategy on (P os[k : n -1], P os[k], P os[n] -P, P ). Consequently, we can assume that P os[k] > b k-1 . Using a similar argument we can also assume that P os[k] < b k+1 .

Among all broadcast strategies, consider the strategy that minimizes the size of

A = {a i | i < k and a i reaches b k+1 }∪{a i | i > k and a i reaches b k-1 }. Without loss of generality, assume that a k does not reach b k-1 , and let i > k such that a i reaches b k-1 .
For each agent a j , let x j , l j , r j be defined as in Lemma 3. Note that r k ≤ P os[k] + P and

r i ≤ l i + P ≤ b k-1 + P ≤ P os[k] + P . Moreover, P os[i] -P ≤ l i ≤ b k-1 ≤ l k .
Consider the new strategy defined as follows: for each agent j / ∈ {i, k}, let x j = x j , l j = l j and r j = r j ; let

x k = x k = P os[k], r k = (P os[k] + P os[i])/2 and l k = P os[i] -P ; let x i = l i = (P os[k] + P os[i])/2 and r i = P os[k] + P . Note that r i + P os[i] -2l i ≤ P and 2r k -P os[k] -l k ≤ P . Since [l i , r i ] ∪ [l k , r k ] ⊆ [P os[i] - P, P os[k] + P ] = [l k , r k ] ∪ [l i , r i ],
this is still a broadcast strategy, in view of Lemma 3. However, in this new strategy, there is one agent less in 3 Centralized convergecast and broadcast on lines

A = {a i | i < k and a i reaches b k+1 } ∪ {a i | i > k and a i reaches b k-1 } than in A,

Centralized convergecast on lines

In this section we consider the centralized convergecast problem for lines. We give an optimal, linear-time, deterministic centralized algorithm, computing the optimal amount of power needed to solve convergecast for line networks and we provide a regular convergecast strategy for this amount of power. As the algorithm is quite involved, we start by observing some properties of the optimal strategies.

Properties of a convergecast strategy

In the following, we only consider regular convergecast strategies. Note that a regular convergecast strategy is fully determined by the value of P and by the partition of the agents into the two sets LR and RL. For each agent a i ∈ LR (resp. a i ∈ RL), we denote f i by Reach c LR (i, P ) (resp. Reach c RL (i, P )). Observe that Reach c LR (i, P ) is the rightmost point on the line to which the set of i agents at initial positions P os[1 : i], each having power P , may transport their total information. Similarly, Reach c RL (i, P ) is the leftmost such point for agents at positions P os[i : n].

Lemma 2 permits to construct a linear-time decision procedure verifying if a given amount P of battery power is sufficient to design a convergecast strategy for a given configuration P os[1 : n] of agents. We first compute two lists Reach c LR (i, P ), for 1 ≤ i ≤ n and Reach c RL (i, P ), for 1 ≤ i ≤ n. Then we scan them to determine if there exists an index j, such that Reach c LR (j, P ) ≥ Reach c RL (j + 1, P ). In such a case, we set LR = {a r | r ≤ j} and RL = {a r | r > j} and we apply Lemma 2 to obtain a regular convergecast strategy where agents a j and a j+1 meet and exchange their information which at this time is the entire initial information of the set of agents. If there is no such index j, no convergecast strategy is possible. This implies Corollary 1. In O(n) time we can decide if a configuration of n agents on the line, each having a given maximal power P , can perform convergecast.

The remaining lemmas of this subsection bring up observations needed to construct an algorithm finding the optimal power P c OP T and designing an optimal convergecast strategy. Note that if the agents are not given enough power, then it can happen that some agent a p may never learn the information from a 1 (resp. from a n ). In this case, a p cannot belong to LR (resp. RL). We denote by Act c LR (p) the minimum amount of power needed to ensure that a p can learn the information from

a 1 : if p > 0, Act c LR (p) = min{P | Reach c LR (p
(p + 1, P ) = P os[p]). For each p, let T H c LR (p) = min{P | Reach c LR (p, P ) = P os[p] + P } and T H c RL (p) = min{P | Reach c RL (p, P ) = P os[p] -P }. Clearly, T H c LR (1) = T H c RL (n) = 0.
The next lemma shows how to compute Reach c LR (q, P ) and Reach c RL (q, P ) if we know T H c LR (p) and T H c RL (p) for every agent p.

Lemma 5. Consider an amount of power P and an index q. If p = max{p ≤ q | T H c LR (p ) < P }, then Reach c LR (q, P ) = 2 q-p P os[p] + (2 q-p+1 -1)P -

q i=p+1 2 q-i P os[i]. Similarly, if p = min{p ≥ q | T H c RL (p ) < P }, then Reach c RL (q, P ) = 2 p-q P os[p] -(2 p-q+1 -1)P - p-1 i=q 2 i-q P os[i].
Proof. We prove the first statement of the lemma; the proof of the other statement is similar. We first show the following claim.

Claim. If for every

i ∈ [p + 1, q], P ≤ T H c LR (i), then
Reach c LR (q, P ) = 2 q-p Reach c LR (p, P ) + (2 q-p -1)P -

q i=p+1 2 q-i P os[i].
We prove the claim by induction on q-p. Note that since P ≤ T H c LR (q), Reach c LR (q, P ) = 2Reach c LR (q-1, P ) + P -P os [q]. Thus if q = p + 1, the statement holds. Suppose now that q > p + 1. Since q -1 > p, by the induction hypothesis, we have

Reach c LR (q -1, P ) = 2 q-1-p Reach c LR (p, P ) + (2 q-1-p -1)P - q-1 i=p+1 2 q-1-i P os[i].
Consequently, we have

Reach c LR (q, P ) = 2Reach c LR (q -1, P ) + P -P os[q] = 2 q-p Reach c LR (p, P ) + (2 q-p -2)P - q-1 i=p+1 2 q-i P os[i] + P -P os[q] = 2 q-p Reach c LR (p, P ) + (2 q-p -1)P - q i=p+1 2 q-i P os[i].
This concludes the proof of the claim.

If p = max{p ≤ q | T H c LR (p ) < P }, then for each p ∈ [p + 1, q], T H c LR (p ) ≥ P and Reach c LR (p, P ) = P os[p] + P . Consequently, Reach c
LR (q, P ) = 2 q-p P os[p] + (2 q-p+1 -1)P -q i=p+1

2 q-i P os[i].

In the following, we denote S c LR (p, q) = q i=p+1 2 q-i P os[i] and S c RL (p, q) = p-1 i=q 2 i-q P os[i].

Remark 2. For every p ≤ q ≤ r, we have S c LR (p, r) = 2 r-q S c LR (p, q) + S c LR (q, r).

We now show that for an optimal convergecast strategy, the last agent of LR and the first agent of RL meet at some point between their initial positions and that they need to use all the available power to meet. Lemma 6. Suppose there exists an optimal convergecast strategy for a configuration P os[1 : n], where the maximum power used by an agent is P . Then, there exists an integer 1 ≤ p < n such that P os

[p] < Reach c LR (p, P ) = Reach c RL (p + 1, P ) < P os[p + 1]. Moreover, ∀q ≤ p, Act c LR (q) < P < T H c RL (q) and ∀q > p, Act c RL (q) < P < T H c LR (q).
Proof. In the proof we need the following claim.

Claim. For every One can show the second statement of the claim using similar arguments. This ends the proof of the claim.

Suppose we are given p and consider the partition of the agents into LR = {a q | q ≤ p} and RL = {a q | q > p}. Consider a regular convergecast strategy for this partition and where the maximum amount of power P used by an agent is minimized. We first show that Reach c LR (p, P ) = Reach c RL (p + 1, P ).

Let Q = max{Act c LR (p),
(p + 1, Q) = Reach c RL (p + 2, Q) = P os[p + 1] + Q, Reach c LR (p, Q) ≤ P os[p] + Q < P os[p + 1] + Q = Reach c RL (p + 1, Q) and thus, Reach c LR (p, Q) -Reach c RL (p + 1, Q) < 0.
By definition of a regular convergecast strategy, there exists . We now prove that for each q ∈ [1, p], Act c LR (q) < P . This follows from the fact that for each a q ∈ LR such that q > 1, we have Act c LR (q) > Act c LR (q -1). Consequently, for each q ∈ [1, p -1], Act c LR (q) > Act LR (p). For similar reasons, for each q ∈ [p + 1, n], Act c RL (q) < P . We finally prove that for each q ∈ [1, p], P < T H RL (q). Suppose there exists q such that P ≥ T H RL (q) and consider LR = {a r | r ≤ q -1} and RL = {a r | r ≥ q}. Since P > Act c LR (q), Reach c LR (q -1, P ) > P os[q] -P = Reach c RL (q, P ) and consequently, the first statement of the lemma implies that there exists P < P such that Reach c LR (q -1, P ) > Reach c RL (q, P ). This implies that P is not the optimal value needed to solve convergecast. This contradiction implies that for each q ∈ [1, p], P < T H RL (q).

Q such that Reach c LR (p, Q ) -Reach c RL (p + 1, Q ) ≥ 0. Consequently, since the difference Reach c LR (p, •) -Reach c RL (p + 1, •) is a continuous increasing function on [Q, +∞), there exists a unique Q < P ≤ Q such that Reach c LR (p, P ) = Reach c RL (p +
For similar reasons, for each q ∈ [p + 1, n], P < T H LR (q).

A linear algorithm to compute the optimal power needed for convergecast

We first sketch a suboptimal but much easier algorithm and later present and analyze in detail a more involved linear-time solution to our problem. First, we need to compute the functions Reach ). The following result shows that the optimal power needed for convergecast on the line can in fact be computed in linear time.

Theorem 1. In O(n) time it is possible to compute the optimal power needed to achieve convergecast on the line for configuration P os[1 : n] and to compute the optimal convergecast strategy.

We first explain how to compute a stack of couples (p, T H c LR (p)) that we can subsequently use to calculate Reach c LR (p, P ) for any given P . Then, we present a linear algorithm that computes the value needed to solve convergecast when the last index r ∈ LR is provided: given an index r, we compute the optimal power needed to solve convergecast assuming that LR = {a q | q ≤ r} and RL = {a q | q > r}. Finally, we explain how to use techniques introduced in the two previous algorithms in order to compute the optimal power needed to solve convergecast.

Computing the threshold values. In order to describe explicitly the function Reach c LR (q, •), we need to identify the indices p such that for every r ∈ [p + 1, q], we have T H c LR (r) > T H c LR (p). They correspond to the breakpoints at which the slopes of the piecewise linear function Reach c LR (q, •) change. Indeed, if we are given such an index p, then for every P comprised between T H c LR (p) and min{T H c LR (r) | p < r ≤ q}, we have Reach c LR (q, P ) = 2 q-p P os[p] + (2 q-p+1 -1)P -S c LR (p, q). We denote by X LR (q) this set of indices {p ≤ q | ∀r ∈ [p + 1, q], T H c LR (r) > T H c LR (p)}. In particular, if we want to compute T H c LR (q + 1), we just need to find p = max{r ≤ q | Reach c LR (q, T H c LR (r)) < P os[q + 1]}, and then T H c LR (q + 1) is the value of power P such that 2 q-p P os[p] + (2 q-p+1 -1)P -S c LR (p, q) = P os[q + 1]. Moreover, by the choice of p, we have X LR (q + 1) = {r ∈ X LR (q) | r ≤ p} ∪ {q + 1}.

Using these remarks, the function ThresholdLR, with an input index r of an agent, returns a stack TH c LR containing couples (p, P ) such that p ∈ X LR (r) and P = T H c LR (p). Note that in the stack TH c LR , the elements (p, P ) are sorted along both components, the largest being on the top of the stack.

The function is described as follows. Initially, the stack TH c LR contains only the couple (1, T H c LR (1)). At each iteration, given the stack corresponding to the index q, in order to compute the stack for the index q + 1, we first pop out all elements (p, P ) such that Reach c LR (q, P ) > P os[q + 1]. After that, the integer p needed to compute T H c LR (q + 1) is located on the top of the stack. Finally, the couple (q + 1, T H c LR (q + 1)) is pushed on the stack before we proceed with the subsequent index q. The function returns the stack TH c LR corresponding to the index r.

Below, we give the pseudo-code of the function.

Function ThresholdLR(array P os[1 : n] of real; r:integer):stack

TH c LR = empty_stack; push (TH c
LR ,(1, 0)); for q = 1 to r -1 do (p, P ) = pop(TH c LR ); /* p = q and P = T H c LR (p) */ while 2 q-p * P os[p] + (2 q-p+1 -1) * P -S c LR (p, q) ≥ P os[q + 1] do (p, P ) = pop(TH c LR ); // while Reach c LR (q, P ) ≥ P os[q + 1] we consider the next element in TH c LR push (TH c LR ,(p, P )); Q = (2 q-p * P os[p] -P os[q + 1] -S c LR (p, q))/(2 q-p+1 -1); /* Q is the solution of Reach c LR (q, P ) = P os[q + 1] */ push (TH c LR ,(q

+ 1, Q)); return (TH c LR );
The number of stack operations performed during the execution of this function is O(r). However, in order to obtain a linear number of arithmetic operations, we need to be able to compute 2 q-p and S c LR (p, q) in constant time.

In order to compute 2 q-p efficiently, we can store the values of 2 i , i ∈ [1, n-1] in an auxiliary array, that we have precomputed in O(n) time. We cannot precompute all values of S c LR (p, q) since this requires calculating Θ(n 2 ) values. However, from Remark 2, we know that

S c LR (p, q) = S c LR (1, q) -2 q-p S c LR (1, p). Consequently, it is enough to precompute S c LR (1, i) for each i ∈ [2, n]. Since S c LR (1, i + 1) = 2S c LR (1, i) + P os[i + 1],
this can be done using O(n) arithmetic operations.

Similarly, we can define the function ThresholdRL (array P os[1 : n] of real, r:integer):stack that returns a stack TH c RL containing all pairs (q, T H c RL (q)) such that for every p ∈ [r, q -1], we have

T H c RL (p) > T H c RL (q).
Computing the optimal power when LR and RL are known. To facilitate further reading, we first show how to compute the optimal power P c OP T , if the sets LR and RL are known. This will be done by function OptimalAtIndex which will be not used in our final algorithm to compute optimal power but whose role is to explain some of the techniques under these additional assumptions.

Suppose that we are given an agent index r and we want to compute the optimal power needed to solve convergecast when LR = {a p | p ≤ r} and RL = {a q | q > r}. From Lemma 6, we know that there exists a unique value P c OP T such that Reach c LR (r, P c OP T ) = Reach c RL (r + 1, P c OP T ). As previously, by Lemma 5, we know that the value of Reach c LR (r, P c OP T ) depends on p = max{p ≤ r | T H c LR (p ) < P c OP T }. Similarly, Reach c RL (r + 1, P c OP T ) depends on q = max{q ≥ r + 1 | T H c RL (q ) < P c OP T }. If we are given the values of p and q, then P c OP T is the unique value of P such that 2 r-p P os[p] -(2 r-p+1 -1)P -S c LR (p, r) = 2 q-r-1 P os[q] -(2 q-r -1)P -S c RL (q, r + 1).

In Function OptimalAtIndex, we first use functions ThresholdLR and ThresholdRL to compute the two stacks TH c LR and TH c RL containing respectively {(p, T H c LR (p)) | p ∈ X LR (r)} and {(q, T H c RL (q)) | q ∈ X RL (r + 1)}. Then at each iteration, we consider the two elements (p, P LR ) and (q, P RL ) that are on top of both stacks. If P LR ≥ P RL (the other case is symmetric), we check whether Reach c LR (r, P LR ) ≥ Reach c RL (r + 1, P LR ). In this case, we have P > P c OP T , so we remove (p, P LR ) from the stack TH c LR and we proceed to the next iteration. If Reach c LR (r, P LR ) < Reach c RL (r + 1, P LR ), we know that P c OP T ≥ P LR ≥ P RL and we can compute the value of P c OP T using Lemma 5. Let Y LR (r, P ) denote {(p, T H c LR (p)) | p ∈ X LR (r) and T H c LR (p) < P } and Y RL (r + 1, P ) = {(q, T H c RL (q)) | q ∈ X RL (r + 1) and T H c RL (q) < P }. */ while 2 r-p P os[p] + (2 r-p+1 -1)P -S c LR (p, r) ≥ 2 q-r-1 P os[q] -(2 q-r -1)P -S c RL (q, r + 1) do /* While Reach c LR (r, P ) ≥ Reach c RL (r + 1, P ) do */ if PLR ≥ PRL then (p, PLR) = pop(TH c LR ); else (q, PRL) = pop(TH c RL ); P = max{PLR, PRL};

P c OP T = (2 q-r-1 P os[q] -S c RL (q, r + 1) -2 r-p P os[p] + S c LR (p, r))/(2 r-p+1 + 2 q-r -2); /* P c OP T is the solution of Reach c LR (r, P c OP T ) = Reach c RL (r + 1, P c OP T ) */ return (P c OP T );
Computing the optimal power for convergecast. We now explain how to compute the optimal amount of power needed to achieve convergecast using a linear number of operations. Notice that Function Optimal-AtIndex does it only provided the partition of the agents in LR and RL. Let P <r be the optimal value needed to solve convergecast when max{s | a s ∈ LR} < r, i.e., when the two agents whose meeting results in merging the entire information are a i and a i+1 for some i < r. If Reach c LR (r, P <r ) ≤ Reach c RL (r + 1, P <r ), then P <r+1 = P <r . However, if Reach c LR (r, P <r ) > Reach c RL (r + 1, P <r ), then P <r+1 < P <r and P <r+1 is the unique value of P such that Reach c LR (r, P ) = Reach c RL (r+1, P ). This corresponds to the value returned by function OptimalAtIndex (P os, r).

The general idea of Function ComputeOptimal is to iteratively compute the value of P <r . If we need a linear time algorithm, we cannot call repeatedly the function OptimalAtIndex. However, from Remark 3, in order to compute P <r+1 when P <r+1 ≤ P <r , it is enough to know Y LR (r, P <r ) and Y RL (r + 1, P <r ). If we know Y LR (r, P <r ) and Y RL (r + 1, P <r ), then we can use the same algorithm as in OptimalAtIndex in order to compute P <r+1 . Moreover, from Remark 3, we also get Y LR (r, P <r+1 ) and Y RL (r + 1, P <r+1 ) when we compute P <r+1 .

Before proceeding to the next iteration, we need to compute Y LR (r + Notice that the partition of agents into sets LR and RL is given by the value of index r when P c OP T is returned by Function ComputeOptimal. Since an optimal regular convergecast strategy is fully determined by the value of P c OP T and by the partition of the agents into the sets LR and RL, Function ComputeOptimal also yields an optimal convergecast strategy. Hence, this concludes the proof of Theorem 1.

Function ComputeOptimal(array P os[1 : n] of real):real

TH c LR = empty_stack; TH c RL = ThresholdRL(P os); (q, PRL) = pop(TH c RL ); P c OP T = PRL; /* q = 1, PRL = T H c RL (1) */ (q, PRL) = pop(TH c RL ); p = 1;PLR = 0; for r = 1 to n -1 do /* P c OP T = P<r ≥ PLR, PRL */ if 2 r-p P os[p] + (2 r-p+1 -1)P c OP T -S c LR (p, r) > 2 q-r-1 P os[q] -(2 q-r -1)P c OP T -S c RL (q, r + 1) then /* If Reach c LR (r, P c OP T ) > Reach c RL (r + 1, P c OP T ) then P c OP T is larger than the value needed to solve convergecast at position r. We apply now the same algorithm as in function OptimalAtIndex.

*/ P = max{PLR, PRL}; while 2 r-p P os[p] + (2 r-p+1 -1)P -S c LR (p, r) ≥ 2 q-r-1 P os[q] -(2 q-r -1)P -S c RL (q, r + 1) do if PLR ≥ PRL then (p, PLR) = pop(TH c LR ); else (q, PRL) = pop(TH c RL ); P = max{PLR, PRL};

P c OP T = (2 q-r-1 P os[q] -S c RL (q, r + 1) -2 r-p P os[p] + S c LR (p, r))/(2 r-p+1 + 2 q-r - 2

Centralized broadcast on lines

In this section we consider the centralized broadcast problem for lines. We give an optimal, linear-time, deterministic centralized algorithm, computing the optimal amount of power needed to solve broadcast for line networks and computing an optimal broadcast strategy.

Properties of a broadcast strategy

In the following, we only consider regular broadcast strategies. Note that a regular broadcast strategy is fully determined by the value of P and by the two possible values of b k for the source agent

a k (b k = b k-1 or b k = b k+1 ).
Let LR = {a 1 , a 2 , . . . , a k-1 } and RL = {a k+1 , a k+2 , . . . , a n }. (Note that we slightly abuse notation by using the same names LR and RL for subsets of agents as in convergecast.) For each agent a i ∈ LR (resp. a i ∈ RL ), we denote b i by Reach b LR (i, P ) (resp. Reach b RL (i, P )). Observe that Reach b LR (i, P ) is the rightmost point on the line from which the set of i agents at initial positions P os[1 : i], each having power P , may pick the information and bring it back to a 1 . Similarly, Reach b RL (i, P ) is the leftmost point from which the agents at positions P os[i : n] may pick the information and bring it back to a n . Lemma 4 permits to construct a linear-time decision procedure verifying if a given amount P of battery power is sufficient to design a broadcast strategy for a given configuration P os are less or equal than P . If one of the inequalities is true then there is a broadcast strategy. Otherwise, broadcast is not possible. This implies Corollary 2. In O(n) time we can decide if a configuration P os[1 : n] of n agents on the line, each having a given maximal power P , can perform broadcast for a given source agent.

Note that if the agents are not given enough power, then it can happen that some agent a p , 1 ≤ p ≤ k (resp. k ≤ q ≤ n) cannot reach the point Reach b LR (p -1, P ) (resp. Reach b RL (q + 1, P )). We denote by Act b LR (p) (resp. Act b RL (q)) the minimum amount of power P we have to give the agents to ensure that a p (resp. a q ) can reach Reach b LR (p -1, P ) (resp. Reach b RL (q + 1, P )). We have : Analogously, for an index q ∈ {k, k + 1, . . . , n}, and an amount of power P ≥ Act b RL (q), we have Reach b RL (q, P ) = Reach b RL (q, Act b RL (q)) -P + Act b RL (q).

Act b LR (1) = Act b RL (n) = 0 and if 2 ≤ p ≤ k, Act b LR (p) = min{P | Reach b LR (p -1, P ) ≥ P os[p] -P }. Similarly, if k ≤ q ≤ n -1, we have Act b RL (q) = min{P | Reach b RL (q +
Proof. Observe that for P = Act b LR (p), we have:

Reach b LR (p, Act b LR (p)) = Reach b LR (p -1, Act b LR (p -1)) -Act b LR (p -1) + P os[p] 2 + Act b LR (p).
Hence we have:

Reach b LR (p, P ) = Reach b LR (p, Act b LR (p)) + P -Act b LR (p)
. This concludes the proof by induction. Similarly, we can show by induction on q that for any ∈ {k, k + 1, . . . , n} and an amount of power

P ≥ Act b LR (p), we have Reach b LR (q, P ) = Reach b LR (q, Act b LR (q)) -P + Act b LR (q).

A linear algorithm to compute the optimal power needed for broadcast

In this section, we prove the following theorem.

Theorem 2. In O(n) time it is possible to compute the optimal power needed to achieve broadcast for a configuration P os[1 : n] of n agents on the line for any source agent and to compute an optimal broadcast strategy.

Function OptimalBroadcast(array P os

Act b RL (n) = 0, Reach b RL (n, Act b RL (n)) = P os[n], q = n; while q > k + 1 do while (q > k + 1) and (P os[q -1] + Act b RL (q) ≥ Reach b RL (q, Act b RL (q)) do Act b RL (q -1) = Act b RL (q); Reach b RL (q -1, Act b RL (q -1)) = (P os[q -1] -Act b RL (q -1) + Reach b RL (q -1, Act b RL (q -1))/2; q = q -1; if (q > k + 1) and (p = k -1 or δLR < δLR) then δRL = (Reach b RL (q, Act b RL (q)) -Act b RL (q) -P os[q -1])/2; Act b RL (q -1) = Act b RL (q); Reach b RL (q -1, Act b RL (q -1)) = P os[q -1]; q = q -1; P = max(Act b LR (k -1), Act b RL (k + 1)); if Act b LR (k -1) > Act b RL (k + 1)) then X b LR = Reach b LR (k -1, Act b LR (k -1)); Y b RL = Reach b RL (k + 1, Act b RL (k + 1)) + Act b LR (k -1) -Act b RL (k + 1)); else X b LR = Reach b LR (k -1, Act b LR (k -1)) -Act b RL (k + 1) + Act b LR (k -1)); Y b RL = Reach b RL (k + 1, Act b RL (k + 1)); if P os[k] ≤ X b LR then δ = (Y b RL -P os[k] -P )/2; if X b LR < P os[k] < Y b RL then δ = (min(P os[k] -X b LR , Y b RL -P os[k]) + (Y b RL -X b LR ) -P )/2; if Y b RL ≤ P os[k] then δ = (P os[k] -X b LR -P )/2; return P + max(0, δ)
Proof. We formulate Function OptimalBroadcast which computes in linear time the optimal power for the broadcast in the line.

In order to compute this value, Function OptimalBroadcast first computes the minimal amount of power Q such that all agents in LR ∪ RL are activated, i.e., Q = max(Act b LR (k -1), Act b RL (k + 1)). In order to compute Q, the function iteratively increases the power sufficient to activate all agents in LR. Then, it does the same with agents in RL. The function computes iteratively for each agent a i from a 1 to a k-1 in LR (respectively from a n to a k+1 in RL), the value Act b LR (i) (respectively Act b RL (i)) and the value

Reach b LR (i, Act b LR (i)) (respectively Reach b RL (i, Act b RL (i))
). Once Q is known, the function computes the minimal amount of power P ≥ Q that enables the agent a k to reach Reach b LR (k-1, P ) and Reach b RL (k+1, P ). This will be proved to be the minimal power to accomplish broadcast.

Notice that in order to accomplish broadcast, agent a k-1 must be able to reach Reach b LR (k -2, Act b LR (k -2)). Hence the optimal value P b OP T of power sufficient to accomplish broadcast must be at least Act b LR (k -1). Similarly, P b OP T must be at least Act b RL (k + 1). Hence, we will first prove that the values of Reach b LR (p, Act b LR (p)), Act b LR (p), Reach b RL (q, Act b RL (q)) and Act b RL (q) are correctly computed for 1 ≤ p < k and k < q ≤ n.

We only prove that the values of Reach b LR (p, Act b LR (p)) and Act b LR (p) are correctly computed for 1 ≤ p < k, as the proof that Reach b RL (q, Act b RL (q)) and Act b RL (q) are correctly computed for k < q ≤ n is similar. The proof is by induction on p. RL (k + 1, P ), we conclude that P is the optimal value of power to achieve broadcast by a regular strategy. In view of Lemma 4, this concludes the proof that P is the optimal value of power to achieve broadcast. The complexity O(n) of the function is straightforward by its formulation.

Since a regular broadcast strategy is fully determined by the value of P and by the two possible values of b k for the source agent a k (b k = b k-1 or b k = b k+1 ), computing the optimal power P yields an optimal broadcast strategy. This concludes the proof of Theorem 2.

Centralized convergecast and broadcast on trees and graphs

We start the section by showing that for arbitrary trees the centralized convergecast problem and the centralized broadcast problem are substantially harder than on lines.

A configuration for convergecast on arbitrary graphs is a couple (G, A) where G is a n-node weighted graph representing the network and A of size k is the set of the starting nodes of the agents. A configuration for broadcast additionally specifies the starting node of the source agent. We consider the centralized convergecast decision problem and the broadcast decision problem formalized as follows.

Centralized convergecast decision problem

Instance: a configuration (G, A) and a real P . Question: Is there a convergecast strategy for (G, A), in which each agent uses at most P battery power ?

Centralized broadcast decision problem

Instance: a configuration (G, A) with a specified source agent and a real P . Question: Is there a broadcast strategy for (G, A) with the specified source agent, in which each agent uses at most P battery power ?

We will prove that both these problems are strongly NP-complete. In order to do this, we consider star configurations, i.e., configurations (G, A) in which G is a star, i.e., a tree of diameter 2. We define a class of strategies in a star called simple that consist of the following two phases :

• The strategy starts with a gathering phase lasting time P , in which each agent uses all its available power to move towards the center of the star and then waits until time P . The agents that have used all their power during this phase without reaching the center are called depleted.

• In the second phase, the agents does not move past depleted agents, i.e., never enter the segment between a leaf and a depleted agent.

The following lemma shows that it is enough to consider simple strategies for convergecast and broadcast.

Lemma 8. If there exists a convergecast strategy (respectively a broadcast strategy) in a star using power P , then there exists a simple convergecast strategy (respectively a simple broadcast strategy) using power P .

Proof. Let S be a convergecast or a broadcast strategy. We construct a simple strategy S as follows. In S , each agent moves towards the center of the star until it has used all its battery power or has reached the center of the star. This gathering phase lasts from time 0 to time P . If an agent has not reached the center in strategy S, then it stops forever in S . Otherwise, consider time t at which it arrives at the center in S.

Then, in strategy S , the agent executes at time t + P each movement performed at time t ≥ t in strategy S. However, if a movement of an agent would result in the agent moving past a depleted agent from time r to r in S, then in strategy S the agent waits at the position of the depleted agent instead of moving past it. By construction, S is a simple strategy. Observe that in strategy S , the non-depleted agents share all their information at the center of the star at time P . Since two depleted agents cannot meet, it remains to show that when a non-depleted agent b meets a depleted agent a at time t in strategy S, they meet at time t + P in S . The final position of agent a is not farther from the center in S than in S. Hence, any agent b that meets agent a at time t is at the new position of a in S at time t + P . Hence, the meeting between a and b occurs in S as well. If S was a convergecast strategy (respectively a broadcast strategy) then S is a simple convergecast strategy (respectively a simple broadcast strategy).

Theorem 3. The centralized convergecast decision problem and the centralized broadcast decision problem are strongly NP-complete for trees.

The proof of Theorem 3 is split into three lemmas. We first show that the centralized convergecast decision problem is strongly NP-hard, then that the centralized broadcast decision problem is strongly NP-hard, and finally that both problems are in NP.

Lemma 9. The centralized convergecast decision problem is strongly NP-hard for trees.

Proof. We construct a polynomial-time many to one reduction from the following strongly NP-Complete problem [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF].

3-Partition problem

Instance: a multiset S of 3m positive integers x i such that for

1 ≤ i ≤ 3m, R/4 < x i < R/2 with R = 3m i=1 xi m . Question: Can S be partitioned into m disjoint sets S 1 , S 2 , . . . , S m of size 3, such that x∈Sj x = R for 1 ≤ j ≤ m ?
We construct an instance (G, U ) of the centralized convergecast problem from an instance of 3-Partition as follows. The graph G is a star with 4m + 2 leaves and U is the set of leaves of G. Hence, there are 4m + 2 agents, each located at a leaf of the star. We consider a partition of the set of agents into three subsets: A, B and C. The subset A = {a i | 1 ≤ i ≤ m + 1} contains m + 1 agents. The leaves containing these agents are incident to an edge of weight 1. The subset B = {b i | 1 ≤ i ≤ 3m} contains 3m agents. For 1 ≤ i ≤ 3m, the weight of the edge incident to the leaf containing agent b i is 2R + 1 + x i . The subset C = {c} contains one agent. The leaf containing agent c is incident to an edge of weight 4R + 1. Figure 1 depicts the star obtained in this way. The battery power P allocated to each agent is equal to 2R + 1. The construction can be done in polynomial time. We show that the constructed instance of the centralized convergecast problem gives answer yes if and only if the original instance of 3-partition gives answer yes. First, assume that there exists a solution S 1 , S 2 , . . . , S m for the instance of the 3-partition problem. We show that the agents can solve the corresponding instance of the centralized convergecast problem using the following strategy. Agent c moves at distance 2R from the center and for each 1 ≤ i ≤ 3m, agent b i moves at distance x i from the center. At this point, all these agents have used all their battery power. Each agent in A moves to the center of the star. For 1 ≤ i ≤ m and for each of the three agents b j such that x j ∈ S i , agent a i moves to meet b j and goes back to the center of the star. The cost of this movement is 2 xj ∈Si = 2R, which is exactly the remaining battery power of agent a i . Observe that since agents in A have met all agents in B, agents in A, located at the center of the star, have the information of all agents except agent c. Then agent a m+1 moves to meet agent c. Agents a m+1 and c have the information of all the agents. Hence, this is a solution of the instance of the centralized convergecast problem. Now assume that there exists a solution (strategy) to the convergecast problem. By Lemma 8, we can assume that the convergecast strategy is simple. Consider the star G after the gathering phase of the simple strategy. Each agent in A is at the center of the star. For 1 ≤ i ≤ m + 1, the agent a i has the remaining power of 2R. For 1 ≤ i ≤ 3m, the agent b i is at distance x i from the center of the star and agent c is at distance 2R from the center. Since the agents in A are the only agents with remaining battery power, they must move to collect the information of agents in B ∪C. We call this phase the collecting phase. Observe that since agent c is at distance 2R from the center, it is impossible for agents in A to transport this information. Indeed, when an agent reaches c, it has used all its battery power. Hence, the entire information must be collected at the position of c. In order to collect the information, agents in A must go to the position of each agent in B and transport the information of these agents to the center. The total cost to move these information is at least twice the sum of the distances between each agent in B and the center. This is equal to 2 i=1 3mx i = 2Rm. Then, this information must be moved to the position of c. This costs at least 2R. Hence, the total cost of collecting information after the gathering phase is at least 2R(m + 1). The amount of power available to the agents for the collecting phase is equal to the amount of power needed to collect the information, since there are m + 1 agents each having power 2R. This means that during the collecting phase, for 1 ≤ j ≤ 3m, agents cannot collectively use a power larger than 2x i to collect the information of b i .

set A of 3m agents . . . . . . 1 2 R + 1 + x 1 2 R + 1 + x3 m 2 R + 1 + x 2 1 1 set B of m + 1 agents 1 agent set C of a 1 a 2 a m+1 b 1 b 2 b 3m c 4R + 1 u
b i moves at distance x i from the center. At this point, all these agents have used all their battery power. Each agent in A moves to the center of the star. Hence, each agent a i obtains the information of a 1 . For 1 ≤ i ≤ m and each of the three agents b j such that x j ∈ S i , agent a i moves to meet b j and goes back to the center of the star. The cost of this movement is 2 xj ∈Si = 2R. Observe that since agents in A have met all agents in B, all agents except those in C have the information of a 1 . Each agent a i moves to meet agent c i . Each agent c i obtains the information of a 1 . Hence, this is a solution to the instance of the centralized broadcast problem. Now assume that there is a solution (strategy) to the broadcast problem. By Lemma 8, we can assume that the centralized broadcast strategy is simple. Consider the star G after the gathering phase of the simple strategy. Each agent in A is at the center of the star. For 1 ≤ i ≤ m, the agent a i has the remaining power of 4R. For 1 ≤ i ≤ 3m, the agent b i is at distance x i from the center of the star. For 1 ≤ i ≤ m, agent c i is at distance 2R from the center. Since the agents in A are the only agents with remaining battery power, they must move to give the information to agents in B ∪ C. Observe that since each agent c i is at distance 2R from the center, an agent in A that moves to meet an agent c i has not enough power to meet another depleted agent afterwards. Hence, each agent a i must meet exactly one agent c j . Without loss of generality, we can assume that each agent a i meets c i . Before agents in A meet agents in C, they must meet agents in B. The total cost to give the information to all agents in B is at least twice the sum of the distances between each agent in B and the center. This is equal to 2 i=1 3mx i = 2Rm. The total cost to give the information to agents in C is 2Rm. The amount of power available to the agents in A is 4Rm, which is exactly the power needed for broadcast. Assume for the sake of contradiction that two or more agents in A enter the same edge incident to the leaf of an agent b i . In this case, one of the agents must meet b i . This costs the agent 2x i and other agents have used some power to enter this edge. This gives a contradiction because the total cost is more than the available power. Thus, we can assume that each agent b j meets exactly one agent a i . Let S 1 , S 2 , . . . , S m be the partition of S defined by S i = {x j | b j met a i }, for each 1 ≤ i ≤ m. We have 2 x∈Si x ≤ 2R since the total power that agents in A can use to meet agents in B is at most 2Rm. The power needed to give information to agents in B is 2mR which is exactly equal to the combined power available to agents in A. This means that each agent in A must use all its power to meet agents in B and 2 x∈Si x = 2R. Hence, S 1 , S 2 , . . . , S m is a solution to the instance of 3-partition.

Lemma 11. The centralized convergecast decision problem and the centralized broadcast decision problem are in NP.

Proof. We consider the verifier-based definition of NP. Consider the strategy S of the agents for an instance of the centralized convergecast or centralized broadcast problems. We construct the certificate for the instance as follows. We say that a meeting of two or more agents is useful if at least one of the agents received a new piece of information during this meeting. Each agent participates in at most k -1 useful meetings where k is the number of agents. Hence, there are at most k(k -1) useful meetings. The certificate contains the list of all useful meetings in chronological order. For the i-th meeting, the certificate encodes the identities of the meeting agents and the location of the meeting: a node x i or an edge (u i , v i ) of the graph G. If the meeting has occurred on an edge, the certificate encodes a variable d i . The variable d i represents the distance between u i and the meeting point p i . If a previous meeting of number j has occurred on the same edge, the certificate encodes if d i < d j , or d i = d j or d i > d j . For each of the meeting agents, the certificate also encodes the node from which it has entered the edge (u i or v i ) just before the meeting and the node from which it exits the edge just after the meeting. We consider the strategy S defined as follows. For each useful meeting in chronological order, the meeting agents move to the meeting location following a shortest path from their previous position. If the meeting occurs on an edge, the meeting agents enter and exit the edge using the node encoded in the certificate. S is a convergecast strategy since each time an agent has collected a new piece of information in S, it collects the same information during the corresponding meeting in S . Moreover, the agents use at most as much power in S as in S since they move to the same meeting points using shortest paths. The verifier simulates the strategy S defined by the certificate. The verifier first checks that all the agents possess the entire information at the end of the algorithm. This can be done in polynomial time. Then, the verifier computes the distance traveled by each agent. These distances are linear sums of variables d i with 1 ≤ i ≤ k(k -1) and of a constant. Finding an assignment of the variables, such that the distance traveled by each agent is less or equal than P , can be done in polynomial time using linear programming. Thus, the certificate can be verified in polynomial time.

Theorem 3 is a direct consequence of Lemmas 9, 10 and 11. Since both decision problems concerning convergecast and broadcast are NP-hard for the class of trees, the same is true for their optimization counterparts, i.e., computing the smallest amount of power that is sufficient to achieve convergecast or broadcast. In spite of that, we will show how to obtain, in polynomial time, a 2-approximation of the power needed to achieve centralized convergecast on arbitrary graphs and a 4-approximation of the power needed to achieve centralized broadcast on arbitrary graphs.

Let D(G, A) = max ∅ X A {min x∈X,y∈A\X {d G (x, y)}}, where d G (x, y) is the distance between x and y in G. The following proposition shows a relation between D(G, A) and the above optimal power values.

Proposition 1. Consider a configuration (G, A) for convergecast and a configuration (G, A) with a specified source agent for broadcast. Then D(G, A) ≤ 2P c OP T and D(G, A) ≤ 2P b OP T for any source agent in (G, A). Proof. We prove the proposition for the case of convergecast. The proof for broadcast is similar. Suppose, by contradiction, that there is a partition of A into X and A \ X such that for each x ∈ X and y ∈ A \ X the distance between x and y is greater than 2P c OP T . It means that no agents in X can meet an agent in A \ X using power P c OP T . This contradicts the fact that there is a convergecast strategy in G using battery power P c OP T . Hence, for every partition of A into X and A \ X, there exist agents x ∈ X and y ∈ A \ X that are at distance at most 2P c OP T .

In view of Proposition 1, the following theorem shows that the convergecast problem has a polynomialtime 2-approximation.

Theorem 4. Consider a configuration (G, A).

There is a polynomial algorithm computing a convergecast strategy in which each agent uses power D(G, A).

Proof. We formulate algorithm KnownGraph which produces the desired convergecast strategy. The parameters of the algorithm are the graph G and the nodes corresponding to the initial positions of agents (stored in A[1 : k]). Let (u i , v i ) be the nodes chosen at the i-th iteration of the first loop and let V i be the value of V at the end of the i-th iteration. We set u 0 = A [START_REF] Albers | Energy-efficient algorithms[END_REF] and V 0 = {v 0 }. We show, by induction, that at the start of the i-th iteration of the second loop, agents that started in V k-i hold collectively all the information. It is clearly true for i = 1. Assume by induction that it is true for i. The agent that started at v k-i moves to node u k-i = v k-j for some j > i, during the i-th iteration of the second loop. After this move, the agent that started at v k-j has the information of the agent that started at v k-i . Agents in V k-(i+1) collectively hold all the information. Hence, the property is true for i + 1 and this concludes the argument by induction. At the end of the algorithm, the agent at A [START_REF] Albers | Energy-efficient algorithms[END_REF] has all the information since V 0 = {A [START_REF] Albers | Energy-efficient algorithms[END_REF]}.

Let A be the set of agents. Consider the partition of A into sets V i-1 and A \ V i-1 . We have

d(u i , v i ) ≤ D(G, A) since (u i , v i ) is the couple (u, v) ∈ V i-1 × (A \ V i-1
) such that d(u, v) is minimal. Hence, no agent will traverse distance larger than 2P c OP T by Proposition 1. In O(n 3 ) time, it is possible to precompute all shortest paths between u and v for all u, v ∈ A. Each iteration of the first repeat loop can be computed in O(n 2 ) time and there are k -1 such iterations where k ≤ n is the number of agents. Hence, executing the first repeat loop takes time O(n 3 ). The execution the second repeat loop takes time O(n 2 ). Hence, the overall complexity of the algorithm is O(n 3 ).

The above theorem gives the following corollary for the broadcast problem on arbitrary graphs.

Corollary 3. The broadcast problem on arbitrary graphs has a polynomial-time 4-approximation.

Proof. Let (G, A) be a configuration with an arbitrary source agent a. By Theorem 4, there is a convergecast strategy S for (G, A) using power at most D(G, A) that can be computed in polynomial time. Let b be the agent that collects all information upon completion of this strategy. Consider the strategy S which consists of performing the reverse of all moves of S in the reverse order. The strategy S is a broadcast strategy for source agent b. Hence, the strategy S followed by S is a broadcast strategy for source agent a. The required power is at most 2D(G, A) which gives a 4-approximation of the broadcast problem in view of Proposition 1.

Distributed convergecast and broadcast on trees

In this section, we consider the convergecast and the broadcast problem in the distributed setting. As explained in the introduction, we consider weighted trees with agents at every leaf. In view of Proposition 1, the following theorem implies that there exists a 2-competitive distributed algorithm for the convergecast problem on trees.

Theorem 5. Consider a configuration (T, A) where T is a tree and A contains all the leaves of T . There exists a distributed convergecast algorithm in which each agent uses power at most D(T, A).

Proof. The idea behind the algorithm is similar to the saturation technique used for message passing systems (see chapter 2.6.1 of [START_REF] Santoro | Design and analysis of distributed algorithms[END_REF]). Each agent starting at a leaf moves until it reaches the neighbor of its starting position. When an agent reaches a node, it waits until an agent has arrived from each incident edge except one. When this happens, the agent with the most remaining power moves via the edge from which no agent has arrived. One can show that each agent will not move more than D(T, A) and thus twice P c OP T by Proposition 1. At some point, the saturation occurs, i.e., two agents meet inside an edge or agents meet at a node coming from all incident edges. At this point, the convergecast is achieved.

The pseudocode of the algorithm (executed distributedly by all agents) is the following.

Algorithm 2: UnknownTree collecting = false; while collecting = false do Wait until there is at most one port unused by an agent incoming at the current node; if all ports of the current node were used by incoming agents then collecting = true if the agent has used less power than any other agent present at the node and collecting = false then Move through the unused incoming port until you meet another agent or reach a node; else collecting = true; if the agent is inside an edge then collecting = true;

First, we show that if each agent executes Algorithm 2 then, eventually, one agent will hold all the information. Consider an agent a executing the algorithm. Let T a (t) be the subtree rooted at the last visited node and containing all nodes accessible from the current position of a by shortest paths containing a non-null part of the last edge traversed by agent a. Hence, when a enters a new node u, u is added to T a . We show by induction on the number of nodes of T a that a has the initial information of every agent that started at a node of T a . For |T a | = 1, this is true since a is the only agent that started in T a . The size of T a grows only when a enters or exits some node v. When a enters a new node v, we show that any agent that started at v did not move yet. Assume by contradiction that there is an agent b that started at v and has moved before the arrival of a. It means that agents have arrived from all but one edge incident to v. In that case, agent b follows the edge from which no agent has arrived. Hence, the only possible edge that agent b can follow is the edge taken by agent a to arrive at v. This leads to a contradiction since agents a and b must have met inside the edge and agent a would have stopped before reaching v.

When an agent a moves from a node v of degree δ, there were δ -1 agents b 1 , b 2 , . . . , b δ-1 that have arrived at v before. By the induction hypothesis, each agent b i , for 1 ≤ i ≤ δ -1, has collected all the information from agents starting inside the subtree T bi . Since agent a moves in the only direction from which no agent has arrived, it has the information of every agent that started in

T a = T b1 ∪ T b2 ∪ • • • ∪ T b δ-1 .
This concludes the proof by induction.

Observe that for each 1 ≤ i ≤ k the tree T ai grows until either a i meets agents that have arrived from all incoming ports of its current position, or another agent a j with more power moves in a yet unexplored direction. In the latter case, T ai ⊆ T aj and the tree T aj will grow under the same conditions. Thus, ∪ k i=1 T ai will eventually be equal to T . This happens when either two agents u 1 , u 2 meet inside an edge or δ agents u 1 , u 2 , . . . , u δ meet at a node of degree δ. These agents have the entire information since

T u1 ∪ T u2 ∪ • • • ∪ T u δ = T (δ = 2 if
the meeting occurs on an edge).

It remains to show that the agents do not use more battery power than D(T, A). Let p be the point where some agent a has finished the execution of the algorithm (when the value of collecting becomes true for this agent) and let v be the last node visited by a before reaching p. Consider T a when a exited v. Agent a is the agent starting in T a for which the distance between its initial position and the node v was the smallest, since it was the agent that has used the least power when it arrived at v. Thus, the distance between the initial position of an agent in T a and an agent in G \ T a is less or equal than D(G, A). Hence we conclude that P ≤ D(T, A). By Property 1, we have that D(T, A) ≤ 2P c OP T and hence the algorithm is 2-competitive. Again in view of Proposition 1, the following corollary implies that there exists a 4-competitive distributed algorithm for the broadcast problem on trees.

Corollary 4. Consider a configuration (T, A) with a specified source agent, where T is a tree and A contains all the leaves of T . There exists a distributed broadcast algorithm in which each agent uses power at most 2D(T, A).

Proof. Let (T, A) be a configuration with a specified source agent a. All agents execute the following algorithm consisting of two phases. In the first phase, each agent executes algorithm UnknownTree from the proof of Theorem 5 to achieve convergecast. Suppose that B is the set of agents that get the total information at the end of the execution of this phase. All agents in B are aware of this fact. Agents in B start the second phase. We call them active agents. Each active agent backtracks to its initial position, by walking along the path reverse to the one used in phase 1. On its way, it activates all agents it meets and conveys all the information to each of them. The process continues until each agent is activated and is back at its initial position. At this time, all information and in particular information of the source agent a is known to all agents. The energy spent is at most 2D(T, A).

The following theorem shows that no distributed algorithm may offer a better competitive ratio than 2 for convergecast or for broadcast, even if we only consider line networks. Theorem 6. Consider any δ > 0, and any value of power P . There exists an integer n and a configuration P os[1 : n] of n agents on the line such that :

• there exists a centralized convergecast strategy using power P and there is no deterministic distributed strategy allowing the agents to solve convergecast when the amount of power given to each agent is (2δ)P .

• there exists a centralized broadcast strategy using power P for source agent starting at P os [START_REF] Albers | Energy-efficient algorithms[END_REF] and there is no deterministic distributed strategy for source agent starting at P os [START_REF] Albers | Energy-efficient algorithms[END_REF] allowing the agents to solve broadcast when the amount of power given to each agent is (2δ)P .

Before proving Theorem 6, we prove two technical lemmas.

Lemma 12. Consider any ε > 0, an amount of power P , and a set {a 1 , a

(k + 1, P ) = 2 k Reach c LR (1, P ) + (2 k -1)P -Σ k i=1 2 k-i P os[i] = Reach c LR (1, P ) + (2 k -1)P -Σ k i=1 2 k-i (P os[i] -Reach c LR (1, P )) ≥ Reach c LR (1, P ) + (2 k -1)P -Σ k i=1 2 k-i (P -ε) ≥ Reach c LR (1, P ) + (2 k -1)P -(2 k -1)(P -ε) ≥ Reach c LR (1, P ) + (2 k -1)ε Consequently, if k ≥ log(P/ε), we have Reach c LR (k + 1, P ) ≥ Reach c LR (1, P ) + P -ε ≥ P os[k + 2], a contradiction.
Lemma 13. Consider an amount of power P , a distance d > 0, and a set {a 1 , a 2 , . . . , a k } of k agents located at positions P os [1 : k]. Let R 1 be the closest point from P os [START_REF] Albers | Exploring unknown environments[END_REF] that a 1 reached. Assume that P os [START_REF] Albers | Exploring unknown environments[END_REF]-R 1 = d.

Suppose that all the agents execute the same distributed deterministic algorithm and do not know their initial position, and assume that some agent a ∈ {a 2 , a 3 . . . , a k } meets agent a 1 before any couple of agents in {a 1 , a 2 , . . . , a k } meet. Then, a = a 2 and when a 2 meets a 1 , for each 2 ≤ i ≤ k, agent a i is located on P os[i]d.

Moreover, if R max is the rightmost point reached by some agent knowing the initial information of agent a 1 , then R max ≤ P os[k] + P -2d.

Proof. Since all agents are executing the same distributed deterministic algorithm, let us consider the execution of the algorithm until some agent meets agent a 1 . During this period, all the agents perform exactly the same moves. Since they started simultaneously, no agent meets another agent before agent a 2 meets a 1 at point R 1 or to the left of R 1 . When agent a 2 meets a 1 , it has moved at least a distance of d. Until this meeting between a 1 and a 2 , every other agent has also moved a distance of at least d, and is located at distance d to the left of its starting position. Consequently, no agent can go further than P -2d to the right of P os[k].

Proof of Theorem 6 :

Let ε = δP/4 and σ = ε/2 = δP/8. Let l = log(8/δ) , k = l + 2 and n = 2l(l + 2) + 2.

Consider a set of n agents positioned on a line as follows (See Figure 3). There is an agent a 1 (resp. a n ) on the left (resp. right) end of the line on position s 0 = 0 (resp. s 2l+1 = ). For each 1 ≤ i ≤ 2l, there is a set A i of k agents that start on distinct positions within a segment [s i , s i ] of length σ such that for each 1 ≤ i ≤ 2l + 1, the distance between s i and s i-1 is 2(Pε). In other words, for each i, s i = (2P -3σ)iσ and s i = (2P -3σ)i.

First, let us consider the execution of the optimal convergecast centralized algorithm for this configuration. We claim that if the amount of power given to each agent is P , then convergecast is achievable. We show by induction on i that for every i, Reach c LR (ik + 1, P ) ≥ s i + P -= s i+1 -P + . For i = 0, Reach c LR (1, P ) = P os [START_REF] Albers | Energy-efficient algorithms[END_REF] + P > P -= s 1 -P + . Suppose that Reach c LR ((i -1)k + 1, P ) ≥ s i -P + . Consider the agents in A i , i.e., the agents a ik+1-j , j ∈ [0, k -1]. Since s i -Reach c LR ((i -1)k + 1, P ) ≤ P -+ σ = Pσ < P , and since l + 1 ≥ log(P/σ), we know by Lemma this concludes the proof by induction. Since Reach c LR (2lk + 1, P ) ≥ s 2l+1 -P + ≥ Reach c RL (2lk + 2, P ), P is sufficient to solve convergecast. Notice that the same strategy guarantees broadcast for source agent a 1 for configuration P os[1 : n] and power P .

Consider any distributed deterministic algorithm where the amount of power given to each agent is (2δ)P , yielding a strategy S of the agents. A step in S is a moment when two agents meet. Let t l,i (resp. t r,i ) be the first step where an agent from A i meets an agent from A i with i < i (resp. i > i). Let R i (resp. L i ) be the rightmost point (resp. the leftmost point) reached by any agent from A i after some agent in A i has met an agent from A i with i < i (resp. i > i). For any 1 ≤ i < j ≤ 2l + 1, let A i,j = A i ∪ A i+1 . . . ∪ A j .

We show by induction on time t that for each i ∈ [1, l] such that t l,i ≤ t and for each j ∈ [l + 1, 2l] such that t r,j ≤ t, the following properties hold:

(i) t l,i < t l,i for each i ∈ [i + 1, l] and t r,j < t r,j for each j ∈ [l + 1, j -1], (ii) for each i ∈ [i + 1, l], if t l,i > t then t r,i > t, and for each j ∈ [l + 1, j -1], if t r,j > t then t l,j > t (iii) R i ≤ s i+1 -(2 i+2 -2)ε and L j ≥ s j-1 + (2 2l-1-j -2)ε, (iv) no agent in A i , i ≥ l meets any agent from A 1,l-1 and no agent in A j , j ≤ l + 1 meets any agent from A l+2,2l+1 .

First, consider t = 0. Clearly, R 1 ≤ s 0 +2P -δP = 2P -4ε = s 1 -2ε and L 2l+1 ≥ s 2l+1 -2P +δP = s 2l +2ε. Since all agents in A 1,2l execute the same algorithm, they all perform the same moves until either the leftmost agent of A 1 meets a 0 (at step t l,1 ), or the rightmost agent of A 2l meets a 2l+1 (at step t r,2l ). In the first case, it shows that t l,1 < t l,i and t l,1 < t r,i for any i ≥ 2. By Lemma 13, R 1 ≤ s 1 + (2δ)P -2(s 1 -R 0 ) ≤ s 2 -2P + 2ε + 2P -4ε -2(2ε) = s 2 -6ε. By symmetry, in the second case, t r,2l < t r,i and t r,2l < t l,i for any i ≤ 2l -1 and L 2l ≥ s 2l-1 + 6ε. In both cases, properties for (i) -(iii) hold for t = 0. Notice that for any i, j ∈ [1, 2l], no agent in A i has met an agent of A j . Hence, property (iv) hold for t = 0.

Suppose that the induction hypothesis holds for all t < t and let i = max{i | t l,i < t} + 1 and j = min{j + 1 | t r,j < t} -1. Note that by (iv), we have i ≤ l -1 and j ≥ l + 2. By (i) and (ii), before step t, no agent in A i , i ≤ i ≤ j has met any other agent from a set A i , i = i . Thus, since all agents in A ij execute the same deterministic distributed algorithm starting simutaneously, they have performed exactly the same moves and they have not met any other agent before step t. Suppose that an agent from A ij meets another agent at step t. Then, either the leftmost agent a i from A i meets an agent a i from A i with i < i, or the rightmost agent from A j meets an agent from A j with j > j.

By symmetry, it is enough to consider only one case. In the following, we assume that a i ∈ A i meets an agent a i ∈ A i with i < i at step t. In this case, t = t l,i and thus t l,i < t l,i and t l,i < t r,i for each i < i ≤ j; consequently, properties (i) and (ii) hold for t. Moreover, by induction hypothesis, the meeting between a i and a i occurs at a point p ≤ R i ≤ R i-1 ≤ s i -(2 i+1 -2)ε. First suppose that i ≤ l -1. By Lemma 13, we have R i ≤ s i + 2P -δP -2(2 i+1 -2)ε = s i+1 -2P + 2ε + 2P -4ε -2 i+2 ε + 4ε = s i+1 -(2 i+2 -2)ε, and thus property (iii) and (iv) holds for t. Then suppose that i = l ≥ log(8/δ) -1. We have R i ≤ s l -(8/δ -2)δP/4 = s l -2P + δP/2 < s l -2P + δP . But this is impossible since the initial position of the leftmost agent a of A l is P os[lk + 1] ≥ s l and the power available to a is 2P -δP . This concludes the proof by induction. In particular, no agent from A 1,l ever meets any agent from A l+1,2l+1 and consequently, S is neither a distributed convergecast strategy nor a distributed broadcast strategy for any source agent.

Theorems 5 and 6 show that for the distributed convergecast problem on the class of trees, the competitive ratio 2 is optimal.

Conclusion and open problems

In the centralized setting, we showed that the breaking point in complexity between polynomial and NPhard, both for the convergecast and for the broadcast problem, is already present inside the class of trees. Namely, agents' optimal power and the strategy using it can be found in polynomial time for the class of lines but it is NP-hard for the class of arbitrary trees. Nevertheless, we found polynomial approximation algorithms for both these problems. It remains open if better approximation constants can be found.

The problem of a single information transfer by mobile agents between two stationary points of the network, which we called carry in the case of lines, is also interesting. In particular, it is an open question whether the problem of finding optimal power for this task is NP-hard for arbitrary tree networks or if a polynomial-time algorithm is possible in this case. Our reduction from 3-partition is no longer valid for this problem.

In the distributed setting, we showed that 2 is the best competitive ratio for the problem of convergecast. However, our distributed algorithm for the broadcast problem is only 4-competitive. It remains open to find the best competitive ratio for the broadcast problem.

Additional natural questions related to our research include other variations of the agent model, e.g., agents with unequal power, agents with non-zero visibility, labeled agents in the distributed setting, as well as fault-tolerant issues, such as unreliable agents or networks with possibly faulty components.

  contradicting the choice of our strategy. Consequently, either 2b k+1 -P os[k]b k-1 > P , or b k+1 + P os[k] -2b k-1 > P and the lemma holds.

Remark 3 .

 3 At the end of the execution of Function OptimalAtIndex, TH c LR and TH c RL contain respectively Y LR (r, P c OP T ) and Y RL (r + 1, P c OP T ). Moreover, if initially the two stacks TH c LR and TH c RL contain respectively Y LR (r, P ) and Y RL (r + 1, P ) for some P ≥ P c OP T , then the value computed by the function is also P c OP T . The pseudo-code of the of Function OptimalAtIndex is given below. Function OptimalAtIndex(array P os[1 : n] of real; r:integer):stack TH c LR = ThresholdLR(r); TH c RL = ThresholdRL(r + 1); (p, PLR) = pop(TH c LR ); (q, PRL) = pop(TH c RL ); P = max{PLR, PRL}; /* p = r, PLR = T H c LR (r), q = r + 1, PRL = T H c RL (r + 1).

  ); /* P c OP T = P<r+1 is the solution of Reach c LR (r, P c OP T ) = Reach c RL (r + 1, P c OP T ) */ if q = r + 1 then return P c OP T ; /* In this case, P c OP T ≥ T H c RL (r + 1) and thus P c OP T = P<r = Act c LR (r + 1): for any s > r, P<s = P<r */ if 2 r-p * P os[p] + (2 r-p+1 -1) * P c OP T -S c LR (p, r) ≥ P os[r + 1] then /* If Reach c LR (r, P c OP T ) ≥ P os[r + 1] then T H c LR (r + 1) ≤ P c OP T and we update TH c LR , using the same algorithm as in function ThresholdLR. */ while 2 r-p * P os[p] + (2 r-p+1 -1) * PLR -S c LR (p, r) do (p, PLR) = pop(TH c LR ); push (TH c LR ,(p, PLR)); PLR = (P os[r + 1] + S c LR (p, r) -2 r-p * P os[p])/(2 r-p+1 -1); p = r + 1;

[ 1 :

 1 n] of agents and a specified source agent a k . We first compute b k-1 = Reach b LR (k -1, P ) and b k+1 = Reach b RL (k + 1, P ). Then we test if |2Reach b LR (k -1, P ) -P os[k] -Reach b RL (k + 1, P )| or |2Reach b RL (k + 1, P ) -P os[k] -Reach b LR (k -1, P )|

2 =

 2 First, we show by induction on p that for any p ∈ {1, 2, . . . , k} and an amount of power P ≥ Act b LR (p), we have Reach b LR (p, P ) = Reach b LR (p, Act b LR (p))+P -Act b LR (p). This is true for p = 1 since Reach b LR (1, P ) = P , Act b LR (1) = 0 and Reach b LR (1, Act b LR (1)) = 0. Now, assume by induction that Reach b LR (p -1, P ) = Reach b LR (p -1, Act b LR (p -1)) + P -Act b LR (p -1). By definition of a regular broadcast strategy, we have for all P ≥ Act b LR : Reach b LR (p, P ) = Reach b LR (p -1, P ) + P os[p] + P Reach b LR (p -1, Act b LR (p -1)) + P -Act b LR (p -1) + P os[p] + P 2 = P + Reach b LR (p -1, Act b LR (p -1)) -Act b LR (p -1) + P os[p] 2

[ 1 :

 1 n] of real; r:integer):real Act b LR (1) = 0, Reach b LR (1, Act b LR (1)) = 0, p = 1; while p < k -1 do while (p < k -1) and (P os[p + 1] -Act b LR (p) ≤ Reach b LR (p, Act b LR (p))) do Act b LR (p + 1) = Act b LR (p); Reach b LR (p + 1, Act b LR (p + 1)) = (P os[p + 1] + Act b LR (p + 1) + Reach b LR (p, Act b LR (p + 1)))/2; p = p + 1; if (p < k -1) then δLR = (P os[p + 1] -Act b LR (p) -Reach b LR (p, Act b LR (p)))/2; Act b LR (p + 1) = Act b LR (p) + δLR; Reach b LR (p + 1, Act b LR (p + 1)) = P os[p + 1]; p = p + 1;

For p = 1 ,

 1 the values of Reach b LR (p, Act b LR (p)) and Act b LR (p) are correctly computed since Reach b LR (1, Act b LR (1)) = 0 and Act b LR (1) = 0. Suppose that the values of Reach b LR (p, Act b LR (p)) and Act b LR (p) are correctly computed. If Reach b LR (p, Act b LR (p)) ≥ P os[p + 1] -P , then Act b LR (p + 1) = Act b LR (p). By Lemma 7, all functions Reach b LR (p, P ) are linear with coefficient 1 on [Act b LR (p), +∞). Hence, if Reach b LR (p, Act b LR (p)) < P os[p + 1] -Act b LR (p), we have Act b LR (p + 1) = Act b LR (p)+(P os[p+1]-P -Reach b LR (p, Act b LR (p)))/2. This shows that Act b LR (p+1) is correctly computed. It remains to show that Reach b LR (p+1, Act b LR (p+1)) is correctly computed. By definition of a regular broadcast strategy, we have Reach b LR (p + 1, Act b LR (p + 1)) = (Reach b LR (p, Act b LR (p + 1)) + Act b LR (p + 1) + P os[p + 1])/2. If Reach b LR (p, Act b LR (p)) ≥ P os[p + 1] -Act b LR (p), then Reach b LR (p + 1) is correctly computed as the above formula is used by the function. Otherwise, we have : Act b LR (p + 1) = Act b LR (p) + (P os[p + 1] -Act b LR (p) -Reach b LR (p, Act b LR (p)))/2. Using the notation r = Reach b LR (p, Act b LR (p)), r = Reach b LR (p, Act b LR (p + 1)), a = Act b LR (p), a = Act b LR (p + 1) we have :Reach b LR (p + 1, Act b LR (p + 1)) = r + a + P os[p + 1] 2 = (r + aa) + (a + (P os[p + 1]ar)/2) + P os[p + 1] 2 = (r + (P os[p + 1]ar)/2)) + (a + (P os[p + 1]ar)/2) + P os[p + 1] 2 = P os[p + 1].This completes the proof by induction. Again, using the fact that all functions Reach b LR (p, P ) are linear with coefficient 1 on [Act b LR (p), +∞), the function OptimalBroadcast computes correctly the value X b LR = Reach b LR (k -1, Q). The same is true for Y b RL = Reach b RL (k + 1, Q). Finally, we consider three cases : P os[k] ≤ X b LR , X b LR < P os[k] < Y b RL or Y b RL ≤ P os[k] to compute the additional power δ that has to be used. By definition of Reach b LR (k -1, P ) and Reach b

Figure 1 :

 1 Figure 1: Instance of the centralized convergecast decision problem constructed from an instance of 3partition.

Algorithm 1 :

 1 KnownGraph(a weighted graph G, an array A[1:k] of nodes)strategy = empty_stack; V := {A[1]}; P := 0; repeat choose a couple (u, v) ∈ V × (A \ V ) such that d(u, v) is minimal; V := V ∪ {v};P ath := shortest path between u and v; push(strategy, (v, P ath, u)); P = max{P, d(u, v)}; until V = A; repeat (v, P ath, u) = pop(strategy); agent starting in v moves to u following path P ath; until strategy = empty_stack;

Figure 3 :

 3 Figure 3: The configuration in the proof of Theorem 6.

Table 1 :

 1 Summary of our results

		• polynomial 2-approximation on arbi-trary graphs	• polynomial 4-approximation on arbi-trary graphs
	Distributed	• 2-competitive algorithm for trees • proof that there is no (2-)-competitive algorithm • 4-competitive algorithm for trees on lines, for any > 0

  the minimal amount of power ensuring that agent a p does not go back when a p ∈ LR (respectively a p ∈ RL), i.e., such that Reach c

-1, P ) + P ≥ P os[p]}. Similarly, we have Act c RL (p) = min{P | Reach c RL (p + 1, P ) -P ≤ P os[p]}. Given a strategy using power P , for each agent p ∈ LR, we have P ≥ Act c LR (p) and either Reach c LR (p -1, P ) ≥ P os[p], or Reach c LR (p -1, P ) ≤ P os[p]. In the first case, Reach c LR (p, P ) = P os[p] + P , while in the second case, Reach c LR (p, P ) = 2Reach c LR (p -1, P ) + P -P os[p]. We define threshold functions T H c LR (p) and T H c RL (p) that compute, for each index p, LR (p -1, P ) = P os[p] (respectively Reach c RL

  1 ≤ p ≤ n, the function Reach c LR (p, •) which assigns the value Reach c LR (p, P ) for any argument P , is an increasing, continuous, piecewise linear function with at most p pieces on [Act c LR (p), +∞). For every 1 ≤ p ≤ n, the function Reach c RL (p, •) which assigns the value Reach c RL (p, P ) for any argument P , is a decreasing continuous piecewise linear function with at most p pieces on [Act c RL (p), +∞). We prove the first statement of the claim by induction on p. For p = 1, Reach c LR (1, P ) = P os[1] + P and the claim holds. Suppose that Reach c First note that Act c LR (p) < Act c LR (p + 1). Since Reach c LR (p, •) is a continuous, increasing function, there exists a unique P = Act c LR (p+1) such that Reach c LR (p, P )+P = P os[p+1] and for every P > Act c LR (p+1), Reach c LR (p, P ) + P > P os[p + 1]. Consequently, Reach c LR (p + 1, •) is well defined on [Act c LR (p + 1), +∞). Since Reach c LR (p, •) is a continuous, increasing function, there exists a unique P = T H c LR (p + 1) such that Reach c LR (p, P ) = P os[p + 1].

	If Act c LR (p + 1) ≥ P ≥ T H c LR (p + 1), Reach c LR (p + 1, P ) = LR (p, P )+P -P os[p+1] and thus Reach c 2Reach c LR (p+1, •) is an increasing, continuous, piecewise linear func-tion on [Act c LR (p+1), T H c LR (p+1)] with at most p pieces. If P ≥ T H c LR (p+1), Reach c LR (P ) = P os[p+1]+P and thus, Reach c LR (p + 1, •) is an increasing, continuous, linear function on [T H c LR (p + 1), +∞). Since 2Reach c LR (p, T H c LR (p + 1)) + T H c LR (p + 1) -P os[p + 1] = P os[p + 1] + T H c LR (p + 1), the function Reach c LR (p + 1, •) is an increasing, continuous, piecewise linear function on [Act c LR (p + 1), +∞) with at most p + 1 pieces.

LR (p, •) is a continuous piecewise linear function on [Act c LR (p), +∞) and consider Reach c LR (p + 1, •).

  Consider an optimal regular convergecast strategy and let P be the maximum amount of power used by any agent. By definition of a regular convergecast strategy, there exists an index p such that Reach c

1, P ). LR (p, P ) = Reach c RL (p + 1, P ). Suppose that Reach c LR (p, P ) ≤ P os[p]. In this case, we have Reach c RL (p, P ) = P os[p]-P < Reach c LR (p-1, P ) since P > Act c LR (p). Consequently, according to what we have shown above, there exists P < P such that Reach c RL (p, P ) ≤ Reach c LR (p -1, P ) and P is not the optimal value needed to solve convergecast. This contradiction shows that P os[p] < Reach c LR (p, P ). For similar reasons, if Reach c RL (p + 1, P ) ≥ P os[p + 1], P is not the optimal value needed to solve convergecast. This contradiction shows that Reach c RL (p + 1, P ) > P os[p + 1]

  This contradicts the first statement of the lemma. Hence, we have P > Act c

c LR (p). Moreover, if Reach c LR (p, P ) is defined, then P ≥ Act c LR (p). If P = Act c LR (p), then Reach c LR (p, P ) = P os[p] -P and thus, Reach c RL (p + 1, P ) ≥ P os[p + 1] -P > P os[p] -P ≥ Reach c LR (p, P ).

  By Lemma 5, the function Reach c LR (p, •) can be computed from the values T H c LR (q) for all q such that 1 ≤ q ≤ p. Starting from p = 1, one can compute all these functions Reach c LR (p, •), since each value T H c LR (p) = min{P | Reach c LR (p -1, P ) = P os[p]} can be deduced from Reach c LR (p -1, •). The computation at step p has a time complexity in O(p) and so the computation of all the functions Reach c LR (p, •) takes time O(n 2 ). Similarly, it is possible to compute all the functions Reach c RL (p, •), for all p such that 1 ≤ p ≤ n, in time O(n 2 ). Since Reach c LR (p, •) and Reach c RL (p + 1, •) are increasing, continuous, piecewise linear functions with at most n pieces, by the claim from the proof of Lemma 6, it is possible to compute the value P such that Reach c LR (p, P ) = Reach c RL (p + 1, P ) in time O(n). Hence the optimal value of power needed to achieve convergecast on lines, which is min 1≤p≤n {P | Reach c LR (p, P ) = Reach c RL (p + 1, P )} by Lemma 6, can be computed in time O(n 2

c LR (p, •) and Reach c RL (p, •) for all p such that 1 ≤ p ≤ n.

  and we can return the value of P <r+1 . In Function ComputeOptimal, at each iteration, the stack TH c LR contains Y LR (r, P <r ) (except its top element) and the stack TH c RL contains Y RL (r + 1, P <r ) (except its top element). Initially, TH c LR is empty and TH c RL contains O(n) elements. In each iteration, at most one element is pushed into the stack TH c LR and no element is pushed into the stack TH c RL . Consequently, the number of stack operations performed by Function ComputeOptimal is linear.

1, P <r+1 ) and Y RL (r + 2, P <r+1 ) from Y LR (r, P <r+1 ) and Y RL (r + 1, P <r+1 ). Note that if T H c LR (r) > P <r+1 , then Y LR (r + 1, P <r+1 ) = Y LR (r, P <r+1 ). If T H c LR (r) ≤ P <r+1 , we can use the same function as in ThresholdLR to compute Y LR (r + 1, P <r+1 ) = {(p, T H c LR (p)) | p ∈ X LR (r)} from Y LR (r, P <r+1 ). Consider now Y RL (r+2, P <r+1 ). If T H c RL (r+ 1) > P <r+1 , then (r + 1, T H c RL (r + 1)) / ∈ Y RL (r + 1, P <r+1 ), and Y RL (r + 2, P <r+1 ) = Y RL (r + 1, P <r+1 ). If T H c RL (r + 1) ≤ P <r+1 , then either P os[r + 1] -P <r+1 ≥ Reach c RL (r + 1, P <r+1 ) if P <r+1 = P <r , or P os[r + 1] -P <r+1 = Reach c RL (r + 1, P <r+1 ) = Reach c LR (r, P <r+1 ) if P <r+1 < P <r . In both cases, it implies that Act c LR (r + 1) ≥ P <r+1 . Therefore, by Lemma 6, P <i = P <r+1 for every i ≥ r + 1

  1, P ) ≤ P os[q] + P }. In a regular broadcast strategy using power P , for each agent p ∈ LR such that P ≥ Act b

	LR (p), we LR (p -1, P ) + P + P os[p])/2. Similarly, for each agent q ∈ RL such that LR (p, P ) = (Reach b have Reach b P ≥ Act b RL (q), we have Reach b RL (q, P ) = (Reach b RL (q + 1, P ) -P + P os[q])/2. The next lemma shows how to compute Reach b LR (p, •) on the interval [Act b LR (p), +∞) for every p ∈ {1, 2, . . . , k} and Reach b RL (q, •) on the interval [Act b RL (q), +∞) for every q ∈ {k, k + 1, . . . , n}.

Lemma 7. Consider an index p ∈ {1, 2, . . . , k} and an amount of power P ≥ Act b LR (p), then Reach b LR (p, P ) = Reach b LR (p, Act b LR (p)) + P -Act b LR (p).

  2 , . . . , a k , a k+2 } of k + 2 agents located at positions P os[1 : k + 2]. If P os[k + 2] -Reach c LR (1, P ) ≤ Pε, and if k ≥ log(P/ε), there exists i ≤ k + 1 such that Reach c LR (i, P ) ≥ P os[i + 1]. Proof. Suppose, by contradiction, that the lemma does not hold. It means that for each 1 ≤ i ≤ k + 1, Reach c LR (i, P ) < P os[i + 1]. Therefore, in view of the claim from the proof of Lemma 5, we have

	Reach c LR

† Partially supported by NSERC discovery grant and by the Research Chair in Distributed Computing at the Université du Québec en Outaouais.

Suppose by contradiction that during the collecting phase, more than one agent in A enters an edge f to collect the information of agent b i at distance x i from the center, for some i such that 1 ≤ i ≤ 3m. Let w be the agent that has reached the position of b i . If w comes back to the center, it has used at least power 2x i . Since at least one other agent has used some power to enter edge f , these agents have used more than 2x i battery power to collect information of agent b i . If w does not come back to the center, then some other agent has to move the information to the center. If the agent w stops at distance r from the center, then at least one other agent has to go to this position (at distance r from the center) and come back. Thus, the cost is at least (2x ir) + 2r > 2x i . In both cases, the agents have used more power than 2x i , which leads to a contradiction. Hence, for each 1 ≤ i ≤ 3m, there is only one agent that collects the information of agent b i and enters the corresponding edge.

We can assume, without loss of generality, that agent a m+1 is the agent that transports the information to c. Observe that a m+1 cannot collect information from other nodes since moving to c uses exactly all its remaining power. Hence, only agents in A = A \ {a m+1 } can collect the information of agents in B. Let S 1 , S 2 , . . . , S m be the partition of S defined by S i = {x j | the information of b j is collected by a i }, for each 1 ≤ i ≤ m. We have 2 x∈Si x ≤ 2R since each agent from A has battery power at most 2R. The power needed to collect information of agents in B is 2mR which is exactly equal to the combined power available to agents in A . This means that each agent in A must use all its power to collect information and 2 x∈Si x = 2R. Hence, S 1 , S 2 , . . . , S m is a solution to the instance of 3-partition.

Lemma 10. The centralized broadcast decision problem is strongly NP-hard for trees.

Proof. Again, we construct a polynomial-time many to one reduction from 3-Partition. The general structure of the proof is similar as in Lemma 9 but details differ.

We construct an instance (G, U ) of the centralized broadcast problem from an instance of 3-Partition as follows. The graph G is a star with 5m leaves and U is the set of leaves of G. Hence, there are 5m agents, each located at a leaf of the star. We consider a partition of the set of agents into three subsets: A, B and C. The subset A = {a i | 1 ≤ i ≤ m} contains m agents. The leaves containing these agents are incident to an edge of weight 1. The subset B = {b i | 1 ≤ i ≤ 3m} contains 3m agents. For 1 ≤ i ≤ 3m, the weight of the edge incident to the leaf containing agent b i is 4R + 1 + x i . The subset C = {c i | 1 ≤ i ≤ m} contains m agents. All leaves containing an agent in C are incident to an edge of weight 6R + 1. Figure 2 depicts the star obtained in this way. The battery power P allocated to each agent is equal to 4R + 1 and agent a 1 is the source agent. The construction can be done in polynomial time. We show that the constructed instance of the centralized broadcast problem gives answer yes if and only if the original instance of 3-partition gives answer yes.

Figure Instance of centralized broadcast problem from an instance of 3-partition.

First, assume that there exists a solution S 1 , S 2 , . . . , S m for the instance of the 3-partition problem. We show that the agents can solve the corresponding instance of the centralized broadcast problem using the following strategy. For each i, agent c i moves at distance 2R from the center and for each 1 ≤ i ≤ 3m, agent