Hagit Attiya

Alessia Milani ⋆⋆

Transactional Scheduling for Read-Dominated Workloads ⋆

The transactional approach to contention management guarantees atomicity by aborting transactions that may violate consistency. A major challenge in this approach is to schedule transactions in a manner that reduces the total time to perform all transactions (the makespan), since transactions are often aborted and restarted. The performance of a transactional scheduler can be evaluated by the ratio between its makespan and the makespan of an optimal, clairvoyant scheduler that knows the list of resource accesses that will be performed by each transaction, as well as its release time and duration. This paper studies transactional scheduling in the context of read-dominated workloads; these common workloads include read-only transactions, i.e., those that only observe data, and late-write transactions, i.e., those that update only towards the end of the transaction. We present the BIMODAL transactional scheduler, which is especially tailored to accommodate read-only transactions, without punishing transactions that write most of their duration, called early-write transactions. It is evaluated by comparison with an optimal clairvoyant scheduler; we prove that BIMODAL achieves the best competitive ratio achievable by a non-clairvoyant schedule for workloads consisting of early-write and read-only transactions. We also show that late-write transactions significantly deteriorate the competitive ratio of any non-clairvoyant scheduler, assuming it takes a conservative approach to conflicts.

Introduction

A promising approach to programming concurrent applications is provided by transactional synchronization: a transaction aggregates a sequence of resource accesses that should be executed atomically by a single thread. A transaction ends either by committing, in which case, all of its updates take effect, or by aborting, in which case, no update is effective. When aborted, a transaction is later restarted from its beginning.

Most existing transactional memory implementations (e.g. [START_REF] Dice | Transactional locking ii[END_REF][START_REF] Herlihy | Software transactional memory for dynamic-sized data structures[END_REF]), guarantee consistency by making sure that whenever there is a conflict, i.e. two transactions access a same resource and at least one writes into it, one of the transactions involved is aborted.

We call this approach conservative. Taking a non-conservative approach, and ensuring progress while accurately avoiding consistency violation, seems to require complex data structures, e.g., as used in [START_REF] Napper | Lock-free serializable transactions[END_REF].

A major challenge is guaranteeing progress through a transactional scheduler, by choosing which transaction to delay or abort and when to restart the aborted transaction, so as to ensure that work eventually gets done, and all transactions commit. 1 This goal can also be stated quantitatively as minimizing the makespan-the total time needed to complete a finite set of transactions. Clearly, the makespan depends on the workloadthe set of transactions and their characteristics, for example, their arrival times, duration, and (perhaps most importantly) the resources they read or modify.

The competitive approach for evaluating a transactional scheduler A calculates the ratio between the makespan provided by A and by an optimal, clairvoyant scheduler, for each workload separately, and then finds the maximal ratio [START_REF] Attiya | Transactional contention management as a non-clairvoyant scheduling problem[END_REF][START_REF] Guerraoui | Robust contention management in software transactional memory[END_REF][START_REF] Guerraoui | Toward a theory of transactional contention managers[END_REF]. It has been shown that the best competitive ratio achieved by simple transactional schedulers is Θ(s), where s is the number of resources [START_REF] Attiya | Transactional contention management as a non-clairvoyant scheduling problem[END_REF]. These prior studies assumed write-dominated workloads, in which transactions need exclusive access to resources for most of their duration.

In transactional memory, however, the workloads are often read-dominated [START_REF] Guerraoui | Stmbench7: a benchmark for software transactional memory[END_REF]: most of their duration, transactions do not need exclusive access to resources. This includes read-only transactions that only observe data and do not modify it, as well as late-write transactions, e.g., locating an item by searching a list and then inserting or deleting.

We extend the result in [START_REF] Attiya | Transactional contention management as a non-clairvoyant scheduling problem[END_REF] by proving that every deterministic scheduler is Ω(s)competitive on read-dominated workloads, where s is the number of resources. Then, we prove that any non-clairvoyant scheduler which is conservative and thus too "coarse", is Ω(m) competitive for some workload containing late-write transactions, where m is the number of cores. (These results appear in Section 3.) This means that, for some workloads, these schedulers utilize at most one core, while an optimal, clairvoyant scheduler exploits the maximal parallelism on all m cores. This can be easily shown to be a tight bound, since at each time, a reasonable scheduler makes progress on at least one transaction.

Contemporary transactional schedulers, like CAR-STM [START_REF] Dolev | CAR-STM: scheduling-based collision avoidance and resolution for software transactional memory[END_REF], Adaptive Transaction Scheduling [START_REF] Yoo | Adaptive transaction scheduling for transactional memory systems[END_REF], and Steal-On-Abort [START_REF] Ansari | Steal-on-abort: Improving transactional memory performance through dynamic transaction reordering[END_REF], are conservative, thus they do not perform well under read-dominated workloads. These transactional schedulers have been proposed to avoid repeated conflicts and reduce wasted work, without deteriorating throughput. Using somewhat different mechanisms, these schedulers avoid repeated aborts by serializing transactions after a conflict happens. Thus, they all end up serializing more than necessary in read-dominated workload, but also in what we call bimodal workload, i.e., a workload containing only early-write and read-only transactions. Actually, we show that there is a bimodal workload, for which these schedulers are at best Ω(m)competitive (Section 4).

These counter-examples motivate our BIMODAL scheduler, which has an O(s) competitive ratio on bimodal workloads with equi-length transactions. BIMODAL alternates between writing epochs in which it gives priority to writing transactions, and reading epochs in which it prioritizes transactions that have issued only reads so far. Due to the known lower bound [START_REF] Attiya | Transactional contention management as a non-clairvoyant scheduling problem[END_REF], no algorithm can do better than O(s) for bimodal traffic. BIMODAL also works when the workload is not bimodal, but being conservative it can only be trivially bound to have O(m) competitive makespan when the workload contains late-write transactions.

Contention managers [START_REF] Herlihy | Software transactional memory for dynamic-sized data structures[END_REF][START_REF] William | Advanced contention management for dynamic software transactional memory[END_REF] were suggested as a mechanism for resolving conflicts and improving the performance of transactional memories. Several papers have recently suggested that having more control on the scheduling of transactions can reduce the amount of work wasted by aborted transactions, e.g., [START_REF] Ansari | Steal-on-abort: Improving transactional memory performance through dynamic transaction reordering[END_REF][START_REF] Dolev | CAR-STM: scheduling-based collision avoidance and resolution for software transactional memory[END_REF][START_REF] Maldonado | Transaction activation: Scheduling support for transactional memory[END_REF][START_REF] Yoo | Adaptive transaction scheduling for transactional memory systems[END_REF]. These schedulers use different mechanisms, in the user space or in the operating system level, but they all end up serializing more than necessary, in read-dominated workloads.

Very recently, Dragojevic et al. [START_REF] Dragojevic | Preventing versus curing: Avoiding conflicts in transactional memories[END_REF] have also investigated transactional scheduling. They have taken a complementary approach that tries to predict the accesses of transactions, based on past behavior, together with a heuristic mechanism for serializing transactions that may conflict. They also present counter-examples to CAR-STM [START_REF] Dolev | CAR-STM: scheduling-based collision avoidance and resolution for software transactional memory[END_REF] and ATS [START_REF] Yoo | Adaptive transaction scheduling for transactional memory systems[END_REF], although they do not explicitly detail which accesses are used to generate the conflicts that cause transactions to abort; in particular, they do not distinguish between access types, and the portion of the transaction that requires exclusive access.

Early work on non-clairvoyant scheduling (starting with [START_REF] Motwani | Non-clairvoyant scheduling[END_REF]) dealt with multiprocessing environments and did not address the issue of concurrency control. Moreover, they mostly assume that a preempted transaction resumes execution from the same point, and not restarted. For a more detailed discussion, see [START_REF] Attiya | Transactional contention management as a non-clairvoyant scheduling problem[END_REF][START_REF] Dragojevic | Preventing versus curing: Avoiding conflicts in transactional memories[END_REF].

Preliminaries

Model

We consider a system of m identical cores with a finite set of shared data items {i 1 , . . . , i s }. The system has to execute a workload, which is a finite partially-ordered set of transactions Γ = {T 1 , T 2 , . . .}; the partial order among transactions is induced by their arrival times. Each transaction is a sequence of operations on the shared data items; for simplicity, we assume the operations are read and write. A transaction that only reads data items is called read-only; otherwise, it is a writing transaction.

