# Load Balancing with Job-Size Testing: Performance Improvement or
Degradation?

Jonatha Anselmi and Josu Doncel  J. Anselmi is with Univ. Grenoble Alpes,
CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France. E-mail:
<EMAIL_ADDRESS>J. Doncel is with the University of the Basque
Country, UPV/EHU, Barrio sarriena s/n, 48940 Leioa, Spain. E-mail:
<EMAIL_ADDRESS>
###### Abstract

In the context of decision making under explorable uncertainty, scheduling
with testing is a powerful technique used in the management of computer
systems to improve performance via better job-dispatching decisions. Upon job
arrival, a scheduler may run some _testing algorithm_ against the job to
extract some information about its structure, e.g., its size, and properly
classify it. The acquisition of such knowledge comes with a cost because the
testing algorithm delays the dispatching decisions, though this is under
control. In this paper, we analyze the impact of such extra cost in a load
balancing setting by investigating the following questions: does it really pay
off to test jobs? If so, under which conditions? Under mild assumptions
connecting the information extracted by the testing algorithm in relationship
with its running time, we show that whether scheduling with testing brings a
performance degradation or improvement strongly depends on the traffic
conditions, system size and the coefficient of variation of job sizes. Thus,
the general answer to the above questions is non-trivial and some care should
be considered when deploying a testing policy. Our results are achieved by
proposing a load balancing model for scheduling with testing that we analyze
in two limiting regimes. When the number of servers grows to infinity in
proportion to the network demand, we show that job-size testing actually
degrades performance unless short jobs can be predicted reliably almost
instantaneously _and_ the network load is sufficiently high. When the
coefficient of variation of job sizes grows to infinity, we construct testing
policies inducing an arbitrarily large performance gain with respect to
running jobs untested.

###### Index Terms:

Dispatching policies, size-based routing, scheduling with testing, load
balancing, explorable uncertainty

††publicationid: pubid:

##  1 Introduction

The efficient management of multi-server distributed systems strongly depends
on the ability to properly classify incoming jobs, as this information can
lead to better scheduling decisions. In the typical scenario, the exact
structure of the incoming jobs is not known in advance but some information
about their size or running time may be extracted by running an auxiliary
_testing algorithm_. This algorithm takes as input the description of a job
and retrieves information by performing operations of various levels of
complexity; see below for examples. Finally, such information is exploited to
make a job-size prediction and to dispatch the given job to the right
resources for processing with the objective of minimizing some performance
criterion such as the mean delay.

In principle, the computational resources that can be dedicated to the testing
algorithm are unbounded because it is well known in computer science that the
“halting problem”, i.e., the problem of determining whether a computer program
will finish running or continue to run forever from a description of an
arbitrary computer program and an input, is undecidable. On the other hand,
while the execution of the testing algorithm comes with a price (because the
job dispatching decisions are delayed), it may provide valuable classification
information that eventually pays off. The investigation of such exploration-
exploitation trade-off under explorable uncertainty, referred in the
literature with the term “scheduling with testing”, has recently gained
traction in scheduling theory [1, 2, 3] and is the focus of this paper; see
Section 1.2 for a review of the literature.

###  1.1 Motivation

Scheduling with testing relies on the idea of possibly running a _test_
against each submitted job. Tests aim at extracting information about the
structure of jobs such as their sizes or running times _before_ their actual
processing. This technique finds applications in a wide range of domains that
we describe in the following, though our main motivation is the application to
High Performance Computing (HPC) distributed systems; see, e.g., [4, 5].

In HPC systems, users submit jobs to the platform over time possibly with an
estimation of their running times, or equivalently job sizes, and a central
scheduler relies on this information to make a prediction about their sizes
and finally dispatch them to the right computational resources [6, 4]. It is
well known that user-provided running time estimations are not accurate [7, 8,
5, 4], hence the idea of improving the estimation by running tests. In
practice, typical job running times are “highly variable” in the sense that
they can be of the order of minutes, hours or days, and these are not known to
the scheduler in advance; see, e.g., [9, Section 3] for neuroscience
applications.

The main objective consists in developing job dispatching strategies that
minimize a performance measure of interest such as the the mean delay or
_makespan_ , and this strongly relies on the ability to reduce the
interference between long and short jobs. Towards this purpose, scheduling
with testing may be a viable option that can be performed at several levels
depending on the available computational resources [6]. Here, the output of a
test is a guess (subject to error) of the exact size of the given job. With an
increasing level of complexity, a test may consist in guessing a job size by
_i)_ just extracting the user-provided estimation of the job execution time
(though this is inaccurate as remarked in [4, 6]), _ii)_ analyzing the job
input parameters [9], _iii)_ analyzing the job source code (e.g., looking at
the Kolmogorov complexity) [10], _iv)_ running a code optimizer [11, 12], or
_v)_ running a prediction toolbox constructed from previous data via machine
learning mechanisms [4, 7, 5]. For linear algebra operations, just looking at
input parameters such as the dimension of the input matrix may be enough to
extract useful information [9]. In fact, if the matrix dimension is small,
then the job is most likely short. On the other hand, the contrapositive may
not hold: if the job is large, then it is not necessarily long because the
matrix may be sparse, and in this case one may consider a more sophisticated
testing strategy digging in the structure of the matrix more deeply and
therefore with an increased testing cost. Other examples include machine
learning or image processing jobs where the input parameters may be the number
of iterations to train the underlying machine learning model or the number of
pixels of the given image, respectively. In this context, it is not well
understood whether the extra cost induced by scheduling with testing brings a
performance benefit or degradation (see Section 1.2 for further details), and
this open question motivates our work.

Besides HPC systems, scheduling with testing is also employed in several other
settings. In communication networks for instance, a testing algorithm may be a
compression algorithm aimed at reducing the size, and thus the transmission
time, of the given file to transmit, and here a compression cost must clearly
be paid [13]; note that an already compressed file is uncompressible but this
knowledge is not available beforehand. In wireless networks, a testing
algorithm may be an algorithm that selects the channel with the optimal
signal-to-noise ratio before the actual transmission takes place. In
maintenance or medical environments, a diagnosis or a test can be carried out
to determine the exact processing time of a job, and this information is used
in turn to prioritize and efficiently allocate resources [14, 1, 15]. We refer
the reader to [2, 16, 12] for more detailed discussions about applications of
scheduling with testing.

###  1.2 Related Work

Scheduling with testing falls in the broad field of _optimization under
explorable uncertainty_. More specifically, it describes a setting where jobs
have unknown processing times that can be explored by running a test for some
time with a scheduler dispatching them tested or untested on a number of
computational resources (servers) to minimize some performance measure of
interest. From a theoretical point of view, this problem has been primarily
investigated on a _single_ server [1, 2, 12, 16, 17] with the objective of
minimizing the sum of completion times. A step further has been recently taken
in [3], where the authors consider the natural generalization of the problem
to _multiple_ identical parallel servers. In these works, the authors provide
algorithms that decide the amount of testing to be performed and demonstrate
their effectiveness by means of competitive-ratio analyses. These are meant to
compare the value of an algorithm with respect to an optimal off-line
solution. In the case of multiple servers, the SBS algorithm developed in [3]
is 3-competitive with respect to the makespan, i.e., the maximum load on any
server, provided that testing times are uniform.

An important assumption underlying the references above is that they focus on
static settings with a finite number of jobs. In this paper however, we focus
on multiple identical parallel servers as in [3] but consider a stochastic and
dynamic setting where an _infinite_ number of jobs joins the system over time
following an exogenous stochastic process. This allows us to develop testing
strategies that can guarantee stability of the scheduler in the sense of
positive Harris recurrence of the underlying Markov process. Moreover,
existing works assume that the exact job sizes are revealed after testing [3,
16, 2, 17], while we will consider a more general stochastic model connecting
the testing times and the amount of revealed information; see Section 2.2.

To the best of our knowledge, our work is the first to investigate scheduling
with testing in a queueing-theoretic load-balancing setting. Nonetheless,
similar approaches have been considered in the queueing literature. Most of
the existing works about load balancing (or equivalently job dispatching among
a set of parallel queues) assume that jobs are dispatched to servers instantly
upon their arrival with no cost, i.e., disregarding the impact of testing; see
[18] for a recent survey. Size-based routing (or load balancing) and the Task
Assignment Guessing Size (TAGS) algorithm [19] are two job-dispatching
strategies that can be interpreted as particular instances of scheduling with
testing in a queueing-theoretic setting. However, these rely on assumptions
that make them structurally different with respect to our approach. Let us
briefly discuss these two approaches. Size-based routing operates under the
assumption that the scheduler knows the exact size of each job upon its
arrival _without_ testing; see, e.g., [20, 21, 22]. The knowledge of exact job
sizes allows one to develop dispatching strategies preventing long jobs from
blocking the execution of several short jobs behind, especially in first-in
first-out systems. It is well known that this approach reduces the mean delay
induced by classical load balancing algorithms such as join-the-shortest-queue
provided that job sizes are variable enough [20, 23]. Size-based routing is a
degenerate case of scheduling with testing where the cost of testing is zero.
The TAGS strategy, proposed in [19], operates as follows. Upon arrival, a job
is dispatched to server one. If its execution takes less than $t_{1}$ time
units, it leaves the system, otherwise it is killed after $t_{1}$ time units
and re-executed from scratch at server two. Here, if its execution takes less
than $t_{2}>t_{1}$ time units, it leaves the system, otherwise it is killed
after $t_{2}$ time units and re-executed from scratch at server three, and the
process repeats until the last server is found, where the job is forced to
complete. TAGS implements a form of job-size testing strategy because at the
$n$-th stage, the hosting server knows that its executing time is at least
$t_{n-1}$. Specifically, the test coincides with the execution of the job
itself for a limited amount of time. The drawback of TAGS is its reduced
stability region (due to the fact that jobs need to be re-executed from
scratch upon re-routing) and the fact that job migration across servers often
implies a prohibitively expensive communication overhead. In fact, this holds
true in HPC systems as typical jobs involve a large amount of data.

Finally, Markov decision processes may be used to identify optimal testing
strategies. However, this approach is prohibitively expensive from a
computational point of view due to the curse of dimensionality, as the size of
the underlying state space is exponential in the number of servers.

###  1.3 Contribution

We propose a Markovian framework for scheduling with testing in a load
balancing setting. Specifically, an infinite sequence of jobs joins the system
over time through a central scheduler (or dispatcher), which is in charge of
routing them to one out of $N$ parallel servers. Each server has its own
queue, processes jobs at speed one and operates under the first-come first-
served scheduling discipline. The scheduler is aware of the probability
distribution of job sizes but it can also rely on a testing algorithm to
extract additional information about the exact size of each job, and this is
exploited to route the job to some server with the objective of minimizing the
mean delay. Therefore, two mechanisms dictate the dynamics of the central
scheduler:

  * i)

a _testing_ policy, which defines the amount of time allocated to the
execution of the testing algorithm,

  * ii)

a _dispatching_ (or load balancing) policy, which defines how jobs are
dispatched to the $N$ servers.

To take into account the extra delay induced by the testing policy, we model
the scheduler as an M/M/1 queue where the service times coincide with the
testing times, and we will focus on testing policies that guarantee stability.
Though the existing literature on load balancing is vast, our framework is the
first to consider a load balancing system with testing policies in a
stochastic and dynamic setting.

Under a general assumption connecting the testing algorithm running time and
the amount of revealed information (see Assumption 1), we analyze the
resulting mean waiting time of jobs in two orthogonal limiting regimes: i) a
limiting regime where the system size $N$ grows to infinity in proportion to
the traffic demand while keeping the network load constant, and ii) a limiting
regime where the coefficient of variation of job sizes grows to infinity.
Importantly, the amount of resources at the central scheduler does not scale
in either case. These regimes, widely considered in queueing theory to
approximate dynamics in the pre-limit, are justified because real HPC systems
are large and because common empirical studies of computer systems show that
realistic probability distributions of job sizes are heavy tailed; e.g., [24,
Chapter 9] and [25, 26].

Our main results identify the conditions under which job-size testing is
effective (or not) to improve the performance of a system that runs jobs
untested. Our findings show that these conditions strongly depend on the
traffic conditions, system size and the coefficient of variation of job sizes,
which implies that some attention should be paid when deploying a testing
policy. To quickly summarize our results:

  * •

In the large system limit ($N\to\infty$), we show that job-size testing is
_not_ worth unless each job brings enough information that can be retrieved
instantly _and_ the network load is sufficiently high; see Theorems 1 and 2.

  * •

For any system size $N$, it is possible to design testing policies such that
their performance benefit is arbitrarily large if and only if the job sizes
are variable enough; see Section 4.2.

Let us elaborate on these insights.

