Antonio Fernández Anta

Alessia Milani
email: milani@labri.fr

Miguel A Mosteiro
email: mosteiro@cs.rutgers.edu

Shmuel Zaks
email: zaks@cs.technion.ac.il

Antonio Fernández
email: antonio.fernandez@imdea.org

Opportunistic Information Dissemination in Mobile Ad-hoc Networks: The Profit of Global Synchrony

Keywords: Mobile Ad-hoc Networks, Radio Networks, Geocast, Broadcast, Lower Bounds

The topic of this paper is the study of Information Dissemination in Mobile Ad-hoc Networks by means of deterministic protocols. We assume a weak set of restrictions on the mobility of nodes, parameterized by α, the disconnection time, and β, the link stability time, such that the Mobile Ad-hoc Networks considered are connected enough for dissemination. Such a connectivity model generalizes previous models in that we assume much less connectivity, or make explicit the assumptions in previous papers. The protocols studied are classified into three classes: oblivious (the transmission schedule of a node is only a function of its ID), quasi-oblivious (the transmission schedule may also depend on a global time), and adaptive.

The main contribution of this work concerns negative results. Contrasting the lower and upper bounds derived, interesting complexity gaps among protocol-classes are observed. These results show that the gap in time complex-

Introduction

A Mobile Ad-hoc Network (aka MANET) is a set of mobile nodes which communicate over a multihop radio network, without relying on a stable infrastructure. In these networks, nodes are usually battery-operated devices that can communicate via radio with other devices that are in range. Due to unreliable power supply and mobility, nodes may have a continuously changing set of neighbors in that range. This dynamic nature makes it challenging to solve even the simplest communication problems in general. Hence, proposed protocols often have strong synchronization and stability requirements, like having a stable connected network for long enough time.

Current trends in networking-architecture developments, like delay and disruption tolerant networks, and opportunistic networking [START_REF] Fall | A delay-tolerant network architecture for challenged internets[END_REF][START_REF] Pelusi | Opportunistic networking: data forwarding in disconnected mobile ad hoc networks[END_REF], aim to deal with the disconnections that naturally and frequently arise in wireless environments. Their objective is to allow communication in dynamic networks, like a MANET, even if a route between sender and receiver never exists in the network. The result is that multihop communication is provided through opportunistic communication, in which the online route of a message is followed one link at a time, as links in the route become avail-able. While the next link is not available, the message is held in a node. With opportunistic communication, strong connectivity requirements are no longer needed. Furthermore, in some cases mobility is the key to allow communication (e.g., consider two disconnected static nodes, where communication between them is provided by a device that, due to mobility, sometimes is in range of one and sometimes of the other).

In this paper, we formally define a particular class of MANET which is suited for opportunistic communication, and which we call potentially epidemic. A MANET is potentially epidemic if the changes in the communication topology are such that an online route exists among any two nodes that wish to communicate.

The network is potentially epidemic because the actual propagation of the information on the online routes, and then the possibility for a node to affect another node, depends on the stability of each communication link of the online route.

In this context, we define and study the deterministic solvability of a problem that we call Dissemination. In this problem, at a given time a source node holds an information that must be disseminated to a given set of nodes belonging to the MANET. The nodes elected to eventually receive the information are the ones that satisfy a given predicate. Depending on this predicate, the Dissemination problem can instantiate most of the common communication problems in distributed systems, such as Broadcast, Multicast, Geocast, Routing, etc.

In particular, we determine assumptions on link stability and speed of nodes under which a distributed deterministic protocol exists that solves Dissemination in potentially epidemic networks. Moreover, we relate the time complexity of the solution to the speed of movement and to the information that protocols may use.

The Dissemination Problem

We study the problem of disseminating a piece of information, initially held by a distinguished source node, to all nodes of a given set in the network. Formally, Definition 1 Given a MANET formed by a set V of n nodes, let P be a predicate on V and s ∈ V a node that holds a piece of information I at time t 1 (s is the source of dissemination). The Dissemination problem consists of distributing I to the set of nodes V P = {x ∈ V :: P(x)}. A node that has received I is termed covered, and otherwise it is uncovered. The Dissemination problem is solved at time slot t 2 ≥ t 1 if, for every node v ∈ V P , v is covered by time slot t 2 .

The Dissemination problem abstracts several common problems in distributed systems. E.g. Broadcast, Multicast, Geocast, Routing etc., are all instances of this problem for a particular predicate P. In order to prove lower bounds, we will use one of these instances: the Geocast problem. The predicate P for Geocast is P(x) = true if and only if, at time t 1 , x is up and running, and it is located within a parametric distance d > 0 (called eccentricity) from the position of the source node at that time.

Model

We consider a MANET formed by a set V of n mobile nodes deployed in R 2 , where no pair of nodes can occupy the same point in the plane simultaneously. It is assumed that each node has data-processing and radio-communication capabilities, and a unique identificator number (ID) in [n] {1, . . . , n}.

Time. Each node is equipped with a clock that ticks at the same uniform rate ρ but, given the asynchronous activation, the clocks of different nodes may start at different times. A time interval of duration 1/ρ is long enough to transmit (resp. receive) a message. Computations in each node are assumed to take no time. Starting from a time instant used as reference, the global time is slotted as a sequence of time intervals or time slots 1, 2, . . . , where slot i > 0 corresponds to the time interval [(i -1)/ρ, i/ρ). All node's ticks are assumed to be in phase with this global tick. The use of a slotted scenario instead of a more realistic unslotted one was justified in [START_REF] Roberts | Aloha packet system with and without slots and capture[END_REF], where it was shown that they differ only by a factor of 2 because a packet can interfere in no more than 2 time slots.

Node Activation. We say that a node is active if it is powered up, and inactive otherwise. It is assumed that, due to lack of power supply or other unwanted events that we call failures, active nodes may become inactive. Likewise, due also to arbitrary events such as replenishing their batteries, nodes may be re-activated. We call the temporal sequence of activation and failures of a node the activation schedule. The activation schedule for each node is assumed to be chosen by an adversary, in order to obtain worst-case bounds. Most of the lower-bound arguments included in this paper hold, even if all nodes are activated simultaneously and never fail (which readily provide a global time), making the results obtained stronger.

We assume that a node is activated in the boundary between two consecutive time slots. If a node is activated between slots t-1 and t we say that it is activated at slot t, and it is active in that slot. Upon activation (or reactivation after a failure) a node immediately starts running from scratch an algorithm previously stored in its hardware.

Due to failures, it is possible that a covered node does not hold the information I. To distinguish a covered node that does not hold the information I from one that holds it, we introduce the following additional terminology: we say that a node p is informed at a given time t if it holds the information I at time t, otherwise p is said to be uninformed.

Radio Communication. Nodes communicate via a collision prone single radio channel. A node v can receive a transmission of another node u in time slot t only if their distance is at most the range of transmission r during the whole slot t. The range of transmission is assumed to be the same for all nodes and all time slots. If two nodes u and v are separated by a distance at most r, we say that they are neighbors. (When r is normalized to 1, this model is called Unit Disk Graph in the Radio Networks literature.) In this paper, no collision detection mechanism is assumed, and a node cannot receive and transmit at the same time slot. Therefore, an active node u receives a transmission from a neighboring node v at time slot j if and only if v is the only node in u's neighborhood transmitting at time slot j. Also, a node cannot distinguish between a collision and no transmission. In general, we say that a node v ∈ V ′ transmits uniquely among the nodes of set V ′ ⊆ V in a slot t if it is the only node in V ′ that transmits in t.

(α, β)-connectivity. We assume that nodes may move on the plane. Thus, the topology of the network is time dependent. For simplicity, we assume that the topology only changes in the boundaries between time slots. Then, at time slot t nodes u and v are connected by a link in the network topology iff they are neighbors during the whole slot t. An online route between two nodes u and v is a path u = w 0 , w 1 , . . . , w k = v and a sequence of time slots t 1 < t 2 < • • • < t k such that the network has a link between w i-1 and w i at time slot t i . Observe that in order to be able to solve an instance of Dissemination, it is necessary that the network is potentially epidemic. I.e. after the initial time t 1 , there is an online route from the source s to every node in V P . However, as argued in [START_REF] Clementi | Communication in dynamic radio networks[END_REF], worst-case adversarial choice of topologies for a dynamic network precludes any deterministic protocol from completing Broadcast, even if connectivity is guaranteed. Note that Broadcast is an instance of Dissemination, and that if there is connectivity then there are online routes between all nodes. Thus, the property that the network is potentially epidemic as described is not sufficient to solve Dissemination, and further limitations to the adversarial movement and activation schedule are in order.

While respecting a bound on the maximum speed v max , which is a parameter, the adversarial movement and activation schedule is limited by the following connectivity property. Let S ⊂ V be any non-empty subset of nodes, and let S = V -S. An edge is k-stable at time t if it exists for k consecutive steps [t, t + k -1]. The opportunistic communication constraint is parameterized by parameters α and β: for every partition (S, S), there are at most α consecutive steps without a β-stable edge between S and S. We call such a network (α, β)-connected. Note, for example, that (α, β)-connectivity requires that any node that fails reboots (and reestablishes connectivity) within α steps. For simplicity, we do not enforce (α, β)-connectivity before the time slot t 1 when the source node is informed.

