# Speed Scaling On Parallel Servers with MapReduce Type Precedence Constraints

Rahul Vaze and Jayakrishnan Nair Rahul Vaze is with the School of Technology
and Computer Science, Tata Institute of Fundamental Research, India.
Jayakrishnan Nair is with the Department of Electrical Engineering, IIT
Bombay, India.

###### Abstract

A multiple server setting is considered, where each server has tunable speed,
and increasing the speed incurs an energy cost. Jobs arrive to a single queue,
and each job has two types of sub-tasks, map and reduce, and a precedence
constraint among them: any reduce task of a job can only be processed once all
the map tasks of the job have been completed. In addition to the scheduling
problem, i.e., which task to execute on which server, with tunable speed, an
additional decision variable is the choice of speed for each server, so as to
minimize a linear combination of the sum of the flow times of jobs/tasks and
the total energy cost. The precedence constraints present new challenges for
the speed scaling problem with multiple servers, namely that the number of
tasks that can be executed at any time may be small but the total number of
outstanding tasks might be quite large. We present simple speed scaling
algorithms that are shown to have competitive ratios, that depend on the power
cost function, and/or the ratio of the size of the largest task and the
shortest reduce task, but not on the number of jobs, or the number of servers.

##  I Introduction

In distributed/parallel processing systems such as MapReduce [9] or Hadoop
[29], Dryad [18], jobs/flows alternate between computation and communication
stages, where a new stage cannot start until all the required tasks/flows have
been processed in the preceding stage. Essentially, there are precedence
constraints between different tasks, e.g. until all the map tasks of a job are
not completed, no reduce task of that job can be started.

A typical figure of merit in these systems is the delay seen by a job/task,
where a job consists of multiple map and reduce tasks, and the precedence
constraints present a new set of challenges for deriving optimal routing and
scheduling policies that minimize the sum of the job/task delays. There are
typically three different metrics that are considered with multiple jobs,
makespan, i.e., the finish time of the last job, completion time, i.e., the
sum of finish times (counted from time $0$) of all jobs, and flow time, i.e.,
the sum of response times (finish minus the arrival time) of all jobs. Solving
the makespan problem is typically easier than the completion time problem and
solving the flow time problem is the hardest.

The MapReduce scheduling problem has been considered in prior work quite
extensively for both single and multiple server systems, however, under the
typical assumption that the server speeds are fixed. In particular, for the
offline setting, where non-causal job arrival information is assumed, [25, 6,
30, 35, 36, 34, 32] considered either the makespan or the completion time
minimization problem, and derived approximation algorithms mostly assuming
that any map task can be split arbitrarily to allow parallel execution on
multiple servers. The more challenging online setting has been considered in
[25, 6, 35, 22], where very recently [7] found an online algorithm with
competitive ratio of $3$ for the makespan minimization problem assuming as
before that any map task can be split and executed in parallel on multiple
servers. There is some work on energy efficient MapReduce scheduling [33, 23]
with heuristic algorithms.

Makespan and flow time minimization has also been considered for general
precedence constraints represented by an acyclic directed graphs (DAG) with
fixed speed multiple servers [12, 5, 8, 27]. Most recent work in this model
does not even assume knowing the size of the jobs when they arrive [11]
(called the non-clairvoyant model).

In this paper, we consider a parallel server setting, where each server has a
tuneable speed. Corresponding to the speed of operation, there is a
power/energy cost for each server identified by function $P$ which is
typically assumed to have the form $P(s)=s^{\alpha}$ for $\alpha>1$. Clearly,
increasing the speed of the server reduces the flow time but incurs a larger
energy cost. Thus, there is a natural tradeoff between the the flow time and
the total energy cost, and a natural objective with tuneable servers is to
minimize a linear combination of the flow time and total energy, called _flow
time plus energy_.

Jobs arrive over time where each job has a fixed number of map and reduce
tasks, and any reduce task of a job can be executed only after all the map
tasks belonging to the job are completed. Both preemption and migration are
allowed, i.e., a task can be preempted on one server and restarted on another
server later, which is a natural requirement with MapReduce constraints, since
map tasks have inherently higher priority. Moreover, no task can be split, and
thus cannot be processed on multiple servers at the same time.

To keep the problem most general, we assume an arbitrary input setting, where
both the arrival times of jobs, and sizes (of tasks) are arbitrary (can be
chosen by an adversary), and the objective is to find optimal online
algorithms (that use only causal information) in terms of the competitive
ratio. Competitive ratio is defined to be ratio of the cost incurred by the
online algorithm to the cost of the optimal offline algorithm $\mathsf{OPT}$
that knows the entire input in advance, maximized over all possible inputs.

In prior work, there is a large body of work on online algorithms for the flow
time plus energy problem, however, to the best of our knowledge except [27,
3], does not consider any precedence constraints. Without precedence
constraints, online algorithms for multiple servers to minimize flow time and
energy with constant competitive ratios have been derived in [19, 13, 4, 2,
16, 20, 15, 1, 10], under both the homogenous server model, i.e., $P(.)$ is
identical for all servers, and the heterogenous model.

The most relevant work for our considered problem is [27, 24, 3], that
considers multiple servers with tuneable speed, and the objective is to find
an optimal algorithm that minimizes the completion time under a total energy
constraint for arbitrary precedence constraints defined by a directed acyclic
graph (DAG) [27] and for MapReduce type constraints [24, 3]. However, the
results of [27] are limited for the case when all jobs are available at time
$0$, and its approximation ratio scales as square of the logarithm of the
number of servers. In [24, 3], an offline problem (where the exact arrival
sequence of jobs is known a priori) to minimize the completion time with
MapReduce precedence constraints is considered. Moreover, [3] requires that
for each task there is a preassigned server that only is allowed to process
it. A power function dependent approximation ratio has been derived in [3]
with energy augmentation, improving upon [24] that considered only a single
server setting.

In this paper, our endeavour is to only consider the MapReduce type of
precedence constraints and find online algorithms for the flow time plus
energy problem with competitive ratios that do not scale with either the
number of jobs or the number of servers. The main difficulty with multiple
servers under precedence constraints is that at certain time, there might be a
large number of outstanding tasks (few map but large number of reduce tasks),
but very small (less than the number of servers) number of tasks that can be
executed (e.g. only map tasks), making some servers idle. Essentially, all the
non-triviality stems in controlling this event, since we are looking for a
sample path result against the optimal offline algorithm ($\mathsf{OPT}$) that
might keep all servers busy making the comparison between any proposed online
algorithm and $\mathsf{OPT}$ difficult.

With precedence constraints, flow time can be counted in two ways, job-wise
(departure time of the last reduce task - arrival time of job) or task-wise.
We consider both these settings in this paper. For the job-wise setting, our
results are limited for the case when all jobs arrive at time $0$ similar to
[27]. For the task-wise flow time, we consider the general online setting,
where jobs arrive over time and the algorithm has only causal information.

Throughout this paper, we consider the shortest remaining processing time
(SRPT) algorithm for executing the outstanding executable tasks on multiple
servers.111The choice of SRPT is motivated from its optimality in single
server environments (see [28]), and its near-optimal performance in multi-
server environments ([21, 31, 14]). In particular, let $n$ be the total number
of outstanding tasks, and $k\leq K$ be the number of tasks that can be
executed at time $t$. Then with $K>1$ servers, the $\min\\{k,K\\}$ tasks with
the shortest remaining size are executed on the $\min\\{k,K\\}$ servers.

With $K$ homogenous servers with power function $P(s)=s^{\alpha}$, our
contributions are as follows.222Generalizable all convex $P$ functions
satisfying Assumption 3.

  1. 1.

For the job-wise flow time + energy problem, the proposed algorithm achieves a
competitive ratio of at most $4(2-1/K)^{\alpha}+o(1)$.

  2. 2.

For the task-wise flow time + energy problem, we first propose an algorithm
that achieves the competitive ratio of at most

$P(2-1/K)(2\beta+2+2(\alpha-1))+o(1),$

where

$\beta=\frac{w_{\max}^{t}}{w_{reduce,\min}},$

and $w_{\max}^{t}$ and $w_{reduce,\min}$ is the maximum size of any map/reduce
task and the minimum size of any reduce task, respectively. Ideally, the
competitive ratio should have no dependence on the size of the map or reduce
tasks, but the competitive ratio of the proposed algorithm is a linear
function of $\beta$ (the ratio of the size of the largest map/reduce task and
the shortest reduce task). For practical MapReduce applications, $\beta$
typically small (since map tasks corresponding to any job are designed to have
nearly equal size, as are reduce tasks [17]), and hence the derived guarantee
is still meaningful. Moreover, from a theoretical point of view, as far as we
know, no competitive ratio result is known in prior work even when $\beta=1$,
i.e. all tasks have equal size.

  3. 3.

For the task-wise flow time + energy problem, for the power function
$P(s)=s^{\alpha}$, we remove the dependence of $\beta$ on the competitive
ratio next, where we show that the proposed algorithm achieves a competitive
ratio of at most $8+\frac{4}{2-\alpha}+3^{\alpha}$, however, the result holds
for only $1<\alpha<2$.

Since we adapt the SRPT algorithm to work with MapReduce constraints in this
paper, we next review and contrast this work with our recent prior work [31]
that considers the online SRPT algorithm without precedence constraints. In
[31], the competitive ratio of the SRPT algorithm with multiple servers
without any precedence constraints has been shown to to be upper bounded by
$P(2-1/m)\left(2+\frac{2}{P^{-1}(1)}\max(1,P(\bar{s}))\right),$ where
$\bar{s}$ is a constant associated with the function $P(\cdot).$ To compare
the results derived in this paper to that of [31], we note that for the job
based flow time + energy (offline) problem, adapting SRPT algorithm to work
with MapReduce constraints only changes the competitive ratio by an additive
$o(1)$ term. Thus, SRPT is adaptable with MapReduce constraints and incurs a
very small penalty in this case.

For the task based flow time + energy problem, compared to [31], using SRPT
algorithm in the presence of MapReduce constraints there is an additional
penalty of $\beta=\frac{w_{\max}^{t}}{w_{reduce,\min}}$, and $w_{\max}^{t}$ in
the competitive ratio, $w_{reduce,\min}$ is the maximum size of any map/reduce
task and the minimum size of any reduce task. Typically,
$\beta=\frac{w_{\max}^{t}}{w_{reduce,\min}}$ is small [17] for MapReduce
applications, the derived competitive ratio guarantee is still meaningful and
adapting SRPT algorithm with MapReduce algorithm is efficient.

In terms of technical novelty compared to [31], enforcing MapReduce
constraints bring in new challenges while using the SRPT algorithm. In
particular, for the job based flow time + energy problem, we introduce a new
job-SRPT algorithm that is clearly sub-optimal but helps in analytical
tractability. In particular, we prove Lemma 1, which allows us to prove the
same competitive ratio bound (upto $o(1)$ term) as in [31] even when there are
arbitrary precedence constraints between different tasks of any one job and
not just MapReduce constraints.

For the task based flow time + energy problem, as long as there are at least
$K$ (number of servers) map tasks, one can directly use results from [31]. The
main technical difficulty arises when there are less than $K$ map tasks but a
large number of reduce tasks (which cannot be processed because of the
precedence constraint). This presents a unique challenge in multi-server
systems, that there are a large number of outstanding tasks but some of the
servers are idling. Since we are considering worst case input, we have to
analyze every single sample path. To deal with this case, we construct a novel
potential function (9), and derive its drift in Lemma 9, and show that the
competitive ratio of the SRPT algorithm in presence of the MapReduce
constraints for the task based flow time + energy problem, increases by a
factor of $\beta=\frac{w_{\max}^{t}}{w_{reduce,\min}}$ compared to the SRPT
algorithm without precedence constraints [31].

To remove the dependence of the competitive ratio on $\beta$, we next consider
a small tweak to the SRPT algorithm that allows multiple tasks to be processed
simultaneously by a single server, and show that we can get a competitive
ratio independent of the instance of the problem $\beta$ that only depends on
the value of $\alpha$ where $P(s)=s^{\alpha}$ as long as $\alpha<2$. The main
technical contribution is the construction of potential function (19) and the
analysis of its derivative ($d\Phi_{4}(t)/dt$) in Appendix XIV similar to
Lemma 9.

##  II System Model

We consider a MapReduce profile of job arrivals, where each job $i$ has
$m_{i}$ map tasks and $r_{i}$ reduce tasks, where any of the reduce tasks of a
job can be executed only after the completion of all the $m_{i}$ map tasks.
Let the input consist of a set of jobs $\mathcal{J}$ with cardinality
$\mathsf{J},$ where job $i\in\mathcal{J}$ arrives (is released) at time
$a_{i},$ with the work/size of its $k^{th}$ map task being
${\mathsf{m}}_{ik},k=1,\dots,m_{i},$ and that of its $\ell^{th}$ reduce task
being ${\mathsf{r}}_{i\ell},\ell=1,\dots,r_{i}$. The set of tasks belonging to
job $i$ is denoted by $\text{Job}_{i}.$ The total number of map (respectively,
reduce) tasks summed across all jobs is denoted by ${\mathsf{n}}_{m}$
(respectively, ${\mathsf{n}}_{r}$).

Note that we are not assuming that the size of the map and reduce tasks are
identical. The model is general, where a map or reduce task can have an
arbitrary size, and derive competitive ratio guarantees that are either
dependent or independent of the map/reduce task sizes.

There are $K$ homogenous parallel servers, each with the same power function
$P(s),$ where $P(s)$ denotes the power consumed while running at speed $s$.
Any task can be processed by any of the $K$ servers, and both preemption and
task migration are allowed, which is essential with precedence constraints
(since map tasks have inherently higher priority, and reduce tasks need to be
migrated).

######  Definition 1.

A task is defined to be free at time $t$, if it can be processed at time $t$.
Thus, a map task is always free, while a reduce task is free at time $t$ if
all the map tasks belonging to the same job have been completed at time $t$. A
reduce task that is not free is called caged.