When $N\to\infty$, the mean testing time necessarily converges to zero as
otherwise the stability condition at the scheduler would not be satisfied.
This leads us to investigate dynamics on a right-neighbourhood of zero. Here,
we show in Theorem 1 that the derivative of the mean waiting time with respect
to the mean testing time is strictly increasing if the amount of information
that the testing algorithm can retrieve instantly upon job arrivals is null.
The latter condition appears natural and can be rephrased more formally as
“the random variable modelling _the prediction_ of the job size obtained with
a zero testing time is independent of the random variable modelling the job
size”. In some applications however, predictions about _short_ jobs are
reliable and obtained almost instantaneously by just looking at input
parameters, while predictions about long jobs are subject to errors; as
commented above, for most of matrix operations a job can be regarded as short
if the size of the given matrix is small while the contrapositive does not
necessarily hold true. This fact leads us to consider the “No False Small”
scenario; see Section 3.3 for a precise definition. Within this scenario and
on a right-neighbourhood of zero, we show in Theorem 2 that the derivative of
the mean waiting time with respect to the mean testing time is strictly
negative if the traffic demand is sufficiently large or if the probability of
having short jobs and exact predictions increases sufficiently fast with the
mean testing time.

When the job sizes follow a heavy tailed distribution where the coefficient of
variation grows to infinity, which is the case of practical interest, the mean
testing time can be designed in a way to control the mean testing cost. Within
this regime and within the testing time design choice given in (18), we
provide in Theorem 3 conditions ensuring that the efficiency ratio, i.e., the
ratio between the mean waiting time obtained with and without testing,
converges to zero. These conditions include the “Independent Predictions for
Zero Testing Time” and “No False Small” scenarios discussed above, and
identify the settings where job-size testing, to our opinion, should be
applied. In contrast, if job sizes are not variable enough, the “universal”
lower bound in Corollary 1 immediately implies that job-size testing is
inefficient.

Finally, our conclusions are supported by numerical results obtained within
job size distributions drawn from a neuroscience application [9].

###  1.4 Organization

The rest of this work is organized as follows. In Section 2, we propose a new
framework for job-size testing and dispatching. This is then analyzed in the
limit where the system size grows to infinity in Section 3 and in the limit
where the degree of variability of job sizes grows to infinity in Section 4.
Then, Section 5 presents empirical results, and Section 6 draws the
conclusions of our work.

##  2 Load Balancing with Job-Size Testing

We describe a framework for load balancing with job-size testing (see Figure 1
for a summary) and define the performance measures of interest.

Figure 1: Architecture of the proposed model for load balancing with job-size
testing. It is assumed that $c\in\mathbb{N}$.

###  2.1 Architecture

We consider a service system composed of $N$ servers, a sequence of _jobs_ and
a _scheduler_ (or dispatcher). Each of the $N$ servers has its own infinite-
room queue and processes jobs at unit rate following the first-come first-
served scheduling discipline. In the following, the terms “server” and “queue”
will be used interchangeably.

####  2.1.1 Jobs

Jobs join the system over time following a Poisson process with rate
$\Lambda:=\lambda N$ and each of them leaves the system after service
completion at its designated server.

The $n$-th arriving job has a size given by random variable $X(n)$ and this is
the amount of work required by the $n$-th job on one server, or equivalently
its service time at any server since servers operate at unit rate. We assume
that the sequence $(X(n))_{n}$ is independent, identically distributed and
also independent of the arrival process. For stability, i.e., positive Harris
recurrence of the underlying Markov process, we assume that
$\rho:=\lambda\mathbb{E}[X(n)]<1$.

We also assume that jobs are classified as either _long_ , i.e., of size
$x_{M}$, or _short_ , i.e., of size $x_{m}$, with $0<x_{m}<x_{M}<\infty$.
Thus, $\mathbb{P}(X(n)=x_{m})+\mathbb{P}(X(n)=x_{M})=1$ for all $n$. We will
be interested in applying our results to the case where job sizes have a
“heavy-tailed” distribution in the sense that

$\displaystyle\mathbb{P}(X=x_{M})=\alpha\,x_{M}^{-\beta},\quad\alpha>0,\,\beta>0,$
(1)

with $x_{M}$ “large”. Here, the tail of $X$ decays polynomially and we will be
particularly interested in the case where $\beta<1$ as this implies high
variability when $x_{M}$ grows.

Let us justify the two-point job size distribution assumption:

  * •

In the context of HPC systems, common workloads are composed of jobs whose
size can be clustered in two groups, “long” and “short”, which yields bimodal
distributions [9, 27, 28]; see also [29, 30, 23]. Several reasons induce such
dichotomy and these may depend on the application at hand. For instance, in
neuroscience applications, users submit jobs together with images that may
contain either little or a lot of information, with a gap of several orders of
magnitude [9]. Here, our two-point distribution assumption is meant to
simplify and approximate such bimodal distribution.

  * •

From a theoretical point of view, a two-point distribution will be enough both
to exhibit the issues and to capture the key properties underlying job-size
testing for load balancing. In the context of scheduling with testing, other
works rely on this assumption to develop _worst-case_ analyses [17]. In fact,
we remark that the distribution that maximizes the variance among the
distributions with bounded support concentrates on the two extreme points of
the support. Thus, in this sense it yields the worst-case scenario as the mean
delay (defined below in (4)) strongly depends on the variance of job sizes.

A generalization of the proposed framework to a general job-size probability
distribution is possible but it is out of the scope of this paper; see the
conclusion section for further details.

####  2.1.2 Scheduler

When jobs arrive, they immediately join a scheduler, which is in charge of
dispatching each job to exactly one queue. In order to make such decisions, it
is allowed to execute a _testing algorithm_ against each job. This algorithm
extracts some information that is exploited to make a prediction about its
actual size. The _testing time_ , i.e. the amount of time dedicated to the
execution of the testing algorithm, is deterministic and under the control of
the system manager. We assume that the same testing time is applied to all
jobs, say $\sigma\geq 0$.

We model the scheduler as an $M/M/1$ queue with arrival rate $\Lambda$ and
mean service time $\sigma$. This is meant to model congestion and to capture
the impact of the runtime phenomena happening during the execution of the
testing algorithm, which stochastically perturb the service times,

For stability, we choose $\sigma$ such that $\Lambda\sigma<1$. Using the
Pollaczek–Khinchine formula [31], the mean delay (sojourn time) at the
scheduler is

$\displaystyle\frac{\sigma}{1-\Lambda\sigma},$ (2)

which can be also interpreted as the mean delay of an $M/G/1$ processor-
sharing queue.

We let $Y_{\sigma}(n)$ denote the $\\{x_{m},x_{M}\\}$-valued random variable
associated to the prediction of the true (unknown) size, $X(n)$, of the $n$-th
arriving job when the testing algorithm is executed for $\sigma$ time units.
We assume that the prediction of the $n$-th job $Y_{\sigma}(n)$ can only
depend on $X(n)$ and $\sigma$. With a slight abuse of notation,
$(X,Y_{\sigma})$ denotes an auxiliary random vector having the same
distribution of the job size and prediction pair $(X(n),Y_{\sigma}(n))$.

The following remark summarizes the information available at the scheduler.

######  Remark 1.

The scheduler knows $\lambda$, $N$ and the distribution of the job size $X$.
For all job $n$, it does not know the exact job size $X(n)$ but can execute a
testing algorithm for $\sigma$ time units to obtain a prediction,
$Y_{\sigma}(n)$, of the size of job $n$. Finally, the scheduler knows the
joint probability mass function of $(X,Y_{\sigma})$ for all $\sigma\geq 0$,
which in practice can be learned from the data.

####  2.1.3 Dispatching Policy

For job dispatching, we assume that there exists a real number $c\in(0,N)$
such that all jobs that are _predicted_ as short ($Y_{\sigma}(n)=x_{m}$) resp.
long ($Y_{\sigma}(n)=x_{M}$) are sent to servers $1,\ldots,\lfloor c\rfloor+1$
resp. $\lfloor c\rfloor+1,\ldots,N$. We will refer to $c$ as _cutoff server_.
Conditioned on $Y_{\sigma}=x_{m}$ resp. $Y_{\sigma}=x_{M}$, a job is sent to
server $i=1,\ldots,\lfloor c\rfloor$ resp. $\lfloor c\rfloor+2,\ldots,N$ with
probability $1/c$ resp. $1/(N-c)$ and to server $\lfloor c\rfloor+1$ with
probability $1-\lfloor c\rfloor/c$ resp. $1-(N-1-\lfloor c\rfloor)/(N-c)$. In
particular, note that i) server $\lfloor c\rfloor+1$ is the only server that
can receive jobs that are predicted as short or long and that this happens
only if $c$ is not an integer, ii) if $c<1$ resp. $c>N-1$, then no server that
only processes jobs predicted as short resp. long exists. The impact of server
$\lfloor c\rfloor+1$ is negligible in the analysis developed in Section 3
where $N\to\infty$. Here, without loss of generality, one could restrict to
the case where $c$ is an integer. When $N$ is finite however, as in the
analysis developed in Section 4, it is necessary to let $c$ take non-integral
values as otherwise it may not be possible to find a dispatching policy that
guarantees stability.

The routing strategy described above is meant to reduce the interference
between short and long jobs by mimicking the behavior of size-based routing
policies discussed in Section 1.2. Here, the underlying principle is that a
server only accepts jobs of size within a certain range so that short and long
jobs are separated. Of course, within our framework it is not guaranteed that
short and long jobs are separated from each other because in general exact
sizes are not known a priori.

###  2.2 Testing Algorithm: Quality of Prediction vs Running Time

The quality of job-size predictions depends on the amount of processing time
dedicated to the execution of the testing algorithm $\sigma$. In the
literature, it is assumed that the exact size (or processing time) of each job
is revealed once the testing algorithm is completed [3, 16, 2]. In contrast,
we follow a more general approach where after testing the scheduler disposes
of a probability distribution about the exact size that depends on $\sigma$.
We define the connection between the quality of predictions and running time
through

$\displaystyle P_{x,y}({\sigma}):=\mathbb{P}(X=x\cap Y_{{\sigma}}=y),$ (3)

where $x,y\in\\{x_{m},x_{M}\\}$ and $\sigma\geq 0$, and
$P({\sigma}):=[P_{x,y}({\sigma}):x,y\in\\{x_{m},x_{M}\\}]$, i.e., the joint
probability mass function of $(X,Y_{\sigma})$. In practice, this matrix can be
learned from the data by user profiling methods. We do not impose a specific
structure on $P({\sigma})$ but we will rely on the following assumption, which
will be implicitly taken in the remainder of the paper.

######  Assumption 1.

The following properties hold:

  * i)

$P({\sigma})$ is continuous in $\sigma$ and, on a right-neighbourhood of zero,
differentiable;

  * ii)

$P_{x,x}({\sigma})$ is non-decreasing and converges to $\mathbb{P}(X=x_{m})$
as ${\sigma}\to\infty$, with $x\in\\{x_{m},x_{M}\\}$;

  * iii)

$P_{x,y}({\sigma})$ is non-increasing and converges to zero as
${\sigma}\to\infty$, with $x\neq y$ and $x,y\in\\{x_{m},x_{M}\\}$.

The rationale behind this assumption is as follows. The monotonicity
properties in points ii) and iii) of Assumption 1 are natural because one
expects that more information about the exact size is retrieved as the testing
time increases. The asymptotic properties in the limit where
${\sigma}\to\infty$ are consistent with the idea that the testing algorithm is
able to get the exact size of each job if it is executed for a sufficiently
large amount of time. Finally, we claim that continuity is also natural while
differentiability will be required for technical reasons and only used for
Theorems 1 and 2.

######  Remark 2.

In Assumption 1, we have defined $P({\sigma})$ on the whole non-negative real
line for generality and because in principle the computational resources that
are required by the testing algorithm are unbounded; recall that the “halting
problem” is undecidable. However, we stress that we will consider “short”
testing times ${\sigma}<\Lambda^{-1}$ as these rule out instability at the
scheduler.

For now, we do not impose any other assumption on the structure of $Y_{0}$,
the random variable of job-size predictions when $\sigma=0$: $Y_{0}$ may
depend on $X$ or not. Moreover, $Y_{\sigma}$ and $X$ are in general different
in distribution. This models the fact that it may be faster to learn how to
make good predictions about short rather than long jobs as the testing time
increases.

###  2.3 Performance Measure

The performance measure of interest is the mean waiting time of jobs, i.e.,
the sum of the mean delay at the scheduler, i.e., (2), and the mean waiting
time at the servers, say $R_{c}^{(N)}(\sigma)$. Within the given set of
dispatching policies, the latter corresponds to the mean waiting time of three
parallel M/G/1 queues because i) the output process of an M/M/1 queue, i.e.,
of the scheduler, is Poisson (by Burke’s theorem) and ii) the thinning of a
Poisson process produces again a Poisson process. Using the
Pollaczek–Khinchine formula [31], we obtain

