Louis-Claude Canon

Anthony Dugois

Loris Marchal

Bounding the Flow Time in Online Scheduling with Structured Processing Sets (extended version)

Keywords: Flow Time, Lower Bound, Restricted Assignment, Processing Set Restrictions, Replication, Key-Value Stores Temps de réponse, borne inférieure, allocation restreinte, ensembles d'exécution, réplication, bases de données clé-valeur

Replication in distributed key-value stores makes scheduling more challenging, as it introduces processing set restrictions, which limits the number of machines that can process a given task. We focus on the online minimization of the maximum response time in such systems, that is, we aim at bounding the latency of each task. When processing sets have no structure, Anand et al.

(Algorithmica, 2017) derive a strong lower bound on the competitiveness of the problem: no online scheduling algorithm can have a competitive ratio smaller than Ω(m), where m is the number of machines. In practice, data replication schemes are regular, and structured processing sets may make the problem easier to solve. We derive new lower bounds for various common structures, including inclusive, nested or interval structures. In particular, we consider xed sized intervals of machines, which mimic the standard replication strategy of key-value stores. We prove that EFT (Earliest Finish Time) scheduling is (3 -2/k)-competitive when optimizing max-ow on disjoint intervals of size k. However, we show that the competitive ratio of EFT is at least m -k + 1 when these intervals overlap, even when unit tasks are considered. We compare these two replication strategies in simulations and assess their eciency when popularity biases are introduced, i.e., when some machines are accessed more frequently than others because they hold popular data.

Even though overlapping intervals suer from a bad worst-case in theory, they enable clusters to reach a maximum load that is up to 50% higher than with disjoint sets.

Introduction

Since more than a decade, a variety of applications increasingly relies on key-value stores to record user data [START_REF] Featherston | Cassandra: Principles and application[END_REF], monitoring information in scientic projects [START_REF] Sicoe | A persistent back-end for the atlas tdaq online information service (p-beast)[END_REF], activity logs, metadata, statistics, etc. Such systems deal with a heavy load and while they succeed to process most requests with reasonable performance, they are prone to high delays for a few tasks (also known as the tail latency problem [START_REF] Atikoglu | Workload analysis of a large-scale key-value store[END_REF][START_REF] Dean | The tail at scale[END_REF]), which motivates the design of ecient processing strategies.

The large amount of stored data most commonly requires the replication of the key-value tuples on distributed resources. This mechanism ensures high availability in the case of a large number of requests. For instance, Dynamo [START_REF] Decandia | Dynamo: amazon's highly available key-value store[END_REF] replicates data on nodes organized as a ring in a clockwise fashion. This approach inspired other implementations such as Cassandra [START_REF] Lakshman | Cassandra: a decentralized structured storage system[END_REF], Riak KV and Project Voldemort [START_REF] Sumbaly | Serving large-scale batch computed data with project voldemort[END_REF]. However, this eligibility constraint of each task to specic machines prevents achieving optimal performance in current systems. Moreover, loads between machines tend to be heterogeneous [START_REF] Cavalcante | Popring: A popularity-aware replica placement for distributed key-value store[END_REF][START_REF] Makris | Load balancing for minimizing the average response time of get operations in distributed key-value stores[END_REF] due to varying popularities between the keys, which constitutes an additional challenge. Finally, requests vary in size and the moment they are performed cannot be predicted precisely, leading to a dicult problem.

In this paper, we focus on the scheduling problems that appear in key-value stores and other distributed systems using data replication. We consider requests for data in the key-value store as tasks to be processed on a server (or machine in the scheduling terminology). In keyvalue stores, the most common objective is to minimize the response time, which is the time between the submission of a request (the release of a task) and the moment a server answers this request (completion time of the task). In the scheduling literature, this is called the ow time. Given the dynamic nature of the problem, we focus on simple practical algorithms with competitive guarantees: we say that an online algorithm (without knowledge of future tasks) is ρ-competitive if it provides a solution that is always at most ρ times worst than an optimal oine solution. Using Graham's notation [START_REF] Graham | Optimization and approximation in deterministic sequencing and scheduling[END_REF], we consider the problem P |online-r i |F max : minimize the maximum ow time (F max ) on identical machines (P ), with tasks released over time (r i )

without prior knowledge of tasks before their release times (online). For this problem, FIFO (First In First Out) is known to be a good solution: it is (3 -2/m)-competitive on m parallel machines [START_REF] Bender | Flow and stretch metrics for scheduling continuous job streams[END_REF][START_REF] Mastrolilli | Scheduling to minimize max ow time: O-line and on-line algorithms[END_REF].

A major diculty that we need to take into account is that data are not replicated everywhere in key-value stores: only a subset of servers holds the data for a specic request. In the scheduling literature, processing set restrictions are used to model the fact that only a subset M i of machines may process some task T i . This constraint makes the problem a lot more dicult: Anand et al. [START_REF] Anand | Minimizing maximum (weighted) ow-time on related and unrelated machines[END_REF] prove a lower bound of Ω(m) on the competitive ratio of any online algorithm.

However, processing set restrictions often exhibit particular structures such as the clockwise ring used by Dynamo. In this case, data are replicated on direct neighbors forming an interval of consecutive machines, and it is unknown if this enables better results. In particular, we show that EFT, which is equivalent to FIFO for the problem P |online-r i |F max (Section 4), is a good strategy in some cases, but suers from inecient worst case performance with such realistic processing set restrictions (Section 6). Moreover, we establish the challenge of this problem, even with specic processing set restrictions, by proving lower bounds on the competitive ratio of any simple algorithm. Section 7 provides the last contribution by assessing the interaction of the popularity bias, or load imbalance, with the replication scheme in key-value stores. The rest of this paper starts by covering related works (Section 2) and presenting the model (Section 3).

RR n°9446 2 Related Work

Max-ow minimization. Bender et al. were the rst to propose the max-ow objective F max = max i (C i -r i ) [START_REF] Bender | Flow and stretch metrics for scheduling continuous job streams[END_REF][START_REF] Bender | New algorithms and metrics for scheduling[END_REF], in which C i and r i denote the completion and release times of the i-th task, respectively. They show that the well-known FIFO strategy is a (3-2/m)-competitive algorithm for minimizing max-ow on m parallel machines (note that this ratio is tight [START_REF] Mastrolilli | Notes on max ow time minimization with controllable processing times[END_REF]), and they give a lower bound of 3/2 on the online problem's competitiveness. The oine minimization of maxow is strongly NP-hard since it is a generalization of the parallel makespan problem; Mastrolilli gives an FPTAS (Fully Polynomial-Time Approximation Scheme) in unrelated setting that runs in time O(nm(n 2 /ε) m ) [START_REF] Mastrolilli | Scheduling to minimize max ow time: O-line and on-line algorithms[END_REF], where n is the number of tasks. When preemption is allowed, the problem becomes solvable on unrelated machines, as F max is a special case of L max , in which a task's deadline is set to the value of its release time (i.e., d i = r i ) [1618]. FIFO has also been shown to be (3 -2/m)-competitive for the preemptive problem [START_REF] Mastrolilli | Scheduling to minimize max ow time: O-line and on-line algorithms[END_REF]. Ambühl et al. rene the lower bound for both the preemptive and non-preemptive versions, proving that no online algorithm can achieve a ratio better than 2 -1/m [START_REF] Ambühl | On-line scheduling to minimize max ow time: an optimal preemptive algorithm[END_REF]. They provide an optimal algorithm for the preemptive case (i.e., matching the lower bound) and a lower bound of 2 for the nonpreemptive problem when m = 2, implying that FIFO is also optimal on two parallel machines. In related setting, Bansal et al. derive lower bounds of Ω(m) and Ω(log m) on the competitive ratio of Slow-Fit and Greedy [START_REF] Bansal | Minimizing maximum ow-time on related machines[END_REF]. They develop a new online algorithm, Double-Fit, that is 13.5-competitive by combining these two strategies. They also present a PTAS in unrelated environment, running in time n O(m/ε) [START_REF] Bansal | Minimizing ow time on a constant number of machines with preemption[END_REF], and an oine O(log n)-approximation [START_REF] Bansal | Minimizing ow-time on unrelated machines[END_REF].

Processing set restrictions. Various surveys have been conducted on scheduling problems involving processing set restrictions. The majority of such problems concern makespan minimization in a wide range of situations, including preemption, structured sets, release times, and so on [2326]. To the best of our knowledge, the only result on online max-ow minimization under (unstructured) processing set restrictions is due to Anand et al., who derive a lower bound

of Ω(m) on the competitive ratio of any online algorithm [START_REF] Anand | Minimizing maximum (weighted) ow-time on related and unrelated machines[END_REF].

Table 1 summarizes existing results on online max-ow minimization. In this table, P , P |M i , Q and R respectively denote parallel machines, parallel machines with processing set restrictions, related machines, and unrelated machines. Note that we have P → Q → R and P → P |M i → R, where A → B means that A is a special case of B.

Model

Even though our problem originates from key-value stores, we formally formulate it using classical scheduling terms. In particular, we want to schedule a set T of n tasks T 1 , . . . , T n on a set M of m homogeneous machines M 1 , . . . , M m (or n requests on m servers/processors). Each task T i has a release time r i ≥ 0 and a processing time p i > 0. Any machine cannot process several tasks simultaneously and preemption is not allowed. Tasks arrive in the system over time and no information (release or processing time) on task T i is available to the scheduler before time r i , which is noted online-r i . Without loss of generality, we assume tasks are numbered such that i < j =⇒ r i ≤ r j .

Processing set restrictions (or eligibility constraints) prevent tasks to be processed on any machine. Formally, a task T i can only be processed by a subset of machines M i ⊆ M and we say that M i is the processing set of T i . Let us consider the following special structures for these processing sets:

M i (interval). Interval processing sets are such that for all T i , ≥ Ω(m)

M i = {M j s.t. a i ≤ j ≤ b i } or M i = {M j s.t. j ≤ a i or b i ≤ j},
[13] Q Non-preemptive Double-Fit Online 13.5 [START_REF] Bansal | Minimizing maximum ow-time on related machines[END_REF] Slow-Fit Online ≥ Ω(m) [START_REF] Bansal | Minimizing maximum ow-time on related machines[END_REF] Greedy Online

≥ Ω(log m) [20] R Non-preemptive Bansal et al. Oine O(log n) [22] Bansal Oine, PTAS 1 + ε in n O(m/ε) [21] Mastrolilli Oine, FPTAS 1 + ε in O(nm(n 2 /ε) m ) [12] Preemptive
Legrand et al. Oine Optimal [START_REF] Legrand | Minimizing the stretch when scheduling ows of divisible requests[END_REF] Table 1: Existing results on max-ow optimization.

M i (nested). Nested processing sets are such that for all T i , T j

(with i = j), either M i ⊆ M j , M j ⊆ M i or M i ∩ M j = ∅.
M i (inclusive). Inclusive processing sets are such that for all T i , T j (with i = j), either M i ⊆ M j or M j ⊆ M i .

M i (disjoint). Disjoint processing sets are such that for all T i , T j (with i = j),