Let $c_{ik}$ be the time at which the task (map/reduce) $k$ of job $i$ is
completed. Then, the flow time ${\mathsf{f}}_{ik}$ for a map/reduce task $k$
of job $i$ is defined as ${\mathsf{f}}_{ik}=c_{ik}-a_{i}$ (completion time
minus the arrival time). We consider the two possible scenarios of counting
flow times that correspond to counting the delay seen by a job, or the sum of
the delays seen by all tasks within a job. For the job-by-job case, we define
the flow time of job $i$ as ${\mathsf{f}}_{i}=T_{i}-a_{i}$, where
$T_{i}=\max_{k\in\text{Job}_{i}}c_{ik}$ is the time at which the last reduce
task of job $i$ finishes, and total flow time is defined as
$F_{\text{job}}=\sum_{i\in\mathcal{J}}{\mathsf{f}}_{i}$. For the task-by-task
case, ${\mathsf{f}}_{i}=\sum_{k\in\text{Job}_{i}}{\mathsf{f}}_{ik}$ and the
total flow time is $F_{\text{task}}=\sum_{i\in\mathcal{J}}{\mathsf{f}}_{i}$.

$F_{\text{job}}$ corresponds to counting per-job delay cost, while the
$F_{\text{task}}$ reflects per-bit delay cost or average flow time. With both
these definitions, the following expressions for the flow time are useful.

$F_{\text{job}}=\int n(t)dt,\quad F_{\text{task}}=\int(n_{f}(t)+n_{c}(t))dt,$

where at time $t$, $n(t)$ is the number of outstanding jobs, while $n_{f}(t)$
and $n_{c}(t)$ is the number of outstanding free and caged tasks,
respectively.

Let server $k$ run at speed $s_{k}(t)$ at time $t$. The energy cost is defined
as $\sum_{k=1}^{K}P(s_{k}(t))$ integrated over the flow time. Choosing larger
speeds reduces the flow time, however, increases the energy cost, and the
natural objective function that has been considered extensively in the
literature is the sum of flow time and energy cost, which we define as

$\displaystyle C_{\text{job}}$ $\displaystyle=\int
n(t)dt+\int\sum_{k=1}^{K}P(s_{k}(t))dt,$ (1) $\displaystyle C_{\text{task}}$
$\displaystyle=\int(n_{f}(t)+n_{c}(t))dt+\int\sum_{k=1}^{K}P(s_{k}(t))dt.$ (2)

Note that we have added the two costs without weighting them, since the weight
can be absorbed in the power function $P$. Any online algorithm only has
causal information, i.e., it becomes aware of job $i$ only at time $a_{i}$.
Using only this causal information, any online algorithm has to decide at what
speed each server should be run at at each time. Let the job arrival sequence
be $\sigma=\\{(a_{i}),({\mathsf{m}}_{ik}),({\mathsf{r}}_{i\ell}),\
i\in\mathcal{J}\\}$. For the online algorithm $\sigma$ is revealed causally,
while for an offline algorithm $\sigma$ is assumed to be known in advance. Let
the cost (1) of an online algorithm $A$ be $C^{A}$, and the cost for the
offline optimal algorithm $\mathsf{OPT}$ be $C^{\mathsf{OPT}}$. Then the worst
case competitive ratio of the online algorithm $A$ is defined as
${\mathsf{c}}_{A}=\max_{\sigma}\frac{C^{A}(\sigma)}{C^{\mathsf{OPT}}(\sigma)}$,
and the objective function considered in this paper is to find an online
algorithm that minimizes the worst case competitive ratio
${\mathsf{c}}^{\star}=\min_{A}{\mathsf{c}}_{A}$.

A typical approach in speed scaling literature to upper bound the competitive
ratio ${\mathsf{c}}_{A}$ for an algorithm A is via the construction of a
potential function $\Phi(t)$ and show that for any input sequence $\sigma,$

$n(t)+\sum_{k=1}^{K}P(s_{k}(t))+\frac{d\Phi(t)}{dt}\leq{\mathsf{c}}_{A}\biggl{(}n^{o}(t)+\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k}(t))\biggr{)},$
(3)

whenever $\frac{d\Phi(t)}{dt}$ exists, and ${\tilde{s}_{k}}$ is the speed of
server $k$ with the $\mathsf{OPT}$ and $n^{o}$ stands for the number of
outstanding jobs with the $\mathsf{OPT}$, and that $\Phi(t)$ satisfies the
following boundary conditions,

  1. 1.

Before any job arrives and after all jobs are finished, $\Phi(t)=0$, and

  2. 2.

$\Phi(t)$ does not have a positive jump discontinuity at any point of non-
differentiability.

For the task based flow time, $n(t)$ is replaced by $n_{f}(t)+n_{c}(t)$ in
(3). Then, integrating (3) with respect to $t$, we get that

$\displaystyle\int\left(n(t)+\sum_{k=1}^{K}P(s_{k}(t))\right)\leq{\mathsf{c}}_{A}\int\biggl{(}n^{o}(t)+\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k}(t))\biggr{)},$

which is equivalent to showing that $C^{A}(\sigma)\leq c_{A}\
C^{\mathsf{OPT}}(\sigma)$ for any input $\sigma$ as required.

######  Remark 2.

Suppose that the second boundary condition is not satisfied, and let $\Phi(t)$
increase by amount $D_{j}$ at the $j^{th}$ discontinuous point, such that the
total increase is $\sum_{j}D_{j}\leq\mathsf{D}\ C^{\mathsf{OPT}}$. If (3)
holds at points where $\Phi(t)$ is differentiable, then we get that
$C^{A}(\sigma)\leq({\mathsf{c}}_{A}+\mathsf{D})\ C^{\mathsf{OPT}}(\sigma)$ for
any input $\sigma$, making the upper bound on the competitive ratio
${\mathsf{c}}_{A}+\mathsf{D}$.

One easy lower bound on the $\mathsf{OPT}$’s cost can be obtained by removing
the precedence constraints, and considering that the arrival sequence is such
that no job/task has to wait behind any other job/task. Thus, the cost of
$\mathsf{OPT}$ for any job/task with size $w$ is $\min_{s}w/s+(w/s)P(s)$. The
optimal speed $s$ satisfies $1+P(s^{\star})=s^{\star}P^{\prime}(s^{\star})$
and the optimal per job/task cost is $wP^{\prime}(s^{\star})$. With
$P(s)=s^{2}$, $s^{\star}=1$, and the minimum flow time + energy for any
job/task is $2w$. Counting across all jobs/tasks, we get the following lower
bound.

######  Proposition 1.

For the $\mathsf{OPT}$, $C_{\text{job}}^{\mathsf{OPT}}(\sigma)\geq
P^{\prime}(s^{\star})(\sum_{j\in\mathcal{J}}w_{j})$ and
$C_{\text{task}}^{\mathsf{OPT}}(\sigma)\geq
P^{\prime}(s^{\star})(\sum_{j\in\mathcal{J}}({\mathsf{m}}_{jk}+{\mathsf{r}}_{j\ell}))$,
where $1+P(s^{\star})=s^{\star}P^{\prime}(s^{\star})$.

Throughout this paper, we make the following assumptions about the power
function $P(.)$.

######  Assumption 3.

$P:{\mathbb{R}}_{+}\rightarrow{\mathbb{R}}_{+}$ with $P(0)=0$ is a
differentiable, strictly increasing, and strictly convex function, which
implies $\lim_{s\rightarrow\infty}P(s)=\infty,$ and $\bar{s}:=\inf\\{s>0\ |\
P(s)>s\\}<\infty$. Moreover, for $x,y>0,$ $P(xy)\leq P(x)P(y).$ We also assume
that $\Delta(x)=P^{\prime}(P^{-1}(x))=o(x)$ as $x\rightarrow\infty.$

Assumption 3 is satisfied by power functions of the form $P(s)=cs^{\alpha},$
where $\alpha>1$ and $c\geq 1.$ For simplicity, we will use $P(s)=s^{\alpha}$
(where $\alpha>1$) in the rest of the paper (our argument generalize easily to
power functions that satisfy Assumption 3); in this case, $\Delta(x)=\alpha
x^{1-1/\alpha}.$ This assumption is needed for application of Lemma 8 that is
useful in bounding the derivative of the potential functions.

######  Assumption 4.

In Section III, where we consider the job-based flow time metric, we assume a
natural _many jobs_ scaling, where the total number of jobs $\mathsf{J}$ is
large, while the maximum size of any job $w_{\max}$ and the number of servers
$K$ satisfy
$Kw_{\max}\Delta\left(\mathsf{J}/K\right)=o(\sum_{i=1}^{\mathsf{J}}w_{j})$,
which is quite a mild requirement and easily satisfied in practice. For
$P(s)=s^{\alpha},$ this means
$K^{1/\alpha}w_{\max}\mathsf{J}^{1-1/\alpha}=o(\sum_{i=1}^{\mathsf{J}}w_{j})$.
In Section IV, where we consider task-based flow time metric, we assume a
natural _many tasks_ scaling where the total number of map plus reduce tasks
${\mathsf{n}}_{m}+{\mathsf{n}}_{r}$ is large, and
$O(\mathsf{J}w^{t}_{\max}K^{2}r_{\max}^{1-\frac{1}{\alpha}})=o(\sum_{j\in\mathcal{J}}({\mathsf{m}}_{jk}+{\mathsf{r}}_{j\ell}))$
where, $w^{t}_{\max}$ denotes the size of the largest map/reduce task, and
$r_{\max}$ is the maximum number of reduce tasks any job can have.

We essentially need Assumption 4 to couple the increase in the potential
functions at the points of discontinuities, and the total cost of the
$\mathsf{OPT}$.

##  III Job Based Flow Time

In this section, we consider the job-by-job flow time and the cost metric is
$C_{\text{job}}$ (1). We restrict ourselves to the case that all jobs are
available at time $0$. The objective is to propose an algorithm with a
constant approximation (competitive) ratio. This is typically a difficult task
since there are intra-job precedence constraints, and the flow time is counted
as the departure time of the last reduce task of a job minus its arrival time,
coupling the processing of different tasks of the system.

To overcome this difficulty, we propose a job-by-job SRPT algorithm, called
job-SRPT, as follows. For any task (map or reduce) $k$ of job $j$, let
$w_{kj}(t)$ be its total remaining work at time $t$. Then the total remaining
cumulative work of job $j$ at time $t$ is defined as
$w_{j}(t)=\sum_{k\in\text{Job}_{j}}w_{kj}(t)$ (sum of the sizes of all its map
and reduce tasks). Index the $n(t)$ outstanding jobs at time $t$ in increasing
order of their remaining cumulative work. If $n(t)\geq K$, the job-SRPT
algorithm processes the $K$ shortest jobs on the $K$ servers, and on each
server the shortest free task of each job is executed. Thus, each server is
executing a task corresponding to a different job at each time. Otherwise, if
$n(t)<K$, then the $n(t)$ distinct jobs (shortest free task of that job) are
executed on the $n(t)$ servers, and for the rest of $K-n(t)$ servers, the
$K-n(t)$ shortest free tasks (other than the ones already executing) across
all outstanding $n(t)$ jobs are executed. For the job-SRPT algorithm, we
propose the following speed. For server $k$,

$s_{k}(t)=\begin{cases}&P^{-1}\left(\frac{n(t)}{K}\right)\ \text{if}\ n(t)\geq
K,\\\ &P^{-1}(1),\ \ \ \ \ \ \ \ \ \text{otherwise}.\end{cases}$ (4)

The main result of this section for the job-based flow time + energy problem
is as follows.

######  Theorem 5.

Under Assumptions 3 and 4, the job-SRPT algorithm with speed scaling (4) for
job based flow time problem has competitive ratio
$P(2-1/K)\left(2+\frac{2}{P^{-1}(1)}\max(1,P(\bar{s}))\right)+o(1)$, where
$\bar{s}$ is defined in Assumption 3.

Taking $P(s)=s^{\alpha}$ for $\alpha>1,$ the competitive ratio equals
$4(2-1/K)^{\alpha}+o(1).$ It is worth noting that this competitive ratio is
same as with the no precedence constraints case in [31] with multi-server SRPT
algorithm up to a $o(1)$ term.

Clearly, the job-SRPT algorithm is not optimal since one can easily construct
an example where executing multiple tasks from the same job on different
servers is better, however, the job-SRPT algorithm allows analytical
tractability because of the following lemma.

######  Lemma 1.

With MapReduce precedence constraints, when all jobs are available at time
$0$, for $K$ fixed speed servers, $\mathsf{OPT}$ that follows the job-SRPT
algorithm with server speed $(2-1/K)$ has a sum of job flow times that is at
most that under $\mathsf{OPT}$ with $K$ servers having speed $1$ for any job
input sequence $\sigma$.

This lemma is similar to the claim for classical SRPT [26], where each job is
a single autonomous entity without any precedence constraints, and follows by
proving Lemma 13 and Lemma 2. Importantly, the claim in [26] is true for
classical SRPT even in the online case, when jobs are released over time.
However, with precedence constraints, it is not true for the job-SRPT
algorithm (Lemma 2 no longer holds) in the online case. The main reason is
that, if at any time there is a single job with multiple tasks that are being
processed simultaneously, an arrival of new job does not guarantee that the
number of jobs departed by any future time is at least as many as the ones
would have departed if the new job would not have arrived.

How Lemma 1 helps is as follows. In light of Lemma 1, we can let
$\mathsf{OPT}$ execute the job-SRPT algorithm with an arbitrary unknown speed
and claim that it is $P(2-1/K)$-approximate with respect to $\mathsf{OPT}$
(executes arbitrary scheduling and speed choice). Note that $\mathsf{OPT}$
will process all tasks of a job at the same speed because of convexity of $P$.
Thus, for a job $j$, let the speed $\mathsf{OPT}$ uses be $s_{j}$. Then for
$\mathsf{OPT}$ following job-SRPT, the speed of job $j$ (whenever any task of
job $j$ is scheduled) is chosen to be $(2-1/K)s_{j}$. Thus, $\mathsf{OPT}$
following job-SRPT will have at most the same flow-time as the $\mathsf{OPT}$
from Lemma 1, with an additional energy cost of $P(2-1/K)$. Thus,
$\mathsf{OPT}$ following job-SRPT is $P(2-1/K)$-approximate with respect to
$\mathsf{OPT}$.