A transaction T is pending after its first operation, and before T completes either by a commit or an abort operation. When a transaction aborts, it is restarted from its very beginning and can possibly access a different set of data items. Generally, a transaction may accesses different data items if it executes at different times. For example, a transaction inserting an item at the head of a linked list, may access different memory locations when accessing the item at the head of the list at different times.

The sequence of operations in a transaction must be atomic: if any of the operations takes place, they all do, and that if they do, they appear to other threads to do so atomically, as one indivisible operation, in the order specified by the transaction. Formally, this is captured by a classical consistency condition like serializability [START_REF] Papadimitriou | The serializability of concurrent database updates[END_REF] or the stronger opacity condition [START_REF] Guerraoui | On the correctness of transactional memory[END_REF].

Two overlapping transactions T 1 and T 2 have a conflict if T 1 reads a data item X and T 2 executes a write access to X while T 1 is still pending, or T 1 executed a write access to X and T 2 accesses X while T 1 is still pending. Note that a conflict does not mean that serializability is violated. For example, two overlapping transactions [read(X), write(Y )] and [write(X), read(Z)] can be serialized, despite having a conflict on X. We discuss this issue further in Section 3.

Transactional Schedulers and Measures

The set of data items accessed by a transaction, i.e., its data set, is not known when the transaction starts, except for the first data item that is accessed. At each point, the scheduler must decide what to do, knowing only the data item currently requested and if the access wishes to modify the data item or just read it.

Each core is associated with a list of transactions (possibly the same for all cores) available to be executed. Transactions are placed in the cores' list according to a strategy, called insertion policy. Once a core is not executing a transaction, it selects, according to a selection policy, a transaction in the list and starts to execute it. The selection policy determines when an aborted transaction is restarted, in an attempt to avoid repeated conflicts. A scheduler is defined by its insertion and selection policies.

Definition 1 (Makespan).

Given scheduler A and a workload Γ , makespan A (Γ ) is the time A needs to complete all the transactions in Γ .

Definition 2 (Competitive ratio). The competitive ratio of a scheduler A for a workload Γ , is makespan A (Γ ) makespan Opt (Γ ) , where OPT is the optimal, clairvoyant scheduler that has access to all the characteristics of the workload. The competitive ratio of A is the maximum, over all workloads Γ , of the competitive ratio of A on Γ .

We concentrate on "reasonable" schedulers, i.e., ones that utilize at least one core at each time unit for "productive" work: a scheduler is effective if in every time unit, some transaction invocation that eventually commits executes a unit of work (if there are any pending transactions).

We associate a real number τ i > 0 with each transaction T i , which is the execution time of T i when it runs uninterrupted to completion.

Theorem 1. Every effective scheduler

A is O(m)-competitive.
Proof. The proof immediately follows from the fact that for any workload Γ , at each time unit some transaction makes progress, since A is effective. Thus, all transactions complete no later than time Ti∈Γ τ i (as if they are executed serially). The claim follows since the best possible makespan for Γ , when all cores are continuously utilized, is

1 m Ti∈Γ τ i . ⊓ ⊔
We say that transaction T i is early-write if the time from its first write access until its completion, denoted ω i , is at least half of its duration (any other constant can be used, in fact). Formally, 2ω i > τ i .

We pick a small constant α > 0 and say that a transaction T i is late-write if ω i ≤ ατ i , i.e., the transaction needs exclusive access to resources during at most an α-fraction of its duration. For a read-only transaction, ω i = 0.

A workload Γ is bimodal if it contains only early-write and read-only transactions; said otherwise, if a transaction writes, then it does so early in its execution.

Lower Bounds

We start by proving a lower bound of Ω(s) on the competitiveness achievable by any scheduler, where s is the number of shared data items, for late-write workloads, including only late-write transactions. This complements the lower bound proved in [START_REF] Attiya | Transactional contention management as a non-clairvoyant scheduling problem[END_REF], for workloads that include only early-write transactions.

We use R h , W h to denote (respectively) a read and a write access to data item i h .

Theorem 2. There is a late-write workload Γ , such that every deterministic scheduler A is Ω(s)-competitive on Γ .

Proof. To prove our result we first consider the scheduler A to be work-conserving, i.e., it always runs a maximal set of non conflicting transactions [START_REF] Attiya | Transactional contention management as a non-clairvoyant scheduling problem[END_REF], and then show how to remove this assumption. Assume that s is even and let q = s 2 . The proof uses an execution of q 2 = s 2 4 equallength transactions, described in Table 1. Since transactions have all the same duration, we normalize it to 1. The data items {i 1 , . . . , i s } are divided into two disjoint sets, D 1 = {i 1 , . . . , i q } and D 2 = {i q+1 , i q+2 , . . . , i 2q }. Each transaction reads q data items in D 1 and reads and writes to one data item in D 2 . For every i j ∈ D 2 , q transactions read and write to i j (the ones in row jq in Table 1).

All transactions are released and available at time t 0 = 0. The scheduler A knows only the first data item requested and if it is accessed for read or write. The data item to be read and then written is decided by an adversary during the execution of the algorithm in a way that forces many transactions to abort. Since the first access of all transactions is a read and A is work conserving, A executes all q 2 transactions.

Let time t 1 be the time at which all q 2 transactions have executed their read access to the data item they will then write, but none of them has already attempt to write. It is simple to see that transactions can be scheduled for this to happen. Then, at some point after t 1 all transactions attempt to write but only q of such transactions can commit (the transactions in a single column of Table 1). Otherwise, serializability is violated. All other transactions abort.

When restarted, all of them write to the same data item i 1 , i.e., [R 1 ,. . .,R q ,R q+1 ,W 1 ]. This implies that after the first q transactions commit (any set in a column), having run in parallel, the remaining q 2q transactions end up being executed serially (i.e., even though they are run in parallel only one of them can commit at each time). So, the makespan of the on-line algorithm is 1 + q 2q.

On the other hand, an optimal scheduler OPT executes the workload as follows: at each time τ i with i ∈ {0, . . . , q -1}, OPT will execute the set of transactions depicted in column i + 1 in Table 1. Thus, OPT achieves makespan q. Therefore, the competitive ratio of any work-conserving algorithm is 1+q 2 -q q = Ω(s).

As in [START_REF] Attiya | Transactional contention management as a non-clairvoyant scheduling problem[END_REF] to remove the initial assumption that the scheduler is work conserving, we modify the requirement of data items in the following way: if a transaction belonging to Γ is executed after time q then it requests to write into i 1 as done in the above proof when a transaction is restarted. Otherwise, it requests the data items as in Table 1. Thus the online scheduler will end up serializing all transactions executed after time q.

On the other hand, the optimal offline scheduler is not affected by the above change in data items requirement since it executes all transactions by time q. The claim follows.

⊓ ⊔

Next, we prove that when the scheduler is too "coarse" and enforces consistency by aborting one conflicting transaction whenever there is a conflict, even if this conflict does not violate serializability, the makespan it guarantees is even less competitive. We remark that all prior competitive results [START_REF] Attiya | Transactional contention management as a non-clairvoyant scheduling problem[END_REF][START_REF] Guerraoui | Robust contention management in software transactional memory[END_REF][START_REF] Guerraoui | Toward a theory of transactional contention managers[END_REF] also assume that the scheduler is conservative. Formally, Definition 3. A scheduler A is conservative if it aborts at least one transaction in every conflict.

Note that prominent transactional memory implementations (e.g., [START_REF] Dice | Transactional locking ii[END_REF][START_REF] Herlihy | Software transactional memory for dynamic-sized data structures[END_REF]) are conservative.

Theorem 3. There is a late-write workload Γ , with α < 1 m , such that every deterministic conservative scheduler A has Ω(m)-competitive makespan on Γ .

Proof. Consider a workload Γ with m late-write transactions, all available at time t = 0. Each transaction T ∈ Γ first reads items {i 1 , i 2 , . . . i s-1 }, and then modifies item i s , i.e., T i = [R 1 , . . . , R s-1 , W s ], for every i ∈ {1, . . . , m}. All transactions have the same duration d, and they do not modify their data set when running at different times.

The scheduler A will immediately execute all transactions. At time dǫ all transactions will attempt to write into i s . Since A is conservative, only one of them commits, while the remaining m -1 transactions abort. Aborted transactions will be restarted later, and each transaction will write into i 1 instead of i s . Thus, all the remaining transactions have to be executed serially in order not to violate serializability. Since A executes all transactions in a serial manner, makespan A (Γ )= m i=1 d i = md. On the other hand, the optimal scheduler OPT has complete information on the set of transactions, and in particular, OPT knows that at time d-ǫ, each transaction attempts to write to i s . Thus, OPT delays the execution of the transactions so that conflicts do not happen: at time t 0 = 0, only transaction T 1 is executed; for every i ∈ {2, . . . , m}, T i starts at time t + (i -1)ǫ, where ǫ = αd. (See Figure 1.) T1: T3: T2: Tm:

1 R1 R2 R3 1 + 2ǫ 1 + ǫ Ws commit d -ǫ d R1 R2 Rs-1 R3 Ws commit R1 R2 Rs-1 Ws commit d + ǫ R1 Rs-1 Ws commit d + (m -1)ǫ
Fig. 1. The execution used in the proof of Theorem 3.

Thus, makespan Opt (Γ )=d + (m -1)ǫ, and the competitive ratio is

md d+(m-1)dα > m 1+α•m ≥ m 2 . ⊓ ⊔
In fact, the makespan is not competitive even relative to a clairvoyant online scheduler [START_REF] Dragojevic | Preventing versus curing: Avoiding conflicts in transactional memories[END_REF], which does not know the workload in advance, but has complete information on a transaction once it arrives, in particular, the set of resources it accesses.

As formally proved in [START_REF] Dragojevic | Preventing versus curing: Avoiding conflicts in transactional memories[END_REF], knowing at release time, the data items a transaction will access, for transactions which do not change their data sets during the execution, facilitates the transactional scheduler execution and greatly improves performance.

Dealing with Read-Only Transactions: Motivating Example

Several recent transactional schedulers [START_REF] Ansari | Steal-on-abort: Improving transactional memory performance through dynamic transaction reordering[END_REF][START_REF] Dolev | CAR-STM: scheduling-based collision avoidance and resolution for software transactional memory[END_REF][START_REF] Maldonado | Transaction activation: Scheduling support for transactional memory[END_REF][START_REF] Yoo | Adaptive transaction scheduling for transactional memory systems[END_REF] attempt to reduce the overhead of transactional memory, by serializing conflicting transactions. Unfortunately, these schedulers are conservative and so, they are Ω(m)-competitive. Moreover, they do not distinguish between read and write accesses and do not provide special treatment to read-only transactions, causing them not to work well also with bimodal workloads.

There are bimodal workloads of m transactions (m is the number of cores) for which both CAR-STM and ATS have a competitive ratio (relative an optimal offline scheduler) that is at least Ω(m). This is because both CAR-STM and ATS do not ensure the socalled list scheduler property [START_REF] Garey | Bound for multiprocessor scheduling with resource constraints[END_REF], i.e., no thread is waiting to execute if the resource it needs are available, and may cause a transaction to wait although the resources it needs are available. In fact, to reduce the wasted work due to repeated conflicts, these schedulers may serialize also read-only transactions.

Steal-on-Abort (SoA) [START_REF] Ansari | Steal-on-abort: Improving transactional memory performance through dynamic transaction reordering[END_REF], in contrast, allows free cores to take transactions from the queue of another busy core; thus, it ensures the list scheduler property, trying to execute as many transactions concurrently as possible. However, in an overloaded system, with more than m transactions, SoA may create a situation in which a starved writing transaction can starve read-only transactions. This yields bimodal workloads in which the makespan of Steal-on-Abort is Ω(m) competitive, as we show below. (Stealon-abort [START_REF] Ansari | Steal-on-abort: Improving transactional memory performance through dynamic transaction reordering[END_REF], as well as the other transactional schedulers [START_REF] Dolev | CAR-STM: scheduling-based collision avoidance and resolution for software transactional memory[END_REF][START_REF] Maldonado | Transaction activation: Scheduling support for transactional memory[END_REF][START_REF] Yoo | Adaptive transaction scheduling for transactional memory systems[END_REF], are effective, and hence they are O(m)-competitive, by Theorem 1.)

The Steal-On-Abort (SoA) scheduler: Application threads submit transactions to a transactional threads pool. Each transactional thread has a work queue where available transactions wait to be executed. When new transactions are available they are distributed among the transactional threads' queues in round robin.

When two running transactions T and T ′ conflict, the contention manager policy decides which to commit. The aborted transaction, say T ′ , is then "stolen" by the transactional thread executing T and is enqueued in a designated steal queue. Once the conflicting transaction commits, the stolen transaction is taken from the steal queue and inserted to the work queue. There are two possible insertion policies: T ′ is enqueued either in the top or in the tail of the queue. Transactions in a queue are executed serially, unless they are moved to other queues. This can happen either because a new conflict happen or because some transactional thread becomes idle and steals transactions from the work queue of another transactional thread (chosen uniformly at random) or from the steal queue if all work queues are empty.

SoA suggests four strategies for moving aborted transactions: steal-tail, steal-head, steal-keep and steal-block. Here we describe a worst case scenario for the steal-tail strategy, which inserts the transactions aborted because of a conflict with a transaction T , at the tail of the work queue of the transactional thread that executed T , when T completes. Similar scenarios can be shown for the other strategies.

The SoA scheduler does not specify any policy to manage conflicts. In [START_REF] Ansari | Steal-on-abort: Improving transactional memory performance through dynamic transaction reordering[END_REF], the SoA scheduler is evaluated empirically with three contention management policies: the simple Aggressive and Timestamp contention managers, and the more sophisticated Polka contention manager. 2 Yet none of these policies outperform the others, and the optimal one depends on the workload. This result is corroborated by an empirical study that has shown that no contention manager is universally optimal, and performs best in all reasonable circumstances [START_REF] Guerraoui | Polymorphic contention management[END_REF] . Moreover, while several contention management policies have been proposed in the literature [START_REF] Guerraoui | Toward a theory of transactional contention managers[END_REF][START_REF] William | Advanced contention management for dynamic software transactional memory[END_REF], none of them, except Greedy [START_REF] Guerraoui | Toward a theory of transactional contention managers[END_REF], has nontrivial provable properties.

Thus, we consider the SoA scheduler with a contention management policy based on timestamps, like Greedy [START_REF] Guerraoui | Toward a theory of transactional contention managers[END_REF] or Timestamp [START_REF] William | Advanced contention management for dynamic software transactional memory[END_REF]. These policies do not require costly data structures, like the P olka policy. Our choice also provides a fair comparison with CAR-STM, which embeds a contention manager based on timestamps.

Theorem 4. Steal-on-Abort with steal-tail has Ω(m)-competitive makespan for some bimodal workload.

Proof. We consider a workload Γ with n = 2m -1 unit-length transactions, two writing transactions and 2m -3 read-only transactions, depicted in Table 2. At time t 1 = 0, a writing transaction U 1 =[R 1 ,W 1 ] is available and at time t 1 + ǫ, when the writing transaction is executing its first access, m-1 read-only transactions [R 2 ,R 1 ,R 3 ] become available. Let S 1 denote this set of read-only transactions.

All the transactions are immediately executed. But in their second access, all the read-only transactions conflict with the writing transaction U 1 . All the read-only transactions are aborted, because U 1 have a greater priority than these latter, and they are inserted in the work queue of the transactional thread where U 1 was in execution.

At time t 2 , immediately before U 1 completes, m -1 other transactions become available: a writing transaction

U 2 =[R 1 ,W 4 ,W 3 ] and a set of m -2 read-only trans- actions [R 1 ,R 4 ], denoted S 2 .
Each of these transactions is placed in one of the idle transactional threads, as depicted in Table 2.

Immediately after time t 2 , U 2 , all the transactions in S 2 and one read-only transaction in S 1 are running. In their second access all the read-only transactions in S 2 conflict with the writing transaction U 2 . We consider U 2 to discover the conflict and to abort all the read-only transaction in S 2 . Actually, if U 2 arrives immediately before the read-only transactions, it has a bigger priority.

The aborted read-only transactions are then moved to the queue of the worker thread which is currently executing U 2 . Then, U 2 conflicts with the third access of the readonly transaction in S 1 . Thus, U 2 is aborted and it is moved to the tail of the corresponding work queue. We assume the time between cascading aborts is negligible.

In the following we repeat the above scenario, until all transactions commit. In particular, for every i ∈ {3, . . . m}, we have that immediately before time t i , there are mi + 1 read-only transactions [R 2 ,R 1 ,R 3 ] and the writing transaction U 2 in the work queue of thread 1 and m-2 read-only transactions [R 1 ,R 4 ] in the work queue of thread i -1. All the remaining threads have no transaction in their work queues. Then, at time t i , the worker thread i takes the writing transaction from the work queue of thread 1 and the other free worker threads take a read-only transaction [R 1 ,R 4 ] from the work queue of thread i -1. Thus, at each time t i , i ∈ {3, . . . m}, the writing transaction U 2 , one read-only transaction [R 2 ,R 1 ,R 3 ] and m -2 read-only transactions [R 1 ,R 4 ] are executed, but only the read-only transaction in S 1 commits.