either M i = M j or M i ∩ M j = ∅.
The nested, inclusive and disjoint processing set restrictions can be seen as special cases of the interval processing set restriction because it is always possible to reorder the machines in each subset M i so that one obtains contiguous intervals of machines. Furthermore, the inclusive and disjoint processing set restrictions are special cases of the nested processing set restriction.

Figure 1 summarizes the relations between the dierent structures in processing set restrictions.

In key-value stores, requests indicate which le to retrieve based on a key that can be used multiple times. This implies that multiple tasks may share the same processing time and processing set.

We can now dene the desired output and objective function. For any scheduling algorithm S, we note ρ S i the time at which T i is scheduled by S, µ S i the index of the machine on which T i

Mi(nested)

Mi(disjoint) Mi(inclusive)

Mi(interval) Mi

RR n°9446

is scheduled by S, and σ S i the starting time of T i under S. In other words, S gives a schedule Π S such that Π S (i) = (µ S i , σ S i ) for all task T i . We want to minimize the maximum ow time

F S max = max F S i , where F S i = C S i -r i (C S i denotes the completion time of T i in Π S : C S i = σ S i +p i ).
The superscript S is omitted when the considered algorithm is obvious from context.

We say that an online algorithm D has the Immediate Dispatch property if all tasks are scheduled as soon as they arrive in the system, i.e., for all T i , we have r i ≤ ρ D i < r i + ε, where 0 < ε 1, and we call D an immediate dispatch algorithm. This property is of particular importance in systems that need to scale and cannot handle large waiting queues; the scheduling phase should be as fast as possible. It is often the case in online distributed systems such as load balancers or replicated key-value stores. [START_REF] Bender | Flow and stretch metrics for scheduling continuous job streams[END_REF][START_REF] Mastrolilli | Scheduling to minimize max ow time: O-line and on-line algorithms[END_REF][START_REF] Bender | New algorithms and metrics for scheduling[END_REF], which makes it optimal on a single machine. In the present paper, we move our focus to the EFT scheduler (see Algorithm 2), which pushes each released task on the machine that nishes the earliest. We show here that both schedulers are equivalent on any instance of the scheduling problem P |online-r i |F max . However, EFT has two main advantages over FIFO, which motivates our choice:

1. FIFO relies on a centralized queue, whereas EFT allocates tasks to machines as soon as they arrive (it is an immediate dispatch algorithm). Hence, it does not require a centralized scheduler with a potentially large queue of jobs, which is impractical in most existing online systems with critical scalability needs.

2. EFT can easily be extended to scenarios with processing set restrictions, whereas transforming FIFO to allow such constraints would be cumbersome.

For each machine M j ∈ M and for any 1 ≤ i ≤ n, let H j,i denote the subset of tasks T 1 , . . . , T i being assigned to M j in a schedule Π:

H j,i = {T i ∈ T s.t. 1 ≤ i ≤ i and µ i = j}.
Then we dene C j,i as the time at which M j completes its assigned tasks among the rst i tasks in Π, i.e., C j,i = max

T i ∈Hj,i {C i } ,
where C i = σ i + p i is the completion time of T i in Π, with the convention C j,0 = 0. Finally, we dene U i as the set of machines that may start the i-th task at the earliest possible time t min,i = max r i , min Mj ∈M {C j,i-1 } , i.e., U i is the set of machines that are in a tie for T i :

U i = {M j ∈ M s.t. C j,i-1 ≤ t min,i } . (1)
Note that EFT needs to know the set U i for each released task T i , which implies that one must know the processing time of arriving tasks with precision, in order to compute the completion times of machines at each step (we are in a clairvoyant setting). In this way, EFT can be readily modied to account for processing set restrictions by changing Equation [START_REF] Featherston | Cassandra: Principles and application[END_REF] to

U i = M j ∈ M i s.t. C j,i-1 ≤ t min,i , (2)

Inria

where t min,i = max r i , min Mj ∈Mi {C j,i-1 } .

For both EFT and FIFO strategies, a tie-break policy decides which machine will process T i . We consider that ties are broken according to the same policy BreakTie in FIFO and EFT (in FIFO, ties are broken when at least 2 machines are idle at the same time; we assume the selected machine runs rst).

Algorithm 1 FIFO Require: Global FIFO queue Q Input: Incoming tasks T i Output: Allocated machines µ i , starting times σ i 1: when a new task T i is released do 2: enqueue(i , Q)

In parallel, do:

1: when some machines U are idle at time t do 2: i ← dequeue(Q) 3: if i = NIL then 4:

u ← BreakTie(U )
5:

µ i ← u 6: σ i ← t
Algorithm 2 EFT Input: Incoming tasks T i Output: Allocated machines µ i , starting times σ i 1: when a new task T i is released do 2: Get U i according to completion times of machines M (Equation (1)) 3: u ← BreakTie(U i ) 4: µ i ← u 5: σ i ← max (r i , C u,i-1 ) 6: Update the completion time of M u Now we show that EFT is equivalent to FIFO for the problem P |online-r i |F max . Proposition 1. For any instance I of the problem P |online-r i |F max , we have FIFO(I) = EFT(I), i.e., Π FIFO (i) = Π EFT (i) for all T i ∈ T in the instance I.

Proof: Let I denote an arbitrary instance of the problem P |online-r i |F max . We prove the following statement by induction: for any

k such that 1 ≤ k ≤ n, Π FIFO (i) = Π EFT (i) for all 1 ≤ i ≤ k, where T i ∈ T in the instance I.
Base case (k = 1). All machines are idle (thus U FIFO

1 = U EFT 1 = M).
As FIFO and EFT have the same tie-break policy and it is called on the same machine subset, they will choose the same machine and execute T 1 as soon as it is released. Induction step. Suppose that for a given k < n, Π FIFO (i) = Π EFT (i) for all 1 ≤ i ≤ k. We show that Π FIFO (k + 1) = Π EFT (k + 1).

On the one hand, at time r k+1 , EFT will schedule the task T k+1 on one machine M u in the subset U EFT k+1 according to the tie-break policy. Thus, we have µ EFT k+1 = u and σ EFT k+1 = max(r k+1 , C EFT u,k ).

On the other hand, at time max(r k+1 , min j C FIFO j,k

), one of the machine in the subset U FIFO k+1 will wake up rst according to the tie-break policy. Let M u denote this machine. M u will

RR n°9446

pull the next task to process from the shared queue Q, which is necessarily T k+1 . Therefore, µ FIFO k+1 = u and σ FIFO k+1 = max(r k+1 , C FIFO u ,k ).

As Π FIFO (i) = Π EFT (i) for all 1 ≤ i ≤ k, we deduce that all machines complete at the same time in Π FIFO and Π EFT when the rst k tasks are considered, i.e., for all j, C FIFO

j,k = C EFT j,k .
This implies that U FIFO k+1 = U EFT k+1 . Thus, as FIFO and EFT break ties the same way, we have u = u , and then C FIFO

u,k = C EFT u ,k . Therefore, µ EFT k+1 = µ FIFO k+1 and σ EFT k+1 = σ FIFO k+1 .
The equivalence between EFT and FIFO implies that all existing results for FIFO also apply to EFT in the context of max-ow minimization on parallel machines without processing set restrictions.

Online Minimization of Max-Flow

In this section, we recall and give some results about the minimization of maximum ow time when there are no processing set restrictions, that is, when tasks can be scheduled on any machine. The oine problem P |r i |F max is clearly strongly NP-hard, as it is a generalization of P ||C max .

For the online version P |online-r i |F max , FIFO has been proven to be a (3-2/m)-competitive online algorithm. We describe the proof here, as the existing proof of Bender et al. is not entirely correct.

Theorem 1 (Bender et al. [START_REF] Bender | Flow and stretch metrics for scheduling continuous job streams[END_REF]). FIFO is (3-2/m)-competitive for the problem P |online-r i |F max .

Let T t denote the set of tasks released before time t and not yet started in schedule Π, i.e.,

T t = {T i ∈ T such that r i ≤ t and σ i > t}, and let δ t,j be the remaining processing time of the task T i being executed by machine M j at time t in Π, i.e., δ t,j = C i -t, where µ i = j and σ i ≤ t ≤ C i . Obviously, if no task is being processed on M j at time t, δ t,j is set to 0. Then, the total work waiting to be processed at time t in Π is dened as

W t = j δ t,j + Ti∈Tt p i .
We also dene the maximum processing time among T 1 , . . . , T i as p max,i . The maximum ow time among T 1 , . . . , T i in schedule Π is noted F max,i .

Lemma 1. For any task

T i , W FIFO ri ≤ W OPT ri + (m -1) p max,i
, where OPT is an optimal oine strategy.

Proof: Let us proceed by induction.

Base case (i = 1). At time r 1 , all machines are idle and we have W FIFO

r1 = W OPT r1 = p 1 .
Induction step. Suppose that W FIFO ri ≤ W OPT ri + (m -1) p max,i for a given i. We consider two cases: (i) All machines are busy between r i and r i+1 in Π FIFO . We have

W FIFO ri+1 = W FIFO ri -m(r i+1 -r i ) + p i+1 . Moreover, W OPT ri+1 ≥ W OPT ri
-m (r i+1 -r i ) + p i+1 (there may be idle times between r i and r i+1 in OPT ). Then,

W OPT ri+1 -W OPT ri ≥ W FIFO ri+1 -W FIFO ri . Inria Hence, W FIFO ri+1 ≤ W OPT ri+1 + W FIFO ri -W OPT ri ≤ W OPT ri+1 + (m -1) p max,i ≤ W OPT ri+1 + (m -1) p max,i+1 .
(ii) There is at least one idle machine between r i and r i+1 in Π FIFO . At time r i+1 , there is thus no waiting tasks except T i+1 (otherwise, it would have already started on an idle machine). In the worst case, m -1 machines start to process some tasks just before time r i+1 for p max,i time units. Then we have W FIFO

ri+1 ≤ p i+1 + (m -1) p max,i .
Furthermore, in the best case T i+1 is the only task in the system at time r i+1 in Π OPT , thus W OPT ri+1 ≥ p i+1 .

Therefore,

W FIFO ri+1 ≤ p i+1 + (m -1) p max,i ≤ W OPT ri+1 + (m -1) p max,i ≤ W OPT ri+1 + (m -1) p max,i+1 .
Proof of Theorem 1: We consider an online schedule Π FIFO built by FIFO and an optimal oine schedule Π OPT . We start by describing two lower bounds for F OPT max,i :

F OPT max,i ≥ p max,i , (3)
F OPT max,i ≥ W OPT ri /m. (4)
Lower bound (3) is immediate. Lower bound (4) follows from the fact that there is always a nonnished task T i such that r i ≤ r i and that will necessarily complete after time r i + W OPT ri /m. Now let T i be a task in Π FIFO . Thenas it is scheduled by FIFOit is the last task in T FIFO ri , and it will not be able to start before time r i +(W FIFO ri -p i )/m in the worst case. Hence,

F FIFO i ≤ W FIFO ri /m + p i - p i m ≤ W FIFO ri /m + 1 - 1 m p max,i
is an upper bound for FIFO. By Lemma 1, we know that W FIFO ri ≤ W OPT ri + (m -1) p max,i for each task T i . Then,