For the rest of the section, we call $\mathsf{OPT}$ following job-SRPT as
$\mathsf{OPT}$. The main advantage of considering job-SRPT for both the
algorithm and the $\mathsf{OPT}$, is that we can get rid of all the precedence
constraints within a job, since at any time only the $K$ distinct shortest
(cumulative) jobs are being processed if the number of outstanding jobs is at
least $K$. Since all jobs are available at time $0$, the case that multiple
tasks belonging to the same job are processed simultaneously occurs only when
the number the number of outstanding jobs is less than $K$, which can be
handled separately.

Using job-SRPT algorithm for scheduling, we use the same potential function
that has been proposed in [31] to analyze multi-server SRPT algorithm. Recall
that the remaining cumulative size of any job be the sum of the remaining
sizes of its map and reduce tasks. At time $t$, let $n^{o}(t,q)$ and $n(t,q)$
denote the number of unfinished jobs with the $\mathsf{OPT}$ and the
algorithm, respectively, with remaining cumulative size at least $q$. In
particular, $n^{o}(t,0)=n^{o}(t)$ and $n(t,0)=n(t)$. Let

$d(t,q)=\max\left\\{0,n(t,q)-n^{o}(t,q)\right\\}.$

Let $f:\\{i/K:\ i\in{\mathbb{Z}}_{+}\\}\rightarrow{\mathbb{R}}_{+}$ is defined
as follows: $f(0)=0,$ and for $i\geq 1,$
$f\left(\frac{i}{K}\right)=f\left(\frac{i-1}{K}\right)+\Delta\left(\frac{i}{K}\right)$,
where $\Delta(x):=P^{\prime}(P^{-1}(x)).$ We consider the potential function

$\displaystyle\Phi(t)$ $\displaystyle=\Phi_{1}(t)+\Phi_{2}(t),$ (5)
$\displaystyle\Phi_{1}(t)$
$\displaystyle=c_{1}\int_{0}^{\infty}f\left(\frac{d(t,q)}{K}\right)dq,$ (6)
$\displaystyle\Phi_{2}(t)$
$\displaystyle=c_{2}\int_{0}^{\infty}(n(t,q)-n^{o}(t,q))dq,$ (7)

where $c_{1},c_{2}$ are positive constants whose value will be specified
later. $\Phi_{1}$ part is sufficient for the case when the $n(t)\geq K$, while
$\Phi_{2}$ is needed to handle the case when $n(t)<K$.

######  Remark 6.

As long as there are $K$ distinct jobs with both the algorithm and the
$\mathsf{OPT}$, because of processing by the algorithm, $d(t+dt,q)=d(t,q)-1$
for $q\in[q_{k}-s_{k}(t)dt,q_{k}]$, where $q_{k},k=1,\dots,K$ is the remaining
(cumulative) size of the shortest $K$ jobs. Similarly, for the $\mathsf{OPT}$,
$d(t,q)=d(t,q)+1$ for $q\in[q^{o}_{k}-{\tilde{s}}_{k}(t)dt,q^{o}_{k}]$, for
$q^{o}_{k},k=1,\dots,K$. Thus, one can use the results from [31] (Lemma 3)
directly when both the algorithm and the $\mathsf{OPT}$ have $K$ distinct
jobs, to bound the drift $d\Phi_{1}/dt$, that are valid for the case when each
job has a single task, and no job can be split and processed parallely on
multiple servers. When either the algorithm or the $\mathsf{OPT}$ has less
than $K$ jobs available, the job-SRPT algorithm, may process more than one
task belonging to the same job simultaneously on multiple servers and [31]
(Lemma 3) is not directly applicable. Since the algorithm’s contribution to
the drift $d\Phi_{1}/dt$ is negative, we can just count one term $d(q)=d(q)-1$
for $q\in[q_{k}-s_{k}(t)dt,q_{k}]$ for each of the distinct jobs and disregard
the contribution in drift $d\Phi_{1}/dt$ from multiple tasks of a same job
that are being processed simultaneously. This, however, cannot be done for the
$\mathsf{OPT}$, since $\mathsf{OPT}$’s contribution is positive in drift
$d\Phi_{1}/dt$, and to handle this case, we introduce deletion of tasks for
the $\mathsf{OPT}$ (defined next) which will make $\Phi_{1}$ and $\Phi_{2}$
increase discontinuously, and we will count the total increase in
$\Phi_{1}(t)$ and $\Phi_{2}$ at all points of discontinuities.

Deleting tasks with the $\mathsf{OPT}$: Let the time instant at which
$\mathsf{OPT}$ has $k$ outstanding jobs be $t_{k}$, where $k=K-1,K-2,\dots,1$.
Note that $t_{k}$’s need not be distinct. Let at time $t_{k}$, the set of jobs
$j$ for which the $\mathsf{OPT}$ is about to process more than one task
parallely be $S_{k}$. Then at $t_{k}^{-}$, for all jobs $j\in S_{k}$, we
delete all its reduce tasks and all the map tasks other than its shortest map
task. This will ensure that there is at most one task of each job being
processed by any of the servers throughout, allowing the applicability of
Lemma 3 [31]. The deletion of tasks will result in a total upward jump in
$\Phi_{1}(t)$ and $\Phi_{2}(t)$ which can be bounded as follows (proof in
Appendix IX).

######  Lemma 2.

The total upward jump in the potential function $\Phi_{1}(t)$ and
$\Phi_{2}(t)$ because of deletion of tasks with the $\mathsf{OPT}$ is
$\sum_{j=1}^{K-1}c_{1}w_{j}\Delta(\frac{\mathsf{J}}{K})+\sum_{j=1}^{K-1}c_{2}w_{j}$,
where $w_{j}$ are the sizes of potentially the $K-1$ largest (cumulative) size
jobs, and $\mathsf{J}$ is the total number of jobs in the input.

Next, we state Lemma 3 and Lemma 4 from [31] that allows us to bound the
derivative of $\Phi_{1}(t)$ and $\Phi_{2}(t)$ as long as $\mathsf{OPT}$ does
not process more than one task belonging to the same job on multiple servers,
and we count contribution of only distinct jobs of the algorithm in
$d\Phi_{1}(t)/dt$ and $d\Phi_{2}(t)/dt$.

######  Lemma 3.

When $\mathsf{OPT}$ does not process more than one task belonging to the same
job simultaneously on multiple servers, for $n\geq K$, $d\Phi_{1}/dt\leq
c_{1}n^{o}-c_{1}n+c_{1}\left(\frac{K-1}{2}\right)+c_{1}\sum_{k\in\mathsf{OPT}}P(\tilde{s}_{k})$,
while for $n<K,$ $d\Phi_{1}/dt\leq
c_{1}n^{o}-c_{1}\frac{n(n+1)}{2K}+c_{1}\sum_{k\in\mathsf{OPT}}P(\tilde{s}_{k})$.

######  Lemma 4.

$d\Phi_{2}/dt\leq-
c_{2}\min(K,n)P^{-1}(1)+c_{2}\sum_{k\in\mathsf{OPT}}\max\\{P(\bar{s}),P({\tilde{s}}_{k})\\}.$

Now, we prove Theorem 5. From Proposition 1, note that the minimum cost
$C_{\text{job}}$ (1) of $\mathsf{OPT}$ is at least
$P(s^{\star})\sum_{j=1}^{\mathsf{J}}w_{j}$. From Lemma 2, we have that the
total jump size at all points of discontinuities is
$\sum_{j=1}^{K-1}c_{1}w_{j}\Delta(\frac{\mathsf{J}}{K})+\sum_{j=1}^{K-1}c_{2}w_{j}$.
From Assumption 3, $\Delta(\frac{\mathsf{J}}{K})=o(\mathsf{J}/K)$, e.g. for
$P(s)=s^{\alpha}$, $\Delta(x)=O(x^{1-1/\alpha})$. Thus, $D=o(1)$ from
Assumption 4 and Remark 2. Thus, if we can show that (3) holds for some $c$,
we will have that the total competitive ratio is upper bounded by $c+o(1)$.
From Remark 6, we ensure that the $\mathsf{OPT}$ never processes more than one
task belonging to the same job, thus applying, Lemma 3 and 4, (similar to
[31]) we get (3)

$\displaystyle n+\sum_{k\in A}P(s_{k})+d\Phi(t)/dt$
$\displaystyle=n+n+1+d\Phi(t)/dt,$ $\displaystyle\leq
c\bigl{(}n^{o}+\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k})\bigr{)},$

is true for $c=\left(2+\frac{2}{P^{-1}(1)}\max(1,P(\bar{s}))\right)$, where
$c_{1}=2$, $c_{2}=2/P^{-1}(1)$.

Discussion: By introducing the job-SRPT algorithm, we have effectively removed
the precedence constraints within each job. By processing as many distinct
jobs, the job-SRPT policy ensures that there is sufficient drift available for
the choice of the potential function, and allows leveraging of the recent
analysis of the multi-server SRPT algorithm [31]. It is worth noting that the
analysis of this section (Theorem 5) holds even when the precedence
constraints are arbitrary within each job.

##  IV Task Based Flow Time

In this section, we consider the task-by-task flow time where the cost metric
is $C_{\text{task}}$ (2). We consider the online setting, where jobs arrive
over time arbitrarily, and the objective is to propose an online algorithm and
bound its competitive ratio. The competitive ratio guarantee of our proposed
online algorithm will be a function of
$\beta=\frac{w_{\max}^{t}}{w_{reduce,\min}}$, where $w_{\max}^{t}$ and
$w_{reduce,\min}$ is the maximum size of any map/reduce task and the minimum
size of any reduce task, respectively. Since for the MapReduce framework, this
ratio is typically small, the guarantees are meaningful [17]. Moreover, even
when $\beta=1$, the problem is non-trivial, since how to construct potential
function for the case when the number of map tasks is smaller than the number
of servers but there are large number of caged reduce jobs is not clear, and
to the best of our knowledge no competitive ratio guarantees are known in the
online case.

$\mathsf{OPT}$: Throughout this section, we assume that the $\mathsf{OPT}$ has
no precedence constraints across tasks, and can process any of its outstanding
tasks at any time. This can only decrease the $\mathsf{OPT}$’s cost. Moreover,
we assume that without precedence constraints, $\mathsf{OPT}$ follows the
multi-server SRPT algorithm, i.e., among its all outstanding tasks $n^{o}$, it
processes the $\min\\{n^{o},K\\}$ shortest tasks (map/reduce since there are
no precedence constraints for $\mathsf{OPT}$) on the $\min\\{n^{o},K\\}$
servers at any time. Since the multi-server SRPT algorithm that has access to
future arrivals and can choose arbitrary speed depending on it is
$P(2-1/K)$-competitive with respect to $\mathsf{OPT}$ with no precedence
constraints [31], we will get an additional factor of $P(2-1/K)$ in the final
competitive ratio.

We need the following definition to describe our algorithm.

######  Definition 7.

For a map task $j$ belonging to job $i$, define its load as
$\ell_{j}={\mathsf{r}}_{i}+1$, the number of reduce tasks in the job $i$ that
it precedes plus $1$ for itself. For a map task $j$, $b_{j}(t)$
($b^{o}_{j}(t)$) be the number of (brother map tasks) outstanding map tasks
belonging to the same job as task $j$ with the algorithm ($\mathsf{OPT}$) at
time $t$. Moroever, let ${\hat{b}}(t)=\min\\{b(t),K\\}$ and
$z_{j}({\hat{b}}_{j},t)=\frac{\ell_{j}+{\hat{b}}_{j}(t)}{{\hat{b}}_{j}(t)}$.

Algorithm: Let the total number of outstanding tasks at time $t$ be $n(t)$ out
of which $n_{f}(t)$ are free, i.e., $n_{f}(t)$ is the sum of all the map tasks
and all the free reduce tasks. The algorithm processes the
$\min\\{n_{f}(t),K\\}$ shortest free tasks on the $\min\\{n_{f}(t),K\\}$
servers. If $n_{f}(t)\geq K$, then all servers process at speed
$P^{-1}\left(\frac{n(t)+1}{K}\right)$. Otherwise, server $k$ has speed

$\displaystyle
s_{k}(t)=\begin{cases}P^{-1}\left(\frac{\ell_{j}+{\hat{b}}_{j}(t)+1}{{\hat{b}}_{j}(t)}\right)\
\text{if $k$ is processing map task}\ j,&\\\ P^{-1}(1)\ \quad\quad\text{if $k$
is processing a free reduce task.}&\end{cases}$ (8)

The main result of this section is as follows.

######  Theorem 8.

The competitive ratio of the proposed online algorithm is
$P(2-1/K)(2\beta+2+2(\alpha-1))+o(1)$, where
$\beta=\frac{w_{\max}^{t}}{w_{reduce,\min}}$.

Next, we work towards proving Theorem 8. At time $t$, let $n^{o}(t,q)$ and
$n(t,q)$ denote the number of unfinished tasks (map + reduce) under the
$\mathsf{OPT}$ and the algorithm, respectively, with remaining size at least
$q$. In particular, $n^{o}(t,0)=n^{o}(t)$ and $n(t,0)=n(t)$. Let
$d(t,q)=\max\left\\{0,n(t,\frac{q}{\beta})-n^{o}(t,\frac{q}{\beta})\right\\}$.
We consider the potential function

$\displaystyle\Phi(t)$ $\displaystyle=\Phi_{1}(t)+\Phi_{2}(t)+\Phi_{3}(t),$
$\displaystyle\Phi_{1}(t)$
$\displaystyle=c_{1}\int_{0}^{\infty}f\left(\frac{d(t,q)}{K}\right)dq,$
$\displaystyle\Phi_{2}(t)$
$\displaystyle=c_{2}\int_{0}^{\infty}(n(t,q)-n^{o}(t,q))dq,$

where $c_{1},c_{2}$ are positive constants and function $\Phi_{3}$ which is
specially designed for handling the precedence constraints is defined in (9).
Let $m(t)=\sum_{i\in\text{outstanding jobs}}m_{i}(t)$ be the number of
outstanding map tasks with the algorithm at time $t$. Similarly, define
$m^{o}(t)$ for the $\mathsf{OPT}$. For the $j^{th},j=1,\dots,m(t)(m_{o}(t))$
map task, let $q_{j}$ ($q_{j}^{o}$) be its remaining size with the algorithm
and the $\mathsf{OPT}$, respectively. Then for the $j^{th}$ map task, let
$h_{j}(t,q)=1$ ($h_{j}^{o}(t,q)=1$) for $q\leq q_{j}$ ($q\leq q_{j}^{o}$) and
zero otherwise. Define