Finally, at time t m U 2 commits, and ,hence, all read-only transactions in S 2 commit at time t m+1 .

Note that, in the scenario we built, the way each thread steals the transactions from the work queues of other threads is governed by a uniformly random distribution as requested by the Steal on Abort work-steal strategy.

Thus, makespan SoA (Γ )=m + 2. On the other hand, the makespan of an optimal offline algorithm is less than 4, because all read-only transactions can be executed in 2 time units, and hence, the competitive ratio is at least m+2 4 .

⊓ ⊔

In the following section, we present a conservative scheduler, called BIMODAL, which is O(s)-competitive for bimodal workloads. BIMODAL embeds a simple contention management policy utilizing timestamps.

The BIMODAL scheduler architecture is similar to CAR-STM [START_REF] Dolev | CAR-STM: scheduling-based collision avoidance and resolution for software transactional memory[END_REF]: each core is associated with a work dequeue (double-ended queue), where a transactional dispatcher enqueues arriving transactions. BIMODAL also maintains a fifo queue, called RO-queue, shared by all cores to enqueue transactions which abort before executing their first writing operation and that are predicted to be read-only transactions.

Transactions are executed as they are available unless the system is overloaded. BIMODAL requires visible reads in order for a conflict to be detected as soon as possible.

Once two transactions conflict, one of them is aborted and BIMODAL prohibits them from executing concurrently again and possibly repeating the conflict. In particular, if the aborted transaction is a writing transaction, BIMODAL moves it to the work dequeue of the conflicting transaction; otherwise, it is enqueued in the RO-queue.

Specifically, the contention manager, embedded in BIMODAL, decides which transaction to abort in a conflict, according to two of priority:

1. In a conflict between two writing transactions, the contention manager aborts the newer transaction. Towards this goal, a transaction is assigned a timestamp when it starts, which it retains even when it aborts, as in the greedy contention manager [START_REF] Guerraoui | Toward a theory of transactional contention managers[END_REF]. 2. To handle a conflict between a writing transaction and a read-only transaction, BI-MODAL alternates between periods in which it privileges the execution of writing transactions, called writing epochs, and periods in which it privileges the execution of read-only transactions, called reading epochs.

Below, we detail the algorithm and we provide its competitive analysis.

Detailed Description of the BIMODAL Scheduler

Transactions are assigned in round-robin to the work dequeues of the cores (inserted at their tail), starting from cores whose work dequeue is empty; initially, all work dequeues are empty. At each time, the system is in a given epoch associated with a pair (mode, ID), where mode ∈ {Reading, Writing} is the type of epoch and ID is a monotonically increasing integer that uniquely identifies the epoch. A shared variable ξ stores the pair corresponding to the current epoch and it is initially set to (Writing, 0).

When in a writing epoch i, the system moves to a reading epoch i + 1, i.e., ξ = (Reading, i + 1), if there are m transactions in the RO-queue or every work dequeue is empty. Analogously, if during a reading epoch i+1, m transactions have been dequeued from the RO-queue or this queue is empty, the system enters writing epoch i + 2, and so on. A process in the system, called ξ-manager, is responsible to managing epoch evolution and updating the shared variable ξ. The ξ-manager checks if the above conditions are verified and sets the variable ξ in a single atomic operation (e.g., using a Read-Modify-Write primitive).

A transaction T that starts in the i-th epoch, is associated with epoch i up to the time it either commits or aborts. An aborted transaction may be associated to a new epoch when restarted. Moreover, it may happen that while a transaction T , associated with epoch i, is running, the system transitions to an epoch j > i. When this happens, we say that epochs overlap. To manage conflicts between transactions associated with different epochs, we give higher priority to the transaction in the earlier epoch. Specifically, if a core executes a transaction T belonging to the current epoch i while some core is still executing a transaction T ′ in epoch i -1, and T and T ′ have a conflict, T is aborted and immediately restarted.

Writing epochs. The algorithm starts in a writing epoch. During a writing epoch, each core selects a transaction from its work dequeue (if it is not empty) and executes it. During this epoch:

1. A read-only transaction that conflicts with a writing transaction is aborted and enqueued in the RO-queue. We may have a false positive, i.e., a writing transaction T , wrongly considered to be a read-only transaction and enqueued in the RO-queue, because it has a conflict before invoking its first writing access. 2. If there is a conflict between two writing transactions T 1 and T 2 , and T 2 has lower priority than T 1 , then T 2 is inserted at the head of the work dequeue of T 1 . (As in the permanent serializing contention manager of CAR-STM.)

Reading epochs. A reading epoch starts when the RO-queue contains m transactions, or the work dequeues of all cores are empty. The latter option ensures that no transaction in the RO-queue is indefinitely, waiting to be executed. During a reading epoch, each core takes a transaction from the RO-queue and executes it. The reading epoch ends when m transactions have been dequeued from the RO-queue or this latter is empty. Conflicts may occur during a reading epoch, due to false positives or because epochs overlap. If there is a conflict between a read-only transaction and a false positive, the writing transaction is aborted. If the conflict is between two writing transactions (two false positives), then one aborts, and the other transaction simply continues its execution; as in a writing epoch, the decisions are based on their priority. Once aborted, a false positive is enqueued in the head of the work dequeue of the core where it executed.

Analysis of the BIMODAL scheduler

We first bound (from below) the makespan that can be achieved by an optimal conservative scheduler.

Theorem 5. For every workload Γ , the makespan of Γ under an optimal, conservative offline scheduler OPT satisfies makespan Opt (Γ ) ≥ max{ P ωi s , P τi m }. Proof. There are m cores, and hence, the optimal scheduler cannot execute more than m transactions in each time unit; therefore, makespan Opt (Γ ) ≥ P τi m . For each transaction T i in Γ with ω i = 0, let X fi be the first item T i modifies. Any two transactions T i and T j whose first write access is to the same item, i.e., that have X fi = X fj , have to execute the part after their write serially.

Thus, at most s transactions with ω i = 0 proceed at each time, implying that makespan Opt (Γ ) ≥ P ωi s .

⊓ ⊔

We analyze BIMODAL assuming all transactions have the same duration.

A key observation is that if a false positive is enqueued in the RO-queue and executed during a reading epoch because it is falsely considered to be a read-only transaction, either it completes successfully without encountering conflicts or it is aborted and treated as a writing transaction once restarted. Theorem 6. BIMODAL is O(s)-competitive for bimodal workloads, in which for every writing transaction T i , 2ω i ≥ τ i .

Proof. Consider the scheduling of a bimodal workload Γ under BIMODAL. Let t k be the starting time of the last reading epoch after all the work deques of cores are empty, and such that some transactions arrive after t k .

At time t k , no transactions are available in the work queues of any core, and hence, no matter what the optimal scheduler OPT does, its makespan is at least t k .

Let Γ k be the set of transactions that arrive after time t k , and let n k = |Γ k |. Since at time t k , OPT does not schedule any transaction, it will schedule new transactions to execute as they arrive. On the other hand, BIMODAL may delay the execution of new available transactions because the cores are executing the transactions in the RO-queue (if any). Since RO-queue has less than m transactions, this will take at most τ time units, where τ is the duration of a transaction (the same for all transactions). By Theorem 5,

Makespan Opt (Γ k ) ≥ 1 2 ( n k i=1 ω i s + n k i=1 τ i m ) ,
and therefore,

Makespan Opt (Γ ) ≥ t k + 1 2 ( n k i=1 ω i s + n k i=1 τ i m ) .
On the other hand, we have that

Makespan Bimodal (Γ ) ≤ t k + τ + n k i=1 4ω i + 1 m n k i=1 τ i .
The penultimate term holds because 2ω i ≥ τ i , for every writing transaction T i ∈ Γ k , and taking into account the impact of false positives during reading epochs. In fact, a writing transaction T may conflict only once during a reading epoch, because when restarted T will be treated as a writing transaction. This is just as if T is executed during a writing epoch with its duration doubled, to account for the time spent for the execution of the read-only transaction that aborted T (if there is one). The last term holds since all transactions have the same duration.

Therefore, the competitive ratio is

Makespan Bimodal (Γ ) Makespan Opt (Γ ) ≤ t k + τ + n k i=1 4ω i + 1 m n k i=1 τ i t k + 1 2 ( P n k i=1 ωi s + P n k i=1 τi m
) , which can be shown to be in O(s).