$\displaystyle
R_{c}^{(N)}(\sigma)=\frac{\Lambda}{2}\frac{\mathbb{P}(Y_{\sigma}=x_{m})^{2}\,p_{m}^{2}\mathbb{E}[X^{2}\mid
Y_{\sigma}=x_{m}]\mathbb{I}_{\\{c\geq 1\\}}}{\lfloor
c\rfloor-\Lambda\mathbb{P}(Y_{\sigma}=x_{m})p_{m}\,\mathbb{E}[X\mid
Y_{\sigma}=x_{m}]}$
$\displaystyle+\frac{\Lambda}{2}\frac{p_{z}^{2}\mathbb{E}[Z^{2}]}{1-\Lambda
p_{z}\,\mathbb{E}[Z]}$
$\displaystyle+\frac{\Lambda}{2}\frac{\mathbb{P}(Y_{\sigma}=x_{M})^{2}p_{M}^{2}\mathbb{E}[X^{2}\mid
Y_{\sigma}=x_{M}]\mathbb{I}_{\\{c\leq N-1\\}}}{N-1-\lfloor
c\rfloor-\Lambda\mathbb{P}(Y_{\sigma}=x_{M})p_{M}\,\mathbb{E}[X\mid
Y_{\sigma}=x_{M}]}$ (4)

provided that $\Lambda\mathbb{P}(Y_{\sigma}=x_{m})p_{m}\,\mathbb{E}[X\mid
Y_{\sigma}=x_{m}]<\lfloor c\rfloor$, $\Lambda p_{z}\,\mathbb{E}[Z]<1$ and
$\Lambda\mathbb{P}(Y_{\sigma}=x_{M})p_{M}\,\mathbb{E}[X\mid
Y_{\sigma}=x_{M}]<N-1-\lfloor c\rfloor$ and infinity otherwise. In (4),

$\displaystyle p_{m}$ $\displaystyle:=\frac{\lfloor
c\rfloor}{c}\,\mathbb{I}_{\\{c\geq 1\\}},\quad p_{M}:=\frac{N-1-\lfloor
c\rfloor}{N-c}\,\mathbb{I}_{\\{c\leq N-1\\}}$ $\displaystyle p_{z}$
$\displaystyle:=\mathbb{P}(Y_{\sigma}=x_{m})\,(1-p_{m})+\mathbb{P}(Y_{\sigma}=x_{M})\,(1-p_{M})$

and $Z$ is an auxiliary random variable equal to $X\mid Y_{\sigma}=x_{m}$ with
probability $\mathbb{P}(Y_{\sigma}=x_{m})(1-p_{m})/p_{z}$ and to $X\mid
Y_{\sigma}=x_{M}$ otherwise. If $p_{z}>0$, the three terms in (4) refer to the
mean waiting time in the groups of servers $\\{1,\ldots,\lfloor c\rfloor\\}$,
$\\{\lfloor c\rfloor+1\\}$ and $\\{\lfloor c\rfloor+2,\ldots,N\\}$,
respectively. Therefore, the mean user-perceived waiting time is
$\frac{\sigma}{1-\Lambda\sigma}+R_{c}^{(N)}(\sigma).$ To make our approach a
little bit more general and to better show the impact of the scheduler, we
take as performance measure of interest the quantity

$\displaystyle
D_{c}^{(N)}(\sigma):=f\left(\frac{\sigma}{1-\Lambda\sigma}\right)+R_{c}^{(N)}(\sigma)$
(5)

where $f:\mathbb{R}_{+}\to\mathbb{R}_{+}$ is any increasing, continuous and
differentiable function such that $f(0)=0$.

We will also be interested in the _efficiency_ of job-size testing relative to
the case where no testing is performed ($\sigma=0$), which we define by

$\displaystyle\mathcal{E}(\sigma):=\mathcal{E}^{(N)}(\sigma):=\frac{\min_{c\in[0,N]}D_{c}^{(N)}(\sigma)}{\min_{c\in[0,N]}D_{c}^{(N)}(0)}.$
(6)

Figure 2 shows plots of $\mathcal{E}(\sigma)$ with respect to a number of
scenarios; see the figure caption for details. The main purpose here is to
have a glimpse of the behavior of $\mathcal{E}(\sigma)$ and to highlight that
the conditions on $\sigma$ under which job-size testing improves performance,
i.e., $\mathcal{E}(\sigma)<1$, are non-trivial.

Figure 2: Plots of the efficiency measure $\mathcal{E}$, see (6), assuming
that (1) holds with $\alpha=1$ and $f(\cdot)=\cdot$. Also,
$P_{x_{m},x_{m}}(\sigma)=(1-e^{-10\sigma})(\mathbb{P}(X=x_{m})-P_{x_{m},x_{m}}(0))+P_{x_{m},x_{m}}(0)$,
$P_{x_{M},x_{M}}(\sigma)=(1-e^{-\sigma})(\mathbb{P}(X=x_{M})-P_{x_{M},x_{M}}(0))+P_{x_{M},x_{M}}(0)$,
$P_{x_{m},x_{M}}(\sigma)=\mathbb{P}(X=x_{m})-P_{x_{m},x_{m}}(\sigma)$ and
$P_{x_{M},x_{m}}(\sigma)=\mathbb{P}(X=x_{M})-P_{x_{M},x_{M}}(\sigma)$, which
means that the profile matrix $P_{a}(\sigma)$ agrees with the law of
diminishing returns.

For instance, when $N=100$, $\rho=0.8$ and $x_{M}=10^{5}$, we also note that
job-size testing may never improve if $\beta\in\\{1.5,2\\}$ while bringing
enormous benefits if in the same conditions $\beta$ moves to $0.5$ (increased
job-size variability).

###  2.4 Additional Notation

Given a real function $g(t)$, we let $g^{\prime}(t):=\frac{{\rm d}g(t)}{{\rm
d}t}$ and if $c$ is a constant, then $g^{\prime}(c):=\left.\frac{{\rm
d}g(t)}{{\rm d}t}\right|_{t=c}$. We let $\mathbb{I}_{\\{A\\}}$ denote the
indicator function of the event $A$. If $\mathbb{I}_{\\{A\\}}=0$, we take the
convention that $\mathbb{I}_{\\{A\\}}/0=\mathbb{I}_{\\{A\\}}\times\infty=0$.

##  3 Large Systems

In this section, we focus on large systems and analyze job-size testing in the
limit where $N\to\infty$. Several works in the literature of size-based
routing have focused on this regime, e.g., [22, 21, 32], which is well
justified because of the large number of servers that compose existing HPC
systems. Within this regime, the testing time must converge to zero as
otherwise the stability condition at the scheduler, i.e., $\lambda N\sigma<1$,
is not satisfied. Thus, to understand under which conditions job size testing
is effective to reduce waiting times with respect to the situation where jobs
run untested, we investigate when $D_{c}^{(N)}(\sigma)$ is decreasing on a
right neighbourhood of zero for all $N$ sufficiently large. More specifically,
given a sequence of cutoff servers $(C_{N})_{N}$, we study the limit as
$N\to\infty$ of the derivative of $D_{C_{N}}^{(N)}(\sigma)$ on $0^{+}$.

We now specify the limiting regime of interest in detail and then perform the
resulting analysis under two complementary assumptions on $Y_{0}$ that are
described below. To quickly summarize the results in this section, our
findings show that job size testing is counterproductive in large systems
unless the system is in heavy-traffic and short jobs can be predicted
reliably.

###  3.1 Limiting Regime

Let

$\displaystyle C_{N}:=c^{*}N+h_{N}$ (7)

where

$c^{*}:=(1-\lambda\mathbb{E}[X\mid Y_{0}])\frac{\sqrt{\mathbb{E}[X^{2}\mid
Y_{0}=x_{m}]}}{\mathbb{E}[\sqrt{\mathbb{E}[X^{2}\mid
Y_{0}]}]}\mathbb{P}(Y_{0}=x_{m})\\\ +\lambda\,\mathbb{E}[X\mid
Y_{0}=x_{m}]\mathbb{P}(Y_{0}=x_{m})$ (8)

and $(h_{N})_{N}$ is a uniformly bounded sequence. One can check that if the
cutoff server is $C_{N}$, i.e., $c=C_{N}$, then the system with $N$ servers is
stable for all $N$ large enough.

The following proposition provides structural properties on the _asymptotic
optimal mean waiting time_ , say $R^{*}$; see the Appendix for a proof. For
any $\tau\geq 0$, it assumes that $\sigma$ is designed such that

$\displaystyle\sigma=\sigma^{(N)}(\tau)=\frac{1}{\lambda N+\tau^{-1}\,o(N)}$
(9)

if $\tau>0$ and $\sigma=0$ if $\tau=0$; clearly, the $o(N)$ term in (9) does
not depend on $\tau$. This design choice for the testing time is convenient
because it satisfies the stability condition at the scheduler while imposing a
controlled budget on its performance cost. In fact, the mean delay at the
scheduler (2) boils down to $\tau/o(N)$.

######  Proposition 1.

Assume that (9) holds. For any $\tau\geq 0$,

$\displaystyle R^{*}$
$\displaystyle:=\lim_{N\to\infty}\min_{c\in[0,N]}R_{c}^{(N)}(\sigma)=\lim_{N\to\infty}R_{C_{N}}^{(N)}(\sigma)$
(10)
$\displaystyle=\frac{\lambda}{2}\frac{\left(\mathbb{E}\left[\sqrt{\mathbb{E}[X^{2}\mid
Y_{0}]}\right]\right)^{2}}{1-\lambda\mathbb{E}[X]}.$ (11)

The limit $R^{*}$ is made explicit and the conditional expectation term in
(10) reveals the impact of predictions on the optimal system performance.

######  Remark 3.

Any sequence of cutoff servers that satisfies (7) induces the optimal
performance at the servers. This motivates us to study the model under
investigation with respect to a sequence of systems indexed by $N$ where for
the $N$-th system the cutoff server is $C_{N}$.

###  3.2 Independent Predictions for Zero Testing Time

When $\sigma=0$, no testing algorithm is executed and in this case it is
reasonable to assume that no additional information about the true job size is
revealed at the moment of its arrival. Since the scheduler knows the
distribution of $X$, its best strategy to predict job sizes consists in
sampling independently from such distribution. This leads us to consider the
case where $X$ and $Y_{0}$ are independent and identically distributed, for
which we have the following negative result; see the Appendix for a proof.

######  Theorem 1.

Assume that $X$ and $Y_{0}$ are independent and equal in distribution. Then,

$\displaystyle\lim_{N\to\infty}\lim_{\sigma\downarrow 0}\frac{{\rm d}}{{\rm
d}\sigma}D_{C_{N}}^{(N)}(\sigma)=f^{\prime}(0).$ (12)

Since $f^{\prime}(0)>0$, $\sigma\mapsto D_{C_{N}}^{(N)}(\sigma)$ is strictly
increasing on a right neighbourhood of zero, for all $N$ large enough. Thus,
it turns out that job testing does not help in this case. While
$R_{C_{N}}^{(N)}(\sigma)$ decreases on a right neighbourhood of zero for any
(finite) $N$, in the proof of Theorem 1 we show that
$\lim_{N\to\infty}\lim_{\sigma\downarrow 0}\frac{{\rm d}}{{\rm
d}\sigma}R_{C_{N}}^{(N)}(\sigma)=0$, which shows that the extra cost of job
testing does not eventually pay off in the large system limit.

###  3.3 No False Small

Now, we analyze the effectiveness of the proposed job testing strategy under
some additional practical assumptions on the structure of predictions.
Specifically, we are interested in a scenario where predictions about _short_
jobs are exact and obtained instantaneously, while predictions of long jobs
are subject to errors. This is justified because just the (little) knowledge
of the fact that the job is executed against “small” parameters, which in
practice can be easily obtained almost instantaneously, often implies that the
job itself is short, while if it is predicted as long, it may be long or
short. For instance, considering matrix operations, e.g., matrix inversion, or
machine learning jobs, which train a machine learning model by running a
suitable number of “iterations”, it should be clear that if the size of the
matrix or the number of iterations is small, then the job is short. In
contrast, if these parameters are large, then the job may not be necessarily
long because the matrix may be sparse or because iteration steps may exploit
data locality. Within this scenario,

$\displaystyle Y_{\sigma}=x_{m}$ $\displaystyle\mbox{ implies }X=x_{m}$

while $X\in[x_{m},x_{M}]$ within the event $Y_{\sigma}=x_{M}$. This leads us
to consider a setting where

$\displaystyle P_{x_{M},x_{m}}(\sigma)=0,\quad P_{x_{m},x_{m}}(\sigma)>0$ (13)

for all $\sigma\geq 0$. Inspired from common parlance in hypothesis testing,
we refer to this scenario as “No False Small”.

Using the definition of conditional probability and given that the
distribution of $X$ is fixed, (13) implies that the following conditions hold
true for all $\sigma\geq 0$:

$\displaystyle P_{x_{M},x_{M}}(\sigma)$ $\displaystyle=\mathbb{P}(X=x_{M})$
(14a) $\displaystyle\mathbb{P}(X=x_{m}\mid Y_{\sigma}=x_{M})$
$\displaystyle=\frac{\mathbb{P}(X=x_{m})}{\mathbb{P}(Y_{\sigma}=x_{M})}$ (14b)
$\displaystyle\mathbb{P}(Y_{\sigma}=x_{m})$
$\displaystyle=P_{x_{m},x_{m}}(\sigma)\leq\mathbb{P}(X=x_{m}).$ (14c)