F FIFO i ≤ W FIFO ri /m + 1 - 1 m p max,i ≤ W OPT ri /m + 2 1 - 1 m p max,i ≤ 3 - 2 m F OPT
max,i (by lower bounds (3) and ( 4)).

As a corollary, the problem is polynomial on a single-machine; FIFO is optimal in this case.

It is also known that P |r i |F max is polynomial on parallel machines for homogeneous tasks [START_REF] Simons | Multiprocessor scheduling of unit-time jobs with arbitrary release times and deadlines[END_REF].

As it solves a more general problem, the proposed algorithm is quite complex; we show that FIFO is sucient to solve P |r i , p i = p|F max .

RR n°9446

Processing Theorem 2. FIFO solves the problem P |online-r i , p i = p|F max to optimality.

Proof: Let OPT be an optimal oine strategy and Π OPT an optimal schedule. If on each machine, tasks are processed by non-decreasing release time, then OPT corresponds to an execution of the FIFO algorithm: two tasks starting simultaneously on two machines may be allocated on dierent machines in OPT and FIFO, but it does modify neither their completion time nor the completion times of other tasks. If this is not the case, let T i and T j be two tasks in Π OPT such that r i ≤ r j , and where T i starts after T j (σ i ≥ σ j ). T i can be on any machine, as well as T j . Thus σ i + p ≥ σ j + p, and then

C i ≥ C j (p i = p j = p). Their contribution to the objective is F = max(C i -r i , C j -r j ) = C i -r i because r i ≤ r j and C i ≥ C j .
Consider what happens if we swap T i and T j . Note that this is possible as T j was originally started rst although T i is released before T j . Their contribution to the maximum ow becomes

F = max(C i -r i , C j -r j ). By construction, C i = C j and C j = C i . We have C i -r i = C j -r i ≤ C i -r i (because C i ≥ C j ), and C j -r j = C i -r j ≤ C i -r i (because r i ≤ r j ). Hence, F ≤ F.
It follows that we can transform Π OPT in another optimal schedule Π FIFO by swapping repeatedly non-sorted tasks. Then, FIFO is optimal.

As we proved the equivalence of FIFO and EFT in Section 4, all the results of the current section also apply to EFT. [START_REF] Lakshman | Cassandra: a decentralized structured storage system[END_REF] Bounds under Processing Set Restrictions

Obviously, the problem P |r i , M i |F max is NP-hard in the oine context, that is, when all details on tasks are available beforehand. However, when considering tasks with unit processing times,

Brucker et al. show that the problem P |r i , p i = 1, M i | w i T i is solvable in polynomial time [23].
Thus, P |r i , p i = 1, M i |L max is also polynomial, and by setting the deadline d i = r i for all tasks, it follows that P |r i ,

p i = 1, M i |F max is polynomial. Anand et al. show that P |online-r i , p i = 1, M i |F max has a lower bound of Ω(m) on the
competitive ratio of any online algorithm [START_REF] Anand | Minimizing maximum (weighted) ow-time on related and unrelated machines[END_REF] (even the ones that do not have the Immediate Dispatch property). However, their proof is only valid for the general constraint M i , and it is unknown if special structures of the processing sets make the problem easier.

We provide here lower bounds on the competitive ratios of scheduling algorithms when considering that the processing sets follow a particular structure. Table 2 gives a summary of the results presented here.

We rst study the inclusive structure of processing sets. We show in Theorem 3 that restricting to this structure reduces the lower bound on the competitive ratios to log 2 (m) + 1 for Inria immediate dispatch algorithms. This is also true for the nested and interval structures, as they generalize the inclusive structure.

Theorem 3. The competitive ratio of any immediate dispatch algorithm is at least log 2 (m) + 1

for the problem P |online-r i , p i = p, M i (inclusive)|F max .

Proof: Let us assume that we work on a number of machines m that is a power of 2, i.e., m = 2 log 2 (m ) , where m is the actual number of machines. Let D be an arbitrary online immediate dispatch algorithm. We build the following adversary. For each such that

1 ≤ ≤ log 2 (m), let T ( ) denote the set of m 2 tasks with p i = p > log 2 (m) and r i = -1 for all T i ∈ T ( ) . A nal task is released at time r i = log 2 (m).
Then we dene M (1) = {M 1 , . . . , M m } and for all > 1, M ( ) denotes the subset of machines of M ( -1) of size m 2 -1 with at least ( -1) m 2 -1 allocated tasks in total after step -1 (we prove below that such a set exists). Finally, for each and for all T i ∈ T ( ) , we set M i = M ( ) . Let us prove by induction that the construction of M ( ) is valid, i.e., that such a subset exists for all > 0. Note that as D is an immediate dispatch algorithm, all tasks of T ( ) are irremediably scheduled at time -1 on some machines of M ( ) . For the construction of M (2) , we start from M (1) = {M 1 , . . . , M m } where m 2 tasks have been allocated on the rst step. We select for M (2) the subset of machines where these tasks have been allocated, possibly with additional machines to reach the proper size m 2 .

We now assume that M ( ) has been constructed and prove that we can build M ( +1) . By induction, M ( ) has been allocated ( -1) m 2 -1 tasks up to step -1, and m 2 new tasks on step . This makes a total of (2 -1) m 2 tasks. We select for M ( +1) the m 2 machines that are the most loaded in M ( ) . We consider two cases:

(i) Each of the selected machines has at least tasks. Then in total, we have at least m 2 tasks, as requested.

(ii) There exists a selected machine with at most -1 tasks. This means that all non-selected machines have at most -1 tasks (otherwise, we would have selected one of them instead), for a total work (on the m 2 non-selected machines) of at most ( -1) m 2 tasks. Thus, on selected machines, the number of tasks is at least

(2 -1) m 2 -( -1) m 2 = m 2 .
At step log 2 (m), M (log 2 (m)) is reduced to two machines, with at least 2(log 2 (m)-1) allocated tasks, where a single task is scheduled at time log 2 (m) -1. This leaves one machine with at least log 2 (m) tasks, where we nally allocate the last task at time log 2 (m), leading to a maximum ow of (log

2 (m) + 1)p -log 2 (m). Note that log 2 (m) + 1 = log 2 (2 log 2 (m ) ) + 1 = log 2 (m ) + 1 = log 2 (m ) + 1 .
The optimal strategy consists in scheduling each set T ( ) on the machines of M ( ) \ M ( +1) , for a max-ow of p. Thus, as p → ∞, we have a competitive ratio of log 2 (m ) + 1 .

The previous result may be adapted for processing sets that do not present any particular structure, but have all the same size k.

Theorem 4. The competitive ratio of any immediate dispatch algorithm is at least log

k (m) for the problem P |online-r i , p i = p, M i , |M i | = k|F max .

RR n°9446

Proof: Let us assume that we work on a number of machines m that is a power of k, i.e., m = k log k (m ) , where m is the actual number of machines. Let D be an arbitrary immediate dispatch algorithm. We proceed by building the following adversary. For each such that

1 ≤ ≤ log k (m), let T ( ) denote the set of m k tasks with p i = p > log k (m) and r i = -1 for all T i ∈ T ( ) .
Note that as D is an immediate dispatch algorithm, all tasks of T ( ) are irremediably scheduled at time -1. Then we dene M ( ) as the set of machines on which the tasks of T ( ) are scheduled at this specic time, with the particular case M (0) = M . Finally, for each and for all T i ∈ T ( ) , we set M i ⊆ M ( -1) , with |M i | = k. Moreover, all processing sets of tasks that belong to the same set T ( ) are mutually disjoint, i.e., M i ∩ M j = ∅ for all T i , T j ∈ T ( ) such that i = j.

D will be forced to schedule each set T ( ) on the exact same machines that are already busy with the tasks of the previous set T ( -1) . As all processing sets are mutually disjoint, we know that the tasks T ( ) are scheduled on T ( ) = m k machines exactly. Moreover, there are exactly m k waiting tasks on these machines at step . Thus, at the last step = log k (m), the completion time is log k (m)p. Therefore, the maximum ow time is

log k (m)p -(log k (m) -1). Note that log k (m) = log k (k log k (m ) ) = log k (m ) .
The optimal strategy consists in scheduling each set T (l) on the machines M (l-1) \ M (l) , for a max-ow of p. Thus, as p → ∞, we have a competitive ratio of log k (m ) .

When considering online algorithms that do not have the Immediate Dispatch property (and thus may allocate tasks only when machines are available for computation), we can still prove a similar lower bound on the competitive ratio, as long as the processing sets are nested. The proof is an adaptation of Anand et al. [START_REF] Anand | Minimizing maximum (weighted) ow-time on related and unrelated machines[END_REF], which did not consider any structure.

Theorem 5. The competitive ratio of any online algorithm is at least 1 3 log 2 (m) + 2 for the problem P |online-r i , p i = 1, M i (nested)|F max .

Proof: Let us assume that we work on a number of machines m that is a power of 2, i.e., m = 2 log 2 (m ) , where m is the actual number of machines. Let N be an arbitrary online scheduling algorithm. Machines are numbered from 1 to m, and let F be a number such that F ≥ log 2 (m) + 2. We construct the following instance. At time t 0 = 0, we consider the interval of machines of size s 0 and starting from u 0 (that is, {M u0 , M u0+1 , . . . , M u0+s0-1 }), denoted by I(u 0 , s 0 ), where u 0 = 1 and s 0 = m. We submit s 0 unit tasks at time t 0 , with the processing set restriction M i = I(u 0 , s 0 ). Let G 1,0 denote this set of tasks. For each machine M j ∈ I(u 0 , s 0 ), we release one unit task at each time t 0 , t 0 + 1, . . . , t 0 + F -1 and feasible only on the machine M j . Let G 2,0 denote this set. Note that at time t 0 + F -1, algorithm N should have completed the tasks of G 1,0 , otherwise the maximum ow time would be greater than log 2 (m) + 2. Now, for all k > 0, we set

t k = t k-1 + F and s k = 1 2 s k-1 . We choose u k such that u k-1 ≤ u k ≤ u k-1 + s k-1 -s k = u k-1 + s k (in other words, I(u k , s k ) is a subinterval of I(u k-1 , s k-1 )
), and such that |G 0,k | is maximized, where G 0,k ⊂ G 2,k-1 is the set of tasks that are submitted before t k but not completed at this time, and that can be executed on one machine only in the interval I(u k , s k ). Then we submit task sets G 1,k and G 2,k as previously: G 1,k is made of s k tasks with processing set I(u k , s k ) released at time t k , and G 2,k contains F tasks for each machine M j ∈ I(u k , s k ) submitted at times t k , t k + 1, . . . , t k + F -1 and that must be processed on M j . Figure 2 illustrates a schedule of the described instance.