The aim of this α,β parameterization is twofold. First, in some previous papers, the connectivity depended explicitly [START_REF] Fernández Anta | Opportunistic information dissemination in mobile ad-hoc networks: The prot of global synchrony[END_REF] or implicitly [START_REF] Pelusi | Opportunistic networking: data forwarding in disconnected mobile ad hoc networks[END_REF] on the protocol (notably, who has and does not have the information I at any given time). Here, we remove the dependency on the protocol, while maintaining a similar flavor to the connectivity constraints. Second, we substantially weaken the connectivity assumptions compared with some previous papers which assumed, for example, a stable spanning tree of edges [START_REF] Kuhn | Distributed computation in dynamic networks[END_REF][START_REF] O'dell | Information dissemination in highly dynamic graphs[END_REF], or that the underlying graph may be non-geometric [START_REF] Baumann | Parsimonious flooding in dynamic graphs[END_REF][START_REF] Clementi | Flooding time in edge-markovian dynamic graphs[END_REF][START_REF] Clementi | Communication in dynamic radio networks[END_REF].

It is of the utmost importance to notice that (α, β)-connectivity is a characterization that applies to any deterministic model of dynamic network, given that for any mobility and activation schedule, and any pair of nodes, there is a minimum time they are connected (even if that time is small) and a maximum time they are disconnected (even if that time is very large). Thus, any dynamic network deterministic model used to study the Dissemination problem has its own α and β values.

Due to the same argument, (α, β)-connectivity does not guarantee by itself that the network is epidemic (i.e. that the information I is eventually disseminated); instead, an (α, β)-connected network is only potentially epidemic. Consider for instance the source node. Thanks to the (α, β)-connectivity, at most every α slots, the source s is connected to other nodes of the network for at least β time slots. But, we have progress only if the protocol to solve Dissemination is able to use the β slots of connectivity to cover some uncovered node. As a consequence of the above discussed, impossibility results only restrict β, whereas α only constrains the running time, as it is shown in this paper.

Protocols for Dissemination

We consider distributed deterministic protocols, i.e., we assume that each node in the network is preloaded with its own and possibly different deterministic algorithm that defines a schedule of transmissions for it. Even if a transmission is scheduled for a given node at a given time, that node will not transmit if it is uninformed.

Following the literature on various communication primitives [START_REF] Kowalski | On selection problem in radio networks[END_REF][START_REF] Kowalski | Time complexity of radio broadcasting: Adaptiveness vs. obliviousness and randomization vs. determinism[END_REF], a protocol is called oblivious if, at each node, the algorithm's decision on whether or not to schedule a transmission at a given time slot depends only on the identifier of the node, and on the number of time slots that the node has been active. Whereas, if no restriction is put on the information that a node may use to decide its communication schedule, the protocol is called adaptive. Additionally, in this paper, we distinguish a third class of protocols that we call quasi-oblivious. In a quasi-oblivious protocol the sequence of scheduled transmissions of a node depends only on its ID and a global time. Quasi-oblivious protocols have sometimes been called oblivious, since the model assumed simultaneous activation, and hence a global time was readily available. However we prefer to make the difference explicit, as done in [START_REF] Peleg | Time-efficient broadcast in radio networks[END_REF], because we found a drastic gap between this class and fully oblivious protocols.

Previous Work

A survey of the vast literature related to Dissemination is beyond the scope of this article. We overview in this section the most relevant previous work. Additionally, a review of relevant related work for static and dynamic networks beyond MANETs can be found in Section 1.5.

The Dissemination problem abstracts several common problems in Radio Networks. When some number 1 ≤ k ≤ n of active nodes hold an information that must be disseminated to all nodes in the network, the problem is called k-Selection [START_REF] Kowalski | On selection problem in radio networks[END_REF] or Many-to-all [START_REF] Chlebus | On many-to-many communication in packet radio networks[END_REF]. If k = 1 the problem is called Broadcast [START_REF] Bar-Yehuda | On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization[END_REF][START_REF] Kushilevitz | An Ω(D log(N/D)) lower bound for broadcast in radio networks[END_REF], whereas if k = n the problem is known as Gossiping [START_REF] Chlebus | Oblivious gossiping in ad-hoc radio networks[END_REF][START_REF] Farach-Colton | Sensor network gossiping or how to break the broadcast lower bound[END_REF]. Upper bounds for these problems in mobile networks may be used for Dissemination, and even those for static networks may apply if the movement of nodes does not preclude the algorithm from completing the task (e.g., round-robin). On the other hand, if only the subset of k nodes have to receive the information, the problem is known as Multicast [START_REF] Chlebus | On many-to-many communication in packet radio networks[END_REF][START_REF] Gasieniec | Deterministic m2m multicast in radio networks[END_REF], and if only nodes initially located at a parametric distance from the source node must receive the information the problem is called Geocast [START_REF] Jinag | A review of geocasting protocols for a mobile ad hoc network[END_REF], defined in Section 1.1.

Deterministic solutions for the problems above have been studied for MANETs. Their correctness rely on strong synchronization or stability assumptions. In [START_REF] Mohsin | Reliable broadcast in wireless mobile ad hoc networks[END_REF], deterministic Broadcast in MANETs was studied under the assumption that nodes move in a one-dimensional grid knowing their position. Two deterministic Multicast protocols are presented in [START_REF] Gupta | An adaptive protocol for reliable multicast in mobile multi-hop radio networks[END_REF][START_REF] Pagani | Reliable broadcast in mobile multihop packet networks[END_REF]. The solutions provided require the network topology to globally stabilize for long enough periods to ensure delivery of messages, and they assume a fixed number of nodes arranged in some logical or physical structure. Leaving aside channel contention, a lower bound of Ω(n) rounds of communication was proved in [START_REF] Prakash | A lower bound for broadcasting in mobile ad hoc networks[END_REF] for MANET Broadcast, even if nodes are allowed to move only in a grid, improving over the Ω(D log n) bound of [START_REF] Bruschi | Lower bounds for the broadcast problem in mobile radio networks[END_REF], where D is the diameter of the network. This bound was improved [START_REF] Dessmark | Broadcasting in geometric radio networks[END_REF] to Ω(n log n) without using the movement of nodes, but the diameter of the network in the latter is linear. Recently, deterministic solutions for Geocast were proposed in [START_REF] Baldoni | Mobility versus the cost of geocasting in mobile ad-hoc networks[END_REF] for a one-dimensional setting and in [START_REF] Fernández Anta | Bounds for deterministic reliable geocast in mobile ad-hoc networks[END_REF] for the plane. In the latter work, the authors concentrate in the structure of the Geocast problem itself, leaving aside communication issues such as the contention for the communication channel.

Related Work

Node activation in distributed computing. The issue of how many nodes start an execution, is of central importance in distributed computing. In rare cases it might affect the solvability of the problem (see Example 1 below), and it certainly might affect the time (see Example 2 below) or the message complexity (see Example 3 below). All these examples refer to asynchronous networks, so the issue of simultaneity is different from the one used in our case. The examples are: [START_REF] Aspnes | An introduction to population protocols[END_REF] In [START_REF] Fischer | Impossibility of distributed consensus with one faulty process[END_REF] it is shown that no algorithm can solve the consensus problem if at least one node might fail during the execution; however, the result does not hold if the failure can occur only at the beginning of the execution. Actually, the problem can be solved as long as a majority of the processes are non-faulty, but those that fail do so at the beginning of the execution. (2) In [START_REF] Gallager | A distributed algorithm for minimum-weight spanning trees[END_REF] an algorithm to find a minimum spanning tree in a network is presented. It is shown that the execution can take Ω(n 2 ) time if the processors are allowed to start at different times; however, if they all start simultaneously then the time complexity is O(n log n). (n is the number of processors). (3) Finding a leader in a network whose topology is a complete graph is of message complexity Ω(n log n) if all nodes start the execution [START_REF] Korach | Optimal lower bounds for some distributed algorithms for a complete network of processors[END_REF], but can be solved by at most O(k log n) messages when only k nodes start [START_REF] Humblet | Selecting a leader in a clique in o(n log n) messages[END_REF].

Static networks. Given that a static network is just an instance of a network where nodes are allowed to move, lower bounds for the Broadcast problem also may apply to Dissemination, but only if the network is geometric (i.e., the adjacencies of the topology assumed can be embedded in R 2 ) and the target of the dissemination are all the nodes in the network. The following bounds are proved for models similar to the one assumed in this paper. Exploiting a lower bound on the size of a combinatorial problem called selective families, a lower bound for deterministic Broadcast of Ω(n log D), where D is the diameter of the layered topology used, was shown in [START_REF] Clementi | Selective families, superimposed codes, and broadcasting on unknown radio networks[END_REF], yielding a linear lower bound if D ∈ O(1). In [START_REF] Kowalski | Time complexity of radio broadcasting: Adaptiveness vs. obliviousness and randomization vs. determinism[END_REF], adaptive and oblivious deterministic lower bounds of Ω(n) and Ω(n min{D, √ n}) respectively were presented for the Broadcast problem in static Radio Networks. The construction used for the former has diameter at most 4 and at least 7 for the latter. Extending the construction used previously in [START_REF] Bruschi | Lower bounds for the broadcast problem in mobile radio networks[END_REF][START_REF] Chlebus | Deterministic broadcasting in unknown radio networks[END_REF] to geometric Radio Networks, a lower bound of Ω(n log n) is shown in [START_REF] Dessmark | Broadcasting in geometric radio networks[END_REF] for the Broadcast problem even if nodes do not move. The diameter of the network used in this case is linear. In [START_REF] Ga ¸sieniec | Broadcasting in udg radio networks with unknown topology[END_REF], it was shown that, for each oblivious deterministic Broadcast algorithm, there exists a network of diameter 2 such that the running time is at least Ω( √ g), where g is the inverse of the minimum Euclidean distance between any pair of nodes, by adversarially placing nodes as the algorithm progresses.