$\displaystyle\Phi_{3}(t)$ $\displaystyle=$ $\displaystyle
c_{3}\left(\sum_{j\in m(t)}\int
g_{z_{j}({\hat{b}}_{j},t)}\left(z_{j}({\hat{b}}_{j},t)h_{j}(t,q)\right)dq\right.$
(9) $\displaystyle-\left.\sum_{j\in m_{o}(t)}\int
g_{z_{j}^{o}({\hat{b}}^{o}_{j},t)}\left(z_{j}^{o}({\hat{b}}^{o}_{j},t)h_{j}^{o}(t,q)\right)dq\right),$

where for $i\in{\mathbb{N}},$ let
$g_{a}\left(ai\right)-g_{a}\left(a(i-1)\right)=\Delta\left(ai\right):=P^{\prime}\left(P^{-1}\left(ai\right)\right)$
and $g_{a}(0)=0$.

Note that both the boundary conditions are satisfied for $\Phi_{1}$ and
$\Phi_{2}$. However, $\Phi_{3}$ only satisfies the first boundary condition,
i.e., $\Phi_{3}=0$ before any job is released and after all jobs are finished.
It does not satisfy the second boundary condition, however, the total jump in
$\Phi_{3}$ at points of discontinuity can be bounded as follows.

######  Lemma 5.

The total upward jump in the potential function $\Phi_{3}(t)$ is at most
$O(\mathsf{J}w_{\max}K^{2}r_{\max}^{1-\frac{1}{\alpha}})$ that is
$o(\sum_{j\in\mathcal{J}}({\mathsf{m}}_{jk}+{\mathsf{r}}_{j\ell}))$ under
Assumption 4.

Next, we work towards finding the drift (derivative) of $\Phi(t)$. The drift
terms for the potential function $\Phi_{1}$ can be derived from [31, Lemma
10], where the only difference between $\Phi_{1}$ considered in this paper and
[31] is that $q$ scaled by $1/\beta$. In [31], without any precedence
constraints, the shortest $\min\\{n(t),K\\}$ jobs (that have a single task)
with size $q_{1}\leq\dots\leq q_{\min\\{n(t),K\\}}$ are processed by the
algorithm, making $n(t,q_{i})=n(t)-i$ for all $i=1,\dots,\min\\{n(t),K\\}$.
With the precedence constraint in this section, the algorithm processes the
$\min\\{n_{f},K\\}$ free tasks which are not necessarily the $\min\\{n,K\\}$
shortest tasks, since a caged reduce task could be smaller but not being
processed. Let $q_{1}\leq q_{2},\dots,\leq q_{\min\\{n_{f},K\\}}$ be the
remaining sizes of the $\min\\{n_{f},K\\}$ shortest free tasks being
processed. This scaling of $q$ by $\beta$ ensures that even when the absolute
shortest task is not being processed by the algorithm $n(t,q_{i}/\beta)\geq
n(t)-i$ for $i=1,\dots,\min\\{n_{f},K\\}$, since the size of any caged reduce
job is at least $w_{reduce,\min}$. Since $\beta$ is a constant, scaling of $q$
by $1/\beta$ translates to having an additional $\beta$ factor in the
derivative of $\Phi_{1}(t)$, and we get the following result, where
${\tilde{s}}_{k}$ is the speed of server $k$ with the $\mathsf{OPT}$.

######  Lemma 6.

[31, Lemma 10] For $n_{f}\geq
K$,$d\Phi_{1}/dt\leq\frac{c_{1}}{\beta}n^{o}-\frac{c_{1}}{\beta}n+\frac{c_{1}}{\beta}\left(\frac{K-1}{2}\right)+c_{1}\sum_{k\in\mathsf{OPT}}P(\tilde{s}_{k}),$
while for $n_{f}<K,$
$d\Phi_{1}/dt\leq\frac{c_{1}}{\beta}n^{o}-\frac{c_{1}}{\beta}\frac{n(n+1)}{2K}+c_{1}\sum_{k\in\mathsf{OPT}}P(\tilde{s}_{k})$.

######  Lemma 7.

[31, Lemma 11] $d\Phi_{2}/dt\leq-
c_{2}\min(K,n)P^{-1}(1)+c_{2}\sum_{k\in\mathsf{OPT}}P(\tilde{s}_{k})$.

Next, we quantify the more non-trivial drift of $\Phi_{3}(t)$ because of the
processing by the algorithm and the $\mathsf{OPT}$. We will need the following
result from [4].

######  Lemma 8.

[Lemma 3.1 in [4]] Let $P$ satisfy Assumption 3. Then for
$s_{k},{\tilde{s}}_{k},x\geq 0$,

$\displaystyle\Delta(x)(-s_{k}+{\tilde{s}}_{k})\leq$
$\displaystyle\left(-s_{k}+P^{-1}(x)\right)\Delta(x)+P({\tilde{s}}_{k})-x.$

Let $n_{fr}(t)$ be the free reduce tasks at time $t$, and let
${\hat{n}}(t)=n(t)-n_{fr}(t)$ $({\hat{n}}^{o}(t))$ be the number of
outstanding tasks other than the free reduce tasks at time $t$ with the
algorithm ($\mathsf{OPT}$). The main new result we need with precedence
constraints is as follows, where ${\mathbf{1}}_{\\{e\\}}=1$ if event $e$ is
true and zero otherwise.

######  Lemma 9.

$d\Phi_{3}/dt\leq-
c_{3}{\mathbf{1}}_{\\{n_{f}<K\\}}{\hat{n}}(t)+c_{3}(\alpha-1)({\hat{n}}^{o}(t))+c_{3}\sum_{k=1}^{m^{o}(t)}P(\tilde{s}_{k})$,

###### Proof.

For notational simplicity, we suppress the time index, since we are
considering a fixed time $t$. Consider the change in $\Phi_{3}$ due to
$\mathsf{OPT}$ ($h_{j}^{o}(q)\rightarrow h_{j}^{o}(q)-1$) for at most $m^{o}$
map tasks in the interval $[q_{j}^{o},q_{j}^{o}-{\tilde{s}}_{j}dt]$ where
$q_{j}^{o}$ is the remaining size of the $j^{th}$ map task with the
$\mathsf{OPT}$:

$\displaystyle d\Phi_{3}$ $\displaystyle\leq$ $\displaystyle
c_{3}\sum_{j=1}^{m^{o}}\biggl{[}g_{z_{j}^{o}({\hat{b}}^{o})}\left(z_{j}^{o}({\hat{b}}^{o})h_{j}^{o}(q_{j}^{o})\right)dq\biggr{.}$
(10)
$\displaystyle-\biggl{.}g_{z_{j}^{o}({\hat{b}}^{o},t)}\left(z_{j}^{o}({\hat{b}}^{o})(h_{j}^{o}(q_{j}^{o})-1)\right)dq\biggr{]}{\tilde{s}}_{j}dt,$
$\displaystyle=$ $\displaystyle
c_{3}\sum_{j=1}^{m^{o}}\Delta\left(\frac{\ell_{j}^{o}+{\hat{b}}_{j}^{o}}{{\hat{b}}_{j}^{o}}h_{j}^{o}(q_{j}^{o})\right){\tilde{s}}_{j}dt,$
$\displaystyle=$ $\displaystyle
c_{3}\sum_{j=1}^{m^{o}}\Delta\left(\frac{\ell_{j}^{o}+{\hat{b}}_{j}^{o}}{{\hat{b}}_{j}^{o}}\right){\tilde{s}}_{j}dt,$

since $h_{j}^{o}(q_{j}^{o})=n_{j}^{o}=1$. Using Lemma 8 individually on the
${m^{o}}$ terms of (10) with $s_{k}=0$, and noting that
$P^{-1}(x)\Delta(x)=(\alpha-1)x$, we get

$\displaystyle d\Phi_{3}$ $\displaystyle\leq$ $\displaystyle
c_{3}(\alpha-1)\sum_{j=1}^{m^{o}}\left(\frac{\ell_{j}^{o}+{\hat{b}}_{j}^{o}}{{\hat{b}}_{j}^{o}}\right)+c_{3}\sum_{j=1}^{m^{o}}P(\tilde{s}_{k}),$
(11) $\displaystyle\leq$ $\displaystyle
c_{3}(\alpha-1)({\hat{n}}^{o}(t))+c_{3}\sum_{j=1}^{m^{o}}P(\tilde{s}_{k}),$
(12)

since the number of tasks $n_{k}$ in job $k$ to which map task $j$ belongs
$n_{k}=\ell_{j}^{o}+{\hat{b}}_{j}^{o}$.

Next, we consider the change in $\Phi_{3}$ because of algorithm’s execution
only when $n_{f}<K$ i.e., there are $n_{m}\leq K-1$ outstanding map tasks. Let
these $n_{m}$ outstanding map tasks belong to $|J|$ distinct jobs. Because of
algorithm’s execution, $h_{j}(q)\rightarrow h_{j}(q)-1$ for map task $j$ in
the interval $[q_{j},q_{j}-s_{j}dt]$ where $q_{j}$ is the remaining size of
the $j^{th}$ map task with the algorithm. Thus,

$\displaystyle d\Phi_{3}$ $\displaystyle=$ $\displaystyle
c_{3}\sum_{j=1}^{n_{m}}\biggl{[}g_{z_{j}({\hat{b}})}\left(z_{j}({\hat{b}})(h_{j}(q_{j})-1)\right)\biggr{.}$
(13)
$\displaystyle\biggl{.}-g_{z_{j}({\hat{b}},t)}\left(z_{j}({\hat{b}})(h_{j}(q_{j}))\right)\biggr{]}s_{j}dt,$
$\displaystyle=$ $\displaystyle-
c_{3}\sum_{j=1}^{n_{m}}\Delta\left(\frac{\ell_{j}+{\hat{b}}_{j}}{{\hat{b}}_{j}}h_{j}(q_{j})\right)s_{j}dt,$
$\displaystyle=$ $\displaystyle-
c_{3}\sum_{j=1}^{n_{m}}\Delta\left(\frac{\ell_{j}+{\hat{b}}_{j}}{{\hat{b}}_{j}}\right)s_{j}dt,$

since $h_{j}(t,q_{j})=1$. Using Lemma 8 individually on each of the $n_{m}$
terms with ${\tilde{s}}_{k}=0$, we get

$\displaystyle d\Phi_{3}$ $\displaystyle\leq$ $\displaystyle
c_{3}\sum_{j=1}^{n_{m}}\left(-s_{j}+P^{-1}\left(\frac{\ell_{j}+{\hat{b}}_{j}}{{\hat{b}}_{j}}\right)\right)\Delta\left(\frac{\ell_{j}+{\hat{b}}_{j}}{{\hat{b}}_{j}}\right)$
(14) $\displaystyle\quad-
c_{3}\sum_{j=1}^{n_{m}}\left(\frac{\ell_{j}+{\hat{b}}_{j}}{{\hat{b}}_{j}}\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}$ $\displaystyle-
c_{3}\sum_{j=1}^{n_{m}}\left(\frac{\ell_{j}+{\hat{b}}_{j}}{{\hat{b}}_{j}}\right),$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}$ $\displaystyle-
c_{3}\sum_{k=1}^{|J|}\sum_{j=1,j\in
J_{k}}^{b_{j}}\left(\frac{\ell_{j}+{\hat{b}}_{j}}{{\hat{b}}_{j}}\right),$
$\displaystyle=$ $\displaystyle-c_{3}{\hat{n}}(t),$

where $(a)$ follows since the speed of map task $j$ is
$s_{j}=P^{-1}\left(\frac{\ell_{j}+{\hat{b}}_{j}(t)+1}{{\hat{b}}_{j}(t)}\right)$
making the first term $<0$, and in $(b)$ we have separated the contributions
from the $|J|$ outstanding jobs, and $J_{k}$ represents the $k^{th}$ job which
has $b_{j}+\ell_{j}$ tasks for $j\in J_{k}$, and the final inequality follows
since the total number of map tasks is $\sum_{j\in n_{m}}b_{j}\leq K-1$.
Combining (11) and (14), we get the result. ∎

Next, we want to show that (3) holds for an appropriate choice of $c$, using
the bounds that we have derived for $d\Phi_{1}/dt,d\Phi_{2}/dt$ and
$d\Phi_{3}/dt$. We begin with the case that $n_{f}\geq K$. In this case, we
only count the positive terms (because of $\mathsf{OPT}$) of $d\Phi_{3}/dt$ of
Lemma 9 and ignore the negative contribution because of the execution of the
algorithm. Combining Lemma 6, Lemma 7, and Lemma 9, we get
$n+\sum_{k=1}^{K}P(s_{k})+d\Phi_{1}/dt+d\Phi_{2}/dt+d\Phi_{3}/dt$

$\displaystyle\leq
n+n+\frac{c_{1}}{\beta}n^{o}-\frac{c_{1}}{\beta}n+\frac{c_{1}}{\beta}\left(\frac{K-1}{2}\right)+c_{1}\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k})$
(15) $\displaystyle\quad-
c_{2}KP^{-1}(1)+c_{2}\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k})+c_{3}(\alpha-1)n^{o},$
(16) $\displaystyle\quad+c_{3}\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k}),$ (17)

When $n_{f}<K$ and $n_{m}>0$, combining Lemma 6, Lemma 7, and Lemma 9,
$n+\sum_{k=1}^{K}P(s_{k})+d\Phi_{1}/dt+d\Phi_{2}/dt+d\Phi_{3}/dt$

$\displaystyle\leq
n+{\hat{n}}+n_{fr}P(P^{-1}(1))+\frac{c_{1}}{\beta}n^{o}-\frac{c_{1}}{\beta}\frac{n(n+1)}{2K}$
$\displaystyle\quad+c_{1}\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k})-c_{2}n_{f}P^{-1}(1)$
$\displaystyle\quad+c_{2}\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k})-c_{3}{\hat{n}}+c_{3}(\alpha-1)n^{o}+c_{3}\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k}).$
(18)