Note that if t k does not exist, we can take t k to be the time immediately before the first transaction in Γ is available, and repeat the reasoning with t k = 0 and Γ k = Γ . ⊓ ⊔

We have studied the competitive ratio achieved by non-clairvoyant transactional schedulers on read-dominated workloads. The BIMODAL transactional scheduler, presented in this paper, allows to achieve maximum parallelism on read-only transactions, without harming early-write transactions. On the other hand, we proved that the long reading periods of late-write transactions cannot be overlapped to exploit parallelism, and must be serialized if the writes at the end of the transactions are in conflict.

This last result assumes that the scheduler is conservative, namely, it aborts at least one transaction involved in a conflict. This is the approach advocated in [START_REF] Herlihy | Software transactional memory for dynamic-sized data structures[END_REF] as it reduces the cost of tracking conflicts and dependencies. It is interesting to investigate, whether less conservative schedulers can reduce the makespan and what is the cost of improving parallelism. Keidar and Perelman [START_REF] Perelman | On avoiding spare aborts in transactional memory[END_REF] prove that contention managers that abort a transaction only when it is necessary to ensure correctness have local computation that is NP-complete; however, it is not clear whether being less accurate in ensuring consistency can be done more efficiently.

Our study should be completed by considering other performance measures, e.g., the average response time of transactions.

The contention manager embedded in SwissTM [START_REF] Dragojevic | Stretching transactional memory[END_REF] is also bimodal, distinguishing between short and long transactions, and it would be interesting to see whether our analysis techniques can be applied to it.

Finally, while we have theoretically analyzed the behavior of BIMODAL, it is important to see how it compares, through simulation, with prior transactional schedulers, e.g., [START_REF] Ansari | Steal-on-abort: Improving transactional memory performance through dynamic transaction reordering[END_REF][START_REF] Dolev | CAR-STM: scheduling-based collision avoidance and resolution for software transactional memory[END_REF][START_REF] Maldonado | Transaction activation: Scheduling support for transactional memory[END_REF][START_REF] Yoo | Adaptive transaction scheduling for transactional memory systems[END_REF].

Table 1 .

 1 The set of transactions used in the proof of Theorem 2.

		1	2	. . .
	. . .	. . .	. . .	. . .	. . .
	. . .	. . .	. . .	. . .	. . .

q 1 [R1, . . .,Rq, Rq+1, Wq+1] [R1, . . .,Rq, Rq+1, Wq+1] . . . [R1, . . .,Rq, Rq+1 , Wq+1] 2 [R1, . . ., Rq,Rq+2, Wq+2] [R1, . . ., Rq,Rq+2, Wq+2] . . . [R1, . . ., Rq,Rq+2, Wq+2] i [R1, . . . ,Rq,Rq+i, Wq+i] [R1, . . . ,Rq,Rq+i, Wq+i] . . . [R1, . . . ,Rq,Rq+i, Wq+i] q [R1, . . . , Rq , R2q, W2q] [R1, . . . , Rq , R2q, W2q] . . . [R1, . . . , Rq , R2q, W2q]

It is typically assumed that a transaction running solo, without conflicting accesses, commits with a correct result[START_REF] Herlihy | Software transactional memory for dynamic-sized data structures[END_REF].

In the Aggressive contention manager, a conflicting transaction always aborts the competing transaction. In the Timestamp contention manager, each transaction is associated with the system time when it starts and the newer transaction is aborted, in case of a conflict. The Polka contention manager increases the priority of a transaction whenever the transaction successfully acquires a data item; when two transactions are in conflict, the attacking transaction makes a number of attempts equal to the difference among priorities of the transactions before aborting the competing transaction, with a exponential backoff between attempts[START_REF] William | Advanced contention management for dynamic software transactional memory[END_REF].

Acknowledgements: We would like to thank Adi Suissa for many helpful discussions and comments, Richard M. Yoo for discussing ATS, and the referees for their suggestions.

⋆ This research is partially supported by the Israel Science Foundation (grant number 953/06). ⋆⋆ On leave from Sapienza, Universitá di Roma; supported in part by a fellowship from the Lady Davis Foundation and by a grant Progetto FIRB Italia-Israele RBIN047MH9.


Martin Farach-Colton

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

Alessia Milani
email: milani@labri.fr

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

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

Martín Farach-Colton

Opportunistic Information Dissemination in Mobile Ad-Hoc Networks: Adaptiveness

Keywords: vs, Obliviousness and Randomization vs, Determinism

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

Introduction

A Mobile Ad-hoc Network (MANET) is a radio network model defined by a set of processing nodes that move in an environment. The communication is node-to-node by fixed-radius radio transmission, and does not rely on any underlying communication infrastructure (such as routers, access points, etc.). Therefore, MANETs are modeled as graphs where edges are defined between nodes within communication radius. Nodes are assumed to have a synchronous clock, in that they have a uniform time step, but they may fail and reboot at any time, so there is no global notion of a fixed time step. We study the complexity of the Dissemination problem [START_REF] Fernández Anta | Opportunistic information dissemination in mobile ad-hoc networks: The profit of global synchrony[END_REF] in MANETs. The Dissemination problem is that of distributing a piece of information initially held by some source node to a given set of nodes in the network. The Dissemination problem is a generalization of several fundamental problems in distributed systems, e.g. Broadcast, Multicast, Routing, etc., depending on the choice of receiving nodes.

The complexity of information dissemination problems depends on the mobility assumptions one makes, becoming more tractable as more assumptions are made about the mobility [START_REF] Clementi | Communication in dynamic radio networks[END_REF][START_REF] Fernández Anta | Opportunistic information dissemination in mobile ad-hoc networks: The profit of global synchrony[END_REF][START_REF] Kuhn | Distributed computation in dynamic networks[END_REF]. However, overly strong assumptions about node mobility may not be realistic. Several mobility models have been proposed as a compromise, attempting to be as general as possible while still tractable. These include delay-tolerant networks [START_REF] Fall | A delay-tolerant network architecture for challenged internets[END_REF] and opportunistic networks [START_REF] Pelusi | Opportunistic networking: data forwarding in disconnected mobile ad hoc networks[END_REF]. Any mobility model translates into a model for edge formation/dissolution since edge connectivity depends on Euclidean distance. Thus, mobility models typically have an edge-connectivity flavor, as follows: For every pair of nodes u, v, a message can reach node v from node u in any window of t steps. That is, there may not be any point in time when there is a path from u to v, but as edges appear and disappear over time, there is a sequence of edges that can be taken to get from u to v (a chrono-path ). Any network with mobility model that requires such connectivity is said to allow opportunistic communication. Models differ, for example, in how long they require individual edges to exist, since radio communication cannot be guaranteed in any particular time step, due to collisions.

In this paper we define a class of MANETs, where nodes can move with bounded speed in a plane, communication between nodes occurs over a collisionprone single channel, and which enforces opportunistic communication, as follows. 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 reestablish connectivity) within α steps.

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 profit 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 information 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] 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].

Our Results. The main contribution of this work concerns negative results. We prove various bounds for probabilistic algorithms for the Dissemination problem, parametrized by α and β, for bounded speed of movement. Our lower bounds show that the (relatively easy) upper bounds shown are asymptotically tight, for any α/β ∈ O(1). In the classic paper of Kowalski and Pelc [START_REF] Kowalski | Time complexity of radio broadcasting: adaptiveness vs. obliviousness and randomization vs. determinism[END_REF], the authors studied the impact of randomization and adaptiveness on the time complexity of solving the Broadcast problem in static Radio Networks. We follow that fruitful line of research for the MANET model of dynamic Radio Networks and follow up on our work on deterministic algorithms [START_REF] Fernández Anta | Opportunistic information dissemination in mobile ad-hoc networks: The profit of global synchrony[END_REF] for this problem.

We classify our results according to the type of randomized protocol considered. (Formal definitions are left to the full version of this paper for brevity.) In oblivious randomized protocols [START_REF] Chlebus | Randomized communication in radio networks[END_REF][START_REF] Kowalski | Time complexity of radio broadcasting: adaptiveness vs. obliviousness and randomization vs. determinism[END_REF], the protocol has access to a sequence of random variables at each node which are independent of the execution of the algorithm and mutually independent. We define locally adaptive randomized algorithms as a generalization of oblivious protocols in that the random variables at each node are independent of the execution but may be mutually dependent. Orthogonally, in fair randomized protocols [START_REF] Chlebus | Randomized communication in radio networks[END_REF][START_REF] Farach-Colton | Lower bounds for clear transmissions in radio networks[END_REF] all nodes transmit with the same probability during each time step.