The above bounds apply also to Geocast, but only if d ≥ D where D is also the eccentricity but with respect to all nodes in the constructions used to prove them. Regarding upper bounds, in [START_REF] Chlebus | Deterministic broadcasting in unknown radio networks[END_REF], Chlebus et al. presented an adaptive protocol that completes deterministic Broadcast in less than 14n steps where n is the number of nodes in the system, for a symmetric network without collision detection where nodes do not have any information of the network except their own unique identity (later denoted ID for short). Making use of the simultaneous activation of all nodes, the protocol defines an eulerian cycle over a spanning tree of the network. Hence, this protocol could be used for Dissemination only if the movement of nodes does not change the topology. None of these assumptions are present in our model. Limiting the adversary to changes of topology due to node failures only, it was proved in [START_REF] Clementi | Round robin is optimal for fault-tolerant broadcasting on wireless networks[END_REF] that the well-known round-robin O(Dn) algorithm, where D is the diameter of the network, is optimal for solving Broadcast restricted to connected non-failing nodes.

Dynamic Networks beyond MANETs. Similar problems have been studied recently for dynamic networks. A suitable model for time-dependent topologies is the Dynamic Graph [START_REF] Baumann | Parsimonious flooding in dynamic graphs[END_REF][START_REF] Clementi | Flooding time in edge-markovian dynamic graphs[END_REF][START_REF] Clementi | Information spreading in stationary markovian evolving graphs[END_REF]. A dynamic graph is a set of n nodes V and a sequence of edge-sets E 1 , E 2 , . . . over V . Mapping each E i with a time slot i, a dynamic graph models a network with a possibly different topology for each time slot, usually called a Dynamic Network [START_REF] Awerbuch | Adapting to asynchronous dynamic networks[END_REF][START_REF] Clementi | Communication in dynamic radio networks[END_REF]. If such topology can be embedded in R 2 , a dynamic network is a suitable model of a MANET (even under failures since a node that is inactive at time step i may be modeled by not including any of its edges to neighboring nodes in E i ). Dynamic networks may be eventually connected [START_REF] Awerbuch | Efficient and reliable broadcast is achievable in an eventually connected network[END_REF]. In other words, the temporal sequence of edgesets may be such that no edge-cut lasts forever, as assumed in population protocols [START_REF] Aspnes | An introduction to population protocols[END_REF].

Communication techniques to solve Dissemination, such as flooding, have been studied for dynamic networks [START_REF] Baumann | Parsimonious flooding in dynamic graphs[END_REF][START_REF] Clementi | Flooding time in edge-markovian dynamic graphs[END_REF][START_REF] Clementi | Communication in dynamic radio networks[END_REF][START_REF] Clementi | Information spreading in stationary markovian evolving graphs[END_REF][START_REF] O'dell | Information dissemination in highly dynamic graphs[END_REF]. In [START_REF] Baumann | Parsimonious flooding in dynamic graphs[END_REF][START_REF] Clementi | Flooding time in edge-markovian dynamic graphs[END_REF][START_REF] Clementi | Communication in dynamic radio networks[END_REF][START_REF] Clementi | Information spreading in stationary markovian evolving graphs[END_REF] the results obtained are stochastic and, as argued in [START_REF] Clementi | Communication in dynamic radio networks[END_REF], worst-case adversarial choice of topologies precludes any deterministic protocol from completing Broadcast, even if connectivity is guaranteed. In [START_REF] O'dell | Information dissemination in highly dynamic graphs[END_REF], they consider deterministic solutions to solve two particular instances of the dissemination problem, e.g., routing and flooding. They do not explicitly deal with the contention for the communication channel, and they request the network to be always connected and to provide some local stability. A data-centric approach for data dissemination in opportunistic networks is studied in [START_REF] Boldrini | Modelling data dissemination in opportunistic networks[END_REF]. The only constraint on mobility is that each node must eventually communicate with an appropriate set of peers. Hence, the performance of the tech-nique is evaluated only experimentally. In [START_REF] Kuhn | Gradient clock synchronization in dynamic networks[END_REF][START_REF] Kuhn | Distributed computation in dynamic networks[END_REF] a model of dynamic network is proposed, in which, for any T consecutive rounds there is a stable connected spanning graph. Guan [START_REF] Guan | Better face routing protocols[END_REF] also proposes a dynamic version of the quasi unit disk graph, where nodes do not move but when they are beyond a certain distance their connectivity can fluctuate. These models are stronger than the models considered here but they do not provide applicable lower bounds.

Our Results

The main contribution of this work concerns negative results. Our main results are summarized in Table 1. Contrasting the lower bounds obtained with the upper bounds derived by careful combination of previous techniques, interesting complexity gaps among protocol-classes are observed.

For a model where nodes may fail, there is no global clock, and nodes may be activated at different times, we show in Theorem 6 that any oblivious protocol takes, in the worst case, Ω((α + n 2 / ln n)n) steps to solve the Geocast problem if v max > πr/6(α+⌊(2n/5)(2n/5-1)/ ln((2n/5)(2n/5-1))⌋-2). Given the upper bound of n(α+4n(n-1) ln(2n)) for Dissemination established in Theorem 8 by means of an oblivious deterministic protocol based on Primed Selection [START_REF] Fernández Anta | Deterministic communication in the weak sensor model[END_REF], this lower bound is tight up to a poly-logarithmic factor.

Moreover, for the same model, Theorem 5 shows that, even if nodes are activated simultaneously and do not fail, and an adaptive protocol is used, any Geocast protocol takes, in the worst case, Ω(n(α + n)) if v max > πr/(3(2α + n -4)). This result should be contrasted with the quasioblivious protocol based on Round-Robin that solves Dissemination in at most n(α + n) steps as established in Theorem 7.

The latter results are asymptotically tight and show that full adaptiveness does not help with respect to quasi-obliviousness. The first lower bound and the last upper bound, show an asymptotic separation almost linear between oblivious and quasi-oblivious protocols. In a more restrictive model, where nodes are activated simultaneously, there exists an oblivious protocol (e.g. Round Robin) that solves Dissemination in at most n(α + n) steps. This can be trivially derived from the fact that when nodes are all activated simultaneously, the above quasi-oblivious protocol does not need the synchronization step and thus simply reduces to the Round Robin protocol. Hence, the lower bound proved in Theorem 6 shows the additional cost of obliviousness when nodes are not simultaneously activated. This gap is what we call the profit of global synchrony, since it represents the gain the network obtains from global synchrony with respect to not having it. Moreover, the quasi-oblivious protocol derived shows that for the Dissemination problem, the simultaneous oblivious quasi-oblivious adaptive lower bounds

Ω(n(α + n 2 / ln n)) - Ω(n(α + n))
upper bounds n(α + 4n(n -1) ln(2n)) n(α + n) -Table 1 Time complexity of deterministic Opportunistic Dissemination Information in Mobile Ad-hoc Networks.

activation performance can be achieved by distributing the time elapsed since the source started the dissemination. Additionally, it is shown in Theorem 1 that no protocol can solve the Geocast problem (and hence Dissemination) in all (α, β)-connected networks unless β ≥ n -1. Interestingly, it is shown in Theorem 2 that this bound becomes β > ⌊(n -1)(n -3)/4 ln((n -1)(n -3)/4)⌋ if the protocol is oblivious. Comparing these bounds with the requirements of the protocols presented above, the quasi-oblivious protocol required β ≥ n, which is almost optimal, while the oblivious protocol required β ∈ Ω(n 2 log n), which is only a polylogarithmic factor larger than the lower bound. These results also expose another aspect of the profit of global synchrony mentioned before: while β = n is enough for quasioblivious protocols to solve Dissemination, oblivious protocols require a value of β almost a linear factor larger.

Finally, for an arbitrary small bound on node speed, we show in Theorem 3 the existence of an (α, β)-connected network where Geocast takes at least α(n -1) steps, even using randomization; and the existence of an (α, β)-connected network where any deterministic protocol that transmits periodically takes at least n(n -1)/2 steps, even if nodes do not move, in Theorem 4.

For the upper bounds, we additionally assume that failing nodes do not lose the information I. This is needed in order to make Dissemination solvable because, otherwise, e.g., the adversary may turn off the source node in the first time step. Our lower bounds are proved independently of whether a failing node loose the information I or not. Our upper bounds also hold under a weaker connectivity model where only the partition defined by the information I is (α, β)connected.

Paper Organization