Thus, for both cases (16) and (18), we get
$n+\sum_{k=1}^{K}P(s_{k})+d\Phi_{1}/dt+d\Phi_{2}/dt+d\Phi_{3}/dt\leq
c\left(n^{o}+\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k})\right)$, for
$c=c_{1}+c_{2}+(\alpha-1)c_{3}$ for $c_{3}\geq 2$. The final case is when the
algorithm has $n_{f}<K$ and $n_{m}=0$, i.e., there are less than $K$ free
tasks and all of them are of reduce type, i.e., $n=n_{fr}$, for which the
proof is provided in Appendix XI. Thus, $c$ for which (3) holds for all the
three cases is $c=2\beta+2+2(\alpha-1)$.

Moreover, recall that that $C_{\text{task}}^{\mathsf{OPT}}\geq
P(s^{\star})(\sum_{j\in\mathcal{J}}({\mathsf{m}}_{jk}+{\mathsf{r}}_{j\ell}))$
from Proposition 1. Thus, from Lemma 5 and Remark 2, we have
$\mathsf{D}=o(1)$, thus, completing the proof of Theorem 8.

Discussion: In this section, we presented a simple speed scaling algorithm
that processes as many shortest free tasks as possible at speed such that the
total power used is equal to the total number of outstanding tasks. Without
precedence constraints, this speed choice can be shown to be locally optimal,
i.e., optimal if no further jobs arrive in future. With precedence
constraints, however, making a similar claim is difficult. The derived
competitive ratio guarantee depends on the size of the map and reduce tasks,
since essentially, we are restricting ourselves to processing shortest free
tasks, in which case a shorter reduce task is not being processed while a
large (free) map/reduce is being processed.

##  V Task Based Flow Time $P(s)=s^{\alpha}$, $\alpha<2$

In the previous section, we derived competitive ratio guarantees as a function
of $\beta$ and $\alpha$. In this section, we show that we can get a
competitive ratio independent of the instance of the problem ($\beta$) that
only depends on the value of $\alpha$ as long as $\alpha<2$.

$\mathsf{OPT}$: Similar to previous section, we assume that the $\mathsf{OPT}$
has no precedence constraints across tasks, and can process any of its
outstanding tasks at any time. This can only decrease the $\mathsf{OPT}$’s
cost. With a single server and without precedence constraints, $\mathsf{OPT}$
always processes the shortest task which could be a map/reduce task. Unlike
the previous section, however, we do not restrict the $\mathsf{OPT}$ to follow
the SRPT algorithm without precedence constraints and avoid the $P(2-1/K)$
penalty as in Theorem 8.

Without loss of generality, we will assume hereafter that the number of reduce
tasks (load of any map task) in each job are identical, i.e.,
$\ell_{j}={\mathsf{r}}$ for all map tasks $j$. This can be done, since if they
are unequal ($\ell_{j}={\mathsf{r}}_{j}$ in job $j$), and the maximum number
of reduce tasks with any job is ${\mathsf{r}}_{\max}$, then we can add
${\mathsf{r}}_{\max}-{\mathsf{r}}_{j}$ tasks of zero size, with equal change
to the cost of the algorithm or the $\mathsf{OPT}$.

###  V-A Single Server Case

First we consider the single server case, since this itself poses new
challenges with the precedence constraints. The cumulative (remaining) map
size of a job is defined as the sum of the sizes of all the (remaining) map
tasks in a job.

Algorithm: We propose the following algorithm, that defines which tasks should
be executed and at what speed. At time $t$, let the number of outstanding map
tasks (summed across different jobs) be $m(t)$, the number of free reduce
tasks be $r_{f}(t)$, and the number of jobs with at least one unfinished map
task be $J(t)$. The algorithm will process (upto) three tasks simultaneously.

  * •

$M_{1}$: The shortest remaining map task among all the outstanding map tasks
with the algorithm at speed $s_{m}(t)=P^{-1}(m(t)+1)$.

  * •

$M_{2}$: The shortest remaining map task of the job that has the smallest
remaining cumulative map size among all the outstanding jobs at speed
$s_{J}(t)=P^{-1}({\mathsf{r}}J(t)+1)$.

  * •

$R_{f}$: The shortest remaining free reduce task among all the outstanding
free reduce tasks at speed $s_{f}(t)=P^{-1}(r_{f}(t)+1)$.

Thus, the total speed is $s(t)=s_{m}(t)+s_{J}(t)+s_{f}(t)$. Note that $M_{1}$
could be equal to $M_{2}$ in which case only two tasks are processed
simultaneously.

For the algorithm, let $m(q)$, $J(q)$, and $r(q)$ denote the number of
unfinished map tasks, jobs with at least one unfinished map tasks, and the
number of unfinished reduce tasks (free or caged) with remaining cumulative
size of at least $q$, respectively. The quantities for the $\mathsf{OPT}$ are
denoted with a superscript $o$. Let
$d_{m}(q)=\max\left\\{0,m(q)-m^{o}(q)\right\\}$,
$d_{J}(q)=\max\left\\{0,{\mathsf{r}}(J(q)-J^{o}(q))\right\\}$, and
$d_{r}(q)=\max\left\\{0,r(q)-r^{o}(q)\right\\}$. We consider the potential
function

$\displaystyle\Phi(t)=\Phi_{1}(t)+\Phi_{2}(t)+\Phi_{3}(t),$ $\displaystyle\
\Phi_{1}(t)=c_{1}\int_{0}^{\infty}f\left(d_{m}(q)\right)dq,$ $\displaystyle\
\Phi_{2}(t)=c_{2}\int_{0}^{\infty}f\left(d_{J}(q)\right)dq,$ (19)

and $\Phi_{3}(t)=c_{3}\int_{0}^{\infty}f\left(d_{r}(q)\right)dq,$ where
$c_{1},c_{2},c_{3}$ are positive constants to be determined later.

The motivation to consider processing three tasks simultaneously is closely
tied with the choice of potential function $\Phi(t)$, where we need the total
drift (derivative of the potential function $\Phi$) to decrease at a rate
$-cn(t)$, where $n(t)$ is the total number of outstanding tasks with the
algorithm. Because of the precedence constraints, the algorithm is not
necessarily allowed to process the shortest task (which can be a caged reduce
task), in contrast to the no-precedence constraint case as in [4]. Thus, to
get sufficient drift, we combine the drifts from processing three jobs,
$M_{1}$ gives $-m(t)$, $M_{2}$ gives $-{\mathsf{r}}J(t)$ and $R$ gives
$-r_{f}(t)$. Since $m(t)+{\mathsf{r}}J(t)+r_{f}(t)\geq n(t)$, we get
sufficient drift.

Following this approach, the main result of this section is as follows.

######  Theorem 9.

For the single server case, for $\alpha<2$, the proposed algorithm has a
competitive ratio of $8+\frac{4}{2-\alpha}+3^{\alpha}$.

The main ingredients in proving Theorem 9 are the following three Lemmas
(proofs in Appendix), where ${\tilde{s}}(t)$ is the speed of server with the
$\mathsf{OPT}$ at time $t$.

######  Lemma 10.

$d\Phi_{1}/dt\leq c_{1}P({\tilde{s}}(t))-c_{1}(m(t)-m^{o}(t))$.

######  Lemma 11.

$d\Phi_{2}/dt\leq
c_{2}P({\tilde{s}}(t))-c_{2}(\alpha-2){\mathsf{r}}J(t)+c_{2}(2-\alpha){\mathsf{r}}J^{o}(t)$.

######  Lemma 12.

$d\Phi_{3}/dt\leq
c_{3}P({\tilde{s}}(t))-c_{3}(r_{f}(t)-(\alpha-1)r(t)-(2-\alpha)r^{o}(t))$.

Next, we prove that (3) holds for some $c$ to prove Theorem 9 using Lemma 10,
11, 12.

######  Proof of Theorem 9.

We only describe the computation when $m(t)\geq m^{o}(t),J(t)\geq J^{o}(t)$
and $r(t)\geq r^{o}(t)$, since otherwise result follows easily. Recall that
the total number of outstanding jobs with the algorithm is
$m(t)+{\mathsf{r}}J(t)+r_{f}(t)$, and the total power used by the algorithm is
$P(s(t))=$

$\displaystyle
P(P^{-1}(m(t)+1)+P^{-1}({\mathsf{r}}J(t)+1)+P^{-1}(r_{f}(t)+1))$
$\displaystyle\quad\leq 3^{\alpha-1}(m(t)+{\mathsf{r}}J(t)+r_{f}(t)+3),$

using Lemma 14 since $P^{-1}(x)=x^{1/\alpha}$ with $n=3$ and $\alpha\geq 1$.
Thus, the running cost $n(t)+P(s(t))$ for the algorithm is at most
$(3^{\alpha-1}+1)(m(t)+{\mathsf{r}}J(t)+r_{f}(t))+3^{\alpha}$. Combining Lemma
10, 11, 12, we can write (3), $n(t)+P(s(t))+d\Phi/dt$

$\displaystyle\leq(3^{\alpha-1}+1)(m(t)+{\mathsf{r}}J(t)+r_{f}(t))+3^{\alpha}$
$\displaystyle\quad+(c_{1}+c_{2}+c_{3})P({\tilde{s}}(t))-c_{1}(m(t)-m^{o}(t))$
$\displaystyle\quad-
c_{2}(\alpha-2){\mathsf{r}}J(t)+c_{2}(2-\alpha){\mathsf{r}}J^{o}(t)$
$\displaystyle\quad-c_{3}(r_{f}(t)-(\alpha-1)r(t)-(2-\alpha)r^{o}(t)),$
$\displaystyle\leq
c(m^{o}(t)+{\mathsf{r}}J^{o}(t)+r^{o}(t)+P({\tilde{s}}(t)))\leq
c(n_{o}(t)+P({\tilde{s}}(t))),$

$c=c_{1}+c_{2}+c_{3}+3^{\alpha}$, where
$c_{1}=4,c_{2}=\frac{4}{2-\alpha},c_{3}=4$, since $\alpha<2$. Thus, the
competitive ratio of the proposed online algorithm is
$8+\frac{4}{2-\alpha}+3^{\alpha}$. ∎

###  V-B Multiple Server Case

In this section, we consider the multi-server version of the problem, where
there are $K$ homogenous servers each with identical power function $P$.
Except this change, everything else remains the same about the model as
described in Section V-A. In the presence of precedence constraints, speed
scaling with multiple servers pose the following new challenge. Let the number
of map plus free reduce jobs be less than $K$, while the number of caged
reduce jobs be large. In this case, even though there are a large number of
outstanding jobs, some of the servers have to idle, making the construction of
the potential function a difficult task.

Algorithm: With multiple servers, we propose the following algorithm, that
defines which tasks should be executed and at what speed. At time $t$, let the
number of outstanding map tasks (summed across different jobs) be $m(t)$, the
number of free reduce tasks be $r_{f}(t)$, and the number of jobs with at
least one unfinished map task be $J(t)$.

  * •

$M_{1}$’s: The $\min\\{m(t),K\\}$ shortest remaining map tasks among all the
outstanding map tasks available with the algorithm at speed
$s_{m}(t)=P^{-1}\left(\min\left\\{\frac{m(t)+1}{K},1\right\\}\right)$ are
processed on any $\min\\{m(t),K\\}$ servers.

  * •

$M_{2}$’s: The $\min\\{J(t),K\\}$ jobs that has the smallest remaining
cumulative size of all the outstanding map tasks at speed
$s_{cm}(t)=P^{-1}\left(\min\left\\{\frac{{\mathsf{r}}J(t)+1}{K},{\mathsf{r}}\right\\}\right)$
are processed on any $\min\\{m(t),K\\}$ servers, where the shortest map tasks
of each job is processed.

  * •

$R_{f}$’s: The $\min\\{m(t),K\\}$ shortest remaining free reduce tasks among
all the free reduce tasks at speed
$s_{f}(t)=P^{-1}\left(min\left\\{\frac{r_{f}(t)+1}{K},1\right\\}\right)$ are
processed on any $\min\\{m(t),K\\}$ servers.

Thus, the algorithm will process (upto) three tasks on each of the $K$ servers
simultaneously, where the speed of any server is
$s(t)=s_{m}(t)+s_{cm}(t)+s_{f}(t)$. For any server, $M_{1}$ could be equal to
$M_{2}$ for some jobs in which case only two tasks are processed on each
server simultaneously.

######  Theorem 10.

For the multi-server case, for $\alpha<2$, the proposed algorithm has a
competitive ratio of $8+\frac{4}{2-\alpha}+3^{\alpha}$.

Proof is provided in the Appendix XIV, where the novelty over the single
server case is the drift $d\Phi_{4}(t)/dt$ that is needed only when $K>1$.
This distinction is required since when number of jobs is less than $K$, but
there are a large number of caged reduce jobs, all jobs of $J(t)$ are being
processed by the algorithm, thus giving the negative drift of $-\sum_{j\in
J(t)}\Delta({\mathsf{r}})s_{j}(t)$ where $s_{j}(t)$ is the speed at which each
of the jobs’s shortest map task is being executed.

##  VI Simulations

In this section, we present simulation results for both the job-based flow
time + energy and task-based flow time + energy problem. Since the
$\mathsf{OPT}$ is unknown, for benchmarking the performance, we remove the
MapReduce constraints, and use the same speed scaling choice as that of the
algorithms presented in the paper. For the task-based flow time + energy
problem, without the MapReduce constraints the algorithm is the same the
multi-server SRPT algorithm with speed choice prescribed in [31], that is
constant competitive with respect to the $\mathsf{OPT}$. Thus, our benchmark
is meaningful. For the job-based flow time + energy problem, without the
MapReduce constraints, there is no guarantee known on the Job-SRPT algorithm
as far as we know, or for that matter any algorithm.