Let s be the source node of the information to be distributed, and let T be the set of target nodes for this information. We say that a node is informed if it has the information. Let I t be the set of informed nodes at time t, and Ît = ∪ i≤t I i . Let C t = T ∩ Ît be the set of covered nodes. The algorithm terminates at time step t if T = C t .

Here, we show an existential lower bound of Ω((n log(1/ε))/ log n) on the time to cover a new node with probability 1 -ε for fair protocols. We show an existential lower bound of Ω(n/ log n) on the time to cover a new node, for oblivious protocols with high probability, and for locally adaptive protocols in expectation.

A second collection of results lower bound the time required to complete Dissemination. We show that it takes Ω(αn + n 2 / log n) time steps to solve the problem, with probability p ≥ 2 -n/2 for fair and oblivious protocols, and in expectation for locally adaptive protocols.

Finally, we show that a straightforward protocol solves Dissemination in O(αn + (1 + α/β)n 2 / log n) time, with probability p ≥ 1 -e -(n-1)/4 . Surprisingly, this bound holds for any value of α ≥ 0, β > 0, arbitrarily large speed of movement, and arbitrary activation schedules. In this protocol, informed nodes always transmit with the same probability. Observe that, when α/β = O(1), the time bound is asymptotically optimal for any of the protocol classes studied, which is rather surprising, given the simplicity of the protocol.