The rest of the paper is organized as follows. In Section 2 we introduce some technical lemmas that will be used to prove our main results; in Section 3 we prove the lower bounds on link stability and on the time complexity to solve the Dissemination problem with respect to some important aspects of the system (e.g. speed of movement of nodes and their activation schedule) and of the protocols (e.g., obliviousness versus adaptiveness). We finally present the corresponding upper bounds in Section 4.

Preliminaries

The following lemmas will be used throughout the analysis. A straightforward consequence of the pigeonhole principle is established in the following lemma.

Lemma 1 For any time step t of the execution of a Dissemination protocol, where a subset V ′ of k informed nodes do not fail during the interval [t, t + k -2], there exists some node v ∈ V ′ such that v does not transmit uniquely among the nodes in

V ′ during the interval [t, t + k -2].
In the following lemma, we show the existence of an activation schedule such that, for any oblivious deterministic protocol, within any subset of at least 3 nodes, there is one that does not have a unique transmission scheduled within a period roughly quadratic in the size of the subset. The proof is based on the probabilistic method.

Lemma 2 For any deterministic oblivious protocol for Dissemination in a MANET of n nodes, where nodes are activated possibly at different times, and for any subset of k nodes, k ≥ 3, there exists a node-activation schedule such that, for any time slot t and letting m = ⌊k(k -1)/ ln(k(k -1))⌋, each of the k nodes is activated during the interval [t -m + 1, t], and there is one of the k nodes that is not scheduled to transmit uniquely among those k nodes during the interval [t, t + m -1].

Proof Consider any oblivious protocol Π and any subset of k nodes, where k is an arbitrary value such that 3 ≤ k ≤ n. If, according to Π, the algorithm of one of the k nodes, call it i, does not schedule any transmission in some period of m steps within the first 2m steps, the claim holds by activating i so that such period starts at time slot t.

Otherwise, the algorithm of all the k nodes must schedule at least one transmission in any period of m steps within the first 2m steps. If, according to Π, the algorithm of one of the k nodes, call it i, schedules less than k transmissions in some period of m steps within the first 2m steps, the claim holds by activating i so that such period starts at time slot t and the other k -1 nodes are activated during the interval [t-m+1, t] so that each of i's transmissions are scheduled at the same time that some other transmission. This is possible because i is scheduled to transmit less than k times during the interval [t, t + m -1] and each of the other k -1 nodes is scheduled to transmit at least once within any period of m steps within the first 2m steps.

Otherwise, the algorithm of all the k nodes must schedule at least k transmissions in any period of m steps within the first 2m steps, we say that the density of scheduled transmissions in such period is at least k/m. Then, we prove the existence of the claimed activation schedule by the probabilistic method.

Consider any of the k nodes, call it i. Let i be activated at time slot t. For each of the other k -1 nodes, choose uniformly and independently at random a slot within the interval [t -m + 1, t] for activation. Consider any time slot t ′ ∈ [t, t + m -1] when i is scheduled to transmit. Consider any of the other k -1 nodes, call it j. Given that the density of scheduled transmissions within the first 2m steps of j is at least k/m, the probability that j has a transmission scheduled at time t ′ is at least k/m. Thus, the probability that no node other than i has a transmission scheduled at time t ′ is less than (1 -k/m) k-1 . Using the union bound over the m slots in [t, t + m -1], we know that the probability that i has a unique (among the k nodes) transmission scheduled during the interval

[t, t+m-1] is less than m(1-k/m) k-1 .
Then, in order to prove the claim, it is enough to show that the probability that i does not have a unique (among the k nodes) transmission scheduled at some time step within i's first m steps is strictly bigger than 0. Replacing, it is enough to prove 1 -⌊k(k -1)/ ln(k(k -1))⌋(1 -k/⌊k(k -1)/ ln(k(k -1))⌋) k-1 > 0, which we do as follows. We know that, for any k ≥ 3, it is ln(k(k -1)) > 1. Dividing both sides by k(k -1),

ln(k(k -1)) k(k -1) > 1 k(k -1) = exp (-ln(k(k -1))) and = exp - ln(k(k -1)) k -1 k-1
.

Using the inequality e -x ≥ 1 -x, for 0 < x < 1 [37, §2.68], we know that

ln(k(k -1)) k(k -1) > 1 - ln(k(k -1)) k -1 k-1 1 > k(k -1) ln(k(k -1)) 1 - ln(k(k -1)) k -1 k-1
.

Which implies that

1 - k(k -1) ln(k(k -1)) 1 -k k(k -1) ln(k(k -1)) -1 k-1 > 0.

⊓ ⊔ 3 Solvability of the Dissemination Problem

If there is at least one node in V P -{s} at least one time slot is needed to solve Dissemination, since the source node has to transmit at least once to pass the information I. Furthermore, if all nodes in V P are neighbors of s, one time slot may also be enough if the source node transmits before neighboring nodes are able to move out of its range. On the other hand, if the latter is not possible, more than one time slot may be needed. Let us consider the Geocast problem. Given that the specific technological details of the radio communication devices used determine the minimum running time when the eccentricity is d ≤ r, all efficiency lower bounds are shown for d > r unless otherwise stated.

Link Stability Lower Bounds

The following theorem shows a lower bound on the value of β for the Geocast problem.

Theorem 1 For any v max > 0, d > r, α > 0, and any deterministic Geocast protocol Π, if β < n -1, there exists an (α, β)-connected MANET of n nodes such that Π does not terminate, even if all nodes are activated simultaneously and do not fail.

Proof Consider three sets of nodes A, B, and C deployed in the plane, each set deployed in an area of size ε arbitrarily small, such that 0 < ε < r and d ≥ r + ε. (See Figure 1.)

≤ r ≤ ε r < δ ≤ r + ε A B C
Fig. 1 Illustration of Theorem 1.

The invariant in this configuration is that nodes in each set form a clique, every node in A is placed within distance r from every node in B, every node in B is placed at most at distance ε from every node in C, and every node in A is placed at some distance r < δ ≤ r+ε from every node in C. ε is set appropriately so that a node can move ε distance in one time slot without exceeding v max . At the beginning of the first time slot, the adversary places n-1 nodes, including the source node s, in the set C, the remaining node x in set A, and activates all nodes. The set B is initially empty.

Given that d ≥ r + ε, x must become informed to solve the problem.

For any protocol Π for Geocast, let t 1 be the first time slot where the source node is the only node to transmit in the set C. Adversarially, let t 1 be the first time slot when the source is informed. (Recall that (α, β)-connectivity is not enforced before t 1 for clarity.) At time slot t 1 , all nodes placed in C are informed.

After time slot t 1 , the adversary moves the nodes as follows. Given that the problem was not solved yet and nodes in C do not fail, according to Lemma 1, there exists a node y ∈ C that does not transmit uniquely among the nodes in

C during the interval [t 1 + 1, t 1 + n -2].
Given that Π is a deterministic protocol, and the adversary knows the protocol and defines the movement of all nodes, the adversary knows which is the node y.

Assume, for the sake of contradiction, that β ≤ n -2. Then, the adversary places y in B for all time slots in the interval [t 1 + 1, t 1 + β]. Additionally, for each time slot t ′ ∈ [t 1 + 1, t 1 + β] where y transmits, the adversary moves to B some node z ∈ C that transmits at t ′ to produce a collision. At the end of each time slot t ′ the adversary moves z back to C. Such a node z exists since y does not transmit uniquely during the interval [t 1 + 1, t 1 + n -2] and n -2 ≥ β. At the end of time slot t 1 + β, the adversary moves y back to C and the above argument can be repeated forever preserving the (α, β)-connectivity and precluding Π from solving the problem. Therefore, β must be at least n -1.

⊓ ⊔

Building upon the argument used in the previous theorem, but additionally exploiting the adversarial node activation, the following theorem shows a lower bound on the value of β for the Geocast problem if the protocol used is oblivious. The idea of the proof is to split evenly the nodes of set C in the proof of Theorem 1 in two groups, so that alternately the nodes in one group are activated while the nodes in the other group produce collisions.

Theorem 2 For any v max > 0, d > r, n ≥ 8, α > 0, and any deterministic oblivious protocol for Geocast Π, if β ≤ m = ⌊(n -1)(n -3)/4 ln((n -1)(n -3)/4)⌋, there exists an (α, β)-connected MANET of n nodes such that Π does not terminate.

Proof (Proof Sketch) Consider again the configuration described in Theorem 1. (See Figure 1.) The invariant, the initial location of nodes, and the value of ε are the same as in Theorem 1. The adversarial node activation schedule follows.

The adversary activates x and s at the beginning of some time slot t 0 . Let t 1 ≥ t 0 be the time slot when the source node is scheduled to transmit the information I for the first time. Adversarially, let t 1 be the first time slot when the source is informed. (Recall that (α, β)-connectivity is not enforced before t 1 for clarity.) For the following interval [t 2 + 1, t 2 + m], the above argument can be repeated using the nodes in the set C e . At time slot t 2 , the transmission of node y will inform all nodes in C e . Each node in C e is deactivated for one time slot in the interval [t 2 -m, t 2 ) according to the activation schedule required by Lemma 2. Given that deactivated nodes restart the execution from scratch upon reactivation, as proved in Lemma 2 some node y ′ ∈ C e does not transmit uniquely among the nodes in C e during the interval [t 2 + 1, t 2 + m]. Given that α ≥ 1 and β ≤ m, (α, β)-connectivity is preserved. Thus, moving nodes between sets C e and B as described before once again x is not informed, this time during the interval [t 2 + 1, t 3 ), where t 3 > t 2 + m is the time slot when y ′ is scheduled to transmit uniquely among the nodes in C e .