Thus, job-size predictions are larger than their exact counterparts. This is
the desired scenario because underprediction is technically unacceptable in
practice as discussed in [4]. Also, note that this scenario is different from
the one considered in Theorem 1 because (13) rules out the case where $X$ and
$Y_{0}$ are independent. This may be interpreted as follows: when a job
arrives, it immediately reveals some of its features, e.g., its parameters,
which provide some information about its size.

Within this setting, the following result provides the conditions under which
testing improves performance.

######  Theorem 2.

Let (13) hold. Then,

$\lim_{N\to\infty}\lim_{\sigma\downarrow 0}\frac{{\rm d}}{{\rm
d}\sigma}D_{C_{N}}^{(N)}(\sigma)=f^{\prime}(0)-P_{x_{m},x_{m}}^{\prime}(0)\frac{\lambda\mathbb{E}[\sqrt{\mathbb{E}[X^{2}|Y_{0}]}]}{1-\lambda\mathbb{E}[X]}\\\
\times\left(\frac{\mathbb{E}[X^{2}\mid
Y_{0}=x_{M}]+x_{m}^{2}}{2\sqrt{\mathbb{E}[X^{2}\mid
Y_{0}=x_{M}]}}-x_{m}\right).$ (15)

In particular, for all $N$ large enough, $\sigma\mapsto
D_{C_{N}}^{(N)}(\sigma)$ is decreasing on a right neighbourhood of zero if

$\displaystyle
P_{x_{m},x_{m}}^{\prime}(0)\,\frac{\lambda}{2}\frac{(\sqrt{\mathbb{E}[X^{2}]}-x_{m})^{2}}{1-\lambda\mathbb{E}[X]}\geq
f^{\prime}(0).$ (16)

Thus, job-size testing is effective in heavy traffic
($\lambda\mathbb{E}[X]\uparrow 1$) or if job sizes are highly variable, as in
this case $\sqrt{\mathbb{E}[X^{2}]}\gg x_{m}$. In contrast, it is ineffective
in light traffic ($\lambda\downarrow 0$) or if $P_{x_{m},x_{m}}(0)$ is close
to its asymptotic limit $\mathbb{P}(X=x_{m})$. In the latter case, we can
expect $P^{\prime}(0)\approx 0$ because $P(t)$ is non-decreasing, and
therefore (15) is not satisfied.

##  4 Heavy Tailed Distributions

Complementary to the approach in the previous section, we now keep the system
size $N$ constant and analyze job testing in a different limiting regime where
the job size variability grows large (see below). Towards this purpose, we
investigate under which choices of $\sigma$ it is possible to make the
efficiency measure $\mathcal{E}(\sigma)$ (see (6)) less than one or
arbitrarily small while keeping $N$ constant.

The approach considered here is orthogonal to the one followed in Section 3.
To quickly summarize the results in this section, our findings show that job
size testing is _very_ effective in presence of heavy-tailed job size
distributions provided that testing times are properly chosen.

###  4.1 Limiting Regime

We consider a limiting regime where $X$ satisfies (1) with $0<\beta<1$ and
$x_{M}\to\infty$. This regime limits the investigation to job size
distributions where the first two moments and the coefficient of variation of
$X$ grow to infinity.

Several works in the literature have investigated regimes where the
coefficient of variation of $X$ grows to infinity, e.g., [23, 33, 34]. In
fact, it is well-known that the introduction of size-based routing and related
techniques were motivated by the observation that job sizes with heavy-tailed
distributions are common in empirical studies of computer systems [24, 25,
26].

###  4.2 Efficiency of Job-Size Testing

Let

$\displaystyle
R^{\downarrow}:=\frac{\lambda}{2}\frac{\mathbb{E}[X]^{2}}{1-\lambda\mathbb{E}[X]}.$
(17)

The next proposition, proven in the appendix, shows that $R^{\downarrow}$ is a
lower bound on the mean waiting time at the servers. This fact does not play a
role in the proof of Theorem 3 below but will ensure that the response time at
the scheduler is smaller than the mean delay at the scheduler, which may be
desired from a practical point of view. The key property on the structure of
$R^{\downarrow}$ will be that it is of the order of $\mathbb{E}[X]$, provided
that the network load $\lambda\mathbb{E}[X]$ is constant.

######  Proposition 2.

$R_{c}^{(N)}(\sigma)\geq R^{\downarrow}$.

A straightforward consequence of Proposition 2 is the following lower bound on
$\mathcal{E}(\sigma)$.

######  Corollary 1.

For all $\sigma$,
$\mathcal{E}(\sigma)\geq\frac{\mathbb{E}[X]^{2}}{\mathbb{E}[X^{2}]}$.

If $\beta>2$, i.e., if $X$ is not variable enough, then
$\mathbb{E}[X]^{2}/\mathbb{E}[X^{2}]\to 1$ as $x_{M}\to\infty$, and thus job-
size testing is clearly inefficient.

Now, we consider the more interesting case where job sizes have increased
variability. The idea is to use $R^{\downarrow}$ as an handle on the response
time at the scheduler. If $\sigma$ is designed such that
$\frac{\sigma}{1-\Lambda\sigma}=\frac{R^{\downarrow}}{\gamma}$, for some
constant $\gamma>0$, then the following proposition basically shows that
$D_{c}^{(N)}$ scales at most as $R^{\downarrow}$ provided that $x_{M}$ and $N$
are sufficiently large; see the Appendix for a proof.

######  Proposition 3.

Let $\rho\in(0,1)$ and $\gamma>0$ be constants independent of $x_{M}$. Let
also

$\sigma^{*}=\left(\lambda N+{\gamma/R^{\downarrow}}\right)^{-1}$ (18)

and

$c:=\left\\{\begin{array}[]{ll}\max\\{Nc^{\star},1\\},&{\rm
if~{}}N(1-\rho)>1\\\ \max\\{Nc^{\star},N(1-\rho)-N\rho\,\phi(x_{M})\\},&{\rm
otherwise}\end{array}\right.$ (19)

where $\phi(x_{M})$ is such that
$\lim_{x_{M}\to\infty}\phi(x_{M})x_{M}^{\theta}=1$, for some
$\theta\in(0,\beta)$, and

$c^{\star}:=(1-\rho)\frac{\sqrt{\mathbb{E}[X^{2}\mid
Y_{\sigma^{\star}}=x_{m}]}}{\mathbb{E}[\sqrt{\mathbb{E}[X^{2}\mid
Y_{\sigma^{\star}}]}]}\mathbb{P}(Y_{\sigma^{\star}}=x_{m})\\\
+\lambda\,\mathbb{E}[X\mid
Y_{\sigma^{\star}}=x_{m}]\mathbb{P}(Y_{\sigma^{\star}}=x_{m}).$

Assume that

  * i)

$P_{x_{M},x_{m}}(t)=O(t^{-\eta_{m}})$ with $\eta_{m}>\frac{2}{1-\beta}$ and
$P_{x_{m},x_{M}}(t)=O(t^{-\eta_{M}})$ with $\eta_{M}>\frac{\beta}{1-\beta}$

  * ii)

the job size distribution satisfies (1) with $\beta<1$;

  * iii)

$\lambda\mathbb{E}[X]=\rho$.

Then, if $N(1-\rho)>1$

$\displaystyle\lim_{x_{M}\to\infty}\frac{D_{c}^{(N)}(\sigma^{*})}{R^{\downarrow}}$
$\displaystyle=\frac{1}{\gamma}+\frac{N(1-\rho)}{N(1-\rho)-1},$ (20)

otherwise

$\displaystyle\lim_{x_{M}\to\infty}\frac{D_{c}^{(N)}(\sigma^{*})}{x_{M}^{\theta}R^{\downarrow}}$
$\displaystyle=(1-\rho)\frac{N-1}{N\rho^{2}}.$ (21)

Now, to investigate the efficiency ratio $\mathcal{E}(\sigma)$, it is enough
to compare $\min_{c\in[0,N]}D_{c}^{(N)}(0)$ with respect to $R^{\downarrow}$,
which is easier. Before doing that, let us elaborate on the assumptions in
Proposition 3:

  * •

The expressions in (18) and (19) are design choices and serve to have a handle
on the mean delay at the scheduler and at the servers. Note that (2) boils
down to $R^{\downarrow}/\gamma$, which is smaller than
$R_{c}^{(N)}(\sigma^{*})$ (if $\gamma\geq 1$) in view of Proposition 2, and
that the expression of $c$ in (19) somewhat minimizes $c\mapsto
R_{c}^{(N)}(\sigma^{*})$.

  * •

Item i) is technical and states that the probability of having a long resp.
short but predicted-short resp. predicted-long job decays sufficiently fast
with the testing time; recall that $P_{x,y}(t)\to 0$ as $t\to\infty$ by
Assumption 1, provided that $x\neq y$. In the “No False Small” scenario
discussed in Section 3.3, this condition is clearly satisfied.

  * •

Item ii) limits the investigation to job size distributions with a large
coefficient of variation, which is in agreement with what is observed in
practice [23].

  * •

Item iii) serves to fix the network load to a desired level $\rho$.

Within the setting of Proposition 3, we can show that the efficiency ratio at
the testing time $\sigma^{*}$ can be arbitrarily small. This is stated
precisely in the following result.

######  Theorem 3.

Let the assumptions of Proposition 3 hold and suppose also that one of the
following conditions holds true:

  * i)

$X$ and $Y_{0}$ are independent,

  * ii)

(13) holds and $P_{x_{m},x_{m}}(0)\leq 1-O(x_{M}^{-\theta})$, for any
$\theta\in(0,\beta)$.

Then,

$\displaystyle\lim_{x_{M}\to\infty}\mathcal{E}(\sigma^{*})=0.$ (22)

Theorem 3 analyzes the efficiency index (6) in the scenarios discussed in
Sections 3.2 and 3.3. In the “No False Small” scenario, i.e., case ii), the
desired property (22) holds under the additional condition that
$P_{x_{m},x_{m}}(0)$ is sufficiently small. This is somewhat necessary: if
$P_{x_{m},x_{m}}(0)$ would be too close to one, which can be expected because
$P_{x_{m},x_{m}}(0)$ can be arbitrarily close to $\mathbb{P}(X=x_{m})$ and
$\mathbb{P}(X=x_{m})=1-\alpha x_{M}^{-\beta}\approx 1$ if $x_{M}$ is large,
then there would be no margin for job testing to further gather useful
information on job sizes. In this case, the extra cost induced by $\sigma^{*}$
does not pay off.

If $X$ and $Y_{0}$ are independent and $N(1-\rho)>1$, in the proof of Theorem
3 we actually show that
$\lim_{x_{M}\to\infty}\mathcal{E}(\sigma^{*})x_{M}^{\theta}=0$ for any
$\theta\in(0,\beta)$. which is slightly stronger than (22).

##  5 Numerical Results

We now investigate the efficiency ratio $\mathcal{E}$ numerically with respect
to realistic job size distributions from neuroscience workflows drawn from
[9]. Here, jobs are divided into two categories, short and long, with the mean
execution time of small jobs of around 25 minutes (i.e., $x_{m}=25$) and that
of large jobs of around 9 hours (i.e., $x_{M}=540$). Here, three cases are
distinguished:

  1. 1.

equal number of small and large jobs ($\mathbb{P}(X=x_{m})=0.5$,
$\mathbb{E}[X]=282.5$),

  2. 2.

workload with 80% large jobs ($\mathbb{P}(X=x_{m})=0.2$, $\mathbb{E}[X]=437$),
and

  3. 3.

workload with 20% large jobs ($\mathbb{P}(X=x_{m})=0.8$, $\mathbb{E}[X]=128$).

In addition, as observed on the ACCRE cluster (the Vanderbilt high-performance
computing cluster), job submissions follow a Poisson process with mean inter-
arrival times of 8 minutes [9].

To completely specify our model, we need to fix a form for the profile matrix
$\sigma\mapsto P_{\sigma}$ as a function of the testing time $\sigma$. Towards
this purpose, we distinguish the “Independent Predictions for Zero Testing
Time” scenario discussed in Section 3.2 and “No False Small” scenario
discussed in Section 3.3. For the former, we assume that

$\displaystyle P_{x_{m},x_{m}}(\sigma)$
$\displaystyle=(1-e^{-a\sigma})(p-P_{x_{m},x_{m}}(0))+P_{x_{m},x_{m}}(0)$
$\displaystyle P_{x_{M},x_{M}}(\sigma)$
$\displaystyle=(1-e^{-b\sigma})(1-p-P_{x_{M},x_{M}}(0))+P_{x_{M},x_{M}}(0)$
$\displaystyle P_{x_{m},x_{M}}(\sigma)$
$\displaystyle=p-P_{x_{m},x_{m}}(\sigma)$ $\displaystyle
P_{x_{M},x_{m}}(\sigma)$ $\displaystyle=1-p-P_{x_{M},x_{M}}(\sigma)$