We prove the following statements by induction: for all k ≥ 0, (i) s k = m/2 k and (ii) there are at least ks k uncompleted tasks on For the base case (k = 0), we have s 0 = m/2 0 = m, and G 0,k = ∅, so there is no completed task on I(1, m) at time 0 before sending G 1,0 and G 2,0 . Now assume that s k = m/2 k is true at a certain step k. At step k + 1, we have s k+1 = 1 2 s k by denition, so s k+1 = 1 2 (m/2 k ) = m/2 k+1 , which proves the statement (i). Suppose that there are at least ks k uncompleted tasks on I(u k , s k ) at time t k , i.e., |G 0,k | ≥ ks k . Then we send G 1,k and G 2,k , which means that there are at least 1 2 s k and by contradiction, assume that no such subinterval contains (k + 1) 1 2 s k uncompleted tasks, i.e., there are at most (k + 1) 1 2 s k -1 uncompleted tasks on each of these subintervals. Thus, there are at most 2 ((k + 1) 1 2 s k -1) = (k + 1)s k -2 uncompleted tasks on I(u k , s k ), which contradicts the fact that I(u k , s k ) holds at least (k + 1)s k uncompleted tasks. Then, the chosen subinterval I(u k+1 , s k+1 ) contains at least (k + 1) 1 2 s k = (k + 1)s k+1 uncompleted tasks at time t k+1 before sending G 1,k+1 and G 2,k+1 (that is, |G 0,k+1 | ≥ (k + 1)s k+1 ), which proves the statement (ii).

I(u k , s k ) at time t k before sending G 1,k and G 2,k , i.e., |G 0,k | ≥ ks k . Inria I(u k-1 , s k-1 ) I(u k , s k ) t k-1 t k t k+1 F F G 0, * G 1, * G 2, *
ks k + s k + F s k -F s k = (k + 1)s k uncompleted tasks on I(u k , s k ) at time t k+1 = t k + F . Now we choose the subinterval I(u k+1 , s k+1 ) ⊂ I(u k , s k ) maximizing |G 0,k+1 | at time t k+1 . Let us divide I(u k , s k ) into 2 disjoint subintervals of size
We stop when we reach the step k such that s k = 1. This means that m/2 k = 1, i.e., k = log 2 (m). Therefore, there remains at least ks k = log 2 (m) uncompleted tasks on an interval of size 1 at time t k , plus 1 task of G 1,k and 1 task of G 2,k , which gives a maximum ow time of at least log 2 (m) + 2. Thus, on all m machines, we have a maximum ow of

log 2 (m) + 2 = log 2 (2 log 2 (m ) ) + 2 = log 2 (m ) + 2 = log 2 (m ) + 2 .
The optimal strategy consists, at each step 0 ≤ k < log 2 (m), in executing all tasks of G 1,k on the subinterval I(u k , s k ) \ I(u k+1 , s k+1 ), for a max-ow of 3: tasks of G 1,k are scheduled rst (with ow 2), followed by tasks of G 2,k , which have a ow at most 3.

The case of disjoint processing sets is particular: we may apply a competitive algorithm independently on each set, which leads to an algorithm with adapted competitive ratio. Theorem 6. From any f (m)-competitive algorithm for the problem P |online-r i |F max , we can design an adapted algorithm with a competitive ratio of max i {f (|M i |)} for the disjoint case (P |online-r i , M i (disjoint)|F max ).

RR n°9446

Louis-Claude Canon, Anthony Dugois, Loris Marchal Proof: Let I be an arbitrary instance of the problem P |online-r i , M i (disjoint)|F max , and let N be an f (m)-competitive algorithm for P |online-r i |F max . By denition of the disjoint processing set restriction, we have M i ∩ M j = ∅ or M i = M j for all tasks T i , T j (with i = j) of the instance I. Let M denote the set of all subsets M i .

Then, for all M u ∈ M, we construct the set of tasks

T u = {T i ∈ T s.t. M i = M u }. As M u ∩ M v = ∅ for all M u , M v ∈ M such that u = v, we clearly have T u ∩ T v = ∅. Moreover, Mu∈M T u = T.
Hence, for all M u ∈ M, T u and M u can clearly constitute an instance I u of the problem P |online-r i |F max . We design an online algorithm N for the original problem by applying N in parallel to each instance I u .

By denition of the competitive ratio of N , we have

F N max (I u ) ≤ f (|M u |)F OPT max (I u )
, where OPT is an optimal oine strategy. As I u is a subproblem of I, we also have

F OPT max (I u ) ≤ F OPT max (I)
for all I u , where OPT is an optimal oine strategy built by applying OPT in parallel on each instance I u . Then,

F N max (I u ) ≤ f (|M u |)F OPT max (I), and F N max (I) = max u F N max (I u ) ≤ max u {f (|M u |)} F OPT max (I).
This result has an important corollary for EFT on disjoint processing sets.

Corollary 1. EFT is (3-2/ max |M i |)-competitive for the disjoint case and (3-2/k)-competitive

when |M i | = k for all M i .
We now move to the study of processing sets that are intervals of xed size, which we outlined in the introduction as being representative of the replication scheme used in key-value stores.

We show that the competitive ratio of any algorithm (even without the Immediate Dispatch property) is not smaller than 2.

Theorem 7. The competitive ratio of any online algorithm is at least 2 for the xed-size interval

problem P |online-r i , p i = p, M i (interval), |M i | = k|F max .
Proof: Let N be an arbitrary online algorithm. At time 0, the adversary sends one task T 1 with processing time p and with M 1 = {M 2 , M 3 }. Now there are two cases: N executes this task (i) on M 2 or (ii) on M 3 , and we denote its starting time by σ 1 . Note that if σ 1 ≥ p, the ow time for this task is at least 2p, while an optimal algorithm could schedule this task at time 0 with a ow time of 1, leading to a ratio larger than, or equal to 2. We thus assume that σ 1 < p.

Let us assume N executes T 1 on M 2 (i). Then the adversary sends two tasks T 2 and T 3 at time σ 1 + 1 with processing time p and with M 2 = M 3 = {M 1 , M 2 }. N will schedule at least one task at time σ 1 + p at the earliest, and this task will complete at time σ 1 + 2p at the earliest, for a max-ow of at least 2p -1. The optimal schedule consists in executing T 1 on M 3 at time 0, to let the next two tasks execute on M 1 and M 2 at time 1, for a max-ow of p. As p → ∞, the competitive ratio is 2. The case (ii) is proved analogously by sending two tasks on interval {M 3 , M 4 }.

The lower bound on the competitive ratio can be largely increased when considering immediate dispatch algorithms, and in particular EFT, as dened in Algorithm 2 in Section 4. Note Inria that among immediate dispatch algorithms, EFT is a very reasonable candidate: when a new task is submitted, it is allocated to the machine that will nish it the earliest. Without processing set restrictions, this is known to produce a very good load balancing, as well as good performance for the max-ow [START_REF] Bender | Flow and stretch metrics for scheduling continuous job streams[END_REF]. It turns out that this is not the case when adding processing interval restrictions. We prove in Theorems 8, 9 and 10 that the competitive ratio of EFT is larger than m -k + 1 in a variety of settings.

To exhibit this result, we need to focus on a specic tie-break function. We start by studying the Min tie-break function: in the set U i of candidate machines that may nish task T i at the earliest, we choose the machine with smallest index. The obtained algorithm is called EFT-Min (Algorithm 3) and its competitive ratio is bounded in Theorem 8.

Algorithm 3 EFT-Min

1: when a new task T i is released do 2: Get U i according to completion times of machines M i (Equation ( 2)) 3:

u ← Min(U i ) 4: µ i ← u 5: σ i ← max (r i , C u,i-1 ) 6: Update the completion time of M u Theorem 8. The competitive ratio of EFT-Min is at least m -k + 1 for the xed-size interval problem P |online-r i , p i = 1, M i (interval), |M i | = k|F max , where 1 < k < m.
We show that the competitive ratio of EFT-Min is at least m -k + 1 for the problem of minimizing max-ow when the processing set is an interval of size k, with 1 < k < m, even when tasks are unitary. For ease of reading, we say that a given task T i is of type λ if its processing interval restriction starts on machine M λ , i.e., M i = {M λ , . . . , M λ+k-1 }, and we say that it is of type ≥ λ (resp. ≤ λ ) if λ ≥ λ (resp. λ ≤ λ ).

Let us build the following adversary (we illustrate an EFT-Min schedule of this adversary in Figure 3). At each time t, we send m tasks such that: 3);