The above argument can be repeated inductively forever so that the problem is not solved but, since β ≤ m, (α, β)connectivity is preserved. Therefore, β must be bigger than m.

⊓ ⊔

Time Complexity Lower Bounds versus Speed, Activation and Obliviousness

Exploiting the maximum time α that a partition can be disconnected, a lower bound on the time efficiency of any protocol for Geocast, even regardless of the use of randomization and even for arbitrarily slow node-movement, can be proved. The following theorem establishes that bound.

Theorem 3 For any v max > 0, d > r, α > 0, and β > 0, there exists an (α, β)-connected MANET of n nodes, for which any Geocast protocol takes at least α(n -1) time slots, even if all nodes are activated simultaneously and do not fail.

Proof The following adversarial configuration and movement of nodes shows the claimed lower bound. Initially, nodes are placed in a circle (as depicted in Figure 2), all are activated simultaneously, and let the source be informed immediately upon activation. Let {v 1 , v 2 , . . . , v n-1 , v n } be the nodes located around the circle in clockwise direction where v 1 = s is the source node. The nodes are located so that the distances between each pair are the following. The distance between v 1 and v 2 is r+ε, where ε > 0 is set appropriately so that a node can move as described below in one time slot without exceeding v max . For each 1 < i < n, the distance between v i and v i+1 is r. The pair v 1 , v n is placed at distance δ, r < δ < d -ε ′ , where ε ′ > 0 is set appropriately so that node v n can move as described below in one time slot without exceeding v max and it will be always within distance d from the source s = v 1 . Every other pair of nodes is separated by distance bigger than r. In order to solve Geocast, node v n must be covered.

v 1 = s v 2 v 3 v n-1 vn r r + ε r < δ < d -ε ′ Fig. 2 Illustration of Theorem 3.
Nodes stay in the position described until time slot α -1 when node v 2 moves so that in time slot α it is placed at distance r of v 1 and at distance r + ε from v 3 . Node v 2 does not move after time slot α. Due to this configuration, the source node is not able to inform v 2 during the first α -1 time slots and, in the best case, v 2 becomes informed in time slot α. After v 2 becomes informed, the argument can be repeated iteratively for v 3 , v 4 , . . . , v n . Given that each node, except for the source, becomes informed at least α time slots after its predecessor, the overall time is lower bounded as claimed. Given that a new uncovered node becomes a neighbor of an informed node within α slots and does not move after that, and all other partitions are always connected, (α, β)connectivity is preserved.

⊓ ⊔

The linear lower bound for Geocast proved in Theorem 3 was shown exploiting the maximum time of disconnection between partitions. Exploiting the adversarial schedule of node activation, even if nodes do not move nor fail, the same bound can be simply proved for arbitrary Geocast protocols, while a quadratic bound can be shown for the important class of equiperiodic protocols. The protocol definition and the theorem for the latter follows.

Definition 2 A protocol of communication for a Radio Network is equiperiodic if for each node, the transmissions scheduled are such that the number of consecutive time steps without transmitting, call it T -1, is always the same. We say that T is the period of transmission of such a node.

Theorem 4

For any v max ≥ 0, d > r, α > 0, β > 0, and any deterministic equiperiodic Geocast protocol Π, there exists an (α, β)-connected MANET of n nodes, for which Π takes at least n(n -1)/2 time slots to solve the problem, even if nodes do not fail and do not move.

Proof The following adversarial configuration and activation schedule of nodes shows the claimed lower bound. Initially, nodes are placed as in Theorem 3, except that now the distance between v 1 and v 2 is r and nodes will be static. (See Figure 2.) The adversary chooses the IDs of nodes so that the periods of transmission are assigned in increasing order. I.e., the smallest period corresponds to the source node v 1 , the second smallest to v 2 , and so on. Then, v 1 and v n are activated by the adversary at the same time, and let the node source v 1 be informed immediately upon activation. Given that they are activated simultaneously, in order to solve Geocast, v n must become covered. The adversary chooses the activation schedule of the rest of the nodes so that, for each node v i with assigned period T i , 1 < i < n, node v i transmits T i -1 steps after becoming covered. In order to preserve (α, β)-connectivity, each node i is activated before v 1 and v n , possibly many periods T i to achieve the above schedule.

Assume that all periods are different. Given that the first period cannot be smaller than 2, and each node i, 1 < i < n, transmits for the first time the information I T i -1 steps after becoming covered, the time bound follows.

If on the other hand the protocol is such that two nodes x, y have the same period of transmission, the following (α, β)-connected network and activation schedule shows that the problem cannot be solved. The adversary places the nodes in a static two-hop topology so that, the nodes x and y are neighbors of all nodes, but the source node is placed within distance d and bigger than r from all nodes except x and y. The adversary activates x and y so their scheduled transmissions coincide in time. The rest of the nodes are activated at the same time that x or y, whichever is the latest. When the source node transmits the information I for the first time, both nodes x and y, and no other node, become covered simultaneously. Given that both nodes are scheduled to transmit at the same time, their transmissions collide forever at the rest of the nodes. Thus, Geocast cannot be solved. The network is (α, β)-connected since it is statically connected.

⊓ ⊔

In Theorems 3 and 4 we showed lower bounds for Geocast for arbitrarily small values of v max . We now show that, by slightly constraining v max , a quadratic lower bound can also be shown for arbitrary deterministic protocols.

Theorem 5 For any v max > πr/(3(2α + n -4)), d > r, α > 0, β > 0, and any deterministic Geocast protocol Π, there exists an (α, β)-connected MANET of n nodes, for which Π takes Ω((α + n)n) time slots to solve the problem, even if all nodes are activated simultaneously and do not fail.

Proof The following adversarial configuration and movement of nodes shows the claimed lower bound. Consider six sets of nodes A, A ′ , B, B ′ , C, and C ′ , each deployed in an area of size ε arbitrarily small, such that 0 < ε < r and d ≥ r + ε, and four points, x, y, x ′ , and y ′ placed in the configuration depicted in Figure 3(a).

The invariant in these sets is that nodes in each set form a clique; each node in A ′ is placed at some distance > r and ≤ r + ε from each node in B and from the points x, y ′ (for clarity, the sets A and A ′ in Figure 3(a) are depicted very well separated from the circle crossing the points x, y, x ′ , y ′ , but in fact ε ≪ r); each node in A is placed at some distance > r and ≤ r + ε from each node in B and from the points x ′ , y; each node in B is placed within distance r of points x, y, x ′ , and y ′ , and each node in C and C ′ ; each node in C is placed at some distance > r and ≤ r + ε from the point x; each node in C ′ is placed at some distance > r and ≤ r + ε from the point x ′ ; and each node in B ′ is placed within distance ε of each node in B and within distance r of each node in C and C ′ . 1At the beginning of the first time slot, the adversary places n/2 nodes, including the source node s, in set B ′ , the remaining n/2 nodes in the set A, and starts up all nodes. (For clarity, assume that n is even.) All the other sets are initially empty. (See Figure 3(b).) Given that d ≥ r + ε, all nodes must be covered to solve the problem. Also, ε is set appropriately so that a node can be moved ε distance in one time slot without exceeding v max , and so that a node can be moved from set A to point x through the curved parts of the dotted line (see Figure 3(c)), of length less than π(r + ε)/6, in α + n/2 -2 time slots without exceeding v max . (To see why the length bound is that, it is useful to notice that the distance between each pair of singular points along each of the circular dotted lines is upper bounded by (r + ε)/2.) Let t be the first time slot when the source is scheduled to transmit. Adversarially, let t be the first time slot when the source is informed. Hence at time t, all nodes in set B ′ become informed but all nodes in set A still have to be informed. Starting at time slot t + 1, the adversary moves the nodes so that only one new node every α + n/2 steps becomes informed. First we give the intuition of the movements and later the details. Refer to Figures 3(c) and 3(d). Nodes that are not in B or B ′ are moved following the dotted lines. Some of the nodes in B ′ are moved back and forth to B. Nodes initially in A are moved clockwise to A ′ , except for one of them, say u, which is moved simultaneously counter-clockwise to the point x. Upon reaching A ′ nodes are moved counter-clockwise back to A, except for one of them, say v, which is moved simultaneously clockwise to the point x ′ , while the node u is also moved simultaneously to the point y. Upon reaching A, the remaining nodes repeat the procedure while u keeps moving towards C and v keeps moving towards C ′ through y ′ respectively. Nodes initially in A are moved in the above alternating fashion, one to C and the next one to C ′ , until all nodes become informed. Movements are produced so that (α, β)-connectivity is preserved. The details follow.

The movement of each node u moved from A to C is carried out in three phases of at least α + n/2 -2 time slots each as follows. As explained below, some nodes initially in A will be moved instead to C ′ , but the movement is symmetric. For clarity, we only describe the whole three phases for one node. The movement within each phase is illustrated in Figures 4, 5, and6.