For all the plots, we use $\alpha=2.5$, and number of servers $K=5$. In the
simulation setup, we consider a slotted time where in each slot, the number of
jobs arriving is Poisson distributed with mean $\lambda$. For each job, the
number of map and reduce tasks are Poisson distributed with mean $2$ and $2$
(reasonable with $K=5$), and the size of a map job and a reduce job is
exponentially distributed with mean $3$ and $5$, respectively. For each
iteration, we generate jobs for $1000$ slots, and count its flow time +
energy, and iterate over 1000 iterations. The performance of the two
algorithms is compared for the same realizations of the random variables, and
then averaged over iterations.

In Fig. 1, we plot the comparison of the job-based flow time + energy with and
without MapReduce constraints as a function of $\lambda$, where even though in
theory we consider that all jobs are available at time $0$, in simulation we
let jobs arrive over time. Clearly, the ratio of the average costs is at most
$5$. Moreover, from simulations we observed that even the maximum ratio of the
two costs remain below $5$. Similarly, in Fig. 2, we plot the comparison of
the task-based flow time + energy with and without MapReduce constraints as a
function of $\lambda$, and observe similar behaviour.

Recall that the competitive ratio bound for the proposed algorithm for the
task-based flow time + energy problem is a function of the ratio of the
largest map/reduce task and the smallest reduce task $\beta$. To illustrate
that, in Fig. 3, we plot the task-based flow time + energy with and without
MapReduce constraints with increasing sizes of map tasks while holding the
size of the reduce tasks constant. In particular, we let the size of the
reduce tasks to be exponentially distributed with mean $1$, and the size of
the map tasks to be exponentially distributed with variable mean $\mu_{m}$.
For Fig. 3, the number of jobs arriving is Poisson distributed with mean $.5$,
and for each job, the number of map and reduce slots are Poisson distributed
with mean $2$ and $5$, respectively. We see that unlike the theoretical
results, the competitive ratio between the algorithm with and without
enforcing the MapReduce constraints, does not increase with the ratio of the
largest map/reduce task and the smallest reduce task.

$\lambda=.5$$\lambda=1$$\lambda=1.5$$\lambda=2$$\lambda=2.5$$0$$1$$2$$3$Job
Flow Time + Energy ($\times 10^{5}$)With Precedence Const.Without Precedence
Const. Figure 1: Comparison of job-based flow time + energy with and without
precedence constraints.
$\lambda=.5$$\lambda=1$$\lambda=1.5$$\lambda=2$$\lambda=2.5$$0$$0.5$$1$$1.5$$2$$2.5$$3$Job
Flow Time + Energy ($\times 10^{6}$)With Precedence Const.Without Precedence
Const. Figure 2: Comparison of task-based flow time + energy with and without
precedence constraints.
$\mu_{m}=2$$\mu_{m}=4$$\mu_{m}=6$$\mu_{m}=8$$0$$0.2$$0.4$$0.6$$0.8$$1$$1.2$$1.4$$1.6$Job
Flow Time + Energy ($\times 10^{5}$)With Precedence Const.Without Precedence
Const. Figure 3: Comparison of task-based flow time + energy with and without
precedence constraints as a function of size of map task being exponentially
distributed with mean $\mu_{m}$, while the size of map task is exponentially
distributed with mean $\mu_{r}=1$.

##  VII Conclusions

In this paper, we have made progress in deriving online algorithms for
scheduling and speed scaling jobs with MapReduce precedence constraints.
Without the precedence constraints there is a large body of literature on
efficiently solving the flow time plus energy problem, however, very little is
known with precedence constraints, that is inherently a hard problem. The
algorithms we proposed followed a simple SRPT policy, (process as many
shortest jobs/tasks as possible) and the total power used by all the servers
is equal to the total number of outstanding tasks, which has a intuitive
appeal in the sense that it balances the energy and the delay cost
effectively. The derived competitive ratio guarantee depends on the power
function $P$, and/or the ratio of the size of the largest map/reduce task and
the smallest reduce task, that is typically small for MapReduce applications.

## References

  * [1] Lachlan L. H. Andrew, Minghong Lin, and Adam Wierman.  Optimality, fairness, and robustness in speed scaling designs.  In Proc. ACM SIGMETRICS, 2010.
  * [2] Lachlan LH Andrew, Minghong Lin, and Adam Wierman.  Optimality, fairness, and robustness in speed scaling designs.  38(1):37–48, 2010.
  * [3] Evripidis Bampis, Vincent Chau, Dimitrios Letsios, Giorgio Lucarelli, Ioannis Milis, and Georgios Zois.  Energy efficient scheduling of mapreduce jobs.  In European Conference on Parallel Processing, pages 198–209. Springer, 2014.
  * [4] Nikhil Bansal, Ho-Leung Chan, and Kirk Pruhs.  Speed scaling with an arbitrary power function.  In ACM-SIAM symposium on discrete algorithms, 2009.
  * [5] Jacek Blazewicz, Jan Karel Lenstra, and AHG Rinnooy Kan.  Scheduling subject to resource constraints: classification and complexity.  Discrete applied mathematics, 5(1):11–24, 1983.
  * [6] Hyunseok Chang, Murali Kodialam, Ramana Rao Kompella, TV Lakshman, Myungjin Lee, and Sarit Mukherjee.  Scheduling in mapreduce-like systems for fast completion time.  In 2011 Proceedings IEEE INFOCOM, pages 3074–3082. IEEE, 2011.
  * [7] Cong Chen, Yinfeng Xu, Yuqing Zhu, and Chengyu Sun.  Online mapreduce scheduling problem of minimizing the makespan.  Journal of Combinatorial Optimization, 33(2):590–608, 2017.
  * [8] Fabián A Chudak and David B Shmoys.  Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds.  Journal of Algorithms, 30(2):323–343, 1999.
  * [9] Jeffrey Dean and Sanjay Ghemawat.  Mapreduce: simplified data processing on large clusters.  Communications of the ACM, 51(1):107–113, 2008.
  * [10] Nikhil R Devanur and Zhiyi Huang.  Primal dual gives almost optimal energy-efficient online algorithms.  ACM Transactions on Algorithms, 14(1):5, 2018.
  * [11] Naveen Garg, Anupam Gupta, Amit Kumar, and Sahil Singla.  Non-Clairvoyant Precedence Constrained Scheduling.  In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 63:1–63:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  URL: urlhttp://drops.dagstuhl.de/opus/volltexte/2019/10639, href http://dx.doi.org/10.4230/LIPIcs.ICALP.2019.63 pathdoi:10.4230/LIPIcs.ICALP.2019.63.
  * [12] RL Graham.  Bounds for certain multiprocessor anomalies, Bell Systems Tech.  J, 45:1563–1581, 1966.
  * [13] Gero Greiner, Tim Nonner, and Alexander Souza.  The bell is ringing in speed-scaled multiprocessor scheduling.  In Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, 2009.
  * [14] Isaac Grosof, Ziv Scully, and Mor Harchol-Balter.  Srpt for multiserver systems.  Performance Evaluation, 127:154–175, 2018.
  * [15] Anupam Gupta, Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, and Kirk Pruhs.  Scheduling heterogeneous processors isn’t as easy as you think.  In ACM-SIAM symposium on Discrete algorithms, 2012.
  * [16] Anupam Gupta, Ravishankar Krishnaswamy, and Kirk Pruhs.  Scalably scheduling power-heterogeneous processors.  In International Colloquium on Automata, Languages, and Programming, pages 312–323. Springer, 2010.
  * [17] Mohammad Hammoud and Majd F Sakr.  Locality-aware reduce task scheduling for mapreduce.  In 2011 IEEE Third International Conference on Cloud Computing Technology and Science, pages 570–576, 2011.
  * [18] Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly.  Dryad: distributed data-parallel programs from sequential building blocks.  In ACM SIGOPS operating systems review, volume 41, pages 59–72. ACM, 2007.
  * [19] Tak-Wah Lam, Lap-Kei Lee, Isaac KK To, and Prudence WH Wong.  Competitive non-migratory scheduling for flow time and energy.  In Proceedings of the annual symposium on Parallelism in algorithms and architectures, 2008.
  * [20] Tak-Wah Lam, Lap-Kei Lee, Isaac KK To, and Prudence WH Wong.  Improved multi-processor scheduling for flow time and energy.  Journal of Scheduling, 15(1):105–116, 2012.
  * [21] Stefano Leonardi and Danny Raz.  Approximating total flow time on parallel machines.  Journal of Computer and System Sciences, 73(6):875–891, 2007.
  * [22] Taibo Luo, Yuqing Zhu, Weili Wu, Yinfeng Xu, and Ding-Zhu Du.  Online makespan minimization in mapreduce-like systems with complex reduce tasks.  Optimization Letters, 11(2):271–277, 2017.
  * [23] Lena Mashayekhy, Mahyar Movahed Nejad, Daniel Grosu, Quan Zhang, and Weisong Shi.  Energy-aware scheduling of mapreduce jobs for big data applications.  IEEE transactions on Parallel and distributed systems, 26(10):2720–2733, 2014.
  * [24] Nicole Megow and José Verschae.  Dual techniques for scheduling on a machine with varying speed.  In International Colloquium on Automata, Languages, and Programming, pages 745–756. Springer, 2013.
  * [25] Benjamin Moseley, Anirban Dasgupta, Ravi Kumar, and Tamás Sarlós.  On scheduling in map-reduce and flow-shops.  In Proceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures, pages 289–298. ACM, 2011.
  * [26] Cynthia A Phillips, Cliff Stein, Eric Torng, and Joel Wein.  Optimal time-critical scheduling via resource augmentation.  In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 140–149. ACM, 1997.
  * [27] Kirk Pruhs, Rob van Stee, and Patchrawat Uthaisombut.  Speed scaling of tasks with precedence constraints.  Theory of Computing Systems, 43(1):67–80, 2008.
  * [28] Linus Shrage.  A proof of the optimality of the shortest remaining processing time discipline.  Operations Research, 16:687–690, 1968.
  * [29] Konstantin Shvachko, Hairong Kuang, Sanjay Radia, Robert Chansler, et al.  The hadoop distributed file system.  In MSST, volume 10, pages 1–10, 2010.
  * [30] Jian Tan, Xiaoqiao Meng, and Li Zhang.  Performance analysis of coupling scheduler for mapreduce/hadoop.  In 2012 Proceedings IEEE INFOCOM, pages 2586–2590. IEEE, 2012.
  * [31] Rahul Vaze and Jayakrishnan Nair.  Multiple server SRPT with speed scaling is competitive.  IEEE/ACM Transactions on Networking, to appear 2020.
  * [32] Weina Wang, Kai Zhu, Lei Ying, Jian Tan, and Li Zhang.  Maptask scheduling in mapreduce with data locality: Throughput and heavy-traffic optimality.  IEEE/ACM Transactions on Networking (TON), 24(1):190–203, 2016\.
  * [33] Nezih Yigitbasi, Kushal Datta, Nilesh Jain, and Theodore Willke.  Energy efficient scheduling of mapreduce workloads on heterogeneous clusters.  In Green Computing Middleware on Proceedings of the 2nd International Workshop, page 1. ACM, 2011.
  * [34] Yi Yuan, Dan Wang, and Jiangchuan Liu.  Joint scheduling of mapreduce jobs with servers: Performance bounds and experiments.  In IEEE INFOCOM 2014-IEEE Conference on Computer Communications, pages 2175–2183. IEEE, 2014.
  * [35] Yousi Zheng, Ness B Shroff, and Prasun Sinha.  A new analytical technique for designing provably efficient mapreduce schedulers.  In 2013 Proceedings IEEE INFOCOM, pages 1600–1608. IEEE, 2013.
  * [36] Yuqing Zhu, Yiwei Jiang, Weili Wu, Ling Ding, Ankur Teredesai, Deying Li, and Wonjun Lee.  Minimizing makespan and total completion time in mapreduce-like systems.  In IEEE INFOCOM 2014-IEEE Conference on Computer Communications, pages 2166–2174. IEEE, 2014.

##  VIII Proof of Lemma 1

An algorithm is called job-work conserving algorithm, if it processes as many
distinct jobs as possible, and multiple tasks of any one job are processed on
multiple machines only if the number of jobs is less than $K$. Thus, if $n(t)$
is the number of outstanding job, where each job has multiple map and reduce
tasks, then the algorithm definitely processes some task of $\min\\{n(t),K\\}$
distinct jobs on the $\min\\{n(t),K\\}$ servers.

Let $A(j,t)$ denote the amount of work (total volume of jobs processed)
completed by a job-work conserving algorithm $A$ for job $j$ by time $t$. For
set of jobs $J$, $A(J,t)=\sum_{j\in J}A(j,t)$.

######  Lemma 13.

For a job arrival sequence $\sigma$, at any time $t$, let
$1\leq\rho\leq(2-1/K)$, and $\gamma=\frac{2-1/K}{\rho}$. For any job-work
conserving algorithm $A$ with $K$ servers having speed $\gamma$,
$A(\sigma,\rho t)\geq A^{\prime}(\sigma,t)$ for any algorithm $A^{\prime}$
(including $\mathsf{OPT}$) using $K$ speed $1$ servers.

Thus, the amount of work completed by any job-work conserving algorithm by
time $(2-1/K)t$ is at least as much as work done by $\mathsf{OPT}$ by time
$t$. The proof is identical to [26], that proves an identical result when each
job has a single task. The key idea that makes this work is that the algorithm
is job-work conserving, to ensure that the algorithm processes as many
distinct jobs as possible at any given time. Clearly, it does not hold if an
algorithm processes more than one task of a job on multiple servers
simultaneously and provides no processing for any task of an outstanding job.

With all jobs being available at time $0$, the input sequence $\sigma$ is
essentially the set of jobs (that consists of map and reduce tasks). For the
job-SRPT algorithm the following property is easy to prove.

######  Proposition 2.

If the number of jobs finished completely by job-SRPT algorithm is $k$ by time
$t$ with input sequence $\sigma^{\prime}$. Then the number of jobs finished
completely by job-SRPT algorithm is at least $k$ by time $t$ with input
sequence $\sigma^{\prime}$, where
$\sigma^{\prime}\subseteq\sigma^{\prime\prime}$.

###### Proof of Lemma 1.