(i) for 1 ≤ i ≤ m -k, task T i is of type m -k -i + 2 (blue task in Figure
(ii) for m -k < i ≤ m, task T i is of type 1 (red task in Figure 3). This adversary relies on the key observation that EFT-Min is naive: when several machines present the minimum load value among all machines, it will choose the rst machine that satises its load-minimality criterion, i.e., the machine whose index is the lowest.

Note that at time t, just before sending the m next tasks, mt tasks have already been scheduled in Π EFT , and each machine M j completes at time C j,mt . Let w t (j) = max(0, C j,mt -t) be the work allocated on machine M j and waiting to be processed, just before the adversary releases the m tasks. We call w t the schedule prole of EFT at time t.

The proof consists in showing that EFT-Min converges to a stable schedule prole w τ such that for all j, w τ (j) = min(m -j, m -k). Figure 4 shows an example of a schedule prole w t , which is behind the stable prole w τ . Denition 1. For any t = t , we say that (i) w t = w t if w t (j) = w t (j) for all j; RR n°9446 Colored tasks are released in-order at each time t.

M 1 M 2 M 3 M 4 M 5 M 6 t = 2
wt wτ Figure 4: The schedule prole w t of EFT-Min at time t (in green), just before the adversary sends m new tasks. w t is strictly behind the stable prole w τ we want to reach (in purple).

(ii) w t ≤ w t if w t (j) ≤ w t (j) for all j (w t is behind w t );

(iii) w t < w t if w t ≤ w t and there is at least one machine M j such that w t (j) < w t (j) (w t is strictly behind w t ).

The proof consists in two phases: rst, we show that when the schedule prole is strictly behind w τ , there exists a future time such that the schedule prole is closer to w τ (Lemma 3); second, we show that at any time, either we can nd a past time such that the schedule prole exceeds w τ , or the current schedule prole is behind w τ (Lemma 4).

Before we dive into the proof, we start with the following lemma, which proves that for any t, w t is a non-increasing function. This will be of particular importance when proving Lemma 3.

Lemma 2. At any time t and for all j such that 1 ≤ j < m, w t (j + 1) ≤ w t (j).

Proof: Let us proceed by induction.

Base case (t = 0). No task arrived yet, so w 0 (j) = 0 for all machines j. Induction step. Now we assume that for a given t, w t (j + 1) ≤ w t (j) for all j such that 1 ≤ j < m. By contradiction, suppose there exists j such that w t+1 (j + 1) > w t+1 (j). We begin by showing that, as a consequence, only one task can have been scheduled on machine M j+1 at time t, which will lead to a contradiction. Let T i be the last allocated task on machine M j+1 . By induction hypothesis, we know that w t (j + 1) ≤ w t (j), and we assumed that w t+1 (j + 1) > w t+1 (j), thus T i has been scheduled at a Inria T i wt(j) w t+1 (j) wt(j + 1)

w t+1 (j + 1) M j M j+1 t t + 1 wt w t+1
Figure 5: Schedule proles on M j and M j+1 at times t and t+ 1, under the described hypotheses.

time comprised between t and t + 1 (let t + ε denote this specic time).

If we had w t+ε (j) > w t+ε (j + 1), then T i could not be the last allocated task on M j+1 at time t + 1, because we assumed that w t+1 (j + 1) > w t+1 (j), and EFT-Min is an immediate dispatch algorithm. Therefore, we necessarily had w t+ε (j) ≤ w t+ε (j + 1) at time t + ε, just before scheduling T i . We can deduce that we have M i = {M j+1 , . . . , M j+k }, otherwise we would have scheduled T i on the less-loaded machine M j (then we say that T i is of type j + 1). Furthermore, all machines M j+2 , . . . , M j+k were at least as much loaded as M j+1 at time t + ε (w t+ε (j ) ≥ w t+ε (j + 1) for all j such that j + 1 < j ≤ j + k), otherwise we would not have scheduled T i on M j+1 .

By construction of the adversary, the tasks sent before T i at time t cannot have been placed on M j+1 because their interval restriction starts after M j+1 (they are of type ≥ j +2). Moreover, the tasks sent after T i at time t cannot have been placed on M j+1 as well (otherwise, T i would not be the last task on M j+1 ). Hence, T i is the only task scheduled on M j+1 between times t and t + 1.

We consider two cases: (i) First, suppose that w t (j + 1) = 0. This means that EFT-Min makes T i starting at time t on M j+1 , and then T i completes at time t + 1. We proved that T i is the only task that is scheduled on M j+1 at time t, and as it completes at time t + 1, we can say that there is no remaining work at this exact time, i.e., w t+1 (j + 1) = 0. This contradicts our hypothesis w t+1 (j + 1) > w t+1 (j) ≥ 0.

(ii) Now suppose that w t (j + 1) > 0. Following our two hypothesis w t (j + 1) ≤ w t (j) and w t+1 (j + 1) > w t+1 (j), and from the consequent fact that exactly one task has been scheduled on M j+1 between t and t + 1, the only way to match all these assumptions is when there is as much waiting work on M j as on M j+1 at time t, i.e., w t (j) = w t (j +1), and no task is scheduled on M j between t and t + 1. But the last task T i scheduled on M j+1 is of type j + 1, which means that, by construction, at least one task of type j arrived after T i at time t. We showed that all machines M j+2 , . . . , M j+k were at least as much loaded as M j+1 at time t + ε, thus they were at least as much loaded as M j . As a consequence, at least one task must have been scheduled by EFT-Min on M j between t + ε and t + 1, which is a contradiction.

Now we are able to show the rst part of our proof: when the schedule prole of EFT-Min is strictly behind the stable prole w τ , there must exist a future time t such that the waiting work volume is greater than the current volume, i.e., j w t (j) < j w t (j).

RR n°9446

Lemma 3. At any time t such that w t < w τ , there exists a time t > t such that:

(i) for all t 1 such that t ≤ t 1 < t , we have j w t1 (j) = j w t (j);

(ii) j w t (j) < j w t (j).

Proof: Idleness property. The rst thing to notice is that when w t is empty for a given machine that is not the last one, i.e., there exists j < m such that w t (j) = 0, we know that all subsequent machines have no remaining work to do as well: w t (j ) = 0 for all j > j (Lemma 2). When it happens, EFT-Min will not schedule any task on the last machine, because the only eligible task is the rst one, which is of type m -k + 1; that task will be scheduled on M max(j,m-k+1) (the rst lightly-loaded compatible machine) at time t. Therefore, m new tasks are released by the adversary and at most m -1 tasks are processed (no work can be done by the last machine), so we have

j w t+1 (j) ≥ j w t (j) + m -(m -1),
and thus j w t+1 (j) > j w t (j). This means that if w t (j) = 0 for some j < m, we have j w t+1 (j) > j w t (j). The proof is mainly based on this useful property that we call the Idleness Property. If the schedule prole is strictly behind w τ , we will show that there must exist a plateau on some machines, and this plateau will necessarily propagate on next machines step by step, until we reach a time t such that w t (m -1) = 0.

Existence of a plateau. Now suppose that the schedule prole w t is strictly behind w τ (w t < w τ ). By Denition 1, this means that w t (j) ≤ w τ (j) for all j, and there is at least one machine M j such that w t (j ) < w τ (j ).

(5)

Let j be the highest index of such a machine; then we have w t (j) = w τ (j) for all j > j , [START_REF] Lakshman | Cassandra: a decentralized structured storage system[END_REF] and in particular, w t (j + 1) = w τ (j + 1). Let us show that there is a plateau on M j and M j +1 at time t, i.e., that w t (j ) = w t (j + 1). First, note that by denition of w τ , we have w τ (j) = w τ (j + 1) + 1 for all k ≤ j < m. [START_REF] Sumbaly | Serving large-scale batch computed data with project voldemort[END_REF] We have j ≥ k, because if w t (j) < w τ (j) for some j < k, schedule proles of all machines M j+1 , . . . , M k are also strictly behind the stable prole w τ (by Lemma 2 and denition of w τ ), and we dened j as the highest index; furthermore, j < m, because we assumed that w t (j ) < w τ (j ) and by denition w τ (m) = 0 (w t (m) cannot be lower than 0). Therefore, w t (j + 1) ≤ w t (j ) < w τ (j ) (by Lemma 2 and Eq. ( 5))

< w τ (j + 1) + 1 (by Eq. ( 7)) < w t (j + 1) + 1 (by Eq. ( 6)) which gives w t (j + 1) ≤ w t (j ) ≤ w t (j + 1), [START_REF] Cavalcante | Popring: A popularity-aware replica placement for distributed key-value store[END_REF] and then w t (j ) = w t (j + 1).

Inria T 1 T 2 T 3 T m-j M j M j +1 M j +2 Mm t t + 1 wt w t+1
Plateau at time t Plateau at time t + 1

Figure 6: Propagation of the plateau from machines M j and M j +1 at time t to machines M j +1 and M j +2 at time t + 1.

By denition, w τ (m) = 0, and as w t < w τ , w t (m) = 0. If j = m -1, we have w t (j ) = w t (m -1) = w t (m) = 0, and by the Idleness Property, the conclusion is immediate. Otherwise, j < m-1, so w t (m-1) = w τ (m-1) = 1. By Lemma 2, w t (j) ≥ 1 for all j < m, and then EFT-Min will schedule the rst task on the last machine. Overall, m tasks will be processed at time t, and m tasks are sent by the adversary; therefore, j w t+1 (j) = j w t (j) -m + m = j w t (j).

Propagation of the plateau. Now we show that the plateau propagates on the next machine in the next step, i.e., as j < m-1, w t (j ) = w t (j +1) implies w t+1 (j +1) = w t+1 (j +2).

By Eq. ( 6), w t (j) = w τ (j) for all j > j , which means that the rst m -j -1 tasks will be scheduled on their last machine (µ mt+i = m -i + 1 for each 1 ≤ i < m -j ). The corresponding machines will process one task at time t. Thus, w t+1 (j) = w t (j) -1 + 1 = w t (j) for all j > j + 1, and in particular, w t+1 (j + 2) = w t (j + 2). As w t (j ) = w t (j + 1), the (m -j )-th task will not be scheduled on M j +1 (the index of the machine it will be placed on is at most j : µ mt+m-j < j + 1). All remaining tasks will be scheduled on machines M 1 , . . . , M j , because they are of type ≤ j -k + 1. Figure 6 shows the propagation process.

Then M j +1 does not receive any additional task at time t, but it still processes one task at this time, so we have: w t+1 (j + 1) = w t (j + 1) -1 = w τ (j + 1) -1 (by Eq. ( 6))

= w τ (j + 2) (by Eq. ( 7)) = w t (j + 2) (by Eq. ( 6))

= w t+1 (j + 2).

(by Eq. ( 9)) This shows that the plateau propagates on machines M j +1 and M j +2 at time t+1. By repeating the process, we reach a time at which j +1 = m-1 and j +2 = m, thus w t (m-1) = w t (m) = 0, and the Idleness Property applies. This concludes the proof.

The second phase of our proof consists in showing that either there exists a past time such that the schedule prole exceeds the stable prole w τ , or the current prole is behind w τ .

RR n°9446

Lemma 4. At any time t, either (i) there exists a time t ≤ t such that w t (j) > m -k for some j or (ii) w t ≤ w τ .

Proof: Let us proceed by induction.

Base case (t = 0). Obviously, the base case is true (w 0 = 0 ≤ w τ ). Induction step (case (i)). First suppose there exists a time t ≤ t such that w t (j) > m -k for some j. This is obviously still true at time t + 1.

Induction step (case (ii)). Now suppose that w t ≤ w τ for some t. By contradiction, let us assume that there exists a machine M j such that w t+1 (j) > w τ (j). Combined to the fact that w t (j) ≤ w τ (j), we have w t+1 (j) ≥ w t (j) + 1. Let q denote the number of tasks scheduled on M j at time t, such that w t (j) + q -1 = w t+1 (j). Then, w t (j) + q -1 ≥ w t (j) + 1, i.e., q ≥ 2.

So at least 2 tasks must have been scheduled on machine M j at time t. Let j be the highest index of such a machine. Two subcases arise:

(a) j ≤ k. Then by construction w τ (j) = m -k, and we have w t+1 (j) > w τ (j) = m -k. This proves the induction.

(b) j > k. By induction hypothesis, we know that w t (m) = 0 (because w τ (m) = 0), and by construction, at most one task can be scheduled on the last machine at time t. Therefore, w t+1 (m) = 0, so j < m. Let T i be the last allocated task on M j , with σ i its starting time:

σ i = t + 1 + w t+1 (j) -1 = t + w t+1 (j).
Let λ i be the type of T i , i.e., M i = {M λi , . . . , M λi+k-1 }. As T i has been allocated to M j , we necessarily have λ i ≤ j ≤ λ i + k -1.

Suppose λ i = j. By construction, all tasks sent before T i at time t cannot have been scheduled on M j , because their machine interval starts after M λi . As T i is the last task of M j , no task sent after T i at time t can have been scheduled on this machine. Then T i is the only task scheduled on M j between t and t + 1, which contradicts the fact that at least 2 tasks must have been scheduled on M j . Hence, λ i < j.

Now, as T i has been allocated on M j and not on M j-1 , we know there was already a task T i on M j-1 when the scheduling of T i occurred, with σ i = σ i = t + w t+1 (j).

At time t, just before the adversary releases the m tasks, M j-1 completes at time C j-1,mt = t + w t (j -1). We have w t (j -1) ≤ w τ (j -1) (induction hypothesis); we supposed that w t+1 (j) > w τ (j); nally, w τ (j -1) = w τ (j) + 1 (by construction of w τ ). Therefore, t + w t (j -1) ≤ t + w τ (j -1)

≤ t + w τ (j) + 1 < t + w t+1 (j) + 1 = σ i + 1,
which means that σ i ≥ t + w t (j -1). In other words, T i starts after time C j-1,mt . Hence, the scheduling of T i occurred between t and t + 1, before the scheduling of T i (t ≤ ρ i < ρ i < t + 1). Let λ i be the type of T i . We necessarily have λ i > λ i .

If k = 2, this is a contradiction, because T i cannot have been scheduled on M j-1 (we proved that λ i < j, so M i = {M j-1 , M j }, and then λ i > j -1).

If k > 2, we deduce that T i has been scheduled on M j-1 because all the machines M j , . . . , M λ i +k-1 are planned to nish at or after time σ i . In particular, we have

C j+1,i ≥ σ i ≥ t + w t+1 (j) > t + w τ (j).

Inria

Then, C j+1,i -1 > t + w τ (j) -1 = t + w τ (j + 1).

Moreover, C j+1,i ≤ C j+1,m(t+1) = t + 1 + w t+1 (j + 1). Therefore, t + w t+1 (j + 1) > t + w τ (j + 1),

i.e., w t+1 (j + 1) > w τ (j + 1). This is a contradiction, because we had chosen j to be the highest index such that w t+1 (j) > w τ (j). This concludes the proof.

Proof of Theorem 8: To exhibit the lower bound of m -k + 1 on the competitive ratio of EFT-Min, we rst show there exists a time t such that w t = w τ or w t (j) > m -k for some j.

For a given time t, we know by Lemma 4 that either (i) there exists a time t ≤ t such that w t (j) > m -k for some j or (ii) w t ≤ w τ . If case (i) is true, then we found a time t such that w t (j) > m -k for some j. If case (ii) is true, either w t < w τ or w t = w τ . Suppose that w t < w τ . Then by Lemma 3, we can nd a future time t such that w t (j) > w t (j). Therefore, while we have w t < w τ , we can always nd a future time such that the schedule prole is closer to w τ . If we proceed step by step, we necessarily reach a time t such that w t = w τ . This proves our initial claim. Now, if w t (j) > m-k for some t, j, there exists a task T i such that F i ≥ m-k +1. If w t = w τ for some t, EFT-Min will schedule one task on each machine (by denition of the adversary and w τ ). Hence, the k last tasks will be allocated on the k rst machines, and they will have a ow time of m -k + 1. In any case, we have F max ≥ m -k + 1.

On the described instance, at each time step, the optimal strategy consists in scheduling each task of type ≥ k + 1 on the compatible machine of highest index. This allows reserving the k rst machines to the k last tasks, and avoid any delay accumulation. Therefore, for all tasks T i , we have F OPT i = 1, and then F OPT max = 1.

The previous bound on the competitive ratio of EFT-Min can be extended to the case where EFT uses a random tie-break function Rand, and we call this algorithm EFT-Rand (Algorithm 4). The only condition for Theorem 9 to hold is that among a set of candidate machines, the random tie-break function chooses each machine with positive probability, i.e., no machine is systematically discarded when it is a possible candidate.

Algorithm 4 EFT-Rand 1: when a new task T i is released do 2: Get U i according to completion times of machines M i (Equation ( 2)) 3:

u ← Rand(U i ) 4: µ i ← u 5: σ i ← max (r i , C u,i-1 ) 6: Update the completion time of M u Theorem 9. The competitive ratio of EFT-Rand is at least m -k + 1 (almost surely) for the xed-size interval problem P |online-r i , p i = 1, M i (interval), |M i | = k|F max , where 1 < k < m.
In other words, there exists an instance for which we have

P F max ≥ (m -k + 1)F OPT max = 1.
Before starting the proof, we dene the weighted distance on machine M j at time t as ϕ t (j) = 2 wτ (j) (m -k + 1 -w t (j)).

RR n°9446

For any j 1 , j 2 such that 1 ≤ j 1 ≤ j 2 ≤ m, the partial weighted distance between M j1 and M j2 at time t is dened as

Φ t (j 1 , j 2 ) = j2 j=j1 ϕ t (j),
and the total weighted distance is denoted by Φ t = Φ t (1, m). Intuitively, this distance quanties the proximity between the schedule at time t and a simplied version of the stable schedule prole w τ . In the Lemma 5, we show that this distance decreases with t.

Lemma 5. At any time t, (i) if there exists a task T i≤m-k released at t and that is not scheduled on its last machine, i.e.,

µ mt+i = m -i + 1, then Φ t+1 < Φ t , (ii) otherwise Φ t+1 ≤ Φ t .
Proof: Case (i). At a given time t, suppose there exists at least one task T i≤m-k released at t and that is not scheduled on its last machine, i.e., µ mt+i = m -i + 1. Let i be the highest index of such a task. We will study the value of Φ t -Φ t+1 in two steps: rst, the value of

Φ t (1, m -i) -Φ t+1 (1, m -i) on machines M 1 , . . . , M m-i ; second, the value of Φ t (m -i + 1, m) -Φ t+1 (m -i + 1, m) on machines M m-i+1 , . . . , M m .
From 1 to m -i. We choose i to be the highest index such that T i is not put on its last machine; this means that all tasks T i such that i < i ≤ m -k are scheduled on their last machine M m-i +1 , and the last k tasks are scheduled on any of the rst k machines (because they are of type 1). In summary, all tasks T i such that i ≤ i ≤ m are scheduled on the rst m -i machines, and there are m -i + 1 such tasks.

Any machine M j among M 1 , . . . , M m-i can process at most 1 task between t and t + 1. Let q t,j be the number of tasks released at time t and scheduled on M j . Hence, w t+1 (j) ≥ w t (j) -1 + q t,j , and then 2 wτ (j) (m -k + 1 -w t+1 (j)) ≤ 2 wτ (j) (m -k + 1 -w t (j) + 1 -q t,j ).

Therefore, ϕ t+1 (j) ≤ ϕ t (j) + 2 wτ (j) -2 wτ (j) q t,j . By summing over j, we have

m-i j=1 ϕ t+1 (j) ≤ m-i j=1 ϕ t (j) + m-i j=1 2 wτ (j) - m-i j=1 2 wτ (j) q t,j . Note that m-i j=1 2 wτ (j) q t,j ≥ m i =i 2 wτ (µ mt+i ) ,
as we have shown that at least the last m -i + 1 tasks released at t are scheduled on the rst m -i machines.

Then,

Φ t+1 (1, m -i) ≤ Φ t (1, m -i) + m-i j=1 2 wτ (j) - m i =i 2 wτ (µ mt+i ) . (10) Inria Now we notice that m i =i 2 wτ (µ mt+i ) = 2 wτ (µmt+i) + m-k i =i+1 2 wτ (µ mt+i ) + m i =m-k+1 2 wτ (µ mt+i ) = 2 wτ (µmt+i) + m-i j=k+1 2 m-j + k j=1 2 m-k = 2 wτ (µmt+i) + m-i j=1 2 wτ (j) .
Finally, by simplifying Eq. ( 10),

Φ t (1, m -i) -Φ t+1 (1, m -i) ≥ 2 wτ (µmt+i) . (11)
From m -i + 1 to m. We saw earlier that the last m -i + 1 tasks released at time t must have been scheduled on the rst m -i machines. We deduce that only the rst i -1 tasks can have been put on the last i machines. There are more machines than tasks; therefore, there exists at least one machine M j such that j > m -i that did not receive any task at time t. M j can process at most one task between t and t + 1, so we have w t+1 (j) ≥ w t (j) -1, and then ϕ t (j) -ϕ t+1 (j) ≥ -2 wτ (j) .

In the worst case, all machines M j such that j > m -i receive no task. Then we have m j=m-i+1

(ϕ t (j) -ϕ t+1 (j)) ≥ - m j=m-i+1
2 wτ (j) , and then

Φ t (m -i + 1, m) -Φ t+1 (m -i + 1, m) ≥ - m j=m-i+1 2 wτ (j) . (12)
Now we sum Eq. ( 11) and ( 12), and we get

Φ t -Φ t+1 ≥ 2 wτ (µmt+i) - m j=m-i+1 2 wτ (j) .
Because µ mt+i ≤ m -i, we have 2 wτ (µmt+i) ≥ 2 wτ (m-i) , and as i ≤ m -k, 2 wτ (m-i) = 2 i and m -i

+ 1 ≥ k + 1. Therefore, Φ t -Φ t+1 ≥ 2 i - m j=m-i+1 2 m-j = 2 i - i-1 j =0 2 j = 2 i -2 i -1 = 1,
and we conclude that Φ t -Φ t+1 > 0.

Case (ii). Now suppose that at a given time t, all tasks T i≤m-k released at t are scheduled on their last machine, i.e., µ mt+i = m -i + 1.

From 1 to k. Only the last k tasks released at time t can have been put on the rst k machines. Moreover, these machines can process at most k tasks between t and t + 1. Hence,

k j=1 w t+1 (j) ≥ k j=1 w t (j) + k -k = k j=1 w t (j),

RR n°9446

and then

2 m-k k j=1 (m -k + 1 -w t+1 (j)) ≤ 2 m-k k j=1 (m -k + 1 -w t (j)), which gives k j=1 2 wτ (j) (m -k + 1 -w t+1 (j)) ≤ k j=1 2 wτ (j) (m -k + 1 -w t (j)). Therefore, Φ t (1, k) -Φ t+1 (1, k) ≥ 0. (13)
From k + 1 to m. All tasks T i≤m-k are put on their last machines. Then all machines M k+1 , . . . , M m receive exactly one task at time t, and we have w t+1 (j) = w t (j) for these machines, i.e., ϕ t (j) -ϕ t+1 (j) = 0.

Hence, m j=k+1 (ϕ t (j) -ϕ t+1 (j)) = 0, and then

Φ t (k + 1, m) -Φ t+1 (k + 1, m) = 0. (14)
By summing Eq. ( 13) and ( 14), we get Φ t -Φ t+1 ≥ 0. Now we prove that if we have no choice at a given time t (i.e., there is no tie-break) and if all tasks released at this time are put on their last machine, then we have reached a prole that is similar to the stable prole w τ , where the load of machines decreases with their index. Lemma 6. At any time t, if µ mt+i = m -i + 1 and |U mt+i | = 1 for all task T i≤m-k released at t, then w t (j + 1) < w t (j) for all k ≤ j < m.

Proof: Suppose that for a given time t, all tasks T i≤m-k are scheduled on their last machine. This means that all machines M k+1 , . . . , M m receive only one task at time t. Let T i be such a task (we have µ mt+i = m -i + 1). Suppose that there is no tie for T i (|U mt+i | = 1).

By denition of the tie, we have

C m-i+1,mt+i-1 < C j,mt+i-1 for all j such that m -k -i + 2 ≤ j < m -i + 1. Moreover, we have C m-i+1,mt+i-1 = C m-i+1,mt
and C j,mt+i-1 = C j,mt , because all tasks T i <i have been put on their last machine M m-i +1 , and we have m

-i + 1 > m -i + 1.
Hence, C m-i+1,mt < C j,mt , and then t + w t (m -i + 1) < t + w t (j), Inria which gives w t (m -i + 1) < w t (j). In particular, w t (m -i + 1) < w t (m -i). As this is true for all 1 ≤ i ≤ m -k, we have w t (j + 1) < w t (j) for all k ≤ j < m.

Before starting the proof of Theorem 9, we describe the class of random tie-break functions that we consider: Rand corresponds to any randomized policy for which there exists a constant θ > 0 such that the probability to put any task on its last machine is lower than, or equal to 1 -θ, if there exists a tie for this task. In other words, Rand never discards a candidate machine during a tie.

Proof of Theorem 9: It is clear from Lemma 5 that Φ is non-increasing: at any time t, Φ t+1 ≤ Φ t . Then there are two cases: either (i) for all time t, we can nd t > t such that Φ t < Φ t , or (ii) there exists a time t such that Φ t = Φ t for all t > t.

Case (i). Suppose that for all t, there exists a future time t > t such that Φ t < Φ t . As Φ t ∈ Z for all t, there must exist a time t * such that Φ t * ≤ 0, i.e., j ϕ t * (j) ≤ 0. Then, there exists at least one j such that ϕ t * (j) ≤ 0. By denition, we deduce that m -k + 1 -w t * (j) ≤ 0, thus w t * (j) ≥ m -k + 1.

The last scheduled task T i on M j will complete at time t * + m -k + 1, and we have

r i ≤ t * . Therefore, F max ≥ F i ≥ m -k + 1.
Case (ii). Now suppose that there exists a time t such that Φ t = Φ t for all future time t > t. By contraposition of Lemma 5, for all t > t, we have µ mt +i = m -i + 1 for all T i≤m-k released at time t , i.e., the rst m -k tasks released at each t are put on their last machine.

We consider rst the scenario in which for all t > t, there is at least one task T i≤m-k released at t for which there is a tie (i.e., |U mt +i | > 1). Since the rst m -k tasks released at each t are put on their last machine, its implies that Rand has selected the last machine through a tie-break for all t > t. By denition, Rand schedules each such task on any other machine than its last one with a non-zero probability. Therefore, Rand repeatedly makes this decision an innite number of time with a probability of zero and the initial scenario thus occurs with the same probability.

Then, with probability 1, there exists at least one time t > t such that |U mt +i | = 1 for all T i≤m-k released at t . By Lemma 6, we have w t (j + 1) < w t (j) for all k ≤ j < m, i.e., w t (k) ≥ m -k. Therefore, there exists a task scheduled on machine M k and released before time t that will necessarily complete at time t +m-k. We conclude that F max ≥ t +m-k -(t -1) = m -k + 1.

Finally, this result holds for any tie-break function provided that tasks are not anymore of unitary duration.

Theorem 10. The competitive ratio of EFT (with any tie-break policy) is at least

m -k + 1 for the xed-size interval problem P |online-r i , M i (interval), |M i | = k|F max .
Proof: The proof relies on the same instance as in Theorem 8, with some additional tasks with smaller duration. Original tasks from the instance of Theorem 8 are called regular tasks.

Our objective is to enforce the following property: Property 1. Consider a machine M i at time t, right before the allocation of regular tasks released at t. During time interval [t -1; t], M i has h ≥ 0 regular tasks waiting for execution (excluding the eventual one that is already started). These tasks will be completed at time t + h + iδ.

The value of δ will be set later to a very small value so that (i) m delays of δ is smaller than the duration of a regular task (1 time unit) and (ii) the total volume of small tasks can be considered as negligible in the optimal solution. Once a value of δ < 1/m is chosen, we set ε < δ/(2m). As we will see below, the iδ delays on each processor allow emulating the original RR n°9446 EFT-Min algorithm, which breaks ties among available processors by choosing the one with minimum index.

We now explain how small tasks are added to the original schedule. Consider any integer time t (including t = 0). We have two rounds of small tasks submitted at time t, right before the regular tasks. We consider the set of processors that do not process regular tasks during time interval [t -1, t] (all processors in the case of t = 0). Let m idle be the number of such processors.

Intuitively, we rst submit m idle small dummy tasks at time t that are scheduled by EFT using its tie-break policy (which we do not control). All dummy tasks have dierent durations such that there is no tie anymore among these machines for the second round. In the second round, we submit tasks whose duration is carefully crafted to ensure that each machine nishes its computation at the prescribed time t + iδ.

First round. We rst initialize a counter c ← 1. At time t, while there exists an idle processor M ic with i c ≥ 0, we submit a task T 1 c of duration cε with an interval covering processor M ic (i.e. M ic ∈ M(T 1 c ), for example interval [i c , i c + k] if i c + k < m, and [m -k, m] otherwise). We then increment the counter c ← c + 1.

Second round. When all tasks of the rst round are submitted and allocated, we submit new tasks based on the allocation of the tasks of the rst round. For each c = 1, . . . , m idle , we consider the processor M i where the task T 1 c of the rst round has been allocated. We submit a task T 2 c,i of duration iδ -cε with an interval covering M i (as above).

T 2 2,4

T 1 2 T 2 1,5 T 1 1 T 2 2,4 T 1 2 T 2 1,3 T 1 1 time t -1 t M 1 (h = 0) M 2 (h = 0) M 3 (h = 1) M 4 (h = 0) M 5 (h = 0) M 6 (h = 2)
Figure 7: Illustration of the construction of the instance for Theorem 10 when adding small tasks at time t. Regular tasks submitted before t are depicted in blue. Small tasks added to ensure the common delay of iδ are in red (dark red for step t, light red for step t -1), and regular tasks submitted at step t are in green. Only two processors are not processing any regular tasks before time t (M 4 and M 5 ) and require small tasks to ensure the common delay of iδ.

We now prove that Property 1 is veried at all time, by induction on the time t.

Let us rst consider the beginning of the schedule (t = 0): small tasks are submitted for all idle processors M i with i ≥ 0, before the submission of regular tasks. Each task T 1 c of the rst round must be allocated and started at time t = 0 on some idle processor, not necessarily M ic . However, at the end of this rst round, all processors must be processing a small task, as Inria the scheduling algorithm never leaves a processor idle when there is some task to perform on it.

Tasks submitted during the rst round will complete at times t + cε, with c = 1, . . . , m. Thus, the latest completion time for the rst round is equal to t + mε.

We now move to the second round. Note that since ε < δ/(2m), the duration of a task T 2 c,i of the second round is greater than (i -c/(2m))δ and is positive as c < m and i ≥ 1. Note also that M i is the rst machine available in the interval of T 2 c,i : and on all other machines, either the small task of the rst round completes later, or it has already been allocated a task of the second round, which lasts at least iδ -mε > m and thus will complete later. Hence, task T 2 c,i is necessarily allocated to M i , and completes at time t + (cε) + (iδ -cε) = t + iδ. This proves the property for time t = 0.

We now prove the property for t + 1, assuming it is correct for t. We consider a machine M i , which has h ≥ 0 regular tasks waiting for execution during interval [t -1; t] and r ≥ 0 new regular tasks released at time t are allocated to M i . We distinguish two cases:

During interval [t; t + 1], M i starts a regular task either because it has at least one waiting task in interval (h > 1) or a new task released at time t is allocated to it (r > 1). By induction, the machine M i will start this task at time t + iδ and end it at time t + 1 + iδ. Excluding the started task, there remains h = h + r -1 ≥ 0 waiting tasks in interval [t; t+1]. All the regular tasks waiting for execution will be completed at time t+1+iδ+h = (t + 1) + h + iδ with h ≥ 0. Hence, the property is true at time t + 1 for M i .

During interval [t; t + 1], M i starts no regular task (h = 0 and r = 0). At time t + 1, all machines are either idle like M i (when h = 0 and r = 0) or computing a regular task (allocated before t + 1). M i is allocated a small task T 1 c in the rst round at time t + 1 (it is available by induction hypothesis) and completes at time t + 1 + cε. Since there are at most m machines without regular tasks in interval [t; t + 1], all small tasks of the rst round are completed before or at time t + m < t + δ. In the second round, we prove that the task T 2 c,i must be allocated on M i . As seen before, at time t + 1 + cε, all idle machines either completes their tasks of the rst round later than M i or are already computing a task of the second round that completes later. Machines M j with j ≥ 0 that are computing regular tasks will be available at the soonest at time t + jδ to start a regular task by induction hypothesis. Thus, each machine M j will completes at time t + 1 + jδ, which is much later than when M i completes its task from the rst round. Hence, T 2 c,i is allocated to M i , and completes at time t + 1 + iδ. Lemma 7. With the additional (non regular) tasks, the execution of any FIFO algorithm (with any tie-break policy) follows the original FIFO policy (with tie-break by selecting the processor with smallest index), up to a delay of iδ for each processor M i . This lemma is proven by noticing that compared to the original setting, processors are not available simultaneously for regular tasks, but with a small delay iδ of increasing value for increasing processor index. Hence, whenever a regular task can be processed on several processors in the original setting, now the FIFO policy forces the processor with smaller index to execute it, as it was done in the original FIFO policy.

The instance used in the proof of Theorem 10 requires at most m 3 steps (each made of m tasks) to reach a maximum ow of m -k + 1 for the EFT-Min policy. The modied instance enforces such a maximum ow for a EFT scheduler with any tie-break policy. The total volume of small tasks added to this instance at each time step is bounded by m i=1 iδ = m(m + 1)δ/2. Hence the total volume of small tasks during the whole instance is bounded by m 5 δ/2. Choosing δ = o(1/m 5 ) makes this total volume negligible is front of the duration of a single regular task.

RR n°9446

We consider an optimal schedule of the original schedule and allocate the additional small tasks to any processor of their interval. The maximum delay for any processor is of order o(1). Hence the maximum ow of this modied optimal algorithm is 1 + o(1), which proves the asymptotic competitive ratio of m -k + 1.

Experimental Results

In this section, we evaluate the relative impact of structured processing set restrictions on the performance of simple scheduling heuristics. We focus on both interval processing sets, because they are used in actual systems [57], and disjoint processing sets, because it is the restrictions for which we have the best, and only, approximation ratio (Theorem 6). Moreover, the performance of actual systems are aected by the popularity of requests, which is not uniform, i.e., certain tasks restricted to the same processing set appear more frequently than others. We begin by explaining our model of popularity before developing the process we used to evaluate the theoretical maximum load permitted by data item replication. Finally, we perform simulations to provide an experimental perspective to the bounds derived in the previous section. All the related code, data and analysis are available online 1 .

Model of Popularity

Let us consider a cluster of m machines, where tasks have a unit processing time and are released according to a Poisson process with parameter λ (in other words, λ tasks are released in average at each time unit). λ/m measures the average load on the whole cluster; thus, when λ = m, the cluster is loaded at 100%.

For now, suppose that each task can be processed by only one specic machine, i.e., we have |M i | = 1 for all task T i . This corresponds to what happens in key-value stores when data items are not replicated: each task T i carries a key, which is uniquely associated to a data item in the system, and this data item is held by only one machine of the cluster. Therefore, T i has no choice but to be sent and processed on this specic machine.

In practice, some data items are requested more frequently than others during the service lifetime; depending on the data partitioning and popularity bias on requested keys, some machines will potentially have to process more tasks than others, leading to a biased distribution on machine popularity. Let E j be the event in which a task must be processed by machine M j (because it requests a key held by M j ), which occurs with probability P (E j ). Thus, λP (E j ) is the average number of tasks sent on M j at each time unit, and measures the load of M j . Note that because of the non-uniform popularity bias P (E j ), the load of a given machine can be greater than 100% (even if the average cluster load is below 100%). In this case, the machine completely saturates as there is no replication.

Let us consider that the machine popularity follows a Zipf distribution, which has been advocated to model popularity distributions [START_REF] Feitelson | Workload modeling for computer systems performance evaluation[END_REF]. We have P (E j ) = 1 j s Hm,s , where s ≥ 0 is the shape parameter of the distribution and H m,s is the m-th generalized harmonic number of order s. We use s to control the popularity bias: the larger s, the more the popularity heterogeneity increases. In the following, we focus on three specic situations. When s = 0, the distribution degenerates to the uniform distribution, i.e., no machine is more popular than another (we call this case the Uniform case). When s > 0, the Zipf distribution has the particularity to generate a monotonically decreasing load on machines M 1 , . . . , M m . This corresponds to a worst case, as the rst machines concentrate most of the workload (Worst-case). Finally, we randomly 1 https://doi.org/10.6084/m9.figshare.19123139.v1 Inria permute P (E j ) to match with more realistic settings (Shued case). As realistic bias strongly depends on the dataset and system usage, each permutation is chosen uniformly as we assume no prior knowledge. Figure 8 shows an example of load distribution for each case.

Analysis of Theoretical Maximum Load

We want to nd the theoretical maximum cluster load (that is, nding the maximum value of λ such that the load on each machine is below 100%) one can achieve when data items are replicated across the cluster. Up to now, as we did not consider replication yet, we supposed that each task could only be processed by a single machine (the one holding its requested key).

In this case, we clearly have λ ≤ 1/ max j P (E j ).

Let us give more choices to each task by adding more machines to the processing sets M i . This can be seen as replicating data items. Our goal is to study how extending M i under a popularity bias aects performance metrics such as the maximum ow time or the maximum cluster load, and how structures in processing sets impact them.

For each task T i , we build a new set M i from M i by dening a replication strategy; in other words, starting from a set with a single machine M i = {M u }, we replicate the keys held by M u on all machines of M i . We focus on strategies that consist in adding k -1 machines (with 1 ≤ k ≤ m) to the set, such that M i constitutes an interval of size k, i.e., M i = I k (u). We describe two manners to build I k (u) from M u . Figure 9 illustrates these constructions.

Overlapping intervals. There are m distinct overlapping replication intervals of size k, arranged as a ring:

I k (u) = {M j s.t. j = (j -1) mod m + 1 for all u ≤ j ≤ u + k -1}.
This constitutes the basic replication strategy of key-value stores: machines are arranged as a ring, and data items held by a given machine are replicated on the successors of this machine [START_REF] Decandia | Dynamo: amazon's highly available key-value store[END_REF][START_REF] Lakshman | Cassandra: a decentralized structured storage system[END_REF].

We have seen in Theorems 8, 9 and 10 that EFT does not always provide a good competitive ratio when minimizing maximum ow time with this structure. Disjoint intervals. We divide the cluster into m k disjoint replication intervals of size k:

I k (u) = {M j s.t. u + 1 ≤ j ≤ min(m, u + k)}, where u = k u-1 k
. This corresponds to the situation seen in Theorem 6 and related corollaries. EFT guarantees a good competitive ratio when minimizing maximum ow time with this structure. Mi (no replication)

M i (disjoint) M i (overlapping)
Figure 9: Example of replication strategies in overlapping and disjoint settings, with k = 3. For example, suppose that a task T i is feasible on M 3 only (M i = {M 3 }). Then, in overlapping setting (resp. disjoint setting), the new processing set restriction of T i is M

i = {M 3 , M 4 , M 5 } (resp. M i = {M 1 , M 2 , M 3 }).
After replication, all tasks that could only run on a given machine M j can now be processed by any machine of I k (j). To quantify the gain on maximum cluster load permitted by a given replication strategy, we solve the following optimization problem modeled as a Linear Program: maximize λ a ij denotes the average amount of work (in tasks per time unit) that is eventually processed by machine M i and that corresponds to tasks originally restricted to machine M j . We consider the following constraints:

The total work corresponding to tasks originally restricted on M j is exactly equal to the initial work of M j (Equation (15b)).

The average work eventually processed on M i does not exceed 1 (Equation (15c)).

We can transfer work from M j to M i if and only if M i belongs to the interval of size k generated from M j according to the considered replication strategy, i.e., all tasks that could originally run exclusively on M j can now also run on M i (Equation (15d)).

Experimental Evaluation of Theoretical Maximum Load

In the following experiments, we set the cluster size m to 15, which is a common setup when conducting experiments with scheduling in real key-value store systems [START_REF] Jaiman | Héron: Taming tail latencies in key-value stores under heterogeneous workloads[END_REF][START_REF] Suresh | C3: cutting tail latency in cloud data stores via adaptive replica selection[END_REF]. Figure 10a shows the result of our Linear Program (Equations ( 15)) as a function of bias s and interval size k, for both previously described replication strategies, in the Shued case (median over 100 dierent permutations).

Inria

Overlapping Disjoint At rst glance, it seems that the disjoint strategy is less ecient than the overlapping strategy to cope with high cluster load when non-uniform popularity biases are introduced. For example, for s = 1 and k = 5, Figure 10a indicates that the cluster can theoretically tolerate a maximum load of 100% when intervals overlap, whereas the disjoint strategy allows reaching a maximum load of 70%.

The overlapping strategy superiority is clearly conrmed by Figure 10b, which shows the gain on the maximum load permitted by overlapping replication intervals over the disjoint strategy.

The overlapping strategy allows the cluster to handle loads that are up to 50% higher than the disjoint strategy (e.g., for s = 1.25 and k = 6), and we can observe a gain up to 35% for common situations in key-value stores, when 0 < s ≤ 1.5 (moderate popularity bias) and k = 3 (standard replication factor in most implementations). Note that the popularity bias has obviously no eect when data are fully replicated (k = m), and that replication strategies exhibit no dierence on the tolerable load when no bias is introduced (s = 0). strategies. Each facet corresponds to a distinct case (for the Worst-case and Shued case, we set s = 1). Finally, each vertical red line shows the theoretical maximum load value given by the LP [START_REF] Mastrolilli | Notes on max ow time minimization with controllable processing times[END_REF] in the corresponding case.

Simulations with Popularity Bias

Now we simulate EFT scheduling on m = 15 machines with a popularity bias, on 10 000 generated unit tasks, which is sucient to reach a steady state. Figure 11 illustrates the impact of both replication strategies on maximum ow time in the EFT-Min scheduler and its counterpart EFT-Max (which selects the candidate machine with highest index). We consider the three cases of popularity bias (in Worst-case and Shued case, we set s = 1). We repeat the experiment 10 times, and we take the median among max-ow values. We set k = 3 to match with a realistic key-value store system.

In the Uniform case, no dierence is visible between EFT-Min and EFT-Max; however, overlapping replication intervals give better results than the disjoint strategy (e.g., for an average cluster load of 90%, EFT exhibits a max-ow of 5 when intervals overlap, whereas it gives a maxow of 10 with disjoint intervals). When randomly dispatched popularity biases are introduced (Shued case), we see the relative gain of the overlapping strategy increasing. This is even more obvious when we consider the Worst-case. We also see EFT-Max becoming more ecient than EFT-Min for the overlapping strategy, which is consistent with the situation in Theorem 8:

when breaking a tie, EFT-Min will select the most popular machine, whereas EFT-Max does the opposite (as we are in a worst-case, popularity biases are sorted in decreasing order), leading to a smaller max-ow. However, the gain permitted by the scheduling heuristic is rather marginal compared to the gain allowed by a carefully chosen replication structure.

The replication strategy where intervals overlap, commonly used in key-value stores, exhibits better results than the disjoint strategy when popularity biases are introduced, even if the maxow of EFT in disjoint setting is bounded (Theorem 6). However, there is no ecient worst-case guarantee for the overlapping strategy, as seen in Theorem 8. The question of whether there exists a replication strategy giving both good practical results and theoretical guarantees on

EFT scheduling remains open.

Inria 8 Conclusion

The high throughput and scalability needs of key-value stores require immediate dispatch algorithms in which requests are allocated to servers as soon as they arrive (such as EFT). In the absence of processing set restrictions, EFT benets from favorable competitive guarantee for the maximum ow time. However, storage constraints usually prevent replicating all data on all servers; this is modeled by introducing restrictions on the task processing sets. We provide bounds on the competitive ratio for several structured processing sets. In particular, we show that the competitive ratio of EFT goes from (3 -2/m) to m -k + 1 for interval processing sets, which are the most commonly used in key-value stores. However, despite the poor theoretical guarantee for EFT, we show experimentally that interval processing sets allow a load up to 50% larger than disjoint processing sets.

Future directions include devising a structured processing set, or replication strategy, that would provide ecient performance on average and in the worst case. Moreover, the current bound on the competitive ratio of EFT with interval processing sets could be extended to other immediate dispatch algorithms.

Figure 1 :

 1 Figure 1: Reduction graph of structures in processing set restrictions. A → B means that A is a special case of B.

Figure 2 :

 2 Figure 2: Example of scheduling for the described adversary.

Figure 3 :

 3 Figure 3: An EFT-Min schedule of the adversary from time t = 0 to t = 3, for m = 6 and k = 3. Colored tasks are released in-order at each time t.

Figure 5

 5 helps to visualize the described situation.

Figure 8 :M 1 M 2 M 3 M 4 M 5

 812345 Figure 8: Example of load distribution on a cluster of m = 6 machines, with λ = m, for each case.

  ∀i, j s.t. M i / ∈ I k (j), a ij = 0,(15d)∀i, j, a ij ≥ 0,

  Ratio between the max-load of each strategy

Figure 10 :

 10 Figure 10: Maximized load for both overlapping and disjoint strategies, for each 0 ≤ s ≤ 5 (by steps of 0.25) and 1 ≤ k ≤ m, in the Shued case. In Figure (a), we show the median value obtained from 100 dierent permutations of weights P (E j ). In Figure (b), we show the ratio between the median max-loads of both replication strategies.

Figure 11 :

 11 Figure 11: Maximum ow time given by both heuristics EFT-Min and EFT-Max as a function of the average load when k = 3, for both the overlapping (solid lines) and disjoint (dashed lines)

  for some a i ≤ b i .

	Env. Preemption	Algorithm	Type	Approx./Competitive Ratio Ref.
	P Non-preemptive FIFO any	Online Online	3 -2/m ≥ 2 -1/m	[11] [19]
	Preemptive	FIFO Ambühl et al. Online Online any Online	3 -2/m 2 -1/m ≥ 2 -1/m	[12] [19] [19]
	P |Mi Non-preemptive any	Online
					Inria

Table 2 :

 2 Competitive ratio guarantees for the problem P |online-r i , M i |F max with various processing set restrictions and depending on the type of algorithm.

RR n°9446