and for the latter, we assume that

$\displaystyle P_{x_{m},x_{m}}(\sigma)$
$\displaystyle=(1-e^{-a\sigma})(p-P_{x_{m},x_{m}}(0))+P_{x_{m},x_{m}}(0)$
$\displaystyle P_{x_{M},x_{M}}(\sigma)$ $\displaystyle=1-p$ $\displaystyle
P_{x_{m},x_{M}}(\sigma)$ $\displaystyle=p-P_{x_{m},x_{m}}(\sigma)$
$\displaystyle P_{x_{M},x_{m}}(\sigma)$ $\displaystyle=0$

where $p:=\mathbb{P}(X=x_{m})$. These structures make sense from a practical
point of view because they agree with the law of diminishing returns. In
addition, they satisfy Assumption 1 and the assumption in Theorem 3. The
parameters $a$ and $b$ are interpreted as how fast the predictions of short
and long jobs become accurate, respectively. It should be intuitive that in
practice it is easier to estimate short rather than long jobs. Thus, in our
parameter setting, we have used $b=1$ and $a=3$; within higher values of $a$,
e.g., $a=10$, we have noticed no essential change in the numerical results
that follow.

Within this setting, Figure 3 plots the resulting efficiency measure
$\mathcal{E}$, see (6), for different values of the network load $\rho$ and
system size $N$. The vertical lines denote the heuristic testing time choice
given in (18) used in Theorem 3, where we have set $\gamma=10$ for all plots.
The blue resp. red lines refer to a system with $N=10$ resp. $N=100$ servers

Figure 3: Plots of the efficiency measure (6) with respect to job-size
distributions from neuroscience applications [9], where $x_{m}=25$ and
$x_{M}=540$. The vertical lines denote the heuristic testing time choice given
in (18). Blue resp. red lines refer to a system with $N=10$ resp. $N=100$
servers.

In all cases, it turns out that it is possible to find a testing time that
makes $\mathcal{E}$ strictly smaller than one and our heuristic testing time
choice $\sigma^{*}$ provides a near-optimal performance in all cases. In
addition, $\mathcal{E}$ is always decreasing on a right neighbourhood of zero,
which means that even a cheap job inspection pays off to reduce the mean
waiting time. From the figure, we also notice that the gains are more
pronounced when there are many small jobs and fewer long jobs (the plots on
the leftmost column), which is the most frequent case in practice.

##  6 Conclusion and Perspectives

We have proposed and analyzed a performance model for load balancing with job-
size testing. The proposed model generalizes existing approaches on scheduling
with testing, which only consider static settings with a finite number of
jobs. Our main conclusion is that whether job-size testing brings a
performance degradation or improvement strongly depends on the traffic
conditions, system size and the coefficient of variation of job sizes. We have
made explicit such conditions and these may help the system manager to design
efficient testing policies that possibly adapt to changes in, e.g., the
traffic demand.

Let us outline some future perspectives from this work. First, a natural
generalization of the proposed framework considers the case where job sizes
follow a general probability distribution function. In this case, the joint
probability mass function of $(X,Y_{\sigma})$ is captured by
$P=[P_{x,y}(\sigma),x\in\mathbb{R}_{+},y\in\\{x_{m},x_{M}\\}]$ where
$P_{x,y}(\sigma):=\mathbb{P}(X\leq x\cap Y_{\sigma}=y)$ and one can check that
the expressions of $D_{c}^{(N)}(\sigma)$ and $\mathcal{E}(\sigma)$ given in
(5) and (6) respectively are still valid as is. In addition, Propositions 1
and 2, together with Corollary 1, are also valid as their proofs do not use
the particular structure of two-point distributions. Unfortunately, this
approach comes with the technical difficulty that in practice the curve
$\sigma\to P(\sigma)$ is difficult to construct robustly, especially if $X$
admits a density function. Even if $X$ would be discrete, this would require
the identification of $2|\mathrm{supp}(X)|$ functions of $\sigma$, but this
may be feasible only if the support of $X$ is small; hence, the choice in this
paper of a two-point distribution for $X$.

A further generalization, which may also serve as a workaround for the
previous technical difficulty, considers a multiclass setting where jobs come
from different sources. One may interpret jobs from a given class as jobs
issued by the same user or application. Job size distributions are different
across classes, though job sizes from a given source take at most two values
(short or long). In this respect, one could argue that the size of a _random_
job is general enough, provided that the number of classes is large enough.
Here, one may also consider class-dependent testing times rather than one for
all classes. We believe that many of the insights found in this paper hold
even within such generalization, though a deeper investigation is left as
future work.

## References

  * [1] R. Levi, T. Magnanti, and Y. Shaposhnik, “Scheduling with testing,” _Management Science_ , vol. 65, no. 2, pp. 776–793, 2019.
  * [2] C. Dürr, T. Erlebach, N. Megow, and J. Meißner, “An adversarial model for scheduling with testing,” _Algorithmica_ , vol. 82, no. 12, pp. 3630–3675, 2020.
  * [3] S. Albers and A. Eckl, “Scheduling with testing on multiple identical parallel machines,” in _Algorithms and Data Structures: 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings_. Berlin, Heidelberg: Springer-Verlag, 2021, p. 29–42.
  * [4] D. Tsafrir, Y. Etsion, and D. G. Feitelson, “Backfilling using system-generated predictions rather than user runtime estimates,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 18, no. 6, pp. 789–803, 2007.
  * [5] M. Naghshnejad and M. Singhal, “A hybrid scheduling platform: a runtime prediction reliability aware scheduling platform to improve hpc scheduling performance,” _The Journal of Supercomputing_ , vol. 76, 2020.
  * [6] C. Witt, M. Bux, W. Gusew, and U. Leser, “Predictive performance modeling for distributed batch processing using black box monitoring and machine learning,” _Information Systems_ , vol. 82, pp. 33–52, 2019.
  * [7] Y. Fan, P. Rich, W. E. Allcock, M. E. Papka, and Z. Lan, “Trade-off between prediction accuracy and underestimation rate in job runtime estimates,” in _2017 IEEE International Conference on Cluster Computing (CLUSTER)_ , 2017, pp. 530–540.
  * [8] C. Bailey Lee, Y. Schwartzman, J. Hardy, and A. Snavely, “Are user runtime estimates inherently inaccurate?” in _Job Scheduling Strategies for Parallel Processing_ , D. G. Feitelson, L. Rudolph, and U. Schwiegelshohn, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005, pp. 253–263.
  * [9] A. Gainaru, H. Sun, G. Aupy, Y. Huo, B. A. Landman, and P. Raghavan, “On-the-fly scheduling versus reservation-based scheduling for unpredictable workflows,” _The International Journal of High Performance Computing Applications_ , vol. 33, no. 6, pp. 1140–1158, 2019.
  * [10] G. R. Nudd, D. J. Kerbyson, E. Papaefstathiou, S. C. Perry, J. S. Harper, and D. V. Wilcox, “Pace—a toolset for the performance prediction of parallel and distributed systems,” _The International Journal of High Performance Computing Applications_ , vol. 14, no. 3, pp. 228–251, 2000.
  * [11] J. M. Cardoso, J. G. F. Coutinho, and P. C. Diniz, “Chapter 5 - source code transformations and optimizations,” in _Embedded Computing for High Performance_ , J. M. Cardoso, J. G. F. Coutinho, and P. C. Diniz, Eds. Boston: Morgan Kaufmann, 2017, pp. 137–183.
  * [12] C. Dürr, T. Erlebach, N. Megow, and J. Meißner, “Scheduling with explorable uncertainty,” in _9th Innovations in Theoretical Computer Science Conference (ITCS 2018)_ , ser. Leibniz International Proceedings in Informatics (LIPIcs), A. R. Karlin, Ed., vol. 94. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018, pp. 30:1–30:14.
  * [13] Y. Wiseman, K. Schwan, and P. Widener, “Efficient end to end data exchange using configurable compression,” in _24th International Conference on Distributed Computing Systems, 2004. Proceedings._ , 2004, pp. 228–235.
  * [14] S. Alizamir, F. de Véricourt, and P. Sun, “Diagnostic accuracy under congestion,” _Management Science_ , vol. 59, no. 1, pp. 157–171, 2013.
  * [15] A. F. Mills, N. T. Argon, and S. Ziya, “Resource-based patient prioritization in mass-casualty incidents,” _Manufacturing & Service Operations Management_, vol. 15, no. 3, pp. 361–377, 2013.
  * [16] S. Albers and A. Eckl, “Explorable uncertainty in scheduling with non-uniform testing times,” in _Approximation and Online Algorithms: 18th International Workshop, WAOA 2020, Virtual Event, September 9–10, 2020, Revised Selected Papers_. Berlin, Heidelberg: Springer-Verlag, 2020, p. 127–142.
  * [17] F. Dufossé, C. Dürr, N. Nadal, D. Trystram, and Óscar C. Vásquez, “Scheduling with a processing time oracle,” _Applied Mathematical Modelling_ , vol. 104, pp. 701–720, 2022.
  * [18] M. V. der Boor, S. C. Borst, J. S. H. Van Leeuwaarden, and D. Mukherjee, “Scalable load balancing in networked systems: A survey of recent advances,” _SIAM Review_ , vol. 64, no. 3, pp. 554–622, 2022.
  * [19] M. Harchol-Balter, “Task assignment with unknown duration,” _J. ACM_ , vol. 49, no. 2, pp. 260–288, 2002.
  * [20] M. Harchol-Balter, M. E. Crovella, and C. D. Murta, “On choosing a task assignment policy for a distributed server system,” _Journal of Parallel and Distributed Computing_ , vol. 59, no. 2, pp. 204 – 228, 1999.
  * [21] E. Bachmat and H. Sarfati, “Analysis of sita policies,” _Perform. Eval._ , vol. 67, no. 2, pp. 102–120, Feb. 2010.
  * [22] B. Zhang and B. Zwart, “Steady-state analysis for multiserver queues under size interval task assignment in the quality-driven regime,” _Mathematics of Operations Research_ , vol. 38, no. 3, pp. 504–525, 2013\.
  * [23] M. Harchol-Balter, A. Scheller-Wolf, and A. R. Young, “Surprising results on task assignment in server farms with high-variability workloads,” in _Proceedings of the Eleventh International Joint Conference on Measurement and Modeling of Computer Systems_ , ser. SIGMETRICS ’09. New York, NY, USA: ACM, 2009, pp. 287–298.
  * [24] D. G. Feitelson, _Workload Modeling for Computer Systems Performance Evaluation_ , 1st ed. USA: Cambridge University Press, 2015.
  * [25] M. Harchol-Balter and A. B. Downey, “Exploiting process lifetime distributions for dynamic load balancing,” in _Proceedings of the 1996 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems_ , ser. SIGMETRICS ’96. New York, NY, USA: ACM, 1996, p. 13–24.
  * [26] M. E. Crovella, M. S. Taqqu, and A. Bestavros, “A practical guide to heavy tails,” R. J. Adler, R. E. Feldman, and M. S. Taqqu, Eds. Cambridge, MA, USA: Birkhauser Boston Inc., 1998, ch. Heavy-tailed Probability Distributions in the World Wide Web, pp. 3–25.
  * [27] W. Chen, K. Ye, Y. Wang, G. Xu, and C.-Z. Xu, “How does the workload look like in production cloud? analysis and clustering of workloads on alibaba cluster trace,” in _2018 IEEE 24th Int. Conf. on Parallel and Distributed Systems (ICPADS)_ , 2018, pp. 102–109.
  * [28] D. Zivanovic, M. Pavlovic, M. Radulovic, H. Shin, J. Son, S. A. Mckee, P. M. Carpenter, P. Radojković, and E. Ayguadé, “Main memory in hpc: Do we need more or could we live with less?” _ACM Trans. Archit. Code Optim._ , vol. 14, no. 1, mar 2017.
  * [29] S. Di, D. Kondo, and W. Cirne, “Characterization and comparison of cloud versus grid workloads,” in _2012 IEEE International Conference on Cluster Computing_ , 2012, pp. 230–238.
  * [30] L. D. Briceno, B. Khemka, H. J. Siegel, A. A. Maciejewski, C. Groër, G. Koenig, G. Okonski, and S. Poole, “Time utility functions for modeling and evaluating resource allocations in a heterogeneous computing system,” in _2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum_ , 2011, pp. 7–19.
  * [31] S. Asmussen and S. Asmussen, _Applied Probability and Queues_ , ser. Applications of mathematics : stochastic modelling and applied probability. Springer, 2003.
  * [32] J. Anselmi, “Combining size-based load balancing with round-robin for scalable low latency,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 31, no. 4, pp. 886–896, 2020.
  * [33] M. El-Taha and B. Maddah, “Allocation of service time in a multiserver system,” _Management Science_ , vol. 52, no. 4, pp. 623–637, 2006.
  * [34] A. Scheller-Wolf and K. Sigman, “Delay moments for fifo gi/gi/s queues,” _Queueing Syst. Theory Appl._ , vol. 25, no. 1/4, p. 77–95, jan 1997.