-Phase 1. During the first α -2 time slots, u is moved counterclockwise from A towards the point x maintaining a distance > r and ≤ r + ε with respect to every node in B. Simultaneously, the remaining nodes initially in A are moved clockwise to A ′ maintaining the same distance to B. (See Figure 4(a).) In the (α -1)th time slot of this phase, all nodes initially in A are moved within distance r of every node in set B preserving (α, β)-connectivity. (See Figure 4(b).) Nodes in B ∪ B ′ stay static during this interval. Given that only nodes in B ∪ B ′ are informed and the distance between them and the rest is bigger than r, no node becomes covered during this interval. During the following n/2 -1 time slots of the first phase, the counterclockwise movement of node u towards the point x continues, but now maintaining a distance at most r with respect to every node in B. In the last time slot of the second phase, u is moved to point x. Simultaneously, the rest of the nodes originally in A continue their movement towards A ′ maintaining a distance at most r from B preserv-ing (α, β)-connectivity.) Then, even if u becomes informed immediately upon reaching point x, u cannot inform nodes in A ′ because they are separated by a distance > r. (See Figure 4(c).) During this interval, nodes in B ′ are moved back and forth to B as described in Theorem 1 to guarantee that u does not become covered before reaching point x. Upon reaching point x, u and all the other nodes in the network not in B or B ′ remain static. Phase 1 ends the time slot before u becomes covered, when the rest of the nodes originally in A are moved to A ′ . (See Figure 4(d).) -Phase 2. During this phase, u is moved counterclockwise towards point y maintaining a distance at most r with respect to every node in B and B ′ . Simultaneously, nodes that were in A ′ at the end of the second phase are moved counterclockwise to A except for one node v that moves in its own first phase to x ′ . (See Figure 5(a).) Nodes in A ′ are moved to A in the same fashion of Phase 1, i.e., maintaining first a distance > r from B and later on ≤ r to preserve (α, β)-connectivity. (See Figure 5(b).) Nodes moving from A ′ to A maintain a distance > r with respect to u. Thus, even if u becomes covered the information I cannot be passed to the former. At the end of this phase v is placed in point x ′ . Thus, even if v becomes covered immediately after arriving at x ′ , v cannot inform nodes in A because they are separated by a distance > r. (See Figure 5(c).) Phase 2 of u ends the time slot before v becomes covered, when the rest of the nodes in A ′ at the beginning of this phase are moved to A. (See Figure 5(d).) -Phase 3. During this phase, u is moved counterclockwise towards set C maintaining a distance at most r with respect to every node in B and B ′ . Simultaneously, nodes that were in A at the end of the second phase are moved clockwise to A ′ except for one node w that moves in its own first phase to x. Also simultaneously, v continues its movement towards set C ′ in its own second phase. (See Figure 6(a).) Nodes in A are moved to A ′ in the same fashion of Phase 1, i.e., maintaining first a distance > r from B and later on ≤ r to preserve (α, β)connectivity. (See Figure 6(b).) Nodes moving from A to A ′ maintain a distance > r with respect to v. Thus, even if v becomes covered the information I cannot be passed to the former. Also, nodes u and w are moved maintaining a distance > r between them. Thus, u cannot inform w. At the end of this phase u has reached set C, v is placed in point y ′ , and w is placed in point x. Thus, even if w becomes covered immediately after arriving at x, w cannot inform nodes in A because they are separated by a distance > r. ) Upon completing the third phase, u stays static in C forever so that (α, β)-connectivity is preserved.

The three-phase movement detailed above is produced for each node initially in A, overlapping the phases as described, until all nodes have became covered. Given that when a node u reaches the point x, its phase 1 is stretched until the time step before u becomes covered by a node v in B and all other nodes remain static, the next node w that will be moved from A ′ to x ′ does not become covered by v, because w stays in A ′ until u becomes covered. In each phase of at least α + n/2 -2 time slots every node is moved a distance at most π(r + ε)/6 + ε. Thus, setting ε appropriately, the adversarial movement described does not violate v max . Given that n/2 nodes initially in A are covered one by one, each at least within α + n/2 -2 time slots after the previous one, the overall running time is lower bounded as claimed, even if t = 1.

⊓ ⊔

The quadratic lower bound shown in Theorem 5 holds for any deterministic protocol, even if it is adaptive. Building upon the argument used in that theorem, but additionally exploiting the adversarial node activation, the following theorem shows a roughly cubic lower bound for oblivious protocols, even relaxing the constraint on v max . Theorem 6 Let m = ⌊(2n/5)(2n/5-1)/ ln((2n/5)(2n/5-1))⌋. For any n ≥ 8, d > r, α > 0, 0 < β < 2(α + m), v max > πr/(6(α + m -2)), and any oblivious deterministic Geocast protocol Π, there exists an (α, β)-connected MANET of n nodes, for which Π takes Ω((α + n 2 / ln n)n) time slots to solve the problem.

Proof (Proof Sketch) The following adversarial configuration and movement of nodes shows the claimed lower bound. The movement of nodes used in this proof is the same as in Theorem 5, which preserves (α, β)-connectivity as proved. However, here a particular activation schedule will be used to exploit obliviousness. We will explain the impact of such activation schedule in the (α, β)-connectivity at the end of the proof.

Consider again the configuration described in Theorem 5 (illustrated in Figure 3(a)). The sets and distance invariant are the same as in that theorem. Regarding node location, the adversary places 4n/5 nodes, including the source node s, in set B ′ , and the remaining n/5 nodes in the set A. (For clarity, assume that n is a multiple of 5.) All the other sets are initialized empty. (See Figure 3(b).) Also, ε is again set appropriately so that a node can be moved as required without exceeding v max , and all nodes that are active at the time that the source node transmits, must be covered for the particular value of d > r.

The adversarial node activation schedule follows. The adversary activates all nodes in the set A and s simultaneously. Let t 1 be the time slot when the source node is scheduled to transmit the information I for the first time. Adversarially, let t 1 be the first time slot when the source is informed. Given that all nodes in A are active and within distance d of s at time t 1 , all nodes in A must be covered to solve the problem.

Consider These alternating rounds of activation are repeated until the problem is solved. In each of the rounds of activation described here, and concurrently with the movement of nodes in A in the second interval of the first phase described in Theorem 5, nodes are moved between sets B ′ and B as described in Theorem 5, but now using the last node to transmit uniquely in B ′ o and B ′ e alternately. The movement of nodes from A and A ′ to C and C ′ is performed slower than in Theorem 5 since, for example, an uncovered node from A has now at least α+m-2 time steps to be moved from A to x before being informed. In each phase of at least α + m -2 time slots every node is moved a distance at most π(r + ε)/6 + ε. Setting ε appropriately, the adversarial movement described does not violate v max .

Given that n/5 nodes initially in A are covered one by one, each at least within α + m -1 time slots after the previous one, the overall running time is lower bounded as claimed.

The movement of nodes preserves (α, β)-connectivity as proved in Theorem 5. With respect to the activation schedule of the nodes in B ∪ B ′ , notice that each node is active for at least 2(α + m) -1 consecutive steps. Given that β < 2(α + m) the connectivity property holds.

⊓ ⊔

Notice that the upper bound on β in Theorem 6 is bigger than the lower bound on β proved in Theorem 2. Otherwise, the later would subsume the former.

It is interesting to observe the following. The oblivious lower bound was proved using failures, unlike the general lower bound where nodes do not fail. Furthermore, the general lower bound is universal for any β, because each partition is disconnected only once. But the oblivious lower bound is existential because β was restricted to exploit frequent failures. Having a restriction on β for oblivious pro-tocols is intuitively not surprising though because, as β becomes very large for a fixed α, links become "almost" static and node failures are rare. An interesting question left for future work is what is the precise relation between β and the time bound.

Upper Bounds

In this section, a quasi-oblivious protocol and an oblivious one that solve Dissemination, both based on known algorithms particularly suited for our setting, are described and their time efficiency proved. The first bound is asymptotically tight with respect to the more powerful class of adaptive protocols. Recall that, for the upper bounds, we assume that failing nodes do not lose the information I.

A Quasi-Oblivious Protocol. The idea underlying the protocol is to augment the well-known Round-Robin protocol with the synchronization of the clock of each node with the time elapsed since the dissemination started, which we call the global time. This is done by embedding a counter τ , corresponding to the global time, in the messages exchanged to disseminate the information I. Given that the schedule of transmissions of a node depends only on its ID and the global time, the protocol is quasi-oblivious. More details about the algorithm can be found in Algorithm 1. Proof As a worst case, we assume that all nodes in the network must be covered, and v max is arbitrarily big.

Using τ , each node achieves synchronization with respect to the time step when I was transmitted for the first time. Thus, since each node transmits in a unique time slot, collisions are avoided.

Let us denote by C the set of covered nodes, and C(t) the set C at the end of time slot t. Let us denote by t i the time slot at which the set C increases from size i to i + 12 . The time slot when the information I is transmitted for the first time is then t 0 .

We prove that t i+1 -t i ≤ α + n and thus in the worst case, after time n(α + n) all nodes are informed. At time t i , the set of nodes C(t i ) and the remaining nodes in the system V -C(t i ) constitute a non trivial partition.