First note that the job-SRPT algorithm is a job-work conserving algorithm. Let
$\sigma_{t}\subseteq\sigma$ be the set of jobs that the $\mathsf{OPT}$
completely finishes by time $t$ when the input sequence is $\sigma$. Therefore
from Lemma 13, job-SRPT algorithm finishes all $|\sigma_{t}|$ jobs by time
$t(2-1/K)/\gamma$ given speed $\gamma$ for each server if the input sequence
is $\sigma_{t}$. Now using Lemma 2, we let $\sigma_{t}=\sigma^{\prime}$ and
$\sigma=\sigma^{\prime\prime}$ to conclude that for any time $t$, at least
$|\sigma_{t}|$ jobs will be completed by time $(2-1/K)t/\gamma$ with the job-
SRPT algorithm with input sequence $\sigma$. This implies that for any $k$,
the completion time of the $k^{th}$ job with job-SRPT algorithm is no later
than the $(2-1/K)/\gamma$ times the completion time of the $k^{th}$ job with
the $\mathsf{OPT}$ for any job arrival sequence $\sigma$. Recall that the flow
time of job $j$ is $F_{j}=T_{j}-a_{j}$, where $T_{j}$ is the departure time of
the last reduce task of job $j$ and $a_{j}$ is the arrival time of the job
$j$. Note that the order of departure of jobs with the job-SRPT algorithm and
$\mathsf{OPT}$ might be different, but since flow time is
$\sum_{j\in\sigma}(T_{j}-a_{j})$ it is sufficient to show that
$\sum_{j\in\sigma}F_{j}(\mathsf{OPT})=\sum_{j\in\sigma}F_{j}(\text{job-SRPT})$
to claim that $F_{\text{job}}(\mathsf{OPT})=F_{\text{job}}(\text{job-SRPT})$.
Choosing $\gamma=2-1/K$, we get that
$\sum_{j\in\sigma}F_{j}(\mathsf{OPT})=\sum_{j\in\sigma}F_{j}(\text{job-SRPT})$
and the claim follows. ∎

##  IX Proof of Lemma 2

###### Proof.

Let the total size of a job $j$ be $w_{j}$ which is the sum of the sizes of
all its map and reduce tasks. Recall that map/reduce tasks of at most the last
$K-1$ jobs among the total $\mathsf{J}$ are deleted with the $\mathsf{OPT}$
that is executing job-SRPT algorithm. Thus, on any map/reduce tasks deletion
of job $j$, the increase in $d(t,q)\leq 1$ for $q\leq w_{j}$. Thus, the
increase in $\Phi_{1}(t)$ is at most
$c_{1}\int_{0}^{w_{j}}f(d(t,q)+1)dq-\int_{0}^{w_{j}}f(d(t,q))dq\leq
c_{1}\int_{0}^{w_{j}}\Delta(d(t,q))dq\leq
c_{1}\Delta(\frac{\mathsf{J}}{K})\int_{0}^{w_{j}}dq\leq
c_{1}w_{j}\Delta(\frac{\mathsf{J}}{K})$. Since this happens for at most $K-1$
jobs, the total increase in $\Phi_{1}(t)$ at points of discontinuities is
$\sum_{j=1}^{K-1}c_{1}w_{j}\Delta(\frac{\mathsf{J}}{K})$. The increase in
$\Phi_{2}(t)$ because of deletion of map and reduce task of the $j^{th}$ among
the last $K-1$ jobs is simply $c_{2}\int_{0}^{w_{j}}1dq\leq c_{2}w_{j}$. Since
this happens for at most $K-1$ jobs, the total increase in $\Phi_{2}(t)$ at
points of discontinuities is $\sum_{j=1}^{K-1}c_{2}w_{j}$. ∎

##  X Proof of Lemma 5

###### Proof.

On an arrival of a new job, the new addition to the two terms of (9)
corresponding to the new map tasks is identical, thus keeping $\Phi_{3}(t)$
unchanged.

Whenever a map task $j$ is completed by the algorithm or $\mathsf{OPT}$,
$n(t,q)$ or $n_{j}^{o}(t,q)$ is changed for only a single point of $q=0$,
keeping the integral unchanged, and the term corresponding to map task $j$
vanishes continuously in (9), and there is no discontinuity. Map task $j$’s
departure with the algorithm ($\mathsf{OPT}$), however, reduces
${\hat{b}}_{k}(t)$ (${\hat{b}}^{o}_{k}(t)$) by $1$ for map task $k$ that
belong to the same job as map task $j$ if $b_{k}(t)\leq K$ ($b^{o}_{k}(t)\leq
K$). If a map task departs with the $\mathsf{OPT}$, the change in $\Phi_{3}$
is negative, and we disregard this change, and only consider the increase
because of a map task departure with the algorithm. For a job $i$, departure
of its at most $K$ map tasks with the algorithm result in discontinuities
(since $b_{k}(t)\leq K$ for any discontinuity to arise), where for the
$k^{th}$ discontinuity, there are at most $k$ map tasks of job $i$ remaining
in the system. Thus, the increase in $\Phi_{3}(t)$ for any such discontinuity
is bounded as follows. Thus, only when $b_{k}(t)\leq K$,

$\Phi_{3}(t^{+})-\Phi_{3}(t)=\sum_{k=1}^{b_{k}(t)}c_{3}\delta_{k},$

where

$\displaystyle\delta_{k}$ $\displaystyle=\int
g_{z_{k}({\hat{b}},t)}\left(z_{k}({\hat{b}},t)h_{k}(t,q)\right)dq,$
$\displaystyle\quad-c_{3}\int
g_{z_{k}({\hat{b}}+1,t)}\left(z_{k}({\hat{b}}+1,t)h_{k}(t,q)\right)dq,$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\Delta\left(\frac{\ell_{j}+b_{k}(t)}{b_{k}(t)}\right)\int_{0}^{w_{\max}^{t}}1dq,$
$\displaystyle=\Delta\left(\frac{\ell_{j}+b_{k}(t)}{b_{k}(t)}\right)w_{\max}^{t},$

where $(a)$ follows by dropping the second term, and using the definition of
$f$ and fact that $h_{k}(t,q)\leq 1$ for all $q\leq w_{\max}^{t}$, where
$w_{\max}^{t}$ is an upper bound on the size of any map task.

Thus, for any one map task departure for a fixed value of $b_{k}(t)$,

$\Phi_{3}(t^{+})-\Phi_{3}(t)=c_{3}w_{\max}^{t}b_{k}(t)\Delta\left(\frac{\ell_{j}+b_{k}(t)}{b_{k}(t)}\right),$

where $\Delta(x)=o(x)$ by Assumption 3. In particular, $\Delta(x)=\alpha
x^{1-1/\alpha}$ for $P(s)=s^{\alpha}$. Since at most $K$ such map task
departures corresponding to $b_{k}(t)=1,\dots,K$ give rise to discontinuties,
counting for all $K$ such events we have that for any one job, the maximum
increase in $\Phi_{3}(t)$ is
$c_{3}w_{\max}^{t}\sum_{b_{k}(t)=1}^{K}b_{k}(t)\Delta\left(\frac{\ell_{j}+b_{k}(t)}{b_{k}(t)}\right)=O(c_{3}w_{\max}^{t}K^{2}\Delta\left(\ell_{j}+1\right))$.
Thus, counting for all jobs, we get that total increase in $\Phi_{3}(t)$ is
$O(\mathsf{J}c_{3}w_{\max}^{t}K^{2}\Delta\left(\ell_{j}+1\right))$, where
$\mathsf{J}$ is the total number of jobs. Following Assumption 4, we get that
total increase in $\Phi_{3}(t)$ is
$o(\sum_{j\in\mathcal{J}}({\mathsf{m}}_{jk}+{\mathsf{r}}_{j\ell}))$, as
$w_{\max}^{t},K$ is fixed, and
$\sum_{j=1}^{\mathsf{J}}\ell_{j}={\mathsf{n}}_{r}$. ∎

##  XI Proof for remaining case of Theorem 8

When the algorithm has $n_{f}<K$ and $n_{m}=0$, i.e., there less than $K$ free
tasks and all of them are of reduce type, i.e., $n=n_{fr}$, we only count the
positive terms (because of $\mathsf{OPT}$) of $d\Phi_{3}/dt$ of Lemma 9 and
ignore the negative contribution because of the execution of the algorithm.
Combining Lemma 6, Lemma 7, and Lemma 9,

$\displaystyle
n+\sum_{k=1}^{K}P(s_{k})+d\Phi_{1}/dt+d\Phi_{2}/dt+d\Phi_{3}/dt$
$\displaystyle\quad\leq
n_{fr}+n_{fr}P(P^{-1}(1))+c_{1}n^{o}-c_{1}\frac{n(n+1)}{2K},$
$\displaystyle\quad+c_{1}\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k})-c_{2}n_{fr}P^{-1}(1)+c_{2}\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k})$
$\displaystyle\quad+c_{3}(\alpha-1)n^{o}+c_{3}\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k}),$
$\displaystyle\leq
c\left(n^{o}+\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k})\right),$

for $c=c_{1}+c_{2}+(\alpha-1)c_{3}$, where $c_{2}\geq 2$. Thus, $c$ for which
(3) holds for all the three cases is $c=2\beta+2+2(\alpha-1)$, completing the
proof of Theorem 8.

##  XII Proofs of Lemma 10, 11, and 12

###### Proof of Lemma 10.

Since there are only map tasks in $\Phi_{1}(t)$, this proof is identical to
that of Theorem 1.1 [4] for single server speed scaling with no precedence
constraints, since map tasks are always free. ∎

###### Proof of Lemma 11.

We consider the case when $J(t)\geq J^{o}(t)$ since otherwise we can show that
$d\Phi_{2}/dt\leq 0$ similar to [4]. With $J(t)\geq J^{o}(t)$, for the
algorithm, let $q_{c}$ be the sum of the sizes of all the map tasks for the
job with the smallest cumulative map size. The $\mathsf{OPT}$ might be
processing a map or a reduce task. If it is a reduce task, then it does not
affect $d\Phi_{2}/dt$. Otherwise, let $\mathsf{OPT}$ process a map task $k$ of
job $j$, where the sum of the sizes of the map tasks of job $j$ is
$q_{c}^{o}$. Note that job $j$ may not be the job with the smallest sum of the
map tasks, i.e., $J^{o}(q_{c}^{o})\neq J^{o}(t)$. Now we need to separate, the
three cases $q_{c}<q_{c}^{o},q_{c}>q_{c}^{o},q_{c}=q_{c}^{o}$.

Case I: $q_{c}<q_{c}^{o}$. The algorithm is processing the shortest
(cumulative map task size) job, thus making $J(q)=J(q)-1$ for
$q\in[q_{c}-s_{J}(t)dt,q_{c}]$. Thus, $d\Phi_{2}(t)/dt$ because of processing
by the algorithm is
$f({\mathsf{r}}J(q_{c})-{\mathsf{r}}J^{o}(q_{c})-1)-f({\mathsf{r}}J(q_{c})-{\mathsf{r}}J^{o}(q_{c}))s_{J}=-\Delta({\mathsf{r}}J(q_{c})-{\mathsf{r}}J^{o}(q_{c}))s_{J}$.
Now note that $J(q_{c})=J(t)$ since the algorithm is processing the shortest
(cumulative map task size) job, while $J^{o}(q_{c})\leq J^{o}(t)$ always.
Hence

$d\Phi_{1}(t)/dt\leq\Delta({\mathsf{r}}J(q_{c})-{\mathsf{r}}J^{o}(q_{c}))s_{J}=-\Delta({\mathsf{r}}J(t)-{\mathsf{r}}J^{o}(t))s_{J}.$

Processing by $\mathsf{OPT}$ makes $J^{o}(q)=J^{o}(q)-1$ for
$q\in[q_{c}^{o}-{\tilde{s}}(t)dt,q_{c}^{o}]$. Hence, the $\mathsf{OPT}$’s
contribution,

$\displaystyle d\Phi_{1}(t)/dt$ $\displaystyle\leq
f({\mathsf{r}}J(q_{c}^{o})-{\mathsf{r}}J^{o}(q_{c}^{o})+1)-f({\mathsf{r}}J(q_{c}^{o})-{\mathsf{r}}J^{o}(q_{c}^{o})){\tilde{s}},$
$\displaystyle=\Delta({\mathsf{r}}J(q_{c}^{o})-{\mathsf{r}}J^{o}(q_{c})+1){\tilde{s}}.$

Since $\mathsf{OPT}$ is not necessarily processing the map task for a job that
has the smallest cumulative map task size of all the outstanding map jobs,
$J^{o}(q_{c}^{o})\neq J^{o}(t)$ and the best bound we can get is
$J^{o}(q_{c}^{o})\geq 1$. Moreover, since, $J(q_{c}^{o})\leq J(t)$ always, we
get the $\mathsf{OPT}$’s contribution as
$d\Phi_{2}(t)/dt\leq\Delta({\mathsf{r}}J(t)-1)(-s_{J}+{\tilde{s}})$.

Hence, the argument inside $\Delta$ function for the algorithms’ and the
$\mathsf{OPT}$’s contribution are not identical and we have to apply Lemma 8
separately on the algorithms’ and the $\mathsf{OPT}$’s contribution for
$d\Phi_{2}/dt$ to get $d\Phi_{2}/dt\leq
c_{2}P({\tilde{s}}(t))-c_{2}(\alpha-2){\mathsf{r}}J(t)+c_{2}(2-\alpha){\mathsf{r}}J^{o}(t)$
by using the fact that the speed of the algorithm is
$s_{J}(t)=P^{-1}({\mathsf{r}}J(t)+1)$.

The case of $q_{c}>q_{c}^{o}$ and $q_{c}=q_{c}^{o}$ follows similarly.

∎

###### Proof of Lemma 12.

We consider the case when $r(t)\geq r^{o}(t)$ since otherwise we can show that
$d\Phi_{3}/dt\leq 0$ similar to [4]. With $r(t)\geq r^{o}(t)$, let $q_{r}$
($q_{r}^{o}$) be the size of the smallest free reduce task remaining with the
algorithm ($\mathsf{OPT}$). Note that with $\mathsf{OPT}$, all reduce jobs are
always free. Now we need to separate, the three cases
$q_{r}<q_{r}^{o},q_{r}>q_{r}^{o},q_{r}=q_{r}^{o}$.