##  Appendix A Proofs

###  A.1 Proof of Proposition 1

First,

$\displaystyle\min_{c\in[0,N]}R_{c}^{(N)}(\sigma)\leq\min_{C\in\\{1,\ldots,N\\}}R_{C}^{(N)}(\sigma)$
(23)

and when $C$ is an integer, (4) boils down to

$R_{C}^{(N)}(\sigma)=\frac{\Lambda}{2}\frac{\mathbb{P}(Y_{\sigma}=x_{m})^{2}\,\mathbb{E}[X^{2}\mid
Y_{\sigma}=x_{m}]}{C-\Lambda\,\mathbb{P}(Y_{\sigma}=x_{m})\,\mathbb{E}[X\mid
Y_{\sigma}=x_{m}]}\\\
+\frac{\Lambda}{2}\frac{\mathbb{P}(Y_{\sigma}=x_{M})^{2}\,\mathbb{E}[X^{2}\mid
Y_{\sigma}=x_{M}]}{N-C-\Lambda\,\mathbb{P}(Y_{\sigma}=x_{M})\,\mathbb{E}[X\mid
Y_{\sigma}=x_{M}]}$ (24)

provided that $\Lambda\,\mathbb{P}(Y_{\sigma}=x_{m})\,\mathbb{E}[X\mid
Y_{\sigma}=x_{m}]<C$ and
$\Lambda\,\mathbb{P}(Y_{\sigma}=x_{M})\,\mathbb{E}[X\mid
Y_{\sigma}=x_{M}]<N-C$, and infinity otherwise. For any $\sigma$ and $N$, the
RHS term in (24) is strictly convex in $C$ (provided that $C$ is seen as a
real number) and it is not difficult to see, by differentiation, that

$\displaystyle\min_{C\in\\{1,\ldots,N\\}}R_{C}^{(N)}(\sigma)=\min_{C\in\\{\lfloor
c^{\star}N\rfloor,\lfloor c^{\star}N\rfloor+1\\}}R_{C}^{(N)}(\sigma)$ (25)

where
$c^{\star}(\sigma):=(1-\lambda\mathbb{P}(Y_{\sigma}=x_{M})\,\mathbb{E}[X\mid
Y_{\sigma}=x_{M}])\,\gamma_{m}^{*}+\lambda\mathbb{P}(Y_{\sigma}=x_{m})\,\mathbb{E}[X\mid
Y_{\sigma}=x_{m}]\gamma_{M}^{*}$, with

$\displaystyle\gamma_{k}^{*}:=\gamma_{k}^{*}(\sigma):=\frac{\mathbb{P}(Y_{\sigma}=x_{k})\sqrt{\mathbb{E}[X^{2}\mid
Y_{\sigma}=x_{k}]}}{\mathbb{E}[\sqrt{\mathbb{E}[X^{2}\mid Y_{\sigma}]}]},$
(26)

$k=m,M$. Substituting $\gamma_{M}^{*}=1-\gamma_{m}^{*}$ in
$c^{\star}(\sigma)$, it can be written as

$\displaystyle
c^{\star}(\sigma)=\gamma_{m}^{*}(1-\lambda\mathbb{E}[X])+\lambda\mathbb{P}(Y_{\sigma}=x_{m})\,\mathbb{E}[X\mid
Y_{\sigma}=x_{m}]$ (27)

and we notice that $c^{\star}(0)=c^{*}$ (see (8)). Now, let $(C_{N})_{N}$ be a
sequence in the form given in (7) and let also
$\Delta_{k}:=\mathbb{I}_{\\{k=m\\}}-\mathbb{I}_{\\{k=M\\}}$. We obtain

$\displaystyle\min_{C\in\\{\lfloor c^{\star}N\rfloor,\lfloor
c^{\star}N\rfloor+1\\}}R_{C}^{(N)}(\sigma)\leq R_{C_{N}}^{(N)}(\sigma)$
$\displaystyle=\frac{\lambda}{2}\frac{\mathbb{P}(Y_{\sigma}=x_{m})^{2}\,\mathbb{E}[X^{2}\mid
Y_{\sigma}=x_{m}]}{c^{\star}+\frac{h_{N}}{N}-\lambda\,\mathbb{P}(Y_{\sigma}=x_{m})\,\mathbb{E}[X\mid
Y_{\sigma}=x_{m}]}$
$\displaystyle\quad+\frac{\lambda}{2}\frac{\mathbb{P}(Y_{\sigma}=x_{M})^{2}\,\mathbb{E}[X^{2}\mid
Y_{\sigma}=x_{M}]}{1-c^{\star}-\frac{h_{N}}{N}-\lambda\,\mathbb{P}(Y_{\sigma}=x_{M})\,\mathbb{E}[X\mid
Y_{\sigma}=x_{M}]}$
$\displaystyle=\sum_{k=m,M}\frac{\lambda}{2\gamma_{k}^{*}}\frac{\mathbb{P}(Y_{\sigma}=x_{k})^{2}\,\mathbb{E}[X^{2}\mid
Y_{\sigma}=x_{k}]}{1+\frac{h_{N}}{\gamma_{k}^{*}N}\Delta_{k}-\lambda\mathbb{E}[X]}$
(28) $\displaystyle=\frac{\lambda}{2}\mathbb{E}[\sqrt{\mathbb{E}[X^{2}\mid
Y_{\sigma}]}]\sum_{k=m,M}\frac{\mathbb{P}(Y_{\sigma}=x_{k})\sqrt{\mathbb{E}[X^{2}\mid
Y_{\sigma}=x_{k}]}}{1+\frac{h_{N}}{\gamma_{k}^{*}N}\Delta_{k}-\lambda\mathbb{E}[X]}$
(29)
$\displaystyle\xrightarrow[N\to\infty]{}\,\frac{\lambda}{2}\frac{\mathbb{E}[\sqrt{\mathbb{E}[X^{2}\mid
Y_{0}]}]^{2}}{1-\lambda\mathbb{E}[X]}.$ (30)

In (28) we have used the law of total expectation in (29) we have used the
definition of conditional expectation, and in (30) we have used that both
$h_{N}/N$ and $\sigma$ converge to zero as $N\to\infty$ (recall (9)).

To conclude the proof, it is enough to show that there exists a lower bound on
$\min_{c\in[0,N]}R_{c}^{(N)}(\sigma)$ that matches (30) in the limit. This can
be easily achieved by ignoring the
$\frac{\Lambda}{2}\frac{p_{z}^{2}\mathbb{E}[Z^{2}]}{1-\Lambda
p_{z}\,\mathbb{E}[Z]}$ term in (4) and using that $p_{m}\geq\frac{c-1}{c}$ and
$p_{M}\geq\frac{N-c-2}{N-c}$.

###  A.2 Proof of Theorem 1

For simplicity, we assume that $C_{N}\in\mathbb{N}$ for all $N$. This slightly
simplifies the proof because the term
$\frac{p_{z}^{2}\mathbb{E}[Z^{2}]}{1-\Lambda p_{z}\,\mathbb{E}[Z]}$ in (4)
disappears; note that this term is of the order of $1/N$ if $C_{N}$ is not an
integer. For $x\in\\{x_{m},x_{M}\\}$, let
$\Phi_{x}(\sigma):=\mathbb{P}(X=x\mid Y_{\sigma}=x)$. Let also
$T:=T(\sigma):=\mathbb{E}\left[\sqrt{\mathbb{E}[X^{2}\mid Y_{\sigma}]}\right]$
and, for $k=m,M$, $T_{k}:=T_{k}(\sigma):=\sqrt{\mathbb{E}[X^{2}\mid
Y_{\sigma}=x_{k}]}$. First,

$\displaystyle\lim_{\sigma\downarrow 0}\frac{{\rm d}}{{\rm
d}\sigma}D_{C_{N}}^{(N)}(\sigma)$
$\displaystyle=f^{\prime}(0)+\lim_{\sigma\downarrow 0}\frac{{\rm d}}{{\rm
d}\sigma}R_{C_{N}}^{(N)}(\sigma).$ (31)

Then, using (29) and since $\frac{h_{N}}{\gamma_{k}^{*}N}$ does not depend on
$\sigma$,

$\displaystyle\lim_{N\to\infty}\lim_{\sigma\downarrow 0}\frac{{\rm d}}{{\rm
d}\sigma}R_{C_{N}}^{(N)}(\sigma)$
$\displaystyle=\frac{\lambda}{2}\lim_{N\to\infty}\lim_{\sigma\downarrow
0}\frac{{\rm d}}{{\rm
d}\sigma}\sum_{k=m,M}\frac{\mathbb{P}(Y_{\sigma}=x_{k})T_{k}T{}}{1+\frac{h_{N}}{\gamma_{k}^{*}N}\Delta_{k}-\lambda\mathbb{E}[X]}$
(32a) $\displaystyle=\frac{\lambda}{2}\lim_{\sigma\downarrow 0}\frac{{\rm
d}}{{\rm
d}\sigma}\sum_{k=m,M}\frac{\mathbb{P}(Y_{\sigma}=x_{k})T_{k}T{}}{1-\lambda\mathbb{E}[X]}$
(32b) $\displaystyle=\frac{\lambda}{2}\lim_{\sigma\downarrow 0}\frac{{\rm
d}}{{\rm
d}\sigma}\frac{T^{2}}{1-\lambda\mathbb{E}[X]}=\lambda\lim_{\sigma\downarrow
0}\frac{TT^{\prime}}{1-\lambda\mathbb{E}[X]}.$ (32c)

Since $X$ and $Y_{0}$ are independent and identically distributed,
$T_{k}(0)=T(0)=\sqrt{\mathbb{E}[X^{2}]}$ and we obtain

$\displaystyle\lim_{\sigma\downarrow 0}T^{\prime}=\lim_{\sigma\downarrow
0}\sum_{k=m,M}\left(T_{k}\frac{{\rm d}\mathbb{P}(Y_{\sigma}=x_{k})}{{\rm
d}\sigma}+\mathbb{P}(Y_{\sigma}=x_{k})T_{k}^{\prime}\right)$
$\displaystyle=\lim_{\sigma\downarrow
0}\sum_{k=m,M}\left(\sqrt{\mathbb{E}[X^{2}]}\frac{{\rm
d}\mathbb{P}(Y_{\sigma}=x_{k})}{{\rm
d}\sigma}+\mathbb{P}(Y_{\sigma}=x_{k})T_{k}^{\prime}\right)$ (33)
$\displaystyle=\sum_{k=m,M}\mathbb{P}(X=x_{k})\lim_{\sigma\downarrow
0}T_{k}^{\prime}$ (34)

with

$\displaystyle 2\sqrt{\mathbb{E}[X^{2}]}\lim_{\sigma\downarrow
0}T_{m}^{\prime}=\lim_{\sigma\downarrow 0}\frac{{\rm d}\mathbb{E}[X^{2}\mid
Y_{\sigma}=x_{m}]}{{\rm d}\sigma}$
$\displaystyle=\sum_{k=m,M}x_{k}^{2}\lim_{\sigma\downarrow 0}\frac{{\rm
d}}{{\rm d}\sigma}\mathbb{P}(X=x_{k}\mid Y_{\sigma}=x_{m})$
$\displaystyle=\,(x_{m}^{2}-x_{M}^{2})\Phi_{x_{m}}^{\prime}(0)$

and, similarly

$\displaystyle 2\sqrt{\mathbb{E}[X^{2}]}\lim_{\sigma\downarrow
0}T_{M}^{\prime}=$
$\displaystyle(x_{M}^{2}-x_{m}^{2})\Phi_{x_{M}}^{\prime}(0).$

Thus, substituting back in (33), as $\sigma\downarrow 0$, $T^{\prime}$
converges to

$\displaystyle\,(x_{M}^{2}-x_{m}^{2})\frac{\mathbb{P}(X=x_{M})\Phi_{x_{M}}^{\prime}(0)-\mathbb{P}(X=x_{m})\Phi_{x_{m}}^{\prime}(0)}{2\sqrt{\mathbb{E}[X^{2}]}}.$
(35)

Since $\sum_{x,y}P_{x,y}^{\prime}=0$, and since $X$ and $Y_{0}$ are
independent and equal in distribution, for the conditional derivatives we
obtain

$\displaystyle\mathbb{P}(X=x_{m})\Phi_{x_{m}}^{\prime}(0)=P_{x_{m},x_{m}}^{\prime}(0)$
$\displaystyle\qquad\qquad-\mathbb{P}(X=x_{m})(P_{x_{m},x_{m}}^{\prime}(0)+P_{x_{M},x_{m}}^{\prime}(0))$
(36a)
$\displaystyle\mathbb{P}(X=x_{M})\Phi_{x_{M}}^{\prime}(0)=P_{x_{M},x_{M}}^{\prime}(0)$
$\displaystyle\qquad\qquad+\mathbb{P}(X=x_{M})(P_{x_{m},x_{m}}^{\prime}(0)+P_{x_{M},x_{m}}^{\prime}(0)).$
(36b)