Given that the network is (α, β)-connected, for each time slot t, and in particular for time slot t i , there exists a time slot t ′ ≥ t i such that a pair of nodes p ∈ C(t ′ ) and q ∈ V -C(t ′ ) such that, p is informed and q is uncovered at time t ′ , p and q are neighbors and active for all the interval [t ′ , t ′ + β) and this latter intersects with the interval [t i , t i + α). In the worst case at time t ′ + β a new node is covered, since β ≥ n.

Remember that every n time steps each informed node will re-transmit I unless the stop condition is verified. (I.e., n(α + n) time slots after the source node transmitted for the first time.) Since β ≥ n, we know that at time

t i+1 ≤ t ′ + n node q is informed. Since t ′ + n ≤ t i + α + n, we have that t i+1 ≤ t i + α + n. Thus, t i+1 -t i ≤ α + n. ⊓ ⊔
Recall that β ≥ n -1 is required for the problem to be solvable as shown in Theorem 1. This upper bound is asymptotically tight with respect to the lower bound shown in Theorem 5 for general deterministic Geocast protocols when v max > πr/(3(2α + n -4)). Thus, we can conclude that having extra information in this case does not help.

An Oblivious Protocol. We finally describe how to implement an oblivious protocol for Dissemination, based on a protocol presented in [START_REF] Fernández Anta | Deterministic communication in the weak sensor model[END_REF] for the related problem of Recurrent Communication called Primed Selection. Given that in this protocol the schedule of transmissions of a node depends only on its ID, the protocol is oblivious. This upper bound is only a poly-logarithmic factor away from the lower bound shown in Theorem 6.

In order to implement Primed Selection, one of n prime numbers is stored in advance in each node's memory, so that each node holds a different prime number. Let p ℓ denote the ℓ-th prime number. We set the smallest prime number used to be p n , which is at least n, because Primed Selection requires the smallest prime number to be at least the maximum number of neighbors of any node, which in our model is unknown. The algorithm is simple to describe, upon receiving the information I, each node with assigned prime number p i transmits with period p i .

It was shown in [START_REF] Fernández Anta | Deterministic communication in the weak sensor model[END_REF] that, for any Radio Network formed by a set V of nodes running Primed Selection, for any time slot t, and for any node i such that the number of nodes neighboring i is k -1, 1 < k < n, i receives a transmission without collision from each of its neighbors within at most k max j∈V p j steps after t. Given that in our setting the biggest prime number used is p 2n-1 , that p x < x(ln x + ln ln x) for any x ≥ 6 as shown in [START_REF] Rosser | Approximate formulas for some functions of prime numbers[END_REF], and that due to mobility all nodes may get close to i in the worst case, we have that k max j∈V p j < n(2n -1)(ln(2n -1) + ln ln(2n -1)), for n ≥ 4. Which is in turn less than 4n(n -1) ln(2n) for n ≥ 3. Hence, given that in the worst case all nodes must be covered at least one at a time and that the network is (α, β)connected, the overall running time is less than n(α+4n(n-1) ln(2n)). We formalize this bound in the following theorem. Recall that β > ⌊(n-1)(n-3)/4 ln((n-1)(n-3)/4)⌋ is required for the problem to be solvable when n ≥ 8 as shown in Theorem 2.

Theorem 8 Given an (α, β)-connected MANET, where β ≥ n(2n -1)(ln(2n -1) + ln ln(2n -1)) and n ≥ 4, there exists an oblivious deterministic protocol that solves Dissemination for arbitrary values of v max in at most n(α + 4n(n -1) ln(2n)) time steps.

Conclusions

In this paper, we formally define a particular class of MANET, suited for opportunistic communication, where the changes in the communication topology; if any, are such that an online route exists among any two nodes that wish to communicate. In this context, we have studied a fundamental communication problem, Information Dissemination. More generally, a future direction is to understand which are the problems that can be solved in our model and which not. Similarly to other works, e.g., [START_REF] Kuhn | Distributed computation in dynamic networks[END_REF], this research direction contributes to understand which are the necessary assumptions for distributed algorithms to solve fundamental problems in networks of dynamic nature.

In this sense, we have shown that when nodes are activated at different times, the time complexity to solve the Dissemination problem can be improved by almost a linear factor if nodes can use the information in the exchanged messages to synchronize their clock. In fact, we prove that only that piece of non-local information is enough to achieve optimality. This comparison is formalized by considering three classes of algorithms (oblivious, adaptive and quasioblivious) and summarized in Table 1. On one hand, we show a Ω(n(α+n 2 / ln n)) lower bound for oblivious protocols when nodes may be activated at different times. On the other hand, in a more restrictive model where global time is available, there exists an oblivious protocol (Round Robin) that solves Dissemination in at most n(α + n) steps.

  (See Figure 6(c).) Phase 3 of u ends the time slot before w becomes covered, when the rest of the nodes in A at the beginning of this phase are moved to A ′ . (See Figure 6(d).

Algorithm 1 : 1 for each time slot do 2 increase τ by one 3 ifTheorem 7

 11237 Dissemination algorithm for node i. I is the information I to be disseminated. The source node initially sets τ = 0.upon receiving I, τ do τ ≡ i mod n then transmit I, τ4 if τ ≥ n(α + n) then stop 5It can be proved that this quasi-oblivious algorithm solves Dissemination for arbitrary values of v max in at most n(α + n) time steps. Formally, Given an (α, β)-connected MANET where β ≥ n, there exists a quasi-oblivious deterministic protocol that solves Dissemination for arbitrary values of v max in at most n(α + n) time steps.

  Path from A to C and from A to A ′ . Path from A ′ to C ′ and from A ′ to A.

Fig. 3

 3 Fig.[START_REF] Awerbuch | Adapting to asynchronous dynamic networks[END_REF] Illustration of Theorem 5. A small empty circle depicts a point in the plane. A small black circle depicts a node. A big empty area depicts an empty set. A big shaded area depicts a non-empty set.

  End of phase 1 of u.

Fig. 4

 4 Fig.[START_REF] Baldoni | Mobility versus the cost of geocasting in mobile ad-hoc networks[END_REF] Illustration of Theorem 5. A small empty circle depicts a point in the plane. A small black circle depicts a node. A big empty area depicts an empty set. A big shaded area depicts a non-empty set.

  Configuration right before v is informed.

  End of phase 2 of u and phase 1 of v.

Fig. 5

 5 Fig.[START_REF] Bar-Yehuda | On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization[END_REF] Illustration of Theorem 5. A small empty circle depicts a point in the plane. A small black circle depicts a node. A big empty area depicts an empty set. A big shaded area depicts a non-empty set.

  Phase 3 of u, 2 of v, and 1 of w begin.

  (α, β)-connectivity preservation.

  End of phase 3 of u, 2 of v, and 1 of w.

Fig. 6

 6 Fig.[START_REF] Baumann | Parsimonious flooding in dynamic graphs[END_REF] Illustration of Theorem 5. A small empty circle depicts a point in the plane. A small black circle depicts a node. A big empty area depicts an empty set. A big shaded area depicts a non-empty set.

  Consider a partition {C o , C e } of the nodes in C so that |C o | = |C e | = (n -1)/2 and s ∈ C o . (For clarity assume that n is odd.) Nodes in C o -{s} are activated during the interval [t 1 -m + 1, t 1 ] so that some node y ∈ C o does not transmit uniquely among the nodes in C o during the interval [t 1 + 1, t 1 + m]. As proved in Lemma 2, such a node exists because the protocol is oblivious and n ≥ 8. Given that Π is a deterministic oblivious protocol known by the adversary, the adversary knows which is the node y. Nodes in C e are activated at time t 1 -m. Thus, at time t 1 all nodes in C are informed. Let t 2 > t 1 + m be the time slot when y transmits uniquely among the nodes in C o for the first time after t 1 . The adversary places y in B for all time slots in the interval [t 1 + 1, t 2 ). Additionally, for each time slot t ′ ∈ [t 1 + 1, t 2 ) where y transmits, the adversary moves to B some node z ∈ C o that transmits at t ′ to produce a collision at x. At the end of each time slot t ′ the adversary moves z back to C o . Such a node z exists since y does not transmit uniquely during the interval [t 1 + 1, t 2 ). Right before time slot t 2 , the adversary moves y back to C o precluding x from becoming covered.

  a partition {B ′ o , B ′ e } of the nodes in B ′ such that |B ′ o | = |B ′ e | = 2n/5 and s ∈ B ′ o . The nodes in B ′ o -{s} are activated for the first time during the m time slots before t 1 + α so that some node o ∈ B ′ o does not transmit uniquely among the nodes in B ′ o before the time slot t 1 +α+ m. As proved in Lemma 2, such a node exists because the protocol is oblivious and n ≥ 8. Let t 2 be the time slot when node o transmits uniquely for the first time. Nodes in B ′ e are activated for the first time at time t 1 , and reactivated (i.e. turned off for one time slot) during the m time slots before t 2 + α. Given that deactivated nodes restart the execution from scratch upon reactivation, as proved in Lemma 2 some node e ∈ B ′ e does not transmit uniquely among the nodes in B ′ e before the time slot t 2 + α + m -1.

During some periods of time a given set could be empty, we mean that x is separated (within) that distance from any point in the area designated to the set X

It may happen that two nodes receive the message at the same time. But this does not affect the correctness of the proof, it just reduces the time necessary for the problem to be solved.

Acknowledgements

We thank Martín Farach-Colton for useful discussions.

This research was supported in part by the National Science Foundation (CCF-0937829, CCF-1114930), Comunidad de Madrid grant S2009TIC-1692, Spanish MICINN grants TIN2008-06735-C02-01 and TEC2011-29688-C02-01, National Natural Science Foundation of China grant 61020106002.


H Seligman

M Lombardi

O Bohigas

T H Seligman

New evidence of GOE statistics for compound nuclear resonances

New evidence of GOE statistics for compound nuclear resonances

The nuclear data ensemble has been compiled and analysed in reference [1]. There the statistical fluctuations of level sequences, mainly coming from compound nuclear resonances, have been found in excellent agreement with the GOE (Gaussian orthogonal ensemble) prediction [START_REF] Porter | Statistical Theory of Spectral Fluctuations[END_REF]. Further analyses including amplitudes [START_REF] Bohigas | Nuclear Data for Science and Technology[END_REF], as well as higher than two-point correlations [START_REF] Bohigas | [END_REF] confirmed these findings. Yet recently additional more stringent tests were proposed concerning both level statistics [START_REF] Bohigas | Chaos and Quantum Physics[END_REF] and correlations between levels and intensities [START_REF] Lombardi | [END_REF]. In the present article we analyse the nuclear data ensemble according to these new very sensitive tests.

First consider the following result given by Dyson and Mehta [7]: If we have a GOE level sequence and if we omit every other level, we obtain two sequences each of which follows GSE (Gaussian symplectic ensemble) statistics. It is therefore possible to perform this operation on any spectrum and proceed to make statistical analysis on the two resulting spectra. This in itself may not seem very excit-ing, despite of the fact that more complicated combination of the n-point functions enter even if we only look at the two-point function of the new sequences. Yet there is more to this if we consider the square of the Fourier transforms |C(t)|2 of the spectra. This is so because the Fourier transform in the GSE case does not only have the characteristic "correlation hole" [8] at small frequencies, which is due to the long range stiffness of the spectrum, but in addition a very marked feature namely a singularity at frequency 1 [START_REF] Porter | Statistical Theory of Spectral Fluctuations[END_REF]. This singularity corresponds to oscillations that in principle can be seen in the two-level cluster function Y 2 (E) or the number variance Σ 2 (L), but are most spectacular in the Fourier transform or the two-body form factor b(t) related to the Fourier transform by |b(t) -

1| 2 = |C(t)| 2 .
Notice that by taking the absolute value of C(t), all information on higher than two-point functions disappears.

Let us recall [START_REF] Porter | Statistical Theory of Spectral Fluctuations[END_REF] that b(t) is an even function of t, and that for the GOE it reads as

b(t) = 1 -2t + t ln(1 + 2t) 0 < t < 1 -1 + t ln((2t + 1)/(2t -1)) t > 1 (1)
while for the GSE we have

b(t) = 1 -1 2 t + 1 4 t ln(|1 -t|) 0 < t < 2 0 t > 2.
(

) 2
At t = ±1, b(t) and its first two derivatives are continuous for the GOE, whereas for the GSE there is a singularity. This is connected with the fact that the oscillating term in Y 2 (E) is, for large E, of the order E -4 for a GOE and of the order E -1 for a GSE.

For the purpose of reference Fig. 1 shows [8] the square of the Fourier transform of all energy spectra compiled in the nuclear data ensemble [1]. Fig. 2 shows the square of the Fourier transform of the spectrum obtained by omitting every other level and averaged over both sequences. We find excellent agreement between the data and the GSE prediction if we disregard the speckle pattern in the Fourier transform of the data. For a long time the possible correlations between intensities and energies have been considered only by investigating their correlation coefficient. In particular, it has been found [START_REF] Bohigas | Nuclear Data for Science and Technology[END_REF] that its value, when the nuclear data ensemble is analysed, is consistent with zero, as the random matrix model predicts. Recently a marked correlation in the case of Rydberg molecules was found [START_REF] Lombardi | [END_REF] , to which the test of Ref. [START_REF] Bohigas | Nuclear Data for Science and Technology[END_REF] is not sensitive. In the same reference it was suggested to consider the Fourier transform of an intensity spectrum defined by I i δ(E -E i ) in addition to the conventional one of the energy spectrum δ(E -E i ). Here I i is the intensity that can be the square of an amplitude or the partial width of a resonance. For the GOE, amplitudes are independently distributed according to a Gaussian. This leads to a Porter-Thomas distribution for the intensities [START_REF] Porter | Statistical Theory of Spectral Fluctuations[END_REF] and to the multiplication of b(t) by a factor of 1/3 in the formula relating b(t) to |C(t)| 2 [START_REF] Lombardi | [END_REF]8]. We can study the Fourier transform of the intensity spectra of the nuclear data ensemble for those cases where partial width are available (approx. 1200 levels). The results as obtained in Ref. [START_REF] Lombardi | [END_REF] are shown in Fig. 3 and compared with the exact result. We can see the reduction of the correlation hole as expected.