Case I: $q_{r}<q_{r}^{o}$. The algorithm is processing the shortest free
reduce task, thus making $r(q)=r(q)-1$ for $q\in[q_{r}-s_{r}(t)dt,q_{r}]$
while the processing by $\mathsf{OPT}$ makes $r^{o}(q)=r^{o}(q)-1$ for
$q\in[q_{r}^{o}-{\tilde{s}}(t)dt,q_{r}^{o}]$ if the $\mathsf{OPT}$ is
processing a reduce task. If $\mathsf{OPT}$ is processing a map task, then it
does not affect $d\Phi_{3}(t)/dt$. Thus, $d\Phi_{3}(t)/dt$ because of
processing by the algorithm is
$\left(f(r(q_{r})-r^{o}(q_{r})-1)-f(r(q_{r})-r^{o}(q_{r}))\right)s_{r}=-\Delta(r(q_{r})-r^{o}(q_{r}))s_{r}$.
Now note that $r(q_{r})\geq r_{f}(t)$ since the algorithm is processing the
shortest free reduce task, while $r^{o}(q_{r})\leq r^{o}(t)$ always. Hence

$d\Phi_{3}(t)/dt\leq\Delta(r(q_{r})-r^{o}(q_{r}))s_{r}=-\Delta(r_{f}(t)-r^{o}(t))s_{r}.$

Similarly for the $\mathsf{OPT}$’s contribution,

$\displaystyle d\Phi_{3}(t)/dt$
$\displaystyle\leq\left(f(r(q_{r}^{o})-r^{o}(q_{r}^{o})+1)-f(r(q_{r}^{o})-r^{o}(q_{r}^{o}))\right){\tilde{s}},$
$\displaystyle=\Delta(r(q_{r}^{o})-r^{o}(q_{r})+1){\tilde{s}},$
$\displaystyle\leq\Delta(r_{f}(t)-r^{o}(t)){\tilde{s}},$

as $r(q_{r}^{o})\leq r(t)-1$ since $q_{r}<q_{r}^{o}$. Therefore, combining the
algorithm’s and $\mathsf{OPT}$’s contribution, we get
$d\Phi_{3}(t)/dt\leq\Delta(r_{f}(t)-r^{o}(t))(-s_{r}+{\tilde{s}})$. Using
Lemma 8, and the fact that $s_{r}=P^{-1}(r_{f}(t)+1)$, we get
$d\Phi_{3}(t)/dt\leq c_{3}P({\tilde{s}}(t))-c_{3}(r_{f}(t)-r^{o}(t))$ as
required.

Case II $q_{r}>q_{r}^{o}$: The proof for this case is more non-trivial, and
essentially reflects why the competitive ratio guarantee holds only for
$\alpha<2$. In this case, the algorithm’s contribution is

$d\Phi_{3}(t)/dt\leq\Delta(r(q_{r})-r^{o}(q_{r}))s_{r}=-\Delta(r_{f}(t)-r^{o}(t)+1)s_{r},$

since $r^{o}(q_{r})\leq r^{o}(t)-1$ as $q_{r}>q_{r}^{o}$. The $\mathsf{OPT}$’s
contribution

$\displaystyle d\Phi_{3}(t)/dt$
$\displaystyle\leq\left(f(r(q_{r}^{o})-r^{o}(q_{r}^{o})+1)-f(r(q_{r}^{o})-r^{o}(q_{r}^{o}))\right){\tilde{s}},$
$\displaystyle=\Delta(r(q_{r}^{o})-r^{o}(t)+1){\tilde{s}}.$

Ideally we would want $r(q_{r}^{o})=r_{f}(t)$, however, that need not be true,
since $q_{r}>q_{r}^{o}$ and there can be caged reduce tasks that are smaller
in size than the free reduce jobs in which case $r(q_{r}^{o})=r(t)$, where
$r(t)$ is the total number of reduce jobs with the algorithm. Thus, the
$\mathsf{OPT}$’s contribution is
$d\Phi_{3}(t)/dt\leq\Delta(r(t)-r^{o}(t)){\tilde{s}}$. Hence, the argument
inside $\Delta$ function for the algorithms’ and the $\mathsf{OPT}$’s
contribution are not identical and we have to apply Lemma 8 separately on the
algorithms’ and the $\mathsf{OPT}$’s contribution for $d\Phi_{3}/dt$ to get
$d\Phi_{3}/dt\leq
c_{3}P({\tilde{s}}(t))-c_{3}(r_{f}(t)-(\alpha-1)r(t)-(2-\alpha)r^{o}(t))$,
where we have used the fact that the speed of the algorithm for processing the
shortest free reduce task is $P^{-1}(r_{f}(t)+1)$.

The case for $q_{r}=q_{r}^{o}$ follows similarly. ∎

##  XIII Lemma 14

######  Lemma 14.

For $\alpha\geq 1$, and $x_{i}\geq 0$,
$\left(\sum_{i=1}^{n}x_{i}^{1/\alpha}\right)^{\alpha}\leq
n^{\alpha-1}\sum_{i=1}^{n}x_{i}.$

###### Proof.

Let $X$ be a random variable with distribution $D$ over the support
$x_{1},\dots,x_{n}$. Let $\eta>\nu>0$. Then
${\mathbb{E}}\\{|X|^{\eta}\\}^{1/\eta}={\mathbb{E}}\\{(|X|^{\nu})^{\eta/\nu}\\}^{1/\eta}\geq{\mathbb{E}}\\{(|X|^{\nu})\\}^{\frac{\eta}{\nu}\frac{1}{\eta}}={\mathbb{E}}\\{(|X|^{\nu})\\}^{1/\nu}$
where the inequality follows from Jensen’s inequality since $x^{\eta/\nu}$ is
convex. Choosing $D$ to be the uniform distribution, and $\eta=1$ and
$\nu=1/\alpha$ with $\alpha\geq 1$, we get the inequality. ∎

##  XIV Proof of Theorem 10

The potential function we construct as follows is essentially the multi-server
version of (19) as proposed in [31] for analyzing the multi-server SRPT
algorithm, except for the $\Phi_{4}$ term that is needed to handle the unique
challenge posed by the precedence constraints described in the previous
paragraph. Let $d_{m}(q)=\max\left\\{0,\frac{m(q)-m^{o}(q)}{K}\right\\}$,
$d_{J}(q)=\max\left\\{0,{\mathsf{r}}\frac{(J(q)-J^{o}(q))}{K}\right\\}$,
$d_{r}(q)=\max\left\\{0,\frac{r(q)-r^{o}(q)}{K}\right\\}$. We consider the
potential function

$\Phi(t)=\Phi_{1}(t)+\Phi_{2}(t)+\Phi_{3}(t)+\Phi_{4}(t),$ (20)

where $\Phi_{i}(\cdot)$ are defined as follows.

$\displaystyle\Phi_{1}(t)$
$\displaystyle=c_{11}\int_{0}^{\infty}f\left(d_{m}(q)\right)dq+c_{12}\int_{0}^{\infty}(m(q)-m^{o}(q))dq,$
$\displaystyle\Phi_{2}(t)$
$\displaystyle=c_{21}\int_{0}^{\infty}f\left(d_{J}(q)\right)dq$
$\Phi_{3}(t)=c_{31}\int_{0}^{\infty}f\left(d_{r}(q)\right)dq+c_{32}\int_{0}^{\infty}(r(q)-r^{o}(q))dq.$

The sub-potential function $\Phi_{4}(t)$ is special and needed to handle the
case when the number of jobs with the algorithm is less than $K$. For the
$j^{th},j=1,\dots,J(t)(J^{o}(t))$ job, let $q_{j}$ ($q_{j}^{o}$) be the sum of
the remaining size of all its map tasks with the algorithm and the
$\mathsf{OPT}$, respectively. Then for the $j^{th}$ job $n_{j}(t,q)=1$
($n_{j}^{o}(t,q)=1$) for $q\leq q_{j}$ ($q\leq q_{j}^{o}$) and zero otherwise.

Let $\Phi_{4}(t)$

$=c_{4}\left(\sum_{j\in
J(t)}\int_{0}^{\infty}f\left({\mathsf{r}}n_{j}(q)\right)dq-\sum_{j\in
J^{o}(t)}\int_{0}^{\infty}f\left({\mathsf{r}}n_{j}^{o}(q)\right)dq\right).$

$c_{11},c_{12},c_{21},c_{22},c_{31},c_{32},c_{4}$ are positive constants to be
determined later.

The drift of $\Phi_{1},\Phi_{2},\Phi_{3}$ can be computed similar to Lemma 10
and 11 [31], when $\mathsf{OPT}$ has no precedence constraints but is not
restricted to perform multi-server SRPT scheduling.

######  Lemma 15.

$d\Phi_{1}/dt$ For $m(t)\geq K$,

$\displaystyle\leq$ $\displaystyle
c_{11}m^{o}-c_{11}(2-\alpha)m+c_{11}(2-\alpha)\left(\frac{K-1}{2}\right)$
$\displaystyle\qquad+c_{11}\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k})-c_{12}\min(K,m)+c_{12}\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k})$

while for $m(t)<K,$

$\displaystyle d\Phi_{1}/dt$ $\displaystyle\leq
c_{11}m^{o}+\frac{c_{11}(2-\alpha)m}{2}+c_{11}\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k}),$
$\displaystyle\quad-
c_{12}\min(K,m)+c_{12}\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k})$

######  Lemma 16.

For $J(t)\geq K$,

$\displaystyle d\Phi_{2}/dt\leq$ $\displaystyle
c_{21}{\mathsf{r}}J^{o}-c_{21}(2-\alpha){\mathsf{r}}J+c_{21}(2-\alpha)\left(\frac{K-1}{2}\right)$
$\displaystyle\quad+c_{21}\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k})$

while for $J(t)<K$, (by disregarding the algorithm’s contribution)

$\displaystyle d\Phi_{2}/dt\leq$ $\displaystyle
c_{21}{\mathsf{r}}J^{o}+c_{21}(2-\alpha)\left(\frac{K-1}{2}\right)+c_{21}\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k})$

######  Lemma 17.

For $r_{f}(t)\geq K$, $d\Phi_{3}/dt$

$\displaystyle\leq$ $\displaystyle
c_{31}r^{o}-c_{31}(2-\alpha)r_{f}+c_{31}(2-\alpha)\left(\frac{K-1}{2}\right)$
$\displaystyle+c_{31}\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k})-c_{32}\min(K,m)+c_{32}\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k})$

while for $r_{f}(t)<K,$

$\displaystyle d\Phi_{3}/dt$ $\displaystyle\leq
c_{31}r^{o}+\frac{c_{31}(2-\alpha)r_{f}}{2}+c_{31}\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k}),$
$\displaystyle\quad-
c_{32}\min(K,m)+c_{32}\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k})$

The only non-trivial drift is for $\Phi_{4}(t)$ which is needed when $J(t)<K$
is described as follows.

######  Lemma 18.

When

$d\Phi_{4}(t)/dt\leq c_{4}(-{\mathbf{1}}_{J(t)<K}\
{\mathsf{r}}J(t)+{\mathsf{r}}\min\\{J^{o}(t),K)).$

Proof is similar to Lemma 9 and hence omitted.

###### Proof of Theorem 10.

To prove the Theorem we will show that (3) holds for an appropriate choice of
$c$ using Lemma 15, 16, 17 and 18.

For each server, the energy cost is similar to the single server case and is
given by
$P(P^{-1}(\frac{m(t)+1}{K})+P^{-1}(\frac{{\mathsf{r}}J(t)+1}{K})+P^{-1}(\frac{r_{f}(t)+1}{K}))\leq\frac{3^{\alpha-1}}{K}(m(t)+{\mathsf{r}}J(t)+r_{f}(t)+3)$
using Lemma 14 since $P^{-1}(x)=x^{1/\alpha}$ with $n=3$ and $\alpha\geq 1$.
Thus, summing across all the $K$ servers, the total energy cost
$\sum_{k=1}^{K}P(s_{k}(t))$ at any time $\leq
3^{\alpha-1}(m(t)+{\mathsf{r}}J(t)+r_{f}(t)+3)$.

Thus, the running cost $n(t)+\sum_{k=1}^{K}P(s_{k}(t))$ for the algorithm is
at most $3^{\alpha-1}(m(t)+{\mathsf{r}}J(t)+r_{f}(t))+3^{\alpha}$. For the
case when $J(t)<K$, $m(t)\geq K$, $r_{f}\geq K$, combining Lemma 15, 16, 17,
18 we can write (3), $n(t)+\sum_{k=1}^{K}P(s_{k}(t))+d\Phi/dt$

$\displaystyle\leq(3^{\alpha-1}+1)(m(t)+{\mathsf{r}}J(t)+r_{f}(t))+3^{\alpha}+c_{11}m^{o}$
$\displaystyle\quad-
c_{11}(2-\alpha)m+c_{11}(2-\alpha)\left(\frac{K-1}{2}\right)$
$\displaystyle\qquad+c_{11}\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k})-c_{12}\min(K,m)+c_{12}\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k}),$
$\displaystyle\qquad+c_{31}r^{o}-c_{31}(2-\alpha)r_{f}+c_{31}(2-\alpha)\left(\frac{K-1}{2}\right)$
$\displaystyle\qquad+c_{31}\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k})-c_{32}\min(K,m)+c_{32}\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k}),$
$\displaystyle\qquad+c_{4}(-{\mathbf{1}}_{J(t)<K}\
{\mathsf{r}}J(t)+{\mathsf{r}}\min\\{J^{o}(t),K)),$ $\displaystyle\leq
c(n^{o}(t)+\sum_{k\in\mathsf{OPT}}P({\tilde{s}}_{k})),$

for $c=c_{1}+c_{2}+c_{3}+3^{\alpha}$, where
$c_{1}=4,c_{2}=\frac{4}{2-\alpha},c_{3}=4$, since $\alpha<2$ Hence, the
competitive ratio of the proposed online algorithm is
$8+\frac{4}{2-\alpha}+3^{\alpha}$. Other case depending on $J(t)\geq K$ and
$r_{f}<K$ follow similarly. ∎