Taking their difference, we obtain

$\displaystyle\mathbb{P}(X=x_{m})\Phi_{x_{m}}^{\prime}(0)-\mathbb{P}(X=x_{M})\Phi_{x_{M}}^{\prime}(0)$
$\displaystyle=P_{x_{m},x_{m}}^{\prime}(0)-P_{x_{M},x_{M}}^{\prime}(0)-(P_{x_{m},x_{m}}^{\prime}(0)+P_{x_{M},x_{m}}^{\prime}(0))$
$\displaystyle=P_{x_{m},x_{m}}^{\prime}(0)+P_{x_{m},x_{M}}^{\prime}(0)=0$ (37)

where the last follows because
$\mathbb{P}(X=x_{m})=P_{x_{m},x_{m}}(\sigma)+P_{x_{m},x_{M}}(\sigma)$ is
constant in $\sigma$. By (35), we have thus shown that $T^{\prime}\to 0$ as
$\sigma\downarrow 0$ and that (see (32))

$\lim_{N\to\infty}\lim_{\sigma\downarrow 0}\frac{{\rm d}}{{\rm
d}\sigma}R_{C_{N}}^{(N)}(\sigma)=0.$ (38)

The proof is thus concluded by (31).

###  A.3 Proof of Theorem 2

As in the proof of Theorem 1, for simplicity we assume that
$C_{N}\in\mathbb{N}$ for all $N$. Recall the definitions of $T$ and $T_{k}$
given in the proof of Theorem 1. Using (32)

$\displaystyle\lim_{N\to\infty}\lim_{\sigma\downarrow 0}\frac{{\rm d}}{{\rm
d}\sigma}D_{C_{N}}^{(N)}(\sigma)$
$\displaystyle=f^{\prime}(0)+\frac{\lambda\,\mathbb{E}[\sqrt{\mathbb{E}[X^{2}|Y_{0}]}]}{1-\lambda\mathbb{E}[X]}\lim_{\sigma\downarrow
0}T^{\prime}.$ (39)

For $T^{\prime}$, using (14), we obtain

$\displaystyle T^{\prime}=$ $\displaystyle\frac{{\rm d}}{{\rm
d}\sigma}\bigg{(}x_{m}\mathbb{P}(Y_{\sigma}=x_{m})$
$\displaystyle\quad+\mathbb{P}(Y_{\sigma}=x_{M})\sqrt{x_{m}^{2}+(x_{M}^{2}-x_{m}^{2})\frac{\mathbb{P}(X=x_{M})}{\mathbb{P}(Y_{\sigma}=x_{M})}}\bigg{)}$
$\displaystyle=$ $\displaystyle
P_{x_{m},x_{m}}^{\prime}(\sigma)\bigg{(}x_{m}-\frac{\sqrt{\mathbb{E}[X^{2}]-x_{m}^{2}P_{x_{m},x_{m}}(\sigma)}}{2\sqrt{1-P_{x_{m},x_{m}}(\sigma)}}$
$\displaystyle\quad-\frac{x_{m}^{2}\sqrt{1-P_{x_{m},x_{m}}(\sigma)}}{2\sqrt{\mathbb{E}[X^{2}]-x_{m}^{2}P_{x_{m},x_{m}}(\sigma)}}\bigg{)}$
$\displaystyle\xrightarrow[\sigma\downarrow 0]{}$
$\displaystyle\,-P_{x_{m},x_{m}}^{\prime}(0)\left(\frac{\mathbb{E}[X^{2}\mid
Y_{0}=x_{M}]+x_{m}^{2}}{2\sqrt{\mathbb{E}[X^{2}\mid
Y_{0}=x_{M}]}}-x_{m}\right)$

and substituting in (39) gives (15). Now, for $\lim_{\sigma\downarrow
0}TT^{\prime}$ we observe that

$\displaystyle\lim_{\sigma\downarrow
0}T\,T^{\prime}=-P_{x_{m},x_{m}}^{\prime}(0)$
$\displaystyle\quad\times\left(x_{m}P_{x_{m},x_{m}}(0)+\sqrt{1-P_{x_{m},x_{m}}(0)}\sqrt{\mathbb{E}[X^{2}]-x_{m}^{2}P_{x_{m},x_{m}}(0)}\right)$
$\displaystyle\quad\times\left(\frac{\mathbb{E}[X^{2}]+x_{m}^{2}-2x_{m}^{2}P_{x_{m},x_{m}}(0)}{2\sqrt{1-P_{x_{m},x_{m}}(0)}\sqrt{\mathbb{E}[X^{2}]-x_{m}^{2}P_{x_{m},x_{m}}(0)}}-x_{m}\right)$
$\displaystyle<-P_{x_{m},x_{m}}^{\prime}(0)\sqrt{\mathbb{E}[X^{2}]}\left(\frac{\mathbb{E}[X^{2}]+x_{m}^{2}}{2\sqrt{\mathbb{E}[X^{2}]}}-x_{m}\right)$

where the last inequality follows because $P_{x_{m},x_{m}}^{\prime}\geq 0$ (by
Assumption 1) and because the mapping

$\displaystyle z\mapsto$
$\displaystyle\left(x_{m}z+\sqrt{1-z}\sqrt{\mathbb{E}[X^{2}]-x_{m}^{2}z}\right)$
$\displaystyle\times\left(\frac{\mathbb{E}[X^{2}]+x_{m}^{2}-2x_{m}^{2}z}{2\sqrt{1-z}\sqrt{\mathbb{E}[X^{2}]-x_{m}^{2}z}}-x_{m}\right)$

is increasing in $z$ over $[0,1]$. Substituting in (39) and rearranging terms,
$\lim_{N\to\infty}\lim_{\sigma\downarrow 0}\frac{{\rm d}}{{\rm
d}\sigma}D_{C_{N}}^{(N)}(\sigma)<0$ if (16) holds true.

###  A.4 Proof of Proposition 2

Assume that $1<c<N-1$. Let
$v_{m}:=\mathbb{P}(Y_{\sigma}=x_{m})p_{m}\,\mathbb{E}[X\mid
Y_{\sigma}=x_{m}]/\lfloor c\rfloor$, $v_{z}:=p_{z}\,\mathbb{E}[Z]$ and
$v_{M}:=\mathbb{P}(Y_{\sigma}=x_{M})p_{M}\,\mathbb{E}[X\mid
Y_{\sigma}=x_{M}]/(N-1-\lfloor c\rfloor)$. Note that

$\displaystyle\lfloor c\rfloor v_{m}+v_{z}+(N-1-\lfloor c\rfloor)v_{M}$ (40)
$\displaystyle=\mathbb{E}[X\mid Y_{\sigma}=x_{m}]\mathbb{P}(Y_{\sigma}=x_{m})$
(41) $\displaystyle\quad+\mathbb{E}[X\mid
Y_{\sigma}=x_{M}]\mathbb{P}(Y_{\sigma}=x_{M})=\mathbb{E}[X]$ (42)

where the last equality follows by the law of total expectation.

Now, using Jensen’s inequality, we obtain

$\displaystyle\frac{2}{\Lambda}R_{c}^{(N)}(\sigma)$
$\displaystyle\geq\frac{\lfloor c\rfloor v_{m}^{2}}{1-\Lambda
v_{m}}+\frac{v_{z}^{2}}{1-\Lambda v_{z}}+\frac{(N-1-\lfloor
c\rfloor)v_{M}^{2}}{1-\Lambda v_{M}}.$

Let $\mathcal{S}$ denote the set of $(v_{m},v_{z},v_{M})\in[0,1]^{3}$ such
that (40) holds and $v_{m}=v_{z}=v_{M}$. Since the mapping
$s\mapsto\frac{u^{2}}{1-\Lambda u}$ is convex, by Karamata’s inequality,

$\displaystyle\frac{2}{\Lambda}R_{c}^{(N)}(\sigma)$
$\displaystyle\geq\min_{(v_{m},v_{z},v_{M})\in\mathcal{S}}\left\\{\frac{\lfloor
c\rfloor v_{m}^{2}}{1-\Lambda v_{m}}+\frac{v_{z}^{2}}{1-\Lambda
v_{z}}+\frac{(N-1-\lfloor c\rfloor)v_{M}^{2}}{1-\Lambda v_{M}}\right\\}$
$\displaystyle=\frac{1}{N}\frac{\mathbb{E}[X]^{2}}{1-\lambda\mathbb{E}[X]}.$

This concludes the proof.

###  A.5 Proof of Proposition 3

First, (1) implies

$\sigma^{*}=\Theta(x_{M}^{1-\beta})$

and, together with Assumption 1 and since $\beta<1$,

$\displaystyle\lim_{x_{M}\to\infty}P(\sigma^{*})=\begin{bmatrix}1&0\\\
0&0\end{bmatrix}.$ (43)

For $p=1,2$, we notice

$\displaystyle\mathbb{P}(Y_{\sigma^{*}}=x_{m})\mathbb{E}[X^{p}\mid
Y_{\sigma^{*}}=x_{m}]^{\frac{1}{p}}$
$\displaystyle=\mathbb{P}(Y_{\sigma^{*}}=x_{m})^{1-\frac{1}{p}}\left(x_{m}^{p}P_{x_{m},x_{m}}(\sigma^{*})+x_{M}^{p}P_{x_{M},x_{m}}(\sigma^{*})\right)^{\frac{1}{p}}$
$\displaystyle\xrightarrow[x_{M}\to\infty]{}\,x_{m}$ (44)

because
$x_{M}^{2}P_{x_{M},x_{m}}(\sigma^{*})=x_{M}^{2}P_{x_{M},x_{m}}(\Theta(x_{M}^{1-\beta}))=x_{M}^{2}\,O(x_{M}^{-(1-\beta)\eta_{m}})\to
0$ as $x_{M}\to\infty$. Now, since
$1=\mathbb{P}(X=x_{m})+P_{x_{M},x_{m}}+P_{x_{M},x_{M}}=1-\alpha
x_{M}^{-\beta}+P_{x_{M},x_{m}}+P_{x_{M},x_{M}}$, we obtain

$\displaystyle P_{x_{M},x_{M}}(\sigma^{*})=\alpha
x_{M}^{-\beta}-O\left(x_{M}^{-\eta_{m}(1-\beta)}\right),$

and since $\eta_{m}>\frac{2}{1-\beta}$,

$\displaystyle\lim_{x_{M}\to\infty}\frac{P_{x_{M},x_{M}}(\sigma^{*})}{\alpha
x_{M}^{-\beta}}=1.$ (45)

Thus,

$\displaystyle\mathbb{P}(Y_{\sigma^{*}}=x_{M})\frac{\mathbb{E}[X\mid
Y_{\sigma^{*}}=x_{M}]}{\mathbb{E}[X]}$
$\displaystyle=\frac{1}{\mathbb{E}[X]}\left(x_{m}P_{x_{m},x_{M}}(\sigma^{*})+x_{M}P_{x_{M},x_{M}}(\sigma^{*})\right)\xrightarrow[x_{M}\to\infty]{}\,1$
(46)

and similarly

$\displaystyle\lim_{x_{M}\to\infty}\mathbb{P}(Y_{\sigma^{*}}=x_{M})\frac{\sqrt{\mathbb{E}[X^{2}\mid
Y_{\sigma^{*}}=x_{M}]}}{\mathbb{E}[X]}$
$\displaystyle=\lim_{x_{M}\to\infty}\frac{1}{\mathbb{E}[X]}\sqrt{\mathbb{P}(Y_{\sigma^{*}}=x_{M})}\sqrt{\sum_{k=m,M}x_{k}^{2}P_{x_{k},x_{M}}(\sigma^{*})}$
$\displaystyle=\lim_{x_{M}\to\infty}\frac{x_{M}}{\mathbb{E}[X]}\sqrt{P_{x_{M},x_{M}}(\sigma^{*})P_{x_{m},x_{M}}(\sigma^{*})}+\frac{x_{M}P_{x_{M},x_{M}}(\sigma^{*})}{\mathbb{E}[X]}$
$\displaystyle=1.$

In addition, using the previous limit,
$\lim_{x_{M}\to\infty}\mathbb{P}(Y_{\sigma^{*}}=x_{M})\sqrt{\mathbb{E}[X^{2}\mid
Y_{\sigma^{*}}=x_{M}]}=+\infty$, which implies