The main advantage of the use of this procedure is that it is not sensitive to a lack of knowledge about Fig. 4. Smoothed Fourier transform of the Nuclear Data Ensemble omitting every other level and averaged over both sequences. Neutron width weighted spectra displaying GSE statistics curve reduced by intensity effect. Spectra have been unfolded with a second order polynomial. Gaussian smoothing with constant width (0.1 FWHM in level density units).

The theoretical curve (heavy line) has been smoothed the same way and contains no adjustable parameter. The Nuclear Data Ensemble shows no more indications of intensity spacing correlations under this test.

states with small intensities as their effect on the Fourier transform is small. The same holds for lack of experimental resolution of very close states.

The result for nuclei, shown in Fig. 3, must be seen in contrast to molecular situations were the short time behaviour of the Fourier transform depends sensitively on the channel due to correlations [START_REF] Lombardi | [END_REF]. This was shown to be strictly due to energyamplitude correlations as a random permutation of the intensities on the spectrum eliminated the deviations. Note that the entire effect can only be seen for the shortest times as b(t) rapidly approaches zero for longer times. In fact it was shown that, when the semi-classical approximation is valid (which was the case in Rydberg molecules but is extremely dubious in the case of nuclei), this energy-amplitude correlation effect appears for times shorter than the time needed in classical mechanics for the system to mix on a scale given by the wavelength, so that it has a very interesting dynamical meaning.

To have an other test we may use the above procedure of splitting the spectra into two sequences for intensity spectra. A GOE intensity spectrum analysed in this way will yield level correlations typical of a GSE, but the amplitudes will continue to be those of a GOE. Then random matrix theory predicts the same factor 1/3 weighting b(t) in the Fourier transform |C(t)| 2 which we know from the GOE itself.

The results of such an analysis for the nuclear data ensemble are shown in Fig. 4. Again we see that the nuclear spectra are quite compatible with the predicted independence of intensities and energies. Note though that in this case we must know all energy levels as the splitting of the spectrum cannot be performed without this knowledge.

Summarising we can say that new very sensitive tests for the analysis of spectral data have been applied to the nuclear data ensemble and that no disagreement with the GOE hypothesis could be detected. These findings are in line with the result of a recent controversy about the validity of statistical assumptions for neutron resonances, which also confirmed the statistical properties [9,10].

  Fig.1. Smoothed Fourier transform of the Nuclear Data Ensemble. Stick spectra displaying GOE statistics and full correlation hole. Spectra have been unfolded with a second order polynomial. Gaussian smoothing with width increasing with time (equal to 10% of time). The theoretical curve (heavy line) has been smoothed the same way and contains no adjustable parameter.

		1600
	>
	2
	<|C(t)|	800
		0
		0	1	2	3	4
				time (level density)
		2000
	>
	2
	<|C(t)|	1000
		0
		0	1	2	3	4
				time (level density)
	Preprint submitted to Physics Letters B		2 February 1994

Fig.

2

. Smoothed Fourier transform of the Nuclear Data Ensemble omitting every other level and averaged over both sequences. Stick spectra displaying GSE statistics. Spectra have been unfolded with a second order polynomial. Gaussian smoothing with constant width (0.1 FWHM in level density units). The theoretical curve (heavy line) has been smoothed the same way and contains no adjustable parameter.

  Fig.3. Smoothed Fourier transform of the Nuclear Data Ensemble. Neutron width weighted spectra displaying reduced correlation hole. Spectra have been unfolded with a second order polynomial. Average width of each spectrum has been normalized to one. Gaussian smoothing with width increasing with time (equal to 10% of time). The theoretical curve (heavy line) has been smoothed the same way and contains no adjustable parameter. The Nuclear Data Ensemble shows no indication of intensity spacing correlations under this test.

		3000
	>	2000
	2
	<|C(t)|
		1000
		0
		0	1	2	3	4
				time (level density)

Permanent address: Division de Physique Théorique, Institut de Physique Nucléaire, 91406-Orsay Cedex, France.

[START_REF] Porter | Statistical Theory of Spectral Fluctuations[END_REF] Permanent address: Laboratorio de Cuernavaca, Instituto de Física, University of Mexico (UNAM), Cuernavaca, Mexico.