Table 1 summarizes the Dissemination results of this paper, together with the deterministic bounds from [START_REF] Fernández Anta | Opportunistic information dissemination in mobile ad-hoc networks: The profit of global synchrony[END_REF]. The first important observation is that there randomized deterministic [START_REF] Fernández Anta | Opportunistic information dissemination in mobile ad-hoc networks: The profit of global synchrony[END_REF] lower bounds oblivious Ω `αn + n is no gap between oblivious and locally adaptive protocols. The lower bounds derived match the upper bound shown using a fair oblivious protocol, for any α/β ∈ O(1). The second observation is that randomization reduces the time complexity of the problem by a linear factor in the oblivious case and by a logarithmic factor in the adaptive case (for reasonably small values of α).

It is important to note that all lower bounds in this paper hold even without node failures and with simultaneous node activation, whereas non-simultaneous activation was crucial in showing a separation between obliviousness and adaptiveness for deterministic protocols [START_REF] Fernández Anta | Opportunistic information dissemination in mobile ad-hoc networks: The profit of global synchrony[END_REF]. On the other hand, it is fair to notice that the adaptive class of protocols considered in [START_REF] Fernández Anta | Opportunistic information dissemination in mobile ad-hoc networks: The profit of global synchrony[END_REF] is more general, and the constraints on speed assumed to prove the lower bounds are more restrictive.

Roadmap. The rest of this paper is structured as follows. In Section 2 we overview related work. The model used is given in Section 3. In Sections 4 and 5 we present our lower bounds, and the upper bound is proved in Section 6.

Previous Work

The closest work to this paper is [START_REF] Fernández Anta | Opportunistic information dissemination in mobile ad-hoc networks: The profit of global synchrony[END_REF] where we studied deterministic Dissemination in MANETs. The impact of randomization and adaptiveness on the time complexity of Dissemination was studied for the Broadcast problem in static Radio Networks in the paper of Kowalski and Pelc [START_REF] Kowalski | Time complexity of radio broadcasting: adaptiveness vs. obliviousness and randomization vs. determinism[END_REF]. Here, we follow that fruitful line of research for MANETs.Our results also contribute to understand the impact of mobility in the solvability of problems in Radio Networks. The results in [START_REF] Kowalski | Time complexity of radio broadcasting: adaptiveness vs. obliviousness and randomization vs. determinism[END_REF] show that in static networks an adaptive algorithm performs better than an oblivious one, independently of randomization and provided that nodes are synchronized. In [START_REF] Fernández Anta | Opportunistic information dissemination in mobile ad-hoc networks: The profit of global synchrony[END_REF], we show that adaptiveness helps for deterministic Dissemination in MANETs, but only if nodes are not synchronized. We prove here that for randomized algorithms, adaptiveness does not help (for any α/β ∈ O(1)) if the algorithm is fair or if we restrict to local adaptiveness. We structure the rest of the related work in terms of model, problem and bounds.

Model. MANETs are frequently assumed to be always connected, but the topology may vary in time provided that a link remains stable sufficiently long [START_REF] Baldoni | The impact of mobility on the geocasting problem in mobile ad-hoc networks: Solvability and cost[END_REF]. Less restrictive models have been proposed for Dynamic Networks, but the topology may be non-embeddable in R 2 [START_REF] Clementi | Communication in dynamic radio networks[END_REF][START_REF] Kuhn | Gradient clock synchronization in dynamic networks[END_REF][START_REF] Kuhn | Distributed computation in dynamic networks[END_REF]. In [START_REF] Kuhn | Gradient clock synchronization in dynamic networks[END_REF][START_REF] Kuhn | Distributed computation in dynamic networks[END_REF] a model for Dynamic Networks is proposed in which, for any T consecutive rounds, there is a stable connected spanning graph. Our connectivity assumptions are weaker given that the network may be always partitioned and communication is only opportunistic. In [START_REF] Clementi | Communication in dynamic radio networks[END_REF] the communication is opportunistic, but for an arbitrary adversary limited (in terms of our model) to α = 0 and β = 1. In [START_REF] Fernández Anta | Opportunistic information dissemination in mobile ad-hoc networks: The profit of global synchrony[END_REF] communication is opportunistic and the connectivity model is weak, although depends on the protocol.

Bounds. Protocols that do not rely on knowledge of topology may allow node mobility. Topology-independent randomized protocols with theoretical guarantees have been studied, for Gossiping in [START_REF] Chrobak | Fast broadcasting and gossiping in radio networks[END_REF] showing O(n log 4 n) expected time and for Broadcast in [START_REF] Mellier | A mobility-management mechanism for broadcasting in unknown mobile ad hoc networks[END_REF] showing O(n log n) expected rounds. Both protocols require strong connectivity during all the execution and the latter additionally requires collision detection. The first randomized Broadcast protocol for Radio Networks was presented in [START_REF] Bar-Yehuda | On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization[END_REF]. The protocol works in O((D + log n/ε) log n) time with probability at least 1 -ε, where D is the diameter of the network. More recently, the expectation to solve Broadcast was upper bounded by O(D log(n/D) + log 2 n) in [START_REF] Czumaj | Broadcasting algorithms in radio networks with unknown topology[END_REF][START_REF] Kowalski | Broadcasting in undirected ad hoc radio networks[END_REF] for adaptive algorithms, and by O(n min{D, log n}) in [START_REF] Kowalski | Time complexity of radio broadcasting: adaptiveness vs. obliviousness and randomization vs. determinism[END_REF] for oblivious protocols. None of these protocols is resilient to mobility. On the negative results side, a lower bound of Ω(D log(n/D)) was derived in [START_REF] Kushilevitz | An Ω(D log(N/D)) lower bound for broadcast in radio networks[END_REF] for the expected time for any randomized Broadcast protocol and a lower bound of Ω(log 2 n) in [START_REF] Alon | A lower bound for radio broadcast[END_REF], matching together the upper bound in [START_REF] Czumaj | Broadcasting algorithms in radio networks with unknown topology[END_REF][START_REF] Kowalski | Broadcasting in undirected ad hoc radio networks[END_REF]. Later on, it was shown in [START_REF] Kowalski | Time complexity of radio broadcasting: adaptiveness vs. obliviousness and randomization vs. determinism[END_REF] that, for every oblivious randomized Broadcast protocol, there exists a static network such that the protocol takes time in Ω(n) with probability at least 1/2 to complete Broadcast. Given that a static network is a particular case of a MANET, these lower bounds apply to our setting. Nevertheless, we improve these bounds here by exploiting mobility.

Communication techniques to solve Dissemination, such as flooding, have been studied for Dynamic Networks. Only upper bounds apply to MANETs since the topology in Dynamic Networks may be non-geometric. A straightforward protocol was proved [START_REF] Clementi | Communication in dynamic radio networks[END_REF] to complete Broadcast with high probability in O(n 2 / log n) steps in Dynamic Networks where α = 0 and β = 1. Here we show the same upper bound for MANETs but parameterized in arbitrary α ≥ 0 and β > 0. Since MANET is a sub-class of Dynamic Networks, our lower bounds are valid for the more general class.

Model

We consider a MANET formed by a set V of n mobile nodes deployed in R 2 with the Euclidean distance metric. It is assumed that each node has data-processing and radio-communication capabilities, and a unique identity.

Time. Time is slotted as a sequence of intervals, each of length t long enough to transmit (resp. receive) the information to be disseminated. Computations are assumed to take negligible time. Each node is equipped with a clock that ticks at the same uniform rate 1/t. All node's ticks are assumed to be in phase (as in [START_REF] Roberts | Aloha packet system with and without slots and capture[END_REF]). Throughout the paper, we use the term time slot to refer to a global time of reference, and the term time step to refer to the time reference local to a node.

Node Activation. We say that a node is active if it is up and running, and inactive otherwise. Due to various events (failures, recharging batteries, etc.) nodes may become inactive and be re-activated. We call the temporal sequence of activation and deactivations of a node the activation schedule. We assume that a node is activated in the boundary between two consecutive time slots. If a node is activated between t -1 and t we say that it is activated at slot t, and it is active in t.

Node Memory. Upon activation, a node immediately starts running an algorithm previously stored in its hardware. We consider two scenarios regarding node memory. If an inactive node does not lose its memory, we assume that it continues the execution of the algorithm from the failing step upon reactivation. If memory is lost, we assume that it restarts the algorithm from scratch.

Radio Communication. Nodes communicate via a collision-prone single radio channel without collision detection and fixed radius of transmission r. An active node u receives a transmission from a neighbor (a node within radius) v at time slot j if and only if v is the only node in u's neighborhood (including u itself) transmitting at time slot j. We say in this case that the transmission was successful , or unique among the neighbors of u.

Adversary. We assume the presence of an adversary that controls each node movement restricted to the speed and the (α, β)-connectivity constraints. For the upper bound only, we further assume that the adversary controls the activation schedule (including failures). This adversary is adaptive, in the sense that it makes decisions at the end of each time slot with access to all nodes' internal state, but without access to future random bits.

Link Stability Lower Bounds

Link stability assumptions are crucial in solving any Dissemination problem. In our model, such characteristic is parameterized with β. In this section, we relate link stability to the worst-case running time and the probability of solving Geocast, an instance of Dissemination. In Geocast, a node x is a target of the information if and only if, at the initial time, 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. Notably, exploiting fairness, it is possible to quantify such relation no matter how strong are the stability guarantees (that is for any β > 0), which we do in the first theorem.

Theorem 1. For any v max > 0, d > r, 0 < ε < 1, α ≥ 0, β > 0, any k, c ∈ N + , such that 45 ≤ k < n, and for any fair randomized protocol Π for Geocast, there exists an (α, β)-connected MANET formed by a set V of n nodes running Π such that, if T ≤ k log 4 (1/ε)/(4 log k), within cT steps after k nodes are covered, with probability at least ε c , no new node is covered, even if all nodes are activated simultaneously and do not fail.

Proof. Consider three sets of nodes A, B, and B ′ deployed in the plane, each set deployed in an area of size ξ arbitrarily small, such that 0 < ξ < r and d ≥ r + ξ. (An illustration is left to the full version of this paper for brevity.) 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 B ′ , and every node in A is placed at some distance r < δ ≤ r + ξ from every node in B ′ . Also, ξ is set appropriately so that a node can move ξ distance in one time slot without exceeding v max .

Initially, the adversary places k -1 nodes in the set B ′ including the source, an arbitrary node y in the set B, and the remaining n -k nodes in set A. Node y preserves (α, β)-connectivity forever. At the beginning of the first time slot all nodes are activated. Let t be the first time slot when the informed source transmits and, hence, all the nodes in B ∪ B ′ become informed. (If this event never happens the claim of the theorem holds trivially.) The adversary does not move any nodes until then. Given that d ≥ r + ξ, the nodes in A must become informed to solve the problem.

After time slot t, the adversary moves the nodes according to protocol Π as follows. For each time slot t ′ > t where nodes transmit with probability at least 4 log k/k, the adversary moves all nodes in B ′ to B. At the end of time slot t ′ the adversary moves all nodes in B but y back to B ′ , and the procedure is repeated.

We show now that within the first T ≤ ln(1/ε)k/(2 ln k) steps the nodes in A are not informed with probability at least ε. Given that the protocol is fair, in a given time slot all nodes use the same probability of transmission. Let π t ′ be the probability of transmission used in step t ′ . The probability of not achieving a successful transmission in a step t ′ is P r

f ail = 1 -i∈B π t ′ j∈B,j =i (1 - π t ′ ) = 1 -|B|π t ′ (1 -π t ′ ) |B|-1 .
We consider two cases depending on whether π t ′ is larger or smaller than 4 log k/k. For both cases it can be shown that P r f ail ≥ 4 -4 log k/k . The details are omitted in this extended abstract for brevity. Then, the probability of failing to inform the nodes in set A within the interval

[t + 1, t + T ] is P r f ail (T steps) ≥ 4 -4T log k/k ≥ ε, if T ≤ k log 4 (1/ε)/(4 log k).
Conditioned on this event, the same analysis can be applied to the subsequent interval of T steps, and inductively to each subsequent interval of T steps.

⊓ ⊔

For oblivious protocols, possibly not fair, it is shown in the following theorem that, if the link stability guarantees are not strong enough, there exists some configuration where new nodes are not covered with positive probability. The proof, left to the full version of this paper for brevity, uses the adversarial configuration of Theorem 1. However, given that nodes running oblivious protocols may use different probabilities of transmission in a given time slot, in order to preserve the (α, β)-property the node y has to be chosen more carefully. Roughly, the intuition on how y is chosen is the following. We consider each interval of β time slots separately. It is useful to picture one interval as a matrix of probabilities of transmission, one column for each slot of the interval and one row for each node in B ∪ B ′ . Let the columns where the sum over all rows is "small enough" be called quiet, and noisy otherwise. There exists a row where the sum along quiet columns is also "small enough". The adversary chooses y to be the node that corresponds to that row because: (a) it is unlikely that y transmits in a quiet slot; and (b) it is unlikely that exactly one of all nodes transmits in a noisy slot.

Theorem 2. For any v max > 0, d > r, α ≥ 0, β > 0, any k, c ∈ N + , such that e 3 ≤ k < n, and any oblivious randomized protocol Π for Geocast, there exists an (α, β)-connected MANET formed by a set V of n nodes running Π such that if β < k/(2(1 + ln k)), within cβ steps after k nodes are covered, no new node is covered with probability at least (2e e ) -c , even if all nodes are activated simultaneously and do not fail.

We move now to locally adaptive protocols possibly not fair. Recall that the adversary is adaptive, making decisions at the end of each step with access to all the nodes' internal state, but without access to their future random bits. For this class, it is shown that if β is not large enough, there exists some configuration where it is not expected to inform a new node within the first β steps. The proof, left to the full version of this paper for brevity, uses the same adversarial configuration of Theorems 1 and 2. The intuition on how y is now chosen is similar to the previous theorem, that is, for each interval of β slots choose a node that is likely to be silent in the quiet slots of that interval. However, now the adversary does not know in advance the probabilities of transmission (the protocol is adaptive). Nevertheless, it can still compute which is the node that most likely is the correct choice for y, as we show.

Theorem 3. For any locally adaptive randomized protocol Π for Geocast, such that uninformed nodes never transmit, any v max > 0, d > r, α ≥ 0, β > 0, and any k ∈ N + , such that (2/(1 -1/e)) ξ/e < k < n, ξ 2/(1 -1/e) 2 , there exists an (α, β)-connected MANET formed by a set V of n nodes such that if β < k/(2eΓ ), for Γ ξ ln δ, δ β 2 k e/ξ , within β steps after k nodes were covered, in expectation no new node is covered, even if all nodes were activated simultaneously and do not fail.

Dissemination Lower Bounds

In this section, we show that there exists an instance of Dissemination, namely Geocast, for which adversarial configurations of nodes that require a minimum number of steps exist. Theorem 4. For any n > 24, d > r, α ≥ 0, β > 0, v max > πr/(6α), and any fair randomized Geocast protocol Π, there exists an (α, β)-connected MANET of n nodes for which, in order to solve the problem with probability at least 2 -n/2 , Π takes at least αn/2+n 2 /(96 ln(n/2)) time slots, even if all nodes are activated simultaneously and do not fail.

Proof. We prove the claim for fair protocols where the probability of transmission of a node is independent among time slots. For non-independent fair protocols, the same techniques can be used to prove the same bound, with a more detailed analysis.

The following adversarial configuration and movement of nodes show the claimed lower bound. Consider four sets of nodes A, B, B ′ , and C, each deployed in an area of size ε arbitrarily small, such that 0 < ε < r and d ≥ r + ε, and four points x, x ′ , y, y ′ all placed in the following configuration. (An illustration is left to the full version of this paper for brevity.) The invariant in these sets is the following: all nodes in each set form a clique; each node in A is placed at some distance > r and ≤ r + ε from the point x and each node in B, and within distance ε from points x ′ , y ′ ; each node in B is placed within distance r of point x and the set B contains point y; each node in B ′ is placed within distance ε of each node in B and > r from points x, x ′ , y ′ and each node in A; each node in C is placed at some distance > r and ≤ r + ε from the point x and distance > r from each node in A and points x ′ , y ′ . The pairs of points x, x ′ and y, y ′ are located at distance r each.

For clarity, assume that n is even. At the beginning of the first time slot, the adversary places n/2 -1 nodes, including the source node s, in set B ′ , an arbitrary node y in point y (i.e. in set B), an arbitrary node y ′ in point y ′ , and the remaining n/2-1 nodes in the set A, and starts up all nodes. Set C is initially empty. 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 part of the dotted line, of length less than π(r + ε)/6, in α 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 the circular dotted line is upper bounded by (r + ε)/2.) Let t be the first time slot when the informed source transmits. Until time slot t, nodes are not moved, hence, (α, β)-connectivity has been preserved, and only the nodes in B ∪ B ′ become informed at time slot t. At the end of time slot t, node y is moved to B ′ and node y ′ is moved to A. Starting at time slot t + 1, the adversary moves the nodes so that only one new node at a time becomes informed while preserving (α, β)-connectivity.

First, we give a rough description of the nodes' movements, while the details will be presented later. Some of the nodes in B ′ are moved back and forth to B to produce contention. Nodes in A are moved one by one following the dotted lines in two phases, first up to point x, and afterwards to the set C. Right when a node moves to point x, another node moves from A to point x ′ so that (α, β)connectivity is preserved. While a node moves from point x to C the node in point x ′ moves to x. The procedure is repeated until all nodes in A are covered.

The movement of each node u moved from A to C is carried out in two phases of α time slots each separated by an interlude as follows.

-Phase 1. During the first α -1 time slots, u is moved from A towards the point x maintaining a distance > r and ≤ r + ε with respect to every node in B. Nodes in B ′ stay static during this interval. Given that only nodes in B ′ are informed and the distance between them and u is larger than r, u does not become covered during this interval. In the α-th time slot of this phase, u is moved to the point x, some node v ∈ A is moved to the point x ′ , and any node y ∈ B ′ is moved to B, preserving (α, β)-connectivity. The movement detailed above is produced for each node initially in A, overlapping the phases as described, until all nodes have become covered. In each phase of at least α time slots every node is moved a distance at most π(r+ε)/6+ε. Thus, setting ε appropriately, the adversarial movement described does not violate v max .

We prove now the time bound. For any time slot t in the interludes, the probability of covering the node in x is P = i∈B π t j∈B,j =i (1 -π t ) = |B|π t (1 -π t ) |B|-1 . For any t when π t < 8 ln(n/2)/n, we have P < 8 ln(n/2)/n because in this case the adversary puts just a single node in B, which is y. On the other hand, for any t when π t ≥ 8 ln(n/2)/n, we also have P ≤ (n/2) (1 -8 ln(n/2)/n) n/2-1 since 8 ln(n/2)/n < 1 for n > 24. Using that 1-x ≤ e -x for any 0 ≤ x < 1, we have P ≤ n/(2e 8(n/2-1) ln(n/2)/n ) ≤ 8 ln(n/2)/n.

Let X be a random variable denoting the number of successful transmissions along T = n 2 /(96 ln(n/2)) interlude steps. The expected number of successful transmissions is E[X] = T P ≤ n/12. Given that X is the sum of independent Poisson trials, using Chernoff bounds, For n/2 ≥ 6E[X], P r(X ≥ n/2) ≤ 2 -n/2 . We conclude that T interlude steps are necessary to cover all nodes in A with probability at least 2 -n/2 . On the other hand, Phase 1 of all nodes in A adds αn/2 steps to the overall time. Thus, the claim follows.

⊓ ⊔

We move now to prove an existential lower bound for Dissemination oblivious protocols, possibly not fair. The proof, left to the full version of this paper for brevity, uses the same adversarial configuration of Theorem 4, but given that nodes running oblivious protocols may use different probabilities of transmission in a given time slot, node y has to be chosen more carefully as in Theorem 2.

Theorem 5. For any n > 3, d > r, α ≥ 0, β > 0, v max > πr/(6α), and any oblivious randomized Geocast protocol Π, there exists an (α, β)-connected MANET of n nodes for which, Π takes at least αn/2 + n 2 /(48e ln(n/2)) time slots in order to solve the problem with probability at least 2 -n/2 , even if all nodes are activated simultaneously and do not fail.

The following theorem for locally adaptive protocols, can be proved as a straightforward repeated application of Theorem 3 to the configuration and movement of nodes described in Theorem 5, changing the minimum contention under which informed nodes are moved appropriately. The complete proof is omitted for brevity. Theorem 6. For any n > 17, d > r, α ≥ 0, β > 0, v max > πr/(6α), and any locally adaptive randomized Geocast protocol Π, there exists an (α, β)-connected MANET of n nodes for which, Π takes on expectation at least αn/2 + e 2 (e + 1) 2 n 2 /(2(e -1) 2 ln(n/2)) time slots in order to solve the problem, even if all nodes are activated simultaneously and do not fail.

Upper Bound

The Dissemination protocol analyzed in this section is fair and oblivious. The algorithm is straightforward: every informed node transmits the information at each time step with probability p = ln n/n. The same protocol was applied to Broadcast in Dynamic Networks in [START_REF] Clementi | Communication in dynamic radio networks[END_REF] yielding O(n 2 / log n) with high probability. Here, the following theorem shows an upper bound parameterized in α and β for Dissemination in MANETs. For the upper bound we assume that failing nodes do not lose the information. 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. The proof is left to the full version of this paper for brevity. Theorem 7. For any (α, β)-connected MANET where β ≥ 1, n > 2, and any v max > 0, the fair-oblivious randomized protocol described above solves Dissemination in time O(αn + (1 + α/β)n 2 / log n) time slots with probability at least 1 -e -(n-1)/4 , even if nodes are activated at different times and fail.

Table 1 .

 1 Randomized lower bounds are to achieve success probability p ≥ 2 -n/2 , except as noted. Randomized upper bounds are with probability p ≥ 1 -e -(n-1)/4 .

		2 / log n ´Ω `αn + n 3 / log n ádaptive
		Ω `αn + n 2 / log n ´exp.	Ω(αn + n 2 )
	fair	Ω `αn + n 2 / log n ´-
	upper bounds oblivious O `αn + (1 + α/β) n 2 / log n ´O(αn + n 3 log n)
	adaptive	-	O(αn + n 2 )
	fair	O `αn + (1 + α/β) n 2 / log n ´-

  Upon reaching point x, all the nodes that are not in B ∪ B ′ remain static until Phase 2. Phase 1 lasts only α slots, hence (α, β)-connectivity is preserved. -Interlude. During this interval, nodes in B ′ are moved back and forth to B according to protocol Π to produce contention as follows. For each time slot where nodes transmit with probability at least 8 ln(n/2)/n, the adversary moves all nodes in B ′ to B. At the end of the time slot the adversary moves all nodes in B -{y} back to B ′ , and the procedure is repeated until u is covered. At the end of such time slot all nodes in B are moved to B ′ and the interlude ends. During the interlude, all partitions are connected, preserving (α, β)-connectivity. -Phase 2. In the first time slot of this phase, node u moves ε distance away from node v towards set C so that v is not informed by u. During the following α -1 slots, u is moved towards the set C while v is moved from x

′ towards the point x maintaining a distance > r between them, while u maintains a distance ≤ r from B ∪ B ′ . That is, Phase 2 of node u is executed concurrently with Phase 1 of node v (hence, nodes in B ′ stay static during this interval). At the end of this phase u is placed in set C and stays static forever. At this point node v has reached point x, but u cannot cover v because all nodes in C are at distance greater than r from x. Phase 2 lasts only α slots, hence (α, β)-connectivity is preserved.

⋆ This research was supported in part by the National Science Foundation (CCF-0937829, CCF-1114930), Comunidad de Madrid grant S2009TIC-1692, Spanish MICINN grant TIN2008-06735-C02-01. ⋆⋆ We thank Seth Gilbert for triggering the development of this work asking a question at DISC 2010.