$\displaystyle\lim_{x_{M}\to\infty}c^{\star}=\lim_{x_{M}\to\infty}(1-\rho)\frac{\sqrt{\mathbb{E}[X^{2}\mid
Y_{\sigma^{\star}}=x_{m}]}}{\mathbb{E}[\sqrt{\mathbb{E}[X^{2}\mid
Y_{\sigma^{\star}}]}]}\mathbb{P}(Y_{\sigma^{\star}}=x_{m})$
$\displaystyle\quad+\rho\,x^{\beta-1}\mathbb{E}[X\mid
Y_{\sigma^{\star}}=x_{m}]\mathbb{P}(Y_{\sigma^{\star}}=x_{m})$
$\displaystyle=\frac{(1-\rho)x_{m}}{x_{m}+\lim\limits_{x_{M}\to\infty}\mathbb{P}(Y_{\sigma^{*}}=x_{M})\sqrt{\mathbb{E}[X^{2}\mid
Y_{\sigma^{*}}=x_{M}]}}=0.$

If $N(1-\rho)>1$, combining the properties above we obtain

$\displaystyle\lim_{x_{M}\to\infty}\frac{D_{c}^{(N)}(\sigma^{*})}{R^{\downarrow}}=\lim_{x_{M}\to\infty}\frac{1}{R^{\downarrow}}\left(\frac{\sigma^{*}}{1-\Lambda\sigma^{*}}+R_{c}^{(N)}(\sigma^{*})\right)$
$\displaystyle=\frac{1}{\gamma}+\lim_{x_{M}\to\infty}\frac{R_{1}^{(N)}(\sigma^{*})}{R^{\downarrow}}$

and after some algebra we obtain

$\displaystyle=\frac{1}{\gamma}+\lim_{x_{M}\to\infty}\frac{\rho
N}{2R^{\downarrow}\mathbb{E}[X]}\times\frac{\mathbb{P}(Y_{\sigma^{*}}=x_{M})^{2}\mathbb{E}[X^{2}\mid
Y_{\sigma}^{*}=x_{M}]}{N(1-\rho)-1}$
$\displaystyle=\frac{1}{\gamma}+\frac{N(1-\rho)}{N(1-\rho)-1}.$

This proves (20). Therefore, assume that $N(1-\rho)\leq 1$. In this case,
$\lim_{x_{M}\to\infty}c=N(1-\rho)\leq 1$ and therefore no server will receive
jobs that are only predicted as short. Now, we notice that

$\displaystyle\frac{p_{z}\mathbb{E}[Z]}{\mathbb{E}[X]}=$ $\displaystyle
1-\frac{N-1}{N-c}\mathbb{P}(Y_{\sigma^{*}}=x_{M})\,\frac{\mathbb{E}[X\mid
Y_{\sigma^{*}}=x_{M}]}{\mathbb{E}[X]}$ $\displaystyle=$ $\displaystyle
1-\frac{(N-1)\mathbb{P}(Y_{\sigma^{*}}=x_{M})}{N\rho+N\rho\,\phi(x_{M})}\,\frac{\mathbb{E}[X\mid
Y_{\sigma^{*}}=x_{M}]}{\mathbb{E}[X]}$
$\displaystyle\xrightarrow[x_{M}\to\infty]{}\,$ $\displaystyle
1-\frac{N-1}{N\rho}$

where in the last expression we have used (46). Similarly,

$\displaystyle\frac{p_{z}^{2}\mathbb{E}[Z^{2}]}{\mathbb{E}[X^{2}]}=$
$\displaystyle\,p_{z}\left(1-\frac{N-1}{N-c}\mathbb{P}(Y_{\sigma^{*}}=x_{M})\frac{\mathbb{E}[X^{2}\mid
Y_{\sigma^{*}}=x_{M}]}{\mathbb{E}[X^{2}]}\right)$
$\displaystyle\xrightarrow[x_{M}\to\infty]{}\,$ $\displaystyle
1-\frac{N-1}{N\rho}$

Using these limits,

$\displaystyle\lim_{x_{M}\to\infty}\frac{D_{c}^{(N)}(\sigma^{*})}{x_{M}^{\theta}R^{\downarrow}}=\lim_{x_{M}\to\infty}\frac{R_{c}^{(N)}(\sigma^{*})}{x_{M}^{\theta}R^{\downarrow}}$
$\displaystyle=\lim_{x_{M}\to\infty}\frac{\rho
N}{2x_{M}^{\theta}\mathbb{E}[X]R^{\downarrow}}\left(\frac{p_{z}^{2}\mathbb{E}[Z^{2}]}{1-\rho
N\frac{p_{z}\,\mathbb{E}[Z]}{\mathbb{E}[X]}}+\frac{N-1}{N-c}\frac{\mathbb{E}[X]^{2}}{N-c-\rho
N}\right)$ $\displaystyle=\lim_{x_{M}\to\infty}\frac{\rho
Nx_{M}^{-\theta}}{2\mathbb{E}[X]R^{\downarrow}}\left(\frac{p_{z}^{2}\mathbb{E}[Z^{2}]}{N(1-\rho)}+\frac{N-1}{N\rho+N\rho\,\phi(x_{M})}\frac{\mathbb{E}[X]^{2}}{N\rho\,\phi(x_{M})}\right)$
$\displaystyle=\lim_{x_{M}\to\infty}\frac{1-\rho}{x_{M}^{\theta}\mathbb{E}[X]^{2}}\left(\frac{p_{z}^{2}\mathbb{E}[Z^{2}]}{1-\rho}+\frac{N-1}{\rho+\rho\,\phi(x_{M})}\frac{\mathbb{E}[X]^{2}}{N\rho\,\phi(x_{M})}\right)$
$\displaystyle=\left(1-\frac{N-1}{N\rho}\right)\lim_{x_{M}\to\infty}x_{M}^{-\theta}$
$\displaystyle\quad+(1-\rho)\lim_{x_{M}\to\infty}\frac{N-1}{\rho+\rho\,\phi(x_{M})}\frac{1}{N\rho\,\phi(x_{M})\,x_{M}^{\theta}}$
$\displaystyle=(1-\rho)\frac{N-1}{N\rho^{2}}$

and this proves (21).

###  A.6 Proof of Theorem 3

Given Proposition 3, it is enough to show that
$R^{\downarrow}/\min_{c\in[0,N]}R_{c}^{(N)}(0)\to 0$ as $x_{M}\to\infty$. Let
$\mathcal{S}$ be the set of $c\in[1,N-1]$ such that $R_{c}^{(N)}(0)<\infty$.

For now, let us assume that $X$ and $Y_{0}$ are independent. In this case, the
mean user-perceived waiting time corresponds to the mean response time of a
single M/G/1 queue. Using Pollaczek–Khinchine formula, this is given by

$\displaystyle\min_{c\in[0,N]}R_{c}^{(N)}(0)=\frac{\rho}{2\mathbb{E}[X]}\frac{\mathbb{E}[X^{2}]}{1-\lambda\mathbb{E}[X]}$
(47)

Since both $\frac{\mathbb{E}[X^{2}]}{x_{M}\mathbb{E}[X]}$ and
$R^{\downarrow}x_{M}^{1-\beta}$ converge to a strictly positive constant as
$x_{M}\to\infty$,

$\frac{R^{\downarrow}}{\min_{c\in[0,N]}R_{c}^{(N)}(0)}=O(x_{M}^{-\beta})$

and this gives (22) in case i).

Now, assume in the remainder that (13) holds. Let
$\underline{c}:=\Lambda\mathbb{P}(Y_{0}=x_{m})\mathbb{E}[X\mid Y_{0}=x_{m}]$
and notice that $\underline{c}$ makes equal to one the load of servers that
only receives jobs that are predicted as short. Let also

$R_{c,M}^{(N)}:=\frac{\Lambda}{2}\bigg{(}\frac{\mathbb{P}(Y_{0}=x_{M})^{2}(1-p_{M})^{2}\mathbb{E}[X^{2}\mid
Y_{0}=x_{M}]}{1-\Lambda\mathbb{P}(Y_{0}=x_{M})\,(1-p_{M})\,\mathbb{E}[X\mid
Y_{0}=x_{M}]}\\\
+\frac{\mathbb{P}(Y_{0}=x_{M})^{2}p_{M}^{2}\mathbb{E}[X^{2}\mid
Y_{0}=x_{M}]}{N-1-\lfloor
c\rfloor-\Lambda\mathbb{P}(Y_{0}=x_{M})p_{M}\,\mathbb{E}[X\mid
Y_{0}=x_{M}]}\bigg{)}$

which in view of (4) can be interpreted as the mean waiting time at servers
that is due to long-predicted jobs only (i.e., as if jobs that are predicted
as short are discarded). Then,

$\displaystyle\min_{c\in[0,N]}R_{c}^{(N)}(0)\geq\min_{c\in\mathcal{S}}R_{c,M}^{(N)}=\lim_{c\uparrow\underline{c}}R_{c,M}^{(N)}$
$\displaystyle\geq\frac{\Lambda}{2}\frac{\mathbb{P}(Y_{0}=x_{M})^{2}p_{M}^{2}\mathbb{E}[X^{2}\mid
Y_{0}=x_{M}]}{N-1-\lfloor\underline{c}\rfloor-\Lambda\mathbb{P}(Y_{0}=x_{M})p_{M}\,\mathbb{E}[X\mid
Y_{0}=x_{M}]}$
$\displaystyle=\frac{\Lambda}{2}\frac{N-1-\lfloor\underline{c}\rfloor}{N-\underline{c}}\frac{\mathbb{P}(Y_{0}=x_{M})^{2}\mathbb{E}[X^{2}\mid
Y_{0}=x_{M}]}{N-\Lambda\mathbb{E}[\mathbb{E}[X\mid Y_{0}]]}$
$\displaystyle=\frac{\rho}{2\mathbb{E}[X]}\frac{N-1-\lfloor\underline{c}\rfloor}{N-\underline{c}}\frac{\mathbb{P}(Y_{0}=x_{M})^{2}\mathbb{E}[X^{2}\mid
Y_{0}=x_{M}]}{1-\lambda\mathbb{E}[X]}$ (48)

By (14), $\mathbb{P}(Y_{0}=x_{m})=P_{x_{m},x_{m}}(0)$,
$\mathbb{P}(Y_{0}=x_{M})\geq\mathbb{P}(X=x_{M})$,

$\displaystyle\mathbb{P}(Y_{0}=x_{M})^{2}\mathbb{E}[X^{2}\mid Y_{0}=x_{M}]$
$\displaystyle=\mathbb{P}(Y_{0}=x_{M})\left(x_{m}^{2}\mathbb{P}(Y_{0}=x_{M})+(x_{M}^{2}-x_{m}^{2})\mathbb{P}(X=x_{M})\right)$
$\displaystyle=(1-P_{x_{m},x_{m}}(0))\left(\mathbb{E}[X^{2}]-x_{m}^{2}P_{x_{m},x_{m}}(0)\right)$

and, as $x_{M}\to\infty$, $\underline{c}=\rho
N\mathbb{P}(Y_{0}=x_{m})\frac{\mathbb{E}[X\mid
Y_{0}=x_{m}]}{\mathbb{E}[X]}=\rho
N\mathbb{P}(Y_{0}=x_{m})\frac{x_{m}}{\mathbb{E}[X]}\to 0$. Combining these
properties in (48), we have thus shown that

$\displaystyle\min_{c\in[0,N]}R_{c}^{(N)}(0)\geq$
$\displaystyle\frac{\rho}{2\mathbb{E}[X]}\frac{N-1-\lfloor\underline{c}\rfloor}{N-\underline{c}}(1-P_{x_{m},x_{m}}(0))$
$\displaystyle\times\frac{\mathbb{E}[X^{2}]-x_{m}^{2}P_{x_{m},x_{m}}(0)}{1-\rho}$
$\displaystyle=$ $\displaystyle(1-P_{x_{m},x_{m}}(0))\,\Theta(x_{M}).$

Therefore, given the scaling assumptions on $P_{x_{m},x_{m}}(0)$ we obtain

$\frac{R^{\downarrow}}{\min\limits_{c\in[0,N]}R_{c}^{(N)}(0)}\leq\frac{1}{(1-P_{x_{m},x_{m}}(0))\,O(x_{M}^{\beta})}\xrightarrow[x_{M}\to\infty]{}\,0,$

which gives (22) in case ii).

|  Jonatha Anselmi is a tenured researcher at the French National Institute
for Research in Digital Science and Technology (Inria), since 2014. Prior to
this, he was a full-time researcher at the Basque Center for Applied
Mathematics and a postdoctoral researcher at Inria. He received his PhD in
computer engineering at Politecnico di Milano (Italy) in 2009. His research
interests focus on the performance evaluation and optimization of distributed
systems.
---|---
|  Josu Doncel is an assistant professor in the University of the Basque
Country. He obtained from the same university the Industrial Engineering
degree in 2007, the Mathematics degree in 2010 and, in 2011, the Master degree
in Applied Maths and Statistics. He received in 2015 the PhD degree from
Université de Toulouse (France). He has previously held research positions at
LAAS-CNRS (France), INRIA Grenoble (France) and BCAM-Basque Center for Applied
Mathematics (Spain) and teaching positions at ENSIMAG (France), INSA-Toulouse
(France) and IUT-Blagnac (France).
---|---