# Flexible Load Balancing with Multi-dimensional State-space Collapse:
Throughput and Heavy-traffic Delay Optimality

Xingyu Zhou
Department of ECE
The Ohio State University
<EMAIL_ADDRESS>Jian Tan
Department of ECE
The Ohio State University
<EMAIL_ADDRESS>
Ness Shroff
Department of ECE and CSE
The Ohio State University
<EMAIL_ADDRESS>
###### Abstract

Heavy traffic analysis for load balancing policies has relied heavily on the
condition of state-space collapse onto a single-dimensional line in previous
works. In this paper, via Lyapunov-drift analysis, we rigorously prove that
even under a multi-dimensional state-space collapse, steady-state heavy-
traffic delay optimality can still be achieved for a general load balancing
system. This result directly implies that achieving steady-state heavy-traffic
delay optimality simply requires that no server is idling while others are
busy at heavy loads, thus complementing and extending the result obtained by
diffusion approximations. Further, we explore the greater flexibility provided
by allowing a multi-dimensional state-space collapse in designing new load
balancing policies that are both throughput optimal and heavy-traffic delay
optimal in steady state. This is achieved by overcoming various technical
challenges, and the methods used in this paper could be of independent
interest.

##  1 Introduction

We consider a discrete-time load balancing system which consists of one
dispatcher and $N$ servers, each associated with an infinite buffer queue. The
service rate of server $n$ is $\mu_{n}$. At each time-slot $t$, the exogenous
tasks arrive with rate $\lambda_{\Sigma}$, and upon arrival each task is
immediately dispatched to one of the queues. A load balancing policy is a rule
that selects the queue to which a new arrival in each time-slot should be
dispatched. In recent years the development of efficient load balancing
policies has received significant attention because of their applicability in
distributed architectures such as Web service [11], large data storage systems
(e.g., HBase [10]), cloud computing systems [9], etc. A desirable load
balancing policy is often one that is able to improve the average response
time while achieving high utilization of resources. To this end, many works in
the literature have focused on minimizing the average delay in the heavy-
traffic regime where the exogenous arrival rate approaches the boundary of the
capacity region, i.e., the heavy-traffic parameter
$\epsilon=\sum\mu_{n}-\lambda_{\Sigma}$ approaches zero in our system.

At the heart of most heavy-traffic analysis is the notion of state-space
collapse, which roughly means that the original multi-dimensional system space
concentrates around a single dimensional (or generally a lower dimensional)
subspace as the heavy-traffic parameter $\epsilon$ goes to zero. For instance,
via either diffusion approximations [8] or the recently developed drift-based
framework [7], it has been shown that under the so-called join-shortest-queue
(JSQ) policy, the load balancing system in heavy-traffic would collapse to a
one-dimensional line where all the queue lengths are equal. This indicates
that the system behaves as if there is only a single queue with all the
servers pooled together as an aggregated server, which is often called
complete resource pooling. This result directly implies that JSQ is
asymptotically optimal, i.e., heavy-traffic delay optimal, since the response
time in the pooled single-server system is stochastically less than that of a
typical load balancing system. The same one-dimensional state-space collapse
is also the key in establishing heavy-traffic delay optimality for the so-
called power-of-$d$ policy [5], [19], where the dispatcher routes the new
arrival to a server with the shortest queue length among $d\geq 2$ servers
selected uniformly at random. Instead of requiring the information of all the
queue lengths as in JSQ, the power-of-$d$ policy is able to achieve asymptotic
optimality with partial queue length information, and hence provides greater
flexibility and scalability for large-scale distributed systems.

The authors in [16] argue heuristically that state-space collapse to a line
where all the queue lengths are equal may not be necessary for showing heavy-
traffic delay optimality in load balancing systems. In particular, they
proposed a symmetric threshold policy for a load balancing system with _two_
homogeneous servers, and conjectured that as long as the threshold satisfies a
certain property, the total work process under the threshold policy has the
same diffusion limit as that under the optimal JSQ. Nevertheless, the system
state in heavy-traffic limit under the threshold policy is now in the two-
dimensional positive orthant rather than a single-dimensional line where all
the queue lengths are equal. Hence, the authors in [16] argued that the key
feature of a heavy-traffic optimal policy is to keep all the servers busy when
there is substantial work rather than the strong property of maintaining all
the queue lengths equal. This argument is validated in a two-server system
with an asymmetric threshold policy proposed in [23], under which the total
work process is proven to have the same diffusion limit as that of JSQ while
the state space collapses to a line where the lengths of two queues are not
equal. Note that besides only considering a two-server system, a further
limitation in both [16] and [23] is that the asymptotic optimality holds only
for a finite time interval. This is because the interchange of limits has not
been established for the diffusion approximations. Therefore, an interesting
open problem is whether or not steady-state delay optimality in heavy-traffic
holds under a _multi-dimensional_ state-space collapse for a _general_ load
balancing system, and if so, how one can design a load balancing policy to
achieve it.

In this paper, we take a systematic approach to addressing this problem.
First, we extend the recently developed drift-based framework in [7] to
rigorously show that even under a multi-dimensional state-space collapse, a
load balancing policy is still able to achieve heavy-traffic delay optimality
in steady-state. This result then allows us to explore the flexibility in
designing load balancing policies that are not only throughput optimal but
also heavy-traffic delay optimal in steady-state. The main contributions of
this paper can be summarized as follows:

  * •

We rigorously establish heavy-traffic delay optimality in steady-state under a
multi-dimensional state-space collapse for a general load balancing system.
More precisely, we consider a symmetric finitely generated cone
$\mathcal{K}_{\alpha}$ parameterized by a nonnegative $\alpha\in[0,1]$. In
particular, when $\alpha=1$ the cone reduces to the line where all the
components are equal, and when $\alpha=0$ the cone is the nonnegative orthant.
Our first main result (cf. Theorem 1) states that given a throughput optimal
load balancing policy, if the system state collapses to a cone
$\mathcal{K}_{\alpha}$ with any fixed $\alpha\in(0,1]$, this policy is heavy-
traffic delay optimal in steady-state. The importance of this result is two-
fold: (i) it rigorously proves a conjectured insight behind steady-state
heavy-traffic delay optimality in load balancing systems. In particular, it
shows that to achieve the heavy-traffic optimality in steady-state for a
general system, a load balancing policy should also just be able to keep all
the servers busy when there is substantial work, rather than the strong
requirement of maintaining all the queue lengths equal. This complements and
extends the diffusion approximation results in [16], [23]. (ii) it enables us
to establish heavy-traffic delay optimality under general state-space collapse
regions (including even non-convex regions). This can be achieved by showing
that the actual state-space collapse region can be covered by a cone
$\mathcal{K}_{\alpha}$ with some $\alpha\in(0,1]$, which directly implies that
the system state also collapses to the cone $\mathcal{K}_{\alpha}$, and hence
heavy-traffic delay optimality follows from Theorem 1.

  * •

By exploiting the key implications of the first result, we are then able to
characterize the degree of flexibility (from two different dimensions) in
designing new load balancing policies that are both throughput-optimal and
heavy traffic delay-optimal in steady-state. (i) The first dimension of
flexibility is concerned with the frequency of favoring shorter queues. We
find that instead of favoring shorter queues at each time-slot for every
system-state, it is sufficient to favor shorter queues only when the system-
state is outside a cone $\mathcal{K}_{\alpha}$ for any fixed $\alpha\in(0,1]$.
This means that whenever the system-state is within the cone
$\mathcal{K}_{\alpha}$, the dispatcher is allowed to use an arbitrary
Markovian dispatching distribution, and this flexibility increases as $\alpha$
approaches zero. (ii) The second dimension is related to the intensity with
which shorter queues are favored. We find that instead of only joining the
shortest queue as in the JSQ policy or having monotone decreasing
probabilities from joining the shortest queue to the longest queue in the
power-of-$d$ policy, an even weaker intensity of favoring shorter queues is
sufficient and this intensity can be characterized by some parameter $\delta$.
The above flexibilities from two different dimensions are stitched together in
Theorem 2. We also consider the case where these two flexibilities scale with
the heavy-traffic parameter $\epsilon$, i.e., both $\alpha$ and $\delta$
decrease to zero as $\epsilon$ approaches zero. We show that steady-state
heavy-traffic delay optimality is preserved as long as
$\alpha\delta=\Omega(\epsilon^{\beta})$ for any $\beta\in[0,1)$ (cf.
Proposition 1). This result offers us even more flexibility in designing
efficient load balancing policies.

  * •

The techniques used in this paper are of independent interest. For example, in
order to establish throughput optimality defined in this paper, namely
positive recurrence with bounded moments in steady-state, the standard
stochastic drift analysis of a suitable Lyapunov function is very difficult in
our case because the drift within the cone $\mathcal{K}_{\alpha}$ can be
positive. On the other hand, the standard fluid limit methods can only be used
to show positive recurrence but not bounded moments of the queue lengths. To
address the problem, we combine fluid approximations with stochastic Lyapunov
theory. In particular, we show that the Lyapunov function used in the fluid
model, i.e., the sum of the queue lengths, is also a suitable Lyapunov
function for the original stochastic system. This connection allows us to
carry out the drift analysis in the fluid domain. Then, we come back to the
stochastic system and apply the drift-based analysis of the same Lyapunov
function in the original system by leveraging the result in the fluid domain
to show both positive recurrence and bounded moments. Also, for the result of
state-space collapse to a cone, the standard analysis adopted in the single-
dimensional state-space collapse fails as well in this case. This is because
in contrast to the projection onto a line, the projection onto a convex cone
is more complex. In fact, a closed-form formula of the projection onto a
polyhedral cone is still an open problem. To circumvent this difficulty,
instead of obtaining the exact projection, we find that it is sufficient to
establish a monotone property of the projection to show that the system state
collapses to a cone. Moreover, the bounds on the moments in the state-space
collapse result hold even when the system is not in heavy-traffic, and hence
can be independently used as a performance evaluation tool for the pre-limit
load balancing systems.

###  1.1 Related Work

The use of state-space collapse to study the delay performance in the heavy-
traffic regime was introduced in [8] for two parallel servers. The authors,
via diffusion approximations, showed that the two separate servers under the
JSQ policy act as a pooled resource in the heavy-traffic limit. Since then,
the methodology of diffusion limits combined with state-space collapse has
been adopted in a number of papers on parallel servers [21] [2] [5] [3] [13].
For example, the author in [21] generalized the results in [8] to the case of
renewal arrivals and general service times. In [5], power-of-$d$ was shown to
have the same diffusion limit as JSQ in the heavy-traffic limit. The common
step in all these works is to show that the diffusion limit in heavy-traffic
converges to a one-dimensional Brownian motion, which implies sample-path
optimality in finite time. However, in order to show optimality in steady-
state, an interchange of limit argument needs to be proven, which is often
difficult and not undertaken in the aforementioned works. Recently, the
authors in [7] proposed a drift-based framework, which is able to directly
work on the stationary distribution and establish steady-state heavy-traffic
optimality of load balancing policies such as JSQ, and scheduling policies
such as MaxWeight. This framework has been adopted to show steady-state heavy-
traffic optimality of several policies in different scenarios. For instance,
based on this framework, the authors in [19] established the steady-state
heavy-traffic optimality of power-of-$d$ policy. The authors in [30]
identified a class of heavy-traffic delay optimal policies. Moreover, it has
been shown in [26] that a joint JSQ and MaxWeight policy is heavy-traffic
delay optimal for MapReduce clusters under a specific traffic scenario. For
all traffic scenarios, a heavy-traffic delay optimal policy called ‘local-
task-first’ policy was proposed in [27] based on this new framework.

However, it is worth noting that the state-space collapse of all the
aforementioned heavy-traffic optimal load balancing policies is only one-
dimensional. A two-dimensional state-space collapse was considered in [16], in
which the authors argued heuristically that heavy-traffic delay optimality is
preserved in this case, and hence claimed that the key feature of a heavy-
traffic optimal load balancing policy is to keep all the servers busy when
there is substantial remaining work, rather than the strong property of
maintaining all the queue lengths equal. The authors in [23] validated this
claim for a two-server system under an asymmetric threshold policy. In
particular, they showed that the diffusion limit of the work process is the
same as that under JSQ, while the state-space collapses to a line where the
queue lengths of two servers are not equal. However, both the results in [16]
and [23] hold only for a finite time since the validity of the interchange of
limits argument was not established for the diffusion approximations.
Motivated by this, in this paper, we extend the recently developed drift-based
framework [7] and successfully establish steady-state heavy-traffic optimality
under a multi-dimensional state-space collapse for a general load balancing
system, hence complementing and extending the diffusion approximation results
in [16] and [23].

We would also like to remark that besides load balancing (or scheduling) in
parallel servers, state-space collapse result also plays a key role in other
heavy-traffic scenarios. For example, given an $n\times n$ input queued
switch, it was shown that under the complete resource pooling (CRP) condition
(equivalently one-dimensional state-space collapse), the MaxWeight scheduling
algorithm is heavy-traffic delay optimal in the sense of diffusion limit [22].
When the CRP condition is not met, the state-space would then collapse to a
multi-dimensional space instead of a line. In this case, a diffusion limit has
been established in [15]. For the steady-state behavior in this case, via the
drift-based framework, it was showed that the MaxWeight scheduling policy can
guarantee optimal delay scaling with respect to $n$ [18] [17]. However, in
contrast to the case of the single-dimensional state-space collapse in [22],
[7], heavy-traffic delay optimality is not established in [18] [17]. Recently,
multi-dimensional state-space collapse was also used to show delay
insensitivity of the proportionally fair policy in a bandwidth sharing network
in heavy-traffic [25]. We finally remark that the heavy-traffic regime
considered in this paper and all the aforementioned papers is the conventional
heavy-traffic regime, which is different from the Halfin-Whitt heavy-traffic
regime (also known as many-server heavy-traffic regime or quality-and-
efficiency-driven regime). In this regime, the heavy-traffic parameter
$\epsilon$ approaches zero and the number of servers $N$ goes to infinity at
the same time [1], [12], [6].

###  1.2 Notations

The dot product in $\mathbb{R}^{N}$ is denoted by
$\langle\mathbf{x},\mathbf{y}\rangle\triangleq\sum_{n=1}^{N}x_{n}y_{n}$. For
any $\mathbf{x}\in\mathbb{R}^{N}$, the $l_{1}$ norm is denoted by
$\left\lVert\mathbf{x}\right\rVert_{1}\triangleq\sum_{n=1}^{N}|x_{n}|$ and
$l_{2}$ norm is denoted by
$\left\lVert\mathbf{x}\right\rVert\triangleq\sqrt{\langle\mathbf{x},\mathbf{x}\rangle}$.
In general, the $l_{r}$ norm is denoted by
$\left\lVert\mathbf{x}\right\rVert_{r}\triangleq(\sum_{n=1}^{N}|x_{n}|^{r})^{1/r}$.
Let $\mathcal{N}$ denote the set $\\{1,2,\ldots,N\\}$.

##  2 System Model and Preliminaries

This section first precisely describes the system model, and then presents
several necessary preliminaries.

###  2.1 System Model

We consider a discrete-time load balancing system as follows. There is a
central dispatcher and $N$ servers indexed by $n$, each of which maintains a
FIFO (first-in, first-out) infinite buffer size queue denoted by $Q_{n}$. In
each time-slot, the central dispatcher routes the new task arrivals to one of
the servers as in [7, 19, 26, 27, 28, 30]. Once a task joins a queue, it will
remain in that queue until its service is completed.

####  2.1.1 Arrival and Service

Let $A_{\Sigma}(t)$ denote the number of exogenous tasks that arrive at the
beginning of time-slot $t$. We assume that $A_{\Sigma}(t)$ is an integer-
valued random variable, which is _i.i.d._ across time-slots. The mean and
variance of $A_{\Sigma}(t)$ are denoted by $\lambda_{\Sigma}$ and
$\sigma_{\Sigma}^{2}$, respectively. We further assume that there is a
positive probability for $A_{\Sigma}(t)$ to be zero and the arrival process
has a finite support, i.e., $A_{\Sigma}(t)\leq A_{\max}<\infty$ for all $t$.
Let $S_{n}(t)$ denote the amount of service that server $n$ offers for queue
$n$ in time-slot $t$. Note that this is not necessarily equal to the number of
tasks that leaves the queue because the queue may be empty. We assume that
$S_{n}(t)$ is an integer-valued random variable, which is _i.i.d._ across
time-slots. We also assume that $S_{n}(t)$ is independent across different
servers as well as the arrival process. As before, $S_{n}(t)$ is also assumed
to have a finite support, i.e., $S_{n}(t)\leq S_{\max}<\infty$ for all $t$ and
$n$. The mean and variance of $S_{n}(t)$ are denoted as $\mu_{n}$ and
$\nu_{n}^{2}$, respectively. Let
$\mu_{\Sigma}\triangleq\Sigma_{n=1}^{N}\mu_{n}$ and
$\nu_{\Sigma}^{2}\triangleq\Sigma_{n=1}^{N}\nu_{n}^{2}$ denote the mean and
variance of the hypothetical total service process
$S_{\Sigma}(t)\triangleq\sum_{n=1}^{N}S_{n}(t)$.

####  2.1.2 Queue Dynamics

Let $Q_{n}(t)$ be the queue length of server $n$ at the beginning of time slot
$t$. Let $A_{n}(t)$ denote the number of tasks routed to queue $n$ at the
beginning of time-slot $t$ according to the dispatching decision. Then the
evolution of the length of queue $n$ is given by

$Q_{n}(t+1)=Q_{n}(t)+A_{n}(t)-S_{n}(t)+U_{n}(t),n=1,2,\ldots,N,$ (1)

where $U_{n}(t)=\max\\{S_{n}(t)-Q_{n}(t)-A_{n}(t),0\\}$ is the unused service
due to an empty queue.

###  2.2 Preliminaries

In this paper, we assume that the dispatching decision in each time-slot can
at most depend on ${\mathbf{Q}}(t)$. Thus, with the system model above, the
queue length process $\\{{\mathbf{Q}}(t),t\geq 0\\}$ forms a Markov chain. We
consider a set of load balancing systems
$\\{{\mathbf{Q}}^{(\epsilon)}(t),t\geq 0\\}$ parameterized by $\epsilon$ such
that the mean arrival rate of the exogenous arrival process
$\\{A_{\Sigma}^{(\epsilon)}(t),t\geq 0\\}$ is
$\lambda_{\Sigma}^{(\epsilon)}=\mu_{\Sigma}-\epsilon$. Note that the heavy-
traffic parameter $\epsilon$ characterizes the distance between the arrival
rate and the capacity region boundary.

We say that a load balancing system is stable if the Markov chain
$\\{{\mathbf{Q}}(t),t\geq 0\\}$ is positive recurrent, and then use
$\overline{{\mathbf{Q}}}$ to denote the random vector whose distribution is
the same as the steady-state distribution of $\\{{\mathbf{Q}}(t),t\geq 0\\}$.
Now, we are ready to present the definitions of throughput optimality and
steady-state heavy-traffic delay optimality, respectively.

######  Definition 1 (Throughput Optimal).

A load balancing policy is said to be throughput optimal if for any arrival
rate within the capacity region, i.e., for any $\epsilon>0$, it can stabilize
the system and all the moments of
$\big{\lVert}{\overline{{\mathbf{Q}}}^{(\epsilon)}}\big{\rVert}$ are finite.

Note that this is a stronger definition of throughput optimality than that in
[26] [27] [30], because besides the positive recurrence, it also requires all
the moments to be finite in steady state for any arrival rate within capacity
region.

In the heavy-traffic analysis, one is interested in the behavior of the queue
lengths as $\epsilon$ approaches zero. In order to present and understand the
definition of steady-state heavy-traffic delay optimality, we will first
recall the fundamental lower bound on the expected sum queue lengths under any
throughput optimal policy [7].

######  Lemma 1.

Given any throughput optimal policy and assuming that
$(\sigma_{\Sigma}^{(\epsilon)})^{2}$ converges to a constant
$\sigma_{\Sigma}^{2}$ as $\epsilon$ decreases to zero, then

$\liminf_{\epsilon\downarrow
0}\epsilon\mathbb{E}\left[\sum_{n=1}^{N}\overline{Q}_{n}^{(\epsilon)}\right]\geq\frac{\zeta}{2},$
(2)

where $\zeta\triangleq\sigma_{\Sigma}^{2}+\nu_{\Sigma}^{2}$.

The right-hand-side of Eq. (2) is the heavy-traffic limit of a hypothetic
single-server system with arrival process $A_{\Sigma}^{(\epsilon)}(t)$ and
service process $\sum_{n}^{N}S_{n}(t)$ for all $t\geq 0$. This hypothetical
single-server queueing system is often called the resource-pooled system.
Since a task cannot be moved from one queue to another in the load balancing
system, it is easy to see that the expected sum queue lengths of the load
balancing system is larger than the expected queue length in the resource-
pooled system. However, under a certain load balancing policy, the lower bound
in Eq. (2) can actually be attained in the heavy-traffic limit and hence based
on Little’s law this policy achieves the minimum average delay of the system
in steady-state. This directly motivates the following definition of steady-
state heavy-traffic delay optimality as in [7, 19, 26, 27, 28, 30].

######  Definition 2 (Heavy-traffic Delay Optimality in Steady-state).

A load balancing scheme is said to be heavy-traffic delay optimal in steady-
state if the steady-state queue length vector
$\overline{{\mathbf{Q}}}^{(\epsilon)}$ satisfies

$\limsup_{\epsilon\downarrow
0}\epsilon\mathbb{E}\left[\sum_{n=1}^{N}\overline{Q}_{n}^{(\epsilon)}\right]\leq\frac{\zeta}{2},$

where $\zeta$ is defined in Lemma 1.

Before we end this section, we will introduce an $N$-dimensional cone, which
will be very useful in our upcoming analysis. In particular, the cone
$\mathcal{K}_{\alpha}$ is finitely generated by a set of $N$ vectors
$\\{\mathbf{b}^{(n)},n\in\mathcal{N}\\}$, i.e.,

$\mathcal{K}_{\alpha}=\left\\{\mathbf{x}\in\mathbb{R}^{N}:\mathbf{x}=\sum_{n\in\mathcal{N}}w_{n}\mathbf{b}^{(n)},w_{n}\geq
0\text{ for all }n\in\mathcal{N}\right\\},$ (3)

where $\mathbf{b}^{(n)}$ is an $N$-dimensional vector with the $n$th component
being $1$ and $\alpha$ everywhere else for some $\alpha\in[0,1]$. It follows
that, if $\alpha=0$, the cone $\mathcal{K}_{\alpha}$ is the non-negative
orthant of $\mathbb{R}^{N}$, and if $\alpha=1$, the cone
$\mathcal{K}_{\alpha}$ reduces to the single-dimensional line in which all the
components are equal. The polar cone $\mathcal{K}_{\alpha}^{\circ}$ of the
cone $\mathcal{K}_{\alpha}$ is defined as

$\mathcal{K}_{\alpha}^{\circ}=\left\\{\mathbf{x}\in\mathbb{R}^{N}:\langle\mathbf{x},\mathbf{y}\rangle\leq
0\text{ for all }\mathbf{y}\in\mathcal{K}_{\alpha}\right\\},$

which will also be quite important in our analysis.

##  3 Main Results

In this section, we present our main results. First, we show that a load
balancing policy can be heavy-traffic delay optimal in steady-state even under
a multi-dimensional state-space collapse. Then, by leveraging the key insight
behind this result, we are able to explore the degree of flexibility a load
balancing policy can enjoy while guaranteeing both throughput optimality and
heavy-traffic delay optimality. Furthermore, a useful generalization of this
result is presented at the end of this section.

###  3.1 Multi-dimensional State-space Collapse

We will first introduce the notion of state-space collapse used in this paper,
which intuitively means that in steady-state the queue length process
concentrates around a region of the state-space in heavy-traffic. As stated
before, in most of the previous works on load balancing, the state-space
collapse region is a single-dimensional line. In contrast, we are interested
in the situation where the state-space collapse region is the $N$-dimensional
cone $\mathcal{K}_{\alpha}$ defined in Eq. (3), which includes the single-
dimensional line as a special case. For a given cone $\mathcal{K}_{\alpha}$,
we decompose $\overline{{\mathbf{Q}}}^{(\epsilon)}$ into two parts as follows

$\overline{{\mathbf{Q}}}^{(\epsilon)}=\overline{{\mathbf{Q}}}^{(\epsilon)}_{\parallel}+\overline{{\mathbf{Q}}}^{(\epsilon)}_{\perp},$

where $\overline{{\mathbf{Q}}}^{(\epsilon)}_{\parallel}$ is the projection
onto the cone $\mathcal{K}_{\alpha}$, referred to as the parallel component,
and $\overline{{\mathbf{Q}}}^{(\epsilon)}_{\perp}$ is the remainder, referred
to as the perpendicular component, which is actually the projection onto the
polar cone $\mathcal{K}_{\alpha}^{\circ}$. Note that this decomposition is
well defined and unique since the cones $\mathcal{K}_{\alpha}$ and
$\mathcal{K}_{\alpha}^{\circ}$ are both closed and convex, which follows from
the fact that $\mathcal{K}_{\alpha}$ is finitely generated. The norm
$\big{\lVert}{\overline{{\mathbf{Q}}}^{(\epsilon)}_{\perp}}\big{\rVert}$ is
the distance between $\overline{{\mathbf{Q}}}^{(\epsilon)}$ and the cone
$\mathcal{K}_{\alpha}$. We say that the queue length process concentrates
around the cone $\mathcal{K}_{\alpha}$ if the moments of the distance
$\big{\lVert}{\overline{{\mathbf{Q}}}^{(\epsilon)}_{\perp}}\big{\rVert}$ are
upper bounded by constants. This motivates the following definition.

######  Definition 3 (State-space Collapse to $\mathcal{K}_{\alpha}$).

Given an $\alpha\in(0,1]$, we say the state-space of a load balancing system
collapses to the cone $\mathcal{K}_{\alpha}$ if

$\mathbb{E}\left[\left\lVert{\overline{{\mathbf{Q}}}^{(\epsilon)}_{\perp}}\right\rVert^{r}\right]\leq
M_{r}$ (4)

for all $\epsilon\in(0,\epsilon_{0})$, $\epsilon_{0}>0$ and for each
$r=1,2,\cdots$, in which $M_{r}$ are constants that are independent of
$\epsilon$.

######  Remark 1.

It is worth noting that although the result of state-space collapse is often
used as the key step in establishing heavy-traffic delay optimality, the upper
bound itself holds even when the system is not in the heavy-traffic limit, and
this can be of independent interest for analyzing the performance of the
system.

Now, we are ready to present our first main result.

######  Theorem 1.

Given a throughput optimal load balancing policy, if there exists an
$\alpha\in(0,1]$ such that the state-space collapses to the cone
$\mathcal{K}_{\alpha}$, then this policy is heavy-traffic delay optimal in
steady-state.

###### Proof.

See Section 4.1. ∎

Figure 1: A geometric illustration of the key insight of steady-state heavy-
traffic optimality in load balancing systems. In the figures above, we use the
gray area to represent the bounded distance between $\mathbf{Q}$ and the cone
$\mathcal{K}_{\alpha}$. The dashed line represents the total tasks in the
system and hence has order $1/\epsilon$. In (a), $\alpha=1$ and hence the
system state collapses to the one-dimensional line. As a result, the queue
lengths of two servers are nearly equal. However, Theorem 1 tells us that this
is not the key feature of heavy-traffic optimality since in (b) the queue
lengths difference between two servers,
$\lVert{\mathbf{Q}_{\perp}^{(\mathbf{1})}}\rVert$, is of the same order of
$\lVert\mathbf{Q}\rVert$. Rather, the key feature behind heavy-traffic
optimality is that it keeps all the servers busy when there is substantial
work. This is achieved by keeping the system state far away from the boundary
via state-space collapse, as $\epsilon$ approaches zero (see the distance $d$
in both (a) and (b)).

From this theorem, we can make the following important observations regarding
heavy-traffic delay optimality in load balancing systems. A geometric
illustration is presented in Fig. 1 to facilitate the understanding.

  1. (i)

If $\alpha=1$, then this theorem reduces to previous results on heavy-traffic
delay optimality under a single-dimensional state-space. In this case, the
state-space can be regarded as if it evolves in a one-dimensional subspace
where all queues are equal. This is because the queue-length difference
between servers is bounded by a constant and hence is substantially smaller
than the queue lengths themselves, which are on the order of $1/\epsilon$. See
Fig. 1(a).

  2. (ii)

This theorem tells us that in order to be heavy-traffic delay optimal, a
policy does not necessarily have to keep all the queues equal as in the case
of $\alpha=1$. This is because Theorem 1 implies that heavy-traffic delay
optimality is preserved even when the difference between the various queues is
of the same order as the queue lengths themselves, as shown in Fig. 1(b).
Therefore, this theorem indicates that the key feature of a heavy-traffic
delay optimal policy is that it keeps all the servers busy when there are
substantial tasks in the system. This is achieved by keeping system states far
away from the boundary via state-space collapse as $\epsilon$ approaches zero,
see the distance $d$ in Fig. 1.

  3. (iii)

It should also be pointed out that the cone $\mathcal{K}_{\alpha}$ in Theorem
1 is not necessarily the actual region that state-space collapses to. In fact,
this theorem tells us that for heavy-traffic delay optimality, the actual
region of state-space collapse, say $\mathcal{R}$, does not matter as long as
it lies within a cone $\mathcal{K}_{\alpha}$ for some $\alpha\in(0,1]$. This
is because in this case the distance to the cone $\mathcal{K}_{\alpha}$ is not
larger than that to the region $\mathcal{R}$. Thus, once it collapses to the
region $\mathcal{R}$, it also collapses to the cone $\mathcal{K}_{\alpha}$
according to Definition 3, and hence achieves heavy-traffic delay optimality.
This nice property may be of independent interest since it enables us to
establish heavy-traffic delay optimality even when the multi-dimensional
state-space collapse region is non-regular and non-convex.

Now, we turn to provide the high-level intuition on why Theorem 1 holds. To
start with, note that the following equation

$U_{n}(t)Q_{n}(t+1)=0$ (5)

holds for all $n$ and $t$. This follows directly from the queue dynamics in
Eq. (1). Thus, for the single-server resource-pooled system, when there is
positive unused service at time-slot $t$, the queue must be empty at time-slot
$t+1$. In contrast, for a load balancing system, due to the fact that a task
cannot be moved from one queue to another queue, there exist situations when
one queue, say $i$, has positive unused service, i.e., $U_{i}(t)>0$ and hence
$Q_{i}(t+1)=0$, while there are remaining tasks in other queues, i.e.,
$Q_{j}(t+1)>0$ for some $j$. As a result, the average queue length of the
resource-pooled system is the lower bound for the load balancing system.
Therefore, in order to achieve this lower bound (and hence heavy-traffic delay
optimality by definition), a load balancing policy should guarantee that when
one queue has positive unused service, all the other queues should be empty in
steady-state. In fact, this is actually the insight behind the sufficient and
necessary condition for heavy-traffic delay optimality in Lemma 3, i.e.,

$\lim_{\epsilon\downarrow
0}\mathbb{E}\left[\big{\lVert}\overline{{\mathbf{Q}}}^{(\epsilon)}(t+1)\big{\rVert}_{1}\big{\lVert}\overline{{\mathbf{U}}}^{(\epsilon)}(t)\big{\rVert}_{1}\right]=0.$
(6)

Next, let us take a closer look at the condition above. As a result of Eq.
(5), the left-hand side of Eq. (6) is always zero when all the queue lengths
are positive. This explains why it is not necessary to keep all the queue
lengths equal as in the case of single-dimensional state-space collapse.
Instead, what really matters in the condition is the situation when
$U_{i}(t)>0$ (and hence $Q_{i}(t+1)=0$) for some $i$. In this case, the
condition requires all the other queue lengths must be zero as well, i.e.,
$Q_{n}(t+1)=0$ for all $n$. In other words, it requires all the servers be
busy when there is substantial work, which is intuitively satisfied when the
queue length process collapses to the cone $\mathcal{K}_{\alpha}$ for any
$\alpha\in(0,1]$. This is because the cone is far away from the states where
some queue is empty while another queue is non-empty in heavy traffic. The
proof is presented in Section 4.1.

######  Remark 2.

We would remark on the choice of the particular form of cone
$\mathcal{K}_{\alpha}$, which provides further intuitions on Theorem 1. One
reason for the choice is that $\mathcal{K}_{\alpha}$ is finitely generated,
and hence it is closed and convex. This guarantees that the projection onto
this cone is well-defined and unique. Another more important reason is that
$\mathcal{K}_{\alpha}$ can approach the non-negative orthant while
guaranteeing that within the cone there are no ‘bad points’ where some queue
is empty and another queue is non-empty. This directly implies that once the
state-space collapses to the cone $\mathcal{K}_{\alpha}$, the condition in Eq.
(6) is satisfied. One might think of using an ‘ice-cream’ cone defined below
as a substitute of cone $\mathcal{K}_{\alpha}$,

$\displaystyle\mathcal{K}_{\theta}=\left\\{\mathbf{x}\in\mathbb{R}^{N}:\frac{\lVert{\mathbf{x}_{\parallel}^{(\mathbf{1})}}\rVert}{\left\lVert\mathbf{x}\right\rVert}\geq\cos(\theta)\right\\},$

where $\mathbf{x}_{\parallel}^{(\mathbf{1})}$ is the projection of
$\mathbf{x}$ onto the line $\mathbf{1}=(1,1,\ldots,1)$. The key problem with
such a choice is that in order to exclude all the ‘bad points’ from
$\mathcal{K}_{\theta}$ for a large system size $N$, the cone
$\mathcal{K}_{\theta}$ has to basically reduce to the line $\mathbf{1}$, and
hence does not provide us with any further flexibility. To see this, let us
start with $N=2$. In this case, the choice of $\mathcal{K}_{\theta}$ is fine
since it is able to approach the non-negative orthant as $\theta$ approaches
$\pi/4$, while guaranteeing that there are no bad points within the cone. In
fact, it is easy to see that in this case $\theta$ plays the same role as
$\alpha$ in $\mathcal{K}_{\alpha}$. Now, consider the case $N=3$. One might
choose $\theta<\arccos(1/\sqrt{3})$ in order to exclude the ‘bad points’ on
the axes from the cone $\mathcal{K}_{\theta}$. However, all the points on the
line $\mathbf{x}=(1,1,0)$ are also ‘bad points’. Thus, in order to exclude all
of these points, the choice of $\theta$ should be
$[0,\arccos(\sqrt{2}/\sqrt{3}))$. In general, for the $N$-dimension case, the
choice of $\theta$ should be less than $\arccos(\sqrt{N-1}/\sqrt{N})$, which
approaches zero for large $N$. Hence, for a large system size $N$, the cone
$\mathcal{K}_{\theta}$ has to approach the single-dimensional line
$\mathbf{1}$ in order to guarantee heavy-traffic delay optimality, which is
not interesting because it does not provide any significant flexibility
compared to the single-dimensional line. The insight of keeping all the
servers busy by excluding the ‘bad points’ when there is substantial work is
also useful for scheduling problems. For example, the cone considered in [18]
for the scheduling problem in a switch system contains infinitely many ‘bad
points’. It is actually due to this problem that the MaxWeight policy in this
case can only guarantee optimal scaling rather than heavy-traffic delay
optimality under the single-dimensional state-space collapse in [22], [7].

In contrast, the $\mathcal{K}_{\alpha}$ considered in our paper is able to
exclude all the ‘bad points’ for any $\alpha>0$ and hence guarantees heavy-
traffic delay optimality. This fact not only captures the essence of heavy-
traffic delay optimality in load balancing systems via multi-dimensional
state-space collapse, but also provides flexibility in analyzing and designing
new load balancing policies, which will be explored in the next section.

###  3.2 Flexible Load Balancing

In this section, instead of focusing on yet another policy, we step back and
explore the possibility provided by Theorem 1 in analyzing and more
importantly designing flexible load balancing policies that are both
throughput optimal and heavy-traffic delay optimal. This is motivated by the
fact that existing policies are often too restrictive and might not be easily
adopted to guarantee system performance in scenarios where _data locality_ or
_inaccurate_ information of queue lengths exist, which are common in load
balancing systems [29], [20].

Before we present our main result, let us first introduce some necessary
concepts. Let $P_{n}(t)$ be the probability that the new arrivals are
dispatched to the $n$th shortest queue at time-slot $t$. By the Markovian
assumption, the dispatching distribution $\mathbf{P}(t)$ can at most depend on
${\mathbf{Q}}(t)$. Let

$\Delta(t)=\mathbf{P}(t)-\mathbf{P}_{\text{rand}}(t),$ (7)

where $\mathbf{P}_{\text{rand}}(t)$ is the dispatching distribution under
uniform random routing (homogeneous case) or proportional random routing
(heterogeneous case), i.e., for homogeneous servers, each component of
$\mathbf{P}_{\text{rand}}(t)$ is $1/N$, and for heterogeneous servers the
$n$th component of $\mathbf{P}_{\text{rand}}(t)$ is
$\mu_{\sigma_{t}(n)}/\mu_{\Sigma}$ where $\sigma_{t}(n)$ is the index of the
$n$th shortest queue at time-slot $t$.

To facilitate the understanding of the concepts above, let us look at some
examples. Consider a load balancing system with four homogeneous servers.
Under uniform random routing, we have $\Delta(t)=(0,0,0,0)$ for each time-slot
$t$. Under the JSQ policy, the dispatcher always assigns the new arrival to
the shortest queue, and thus we have $\Delta(t)=(3/4,-1/4,-1/4,-1/4)$ for each
time-slot $t$. Under the power-of-$2$ policy, the dispatcher randomly picks
two servers and dispatches the new arrivals to the server with the shorter
queue length. It easily follows that $\Delta(t)=(1/4,1/12,-1/12,-1/4)$ for
each time-slot $t$. Note that, from these examples, we can see that a positive
value of $\Delta_{n}(t)$ means that the dispatcher favors the $n$th shortest
queue, while a non-positive value means the dispatcher disfavors the
corresponding queue. This is because $\Delta(t)$ equals $(0,0,0,0)$ under
uniform random routing, which has no preference over any queues.

Now, we are prepared to present our second main result, which characterizes
the degree of flexibility a load balancing policy enjoys while guaranteeing
throughput and heavy-traffic delay optimality.

######  Theorem 2.

Given a load balancing policy, if there exists a cone $\mathcal{K}_{\alpha}$
with $\alpha\in(0,1]$ such that for all
${\mathbf{Q}}(t)\notin\mathcal{K}_{\alpha}$, there is some
$k\in\\{2,\ldots,N\\}$ such that

$\Delta_{n}(t)\geq 0,n\leq k\text{ and }\Delta_{n}(t)\leq 0,n\geq k$ (8)

and

$\min\left(|\Delta_{1}(t)|,|\Delta_{N}(t)|\right)\geq\delta$ (9)

for some positive constant $\delta$ that is independent of $\epsilon$, then
this policy is both throughput and heavy-traffic delay optimal in steady-
state.

###### Proof.

See Section 4.2 ∎

######  Remark 3.

It can be easily seen that previous steady-state heavy-traffic delay optimal
policies, namely JSQ and power-of-$d$, satisfy the conditions in Theorem 2
with $\alpha=1$.

Before we turn to the technical aspects, let us first elaborate on the key
messages behind this theorem. In sum, this theorem characterizes the
flexibility in achieving throughput and heavy-traffic delay optimality from
the following two dimensions.

  1. (i)

The first dimension relates to the frequency of favoring shorter queues. This
can be seen from the fact that there are no requirements on $\Delta(t)$
whenever ${\mathbf{Q}}(t)$ falls in the cone $\mathcal{K}_{\alpha}$, and
$\alpha$ can be arbitrarily close to zero. This is significantly different
from previous heavy-traffic delay optimal policies, e.g., JSQ and power-
of-$d$. These policies have to favor shorter queues for every time-slot and
every system state. This is often too restrictive and may not be achievable,
especially when considering the data locality problem, since in this case the
dispatcher has to place tasks to servers that store the corresponding input
data chunks. In contrast, the above theorem tells us that a load balancing
policy has the flexibility to adopt any dispatching distribution whenever the
queue-length state falls in a region that can be covered by a cone
$\mathcal{K}_{\alpha}$ for some $\alpha\in(0,1]$. For example, for a load
balancing system with heterogeneous servers, the dispatcher can just use
uniform random routing when the system state lies within a cone
$\mathcal{K}_{\alpha}$, which provides us a lot of flexibility (e.g., easy
implementation and lower message overhead), compared to JSQ policy, and the
flexibility increases as $\alpha$ decreases. It is also worth noting that
although the delay optimality is preserved in heavy-traffic for any
$\alpha\in(0,1]$, the actual delay performance under medium or low loads might
get worse as $\alpha$ decreases in some cases. Thus, the parameter $\alpha$
also captures an important trade-off between flexibility and delay performance
under medium loads, which may be an interesting open problem to explore in the
future.

  2. (ii)

The second dimension is related to the intensity with which shorter queues are
favored. This can be seen from the conditions on $\Delta(t)$ in Eqs. (8) and
(9). Specifically, instead of joining only the shortest queue as in the JSQ
policy or having monotone decreasing probabilities from joining the shortest
queue to the longest queue in the power-of-d policy, an even weaker intensity
of favoring shorter queues is sufficient, and this intensity can be
characterized by the parameter $\delta$. This kind of flexibility is very
useful when the queue length information available at the dispatcher may be
inaccurate due to communication delay or sampling error.

We now highlight the technical contributions behind this theorem. Since this
theorem is proved based on Theorem 1, all we need to show are throughput
optimality and state-space collapse to the cone.

For throughput optimality, i.e., positive recurrence and bounded moments in
steady-state, the standard drift analysis of a suitable Lyapunov function is
very difficult in our case. This is because the drift within the cone
$\mathcal{K}_{\alpha}$ can be positive; hence, it is challenging from renewal
theory to find a sufficiently large $T$ such that the drift within $T$ time
slots is negative outside a finite set. On the other hand, the standard fluid
approximation method results only in positive recurrence. Our approach is to
combine fluid approximations with stochastic Lyapunov theory. In particular,
we show that the Lyapunov function used in the fluid model, i.e., the sum of
the queue lengths, is also a suitable Lyapunov function for the original
stochastic system. This connection allows us to carry out drift analysis in
the fluid domain, which makes it easier to find the $T$. Then, we come back to
the stochastic system and apply the drift analysis of the same Lyapunov
function in the stochastic system to show both positive recurrence and bounded
moments in steady-state. This approach also provides us with a good intuition
on throughput optimality in load balancing systems. Informally speaking, if
${\mathbf{Q}}(t)$ is in the cone $\mathcal{K}_{\alpha}$, the drift of the sum
queue lengths is of order $\epsilon$ towards the origin for any dispatching
distribution since there is no unused service. If ${\mathbf{Q}}(t)$ is outside
the cone $\mathcal{K}_{\alpha}$, it is easy to see that the dispatching
distribution in Theorem 2 is strictly better than random routing, and hence
enjoys a drift towards the origin. Therefore, the sum queue length will not go
to infinity in steady-state.

For the state-space collapse to the cone $\mathcal{K}_{\alpha}$, the standard
analysis adopted in the single-dimensional collapse also fails in this case.
This is because in contrast to the projection onto a line, the projection onto
a cone is very difficult. In fact, a closed-form formula of the projection
onto a polyhedral cone is still an open problem. To circumvent this
difficulty, instead of obtaining the exact projection, we are able to find an
important monotone property on the projection, which is sufficient to
establish a negative drift independent of $\epsilon$ along the direction of
${\mathbf{Q}}_{\perp}$ when the queue length state is outside the cone
$\mathcal{K}_{\alpha}$. This in turn indicates that the distance between the
system state and the cone $\mathcal{K}_{\alpha}$ cannot go to infinity as
$\epsilon$ approaches zero. Therefore, by definition, it establishes the
result of state-space collapse to the cone. Combining this with throughput
optimality yields heavy-traffic delay optimality according to Theorem 1.

######  Remark 4.

We would like to remark that the techniques used to prove Theorem 2 are of
independent interest and may have broader applicability. For example, we are
currently investigating whether this technique can be used to design a broader
class of heavy-traffic delay optimal scheduling policies.

###  3.3 Generalization

In the last section, we have shown that when it comes to designing a heavy-
traffic delay optimal load balancing policy, one has the flexibility of
choosing the frequency and intensity of favoring shorter queues, which are
parameterized by some fixed positive constants $\alpha$ and $\delta$,
respectively. In particular, smaller values of these two constants means
favoring the shorter queues less frequently and with less intensity. In this
section, we will show that these two constants can actually approach zero at a
certain rate with respect to the heavy-traffic parameter $\epsilon$ so that
the given policy can still guarantee heavy-traffic delay optimality. As a
result, we can exploit this fact to achieve even significant flexibility in
designing new policies.

######  Proposition 1.

Given a throughput optimal load balancing policy, if there exists a cone
$\mathcal{K}_{\alpha^{(\epsilon)}}$ such that for all
${\mathbf{Q}}(t)\notin\mathcal{K}_{\alpha^{(\epsilon)}}$, there is some
$k\in\\{2,\ldots,N\\}$ such that

$\Delta_{n}(t)\geq 0,n\leq k\text{ and }\Delta_{n}(t)\leq 0,n\geq k$ (10)

and

$\min\left(|\Delta_{1}(t)|,|\Delta_{N}(t)|\right)\geq\delta^{(\epsilon)}$ (11)

for some $\delta^{(\epsilon)}$. Suppose that $\alpha^{(\epsilon)}$ and
$\delta^{(\epsilon)}$ satisfy

$\displaystyle\alpha^{(\epsilon)}\delta^{(\epsilon)}=\Omega(\epsilon^{\beta})$

for some $\beta\in[0,1)$, then this policy is heavy-traffic delay optimal.

###### Proof.

See Appendix G. ∎

As before, a geometric view of the result of Proposition 1 is presented in
Fig. 2.

######  Remark 5.

It is worth pointing out that under the conditions of Proposition 1, state-
space collapse in this case is different from the one defined in Eq. (4). This
is because the moments of the distance between steady state and the cone
$\mathcal{K}_{\alpha}$ will go to infinity as $\epsilon$ approaches zero
rather than a constant bound in Eq. (4). This type of state-space collapse is
sometimes called multiplicative state-space collapse as in [14], [3], [24]. As
before, a geometric view of the result of Proposition 1 is presented in Fig.
2.

Figure 2: A geometric illustration of the result in Proposition 1. As before,
we use the gray area to represent the distance between $\mathbf{Q}$ and the
cone $\mathcal{K}_{\alpha}$. The dashed line represents the total tasks in the
system and hence has order $1/\epsilon$. As in Fig. 1, in order to guarantee
that all the servers are busy when there is substantial work in the system,
the distance $d$ should be large enough when $\epsilon$ goes to zero. To this
end, it is sufficient to require that the order of distance $m$ is smaller
than that of the distance $d^{\prime}$. It is easy to see
$\alpha^{(\epsilon)}\delta^{(\epsilon)}=\Omega(\epsilon^{\beta})$ for any
$\beta\in[0,1)$ satisfies this requirement.

##  4 Proofs

In this section, we present the proofs of Theorems 1 and 2, respectively.

###  4.1 Proof of Theorem 1

Before we present the proof, we first introduce the following lemma.

######  Lemma 2.

For any $\epsilon>0$ and $t\geq 0$, we have

$Q_{n}^{(\epsilon)}(t+1)U_{n}^{(\epsilon)}(t)=0.$

Moreover, if the system has a finite first moment, then we have for some
constants $c_{1}$ and $c_{r}$

$\mathbb{E}\left[\big{\lVert}\overline{{\mathbf{U}}}^{(\epsilon)}\big{\rVert}_{1}^{2}\right]\leq
c_{1}\epsilon\text{ and
}\mathbb{E}\left[\big{\lVert}\overline{{\mathbf{U}}}^{(\epsilon)}\big{\rVert}^{r}_{r}\right]\leq
c_{r}\epsilon,$

where $r\in(1,\infty)$.

###### Proof.

According to the queues dynamic in Eq. (1), we can see that when $U_{n}(t)$ is
positive, $Q_{n}(t+1)$ must be zero, which directly implies the result
$Q_{n}^{(\epsilon)}(t+1)U_{n}^{(\epsilon)}(t)=0$ for any $\epsilon>0$, $1\leq
n\leq N$ and $t\geq 0$. To show the second result, let us consider the
Lyapunov function
$W_{1}({\mathbf{Q}}(t))\triangleq\left\lVert{\mathbf{Q}}(t)\right\rVert_{1}$.
Since the system has a finite first moment, the mean drift of
$W_{1}({\mathbf{Q}})$ is zero in steady state, which gives

$\mathbb{E}\left[\big{\lVert}\overline{{\mathbf{U}}}^{(\epsilon)}\big{\rVert}_{1}\right]=\epsilon.$

Then, due to the fact that $U_{n}(t)\leq S_{\max}$ for all $1\leq n\leq N$ and
$t\geq 0$, we have
$\big{\lVert}\overline{{\mathbf{U}}}^{(\epsilon)}\big{\rVert}^{r}_{r}\leq(S_{\max})^{r-1}\big{\lVert}\overline{{\mathbf{U}}}^{(\epsilon)}\big{\rVert}_{1}$,
which implies that $c_{r}=(S_{\max})^{r-1}$. Note that
$\big{\lVert}\overline{{\mathbf{U}}}^{(\epsilon)}\big{\rVert}_{1}^{2}\leq
N\big{\lVert}\overline{{\mathbf{U}}}^{(\epsilon)}\big{\rVert}_{2}^{2}$, which
gives $c_{1}=NS_{\max}$. ∎

Now we are ready to prove Theorem 1.

###### Proof of Theorem 1.

We prove this theorem by combining the following lemma with the condition of
state-space collapse to the cone $\mathcal{K}_{\alpha}$. The proof of the
lemma is relegated to Appendix A.

######  Lemma 3.

For a throughput optimal policy, it is heavy-traffic delay optimal if and only
if

$\lim_{\epsilon\downarrow
0}\mathbb{E}\left[\big{\lVert}\overline{{\mathbf{Q}}}^{(\epsilon)}(t+1)\big{\rVert}_{1}\big{\lVert}\overline{{\mathbf{U}}}^{(\epsilon)}(t)\big{\rVert}_{1}\right]=0.$
(12)

Next, we will show that under the condition that the state space collapses to
a cone $\mathcal{K}_{\alpha}$ with $\alpha\in(0,1]$, the condition in Eq. (12)
holds. For brevity, we will omit the references $t$ and $\epsilon$, and use
$\overline{{\mathbf{Q}}}^{+}$ to denote $\overline{{\mathbf{Q}}}(t+1)$ in the
following. First, we have

$\displaystyle\mathcal{T}^{(\epsilon)}$
$\displaystyle\triangleq\mathbb{E}\left[\big{\lVert}\overline{{\mathbf{Q}}}^{(\epsilon)}(t+1)\big{\rVert}_{1}\big{\lVert}\overline{{\mathbf{U}}}^{(\epsilon)}(t)\big{\rVert}_{1}\right]$
$\displaystyle=\mathbb{E}\left[\sum_{i=1}^{N}\overline{U}_{i}\left(\sum_{j=1}^{N}\overline{Q}_{j}^{+}\right)\right]$
$\displaystyle=\mathbb{E}\left[\sum_{i=1}^{N}\overline{U}_{i}\left(\sum_{j=1}^{N}\left(\overline{Q}_{\parallel
j}^{+}+\overline{Q}_{\perp j}^{+}\right)\right)\right],$ (13)

where $\overline{Q}_{\parallel j}^{+}$ is the $j$-th component of
$(\overline{{\mathbf{Q}}}^{+})_{\parallel}$ and similarly $\overline{Q}_{\perp
j}^{+}$ is the $j$-th component of $(\overline{{\mathbf{Q}}}^{+})_{\perp}$.
For simplicity, we use $\overline{{\mathbf{Q}}}_{\parallel}^{+}$ to denote
$(\overline{{\mathbf{Q}}}^{+})_{\parallel}$ and
$\overline{{\mathbf{Q}}}_{\perp}^{+}$ to denote
$(\overline{{\mathbf{Q}}}^{+})_{\perp}$, respectively. Since the vector
$\overline{{\mathbf{Q}}}_{\parallel}^{+}$ is in cone $\mathcal{K}_{\alpha}$ by
definition, there exist non-negative weights $w_{1},\ldots,w_{N}$ such that
$\overline{{\mathbf{Q}}}_{\parallel}^{+}=\sum w_{n}\mathbf{b}^{(n)}$. Recall
that when $U_{n}(t)>0$, $Q_{n}(t+1)=0$ by Lemma 2. Thus, when
$\overline{U}_{i}(t)>0$, we have

$\displaystyle\overline{Q}_{i}^{+}$ $\displaystyle=0$
$\displaystyle\overline{Q}_{\parallel i}^{+}$
$\displaystyle=-\overline{Q}_{\perp i}^{+}$ $\displaystyle\sum
w_{n}b^{(n)}_{i}$ $\displaystyle=\overline{Q}_{\parallel i}^{+}$
$\displaystyle\sum w_{n}b^{(n)}_{j}$ $\displaystyle=\overline{Q}_{\parallel
j}^{+}\leq\frac{1}{\alpha}\overline{Q}_{\parallel i}^{+}\text{ for all }j\neq
i$

The last inequality follows from the definition of vector $\mathbf{b}^{(n)}$.
Therefore, the term $\mathcal{T}$ in Eq. (4.1) can be upper bounded as
follows.

$\displaystyle\mathcal{T}^{(\epsilon)}$
$\displaystyle\mathop{\leq}\limits^{(a)}\mathbb{E}\left[\sum_{i}\overline{U}_{i}\left(-N_{1}\overline{Q}_{\perp
i}^{+}+\sum_{j}\overline{Q}_{\perp j}^{+}\right)\right]$
$\displaystyle=\mathbb{E}\left[\langle\overline{{\mathbf{U}}},-N_{1}\overline{{\mathbf{Q}}}^{+}_{\perp}\rangle\right]+\mathbb{E}\left[\langle\overline{{\mathbf{U}}},\langle\mathbf{1},\overline{{\mathbf{Q}}}^{+}_{\perp}\rangle\mathbf{1}\rangle\right]$
$\displaystyle\mathop{\leq}\limits^{(b)}\mathbb{E}\left[\langle\overline{{\mathbf{U}}},-N_{1}\overline{{\mathbf{Q}}}^{+}_{\perp}\rangle\right]$
$\displaystyle\mathop{\leq}\limits^{(c)}N_{1}\sqrt{\mathbb{E}\left[\left\lVert\overline{{\mathbf{U}}}\right\rVert^{2}\right]\mathbb{E}\left[\left\lVert\overline{{\mathbf{Q}}}^{+}_{\perp}\right\rVert^{2}\right]}.$
$\displaystyle\mathop{\leq}\limits^{(d)}N_{1}\sqrt{c_{2}\epsilon M_{2}}$ (14)

where in (a) $N_{1}=N/\alpha$; (b) comes from the non-negativity of
$\overline{{\mathbf{U}}}$ and the fact that
$\langle\mathbf{1},\overline{{\mathbf{Q}}}^{+}_{\perp}\rangle\leq 0$ since
$\mathbf{1}\in\mathcal{K}_{\alpha}$ and
${\overline{{\mathbf{Q}}}^{+}_{\perp}}\in\mathcal{K}_{\alpha}^{\circ}$; (c) is
the result of Cauchy-Schwartz inequality for random vectors; (d) holds because
of Lemma 2 and the definition of state-space collapse in Eq. (4) combined with
the fact that ${\mathbf{Q}}(t+1)$ and ${\mathbf{Q}}(t)$ have the same
distribution in steady-state. Since $c_{2}$, $M_{2}$ and $N_{1}$ are all
constants that are independent of $\epsilon$, we have $\lim_{\epsilon\to
0}\mathcal{T}^{(\epsilon)}=0$, which establishes the result in Eq. (12), and
hence heavy-traffic delay optimality. ∎

###  4.2 Proof of Theorem 2

As already pointed out, the proof of Theorem 2 naturally falls into two parts:
throughput optimality and state-space collapse. Then, it follows directly from
Theorem 1 that the result in Theorem 2 is true. In both proofs, we will use
the Lyapunov drift-based approach developed in [7] to derive bounded moments
in steady state. The following lemma is a $T$-step version of Lemmas 2 and 3
in [18]. This lemma could be proved by simply replacing the one-step
transition probability to $T$-step transition probability, and hence we omit
the proof here.

######  Lemma 4.

For an irreducible aperiodic and positive recurrent Markov chain
$\\{X(t),t\geq 0\\}$ over a countable state space $\mathcal{X}$, which
converges in distribution to $\overline{X}$, and suppose
$V:\mathcal{X}\rightarrow\mathbb{R}_{+}$ is a Lyapunov function. We define the
$T$ time-slot drift of $V$ at $X$ as

$\Delta V(X)\triangleq[V(X(t_{0}+T))-V(X(t_{0}))]\mathcal{I}(X(t_{0})=X),$

where $\mathcal{I}(.)$ is the indicator function. Suppose for some positive
finite integer $T$, the $T$ time-slot drift of $V$ satisfies the following
conditions:

  * •

(C1) There exists an $\eta>0$ and a $\kappa<\infty$ such that for any
$t_{0}=1,2,\ldots$ and for all $X\in\mathcal{X}$ with $V(X)\geq\kappa$,

$\mathbb{E}\left[\Delta V(X)\mid X(t_{0})=X\right]\leq-\eta.$

  * •

(C2) There exists a constant $D<\infty$ such that for all $X\in\mathcal{X}$,

$\mathbb{P}(|\Delta V(X)|\leq D)=1.$

Then $\\{V(X(t)),t\geq 0\\}$ converges in distribution to a random variable
$\overline{V}$, and all moments of $\overline{V}$ exist and are finite. More
specifically, we have for any $r=1,2,\ldots$

$\mathbb{E}\left[V(\overline{X})^{r}\right]\leq(2\kappa)^{r}+(4D)^{r}\left(\frac{D+\eta}{\eta}\right)^{r}r!.$
(15)

####  4.2.1 Throughput Optimality

We would prove the following result in this subsection.

######  Proposition 2.

Under the condition of Theorem 2, the given policy is throughput optimal.

We would prove this result by combining fluid approximations with stochastic
Lyapunov theory. Thus, let us first introduce some necessary notations and
useful lemmas. In order to distinguish from stochastic analysis, we define
$\mathcal{X}\triangleq(\mathcal{X}(t),t=0,1,2,\ldots)$, in which
$\mathcal{X}(t)\triangleq(Q_{1}(t),Q_{2}(t),\ldots,Q_{n}(t))$ in fluid domain.
Then under our assumption and the queue-length based policy,
$\mathcal{X}=(\mathcal{X}(t),t=0,1,2,\ldots)$ is a discrete-time countable
Markov chain. That is, the system state is denoted by $\mathcal{X}$ in the
fluid approximation analysis. To establish the fluid model of $\mathcal{X}$,
we need several notations. Let us define the norm of $\mathcal{X}(t)$ as
$\left\lVert\mathcal{X}(t)\right\rVert_{1}\triangleq\sum_{n=1}^{N}Q_{n}(t)$.
Let $\mathcal{X}^{(x)}$ denote a process $\mathcal{X}$ with an initial state
satisfying

$\left\lVert\mathcal{X}^{(x)}(0)\right\rVert_{1}=x.$ (16)

Let $\mathcal{A}_{i}(t)$ and $\mathcal{D}_{i}(t)$ denote the accumulated
arrival and actual departure tasks at queue $i$ up to time-slot $t$,
respectively. $\mathcal{A}_{\Sigma}(\tau)$ denotes the accumulated exogenous
arrivals for a given $\tau$ units of time-slots. $\mathcal{S}_{i}(\tau)$
denotes the accumulated offered service for queue $i$ during a given $\tau$
units of time-slots. Moreover, let $\mathcal{G}_{i}(t)$ denote the accumulated
number of time-slots up to time-slot $t$ in which the new arrivals are routed
to queue $i$, and let
$\mathcal{B}_{i}(t)\triangleq\sum_{0}^{t}1\\{Q_{i}(s)>0\\}$ denote the
accumulated number of time-slots up to time-slot $t$ in which queue $i$ is
busy. We also adopt the convention that $\mathcal{A}_{i}(0)=0$,
$\mathcal{D}_{i}(0)=0$, $\mathcal{G}_{i}(0)=0$ and $\mathcal{B}_{i}(0)=0$.
Therefore, we have
$\mathcal{A}_{i}(t)=\mathcal{A}_{\Sigma}(G_{i}(t))\leq\mathcal{A}_{\Sigma}(t)$
and
$\mathcal{D}_{i}(t)=\mathcal{S}_{i}(\mathcal{B}_{i}(t))\leq\mathcal{S}_{i}(t)$.
Then the queue length $Q_{i}$ can be described in an alternative form as
follows

$Q_{i}(t)=Q_{i}(0)+\mathcal{A}_{i}(t)-\mathcal{D}_{i}(t).$ (17)

Let us define another process
$\mathcal{Y}\triangleq(Q,\mathcal{A},\mathcal{D},\mathcal{A}_{\Sigma},\mathcal{S},\mathcal{G},\mathcal{B})$,
i.e., a tuple that denotes a list of processes, and clearly, a sample path of
$\mathcal{Y}^{(x)}$ uniquely determines the sample path of
$\mathcal{X}^{(x)}$. Then, we extend the definition of $\mathcal{Y}$ to each
continuous time $t\geq 0$ as
$\mathcal{Y}^{(x)}(t)\triangleq\mathcal{Y}^{(x)}(\lfloor t\rfloor)$. Recall
that a sequence of functions $f_{n}(\cdot)$ is said to converge to a function
$f(\cdot)$ uniformly over compact (u.o.c) interval if for all $t\geq 0$,
$\lim_{n\to\infty}\sup_{0\leq t^{\prime}\leq
t}\left|f_{n}(t^{\prime})-f(t^{\prime})\right|=0$. We now consider a sequence
of process
$\left\\{\frac{1}{x_{n}}\mathcal{Y}^{(x_{n})}(x_{n}\cdot)\right\\}$, which is
scaled both in time and space, and show the convergence properties of the
sequence in the following lemma.

######  Lemma 5.

With probability one, for any sequence of the process
$\\{\frac{1}{x_{n}}\mathcal{Y}^{(x_{n})}(x_{n}\cdot)\\}$, where $x_{n}$ is a
sequence of positive integers with $x_{n}\to\infty$, there exists a
subsequence $x_{n_{k}}$ with $x_{n_{k}}\to\infty$ as $k\to\infty$ such that
the following u.o.c convergences hold:

$\frac{1}{x_{n_{k}}}{Q}_{i}^{(x_{n_{k}})}(x_{n_{k}}t)\to q_{i}(t)$ (18)
$\frac{1}{x_{n_{k}}}{\mathcal{A}}_{i}^{(x_{n_{k}})}(x_{n_{k}}t)\to a_{i}(t)$
(19) $\frac{1}{x_{n_{k}}}{\mathcal{D}}_{i}^{(x_{n_{k}})}(x_{n_{k}}t)\to
d_{i}(t)$ (20)
$\frac{1}{x_{n_{k}}}{\mathcal{A}}_{\Sigma}^{(x_{n_{k}})}(x_{n_{k}}t)\to
a_{\Sigma}(t)$ (21)
$\frac{1}{x_{n_{k}}}{\mathcal{S}}_{i}^{(x_{n_{k}})}(x_{n_{k}}t)\to s_{i}(t)$
(22) $\frac{1}{x_{n_{k}}}{\mathcal{G}}_{i}^{(x_{n_{k}})}(x_{n_{k}}t)\to
g_{i}(t)$ (23)
$\frac{1}{x_{n_{k}}}{\mathcal{B}}_{i}^{(x_{n_{k}})}(x_{n_{k}}t)\to b_{i}(t)$
(24)

where $q_{i}$, $a_{i}$, $d_{i}$, $a_{\Sigma}$, $s_{i}$, $g_{i}$ and $b_{i}$
are some Lipschitz continuous functions in $[0,\infty)$. Hence all the
functions are differentiable at almost every time $t\in[0,\infty)$, which is
called regular time.

###### Proof.

See Appendix B. ∎

The fluid model of our considered load balancing system is given by the
following lemma. Note that the fluid model holds for any work-conserving FIFO
and queue-length based policy.

######  Lemma 6.

Any fluid limit $(q_{i},a_{i},d_{i},a_{\Sigma},s_{i},g_{i},b_{i})$ satisfies
the following equations

$q_{i}(t)=q_{i}(0)+a_{i}(t)-d_{i}(t)$ (25) $a_{i}(t)=\lambda g_{i}(t)$ (26)
$d_{i}(t)=\mu_{i}b_{i}(t)$ (27) $a_{\Sigma}(t)=\lambda t$ (28)
$s_{i}(t)=\mu_{i}t$ (29) $\sum_{i}^{n}g_{i}(t)=t$ (30)

and for any regular time $t$, we have

$q_{i}^{\prime}(t)=\begin{cases}\lambda
g_{i}^{\prime}(t)-\mu_{i},&q_{i}(t)>0.\\\ 0,&q_{i}(t)=0.\\\ \end{cases}$ (31)

###### Proof.

See Appendix C. ∎

Now we are well prepared to present the proof of Proposition 2 on throughput
optimality.

###### Proof of Proposition 2.

First, recall the permutation $\sigma_{t}(\cdot)$ of $(1,2,\ldots,N)$ which
satisfies $Q_{\sigma_{t}(1)}(t)\leq Q_{\sigma_{t}(2)}(t)\leq\ldots
Q_{\sigma_{t}(N)}(t)$ and ties are broken randomly. Now we can establish the
following claim, the proof of which is relegated to Appendix D.

######  Claim 1.

If
$q_{\sigma_{t}(1)}(t)=q_{\sigma_{t}(2)}(t)=q_{\sigma_{t}(m)}(t)=0<q_{\sigma_{t}(m+1)}(t)\leq\ldots\leq
q_{\sigma_{t}(N)}(t)$ for some $1\leq m<N$, then

$\sum_{n=m+1}^{N}g^{\prime}_{\sigma_{t}(n)}=\sum_{n=m+1}^{N}\left(\Delta_{n}(t)+\frac{\mu_{\sigma_{t}(n)}}{\mu_{\Sigma}}\right),$

and $\Delta(t)$ satisfies the conditions in Eq. (8) and Eq. (9) of Theorem 2.

Now, let us consider a Lyapunov function $V(\mathbf{z})\triangleq\left\lVert
z\right\rVert_{1}$. We would like to show that $\dot{V}(\mathbf{q}(t))\leq-l$
for some constant $l>0$ whenever $V(\mathbf{q}(t))>0$. There are two cases to
consider.

Case 1: $q_{i}(t)>0$ for all $i\in\\{0,1,\ldots,N\\}$.

In this case, by Eqs. (31) and (30), we have

$\dot{V}(\mathbf{q}(t))=\sum_{n=1}^{N}q_{n}^{\prime}(t)=\lambda(\sum_{n=1}^{N}g_{n}^{\prime}(t))-\sum_{n=1}^{N}\mu_{i}=\lambda-\sum_{n=1}^{N}\mu_{n}=-\epsilon.$
(32)

Case 2: For some $1\leq m<N$,
$q_{\sigma_{t}(1)}(t)=q_{\sigma_{t}(2)}(t)=q_{\sigma_{t}(m)}(t)=0<q_{\sigma_{t}(m+1)}(t)\leq\ldots\leq
q_{\sigma_{t}(N)}(t)$.

In this case, we have

$\displaystyle\dot{V}(\mathbf{q}(t))$
$\displaystyle\mathop{=}\limits^{(a)}\sum_{n=m+1}^{N}q_{n}^{\prime}(t)$
$\displaystyle\mathop{=}\limits^{(b)}\sum_{n=m+1}^{N}\lambda\left(\Delta_{n}(t)+\frac{\mu_{\sigma_{t}(n)}}{\mu_{\Sigma}}\right)-\sum_{n=m+1}^{N}\mu_{\sigma_{t}(n)}$
$\displaystyle\mathop{\leq}\limits^{(c)}\sum_{n=m+1}^{N}\lambda\frac{\mu_{\sigma_{t}(n)}}{\mu_{\Sigma}}-\sum_{n=m+1}^{N}\mu_{\sigma_{t}(n)}$
$\displaystyle\mathop{\leq}\limits^{(d)}-\epsilon\frac{\mu_{\min}}{\mu_{\Sigma}}$

where (a) comes from Eq. (31); (b) follows from Claim 1; (c) holds due to the
fact that $\sum_{n=m+1}^{N}\Delta_{n}(t)\leq 0$ when $\Delta(t)$ satisfies
Eqs. (8) and (9); (d) is true since $\lambda=\mu_{\Sigma}-\epsilon$ and
$\mu_{\min}=\min_{1\leq n\leq N}(\mu_{n})$.

Therefore, combining the above two cases, yields

$\dot{V}(\mathbf{q}(t))\leq-l\text{ whenever }V(\mathbf{q}(t))>0$

where $l\triangleq-\epsilon\mu_{\min}/\mu_{\Sigma}>0$. This result implies
that for any $\gamma\in(0,1)$, there exists a finite $T$ such that
$V(\mathbf{q}(T))\leq\gamma$. Now, consider any fixed sequence of processes
$\\{\mathcal{X}^{(x)},x=1,2,\ldots\\}$ (for simplicity also denoted as
$\\{x\\}$). Then, from the convergence in Lemma 5, we have that for any
subsequence $\\{x_{n}\\}$ of $\\{x\\}$, there exists a further
(sub)subsequence $\\{x_{n_{k}}\\}$ with probability one such that

$\lim_{k\to\infty}\frac{1}{x_{n_{k}}}\left\lVert\mathcal{X}^{(x_{n_{k}})}(x_{n_{k}}T)\right\rVert_{1}=\sum_{i}^{n}|q_{i}(T)|\leq\gamma\triangleq
1-\xi.$

This further implies that with probability one,

$\limsup_{x\to\infty}\left[\frac{1}{x}\left\lVert\mathcal{X}^{(x)}(xT)\right\rVert_{1}\right]\leq
1-\xi$

holds, because there is always a subsequence of $\\{x\\}$ that converges to
the same limit as
$\limsup_{x\to\infty}\left[\frac{1}{x}\left\lVert\mathcal{X}^{(x)}(xT)\right\rVert_{1}\right].$

According to Eq. (17), we have
$\left\lVert\mathcal{X}^{(x)}(xT)\right\rVert_{1}\leq
x+\sum_{i=1}^{N}\mathcal{A}_{i}(xT)$. Hence,

$\mathbb{E}\left[\frac{1}{x}\left\lVert\mathcal{X}^{(x)}(xT)\right\rVert_{1}\right]\leq
1+\lambda T\leq\infty.$

Therefore, from the dominated convergence theorem, we have

$\limsup_{x\to\infty}\mathbb{E}\left[\frac{1}{x}\left\lVert\mathcal{X}^{(x)}(xT)\right\rVert_{1}\right]=\mathbb{E}\left[\limsup_{x\to\infty}\frac{1}{x}\left\lVert\mathcal{X}^{(x)}(xT)\right\rVert_{1}\right]\leq
1-\xi.$

This result in turn implies that there exists an $x_{0}$ such that for all
$x=\left\lVert\mathcal{X}^{(x)}(0)\right\rVert_{1}\geq x_{0}$

$\mathbb{E}\left[\left\lVert\mathcal{X}^{(x)}(xT)\right\rVert_{1}-\left\lVert\mathcal{X}^{(x)}(0)\right\rVert_{1}\right]\leq-\frac{\xi
x_{0}}{2}.$ (33)

Now, let us turn to the stochastic analysis of the Lyapunov drift. In
particular, we consider the mean drift of Lyapunov function
$V({\mathbf{Q}}(t))=\left\lVert{\mathbf{Q}}(t)\right\rVert_{1}$. We need to
show that the Lyapunov function $V(.)$ satisfies the conditions (C1) and (C2)
in Lemma 4, respectively.

For Condition (C2), we have

$\begin{split}|\Delta
V({\mathbf{Q}})|&=\big{|}\left\lVert{\mathbf{Q}}(t_{0}+T)\right\rVert_{1}-\left\lVert{\mathbf{Q}}(t_{0})\right\rVert_{1}\big{|}\mathcal{I}({\mathbf{Q}}(t_{0})={\mathbf{Q}})\\\
&\mathop{\leq}\limits^{(a)}\left\lVert{\mathbf{Q}}(t_{0}+T)-{\mathbf{Q}}(t_{0})\right\rVert_{1}\mathcal{I}({\mathbf{Q}}(t_{0})={\mathbf{Q}})\\\
&\mathop{\leq}\limits^{(b)}TN\max(A_{\max},S_{\max})\end{split}$

where (a) follows from the fact that $|\left\lVert{\bf
x}\right\rVert_{1}-\left\lVert{\bf y}\right\rVert_{1}|\leq\left\lVert{\bf
x}-{\bf y}\right\rVert_{1}$ holds for any ${\bf x}$, ${\bf
y}\in\mathbb{R}^{N}$; (b) holds due to the assumptions that the
$A_{\Sigma}(t)\leq A_{\max}$ and $S_{n}(t)\leq S_{\max}$ for all $t\geq 0$ and
all $1\leq n\leq N$, and are independent of the queue length. This establishes
the condition (C2) in Lemma 4.

For Condition (C1), we have

$\displaystyle\mathbb{E}\left[\Delta
V({{\mathbf{Q}}})\mid{\mathbf{Q}}(t_{0})={\mathbf{Q}}\right]$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[\left\lVert{\mathbf{Q}}(t_{0}+T_{1})\right\rVert_{1}-\left\lVert{\mathbf{Q}}(t_{0})\right\rVert_{1}\mid{\mathbf{Q}}(t_{0})={\mathbf{Q}}\right]$
$\displaystyle\mathop{=}\limits^{(a)}$
$\displaystyle\mathbb{E}\left[\left\lVert{\mathbf{Q}}(T_{1})\right\rVert_{1}-\left\lVert{\mathbf{Q}}(0)\right\rVert_{1}\mid{\mathbf{Q}}(0)={\mathbf{Q}}\right]$
$\displaystyle\mathop{\leq}\limits^{(b)}$ $\displaystyle-\frac{\xi x_{0}}{2}$

where (a) follows from the i.i.d assumption of exogenous arrival and service,
and the system is Markovian with respect to the vector of queue lengths; (b)
holds for $T_{1}=x_{0}T$ and $V({\mathbf{Q}}(0))\geq x_{0}$. This directly
comes from Eq. (33) and the fact
$\left\lVert\mathcal{X}(t)\right\rVert_{1}=\sum_{n=1}^{N}Q_{n}(t)$. Hence, it
establishes the condition (C1) in Lemma 4, and thus throughput optimality. ∎

####  4.2.2 State-space Collapse to Cone

We would prove the following result in this subsection, which combined with
the throughput optimality in the last subsection directly implies heavy-
traffic delay optimality according to Theorem 1.

######  Proposition 3.

Under the condition of Theorem 2, the state-space in steady-state collapses to
the cone $\mathcal{K}_{\alpha}$, i.e., there exists
$\epsilon_{0}={\mu_{\Sigma}\delta}/{(4N+2\delta)}$ such that for all
$\epsilon\in(0,\epsilon_{0})$

$\mathbb{E}\left[\left\lVert{\overline{{\mathbf{Q}}}^{(\epsilon)}_{\perp}}\right\rVert^{r}\right]\leq
M_{r}$ (34)

holds for each $r=1,2,\cdots$, in which $M_{r}$ are constants that are
independent of $\epsilon$.

Before we prove Proposition 3, we first define the following Lyapunov
functions and their corresponding drifts.

$V_{\perp}({\mathbf{Q}})\triangleq\left\lVert{\mathbf{Q}}_{\perp}\right\rVert,W({\mathbf{Q}})\triangleq\left\lVert{\mathbf{Q}}\right\rVert^{2}\text{
and
}W_{\parallel}({\mathbf{Q}})\triangleq\left\lVert{\mathbf{Q}}_{\parallel}\right\rVert^{2}$

with the corresponding one time-slot drift given by

$\begin{split}&\Delta
V_{\perp}({\mathbf{Q}})\triangleq[V_{\perp}({\mathbf{Q}}(t_{0}+1))-V_{\perp}({\mathbf{Q}}(t_{0}))]\mathcal{I}({\mathbf{Q}}(t_{0})={\mathbf{Q}})\\\
&\Delta
W({\mathbf{Q}})\triangleq[W({\mathbf{Q}}(t_{0}+1))-W({\mathbf{Q}}(t_{0}))]\mathcal{I}({\mathbf{Q}}(t_{0})={\mathbf{Q}})\\\
&\Delta
W_{\parallel}({\mathbf{Q}})\triangleq[W_{\parallel}({\mathbf{Q}}(t_{0}+1))-W_{\parallel}({\mathbf{Q}}(t_{0}))]\mathcal{I}({\mathbf{Q}}(t_{0})={\mathbf{Q}})\\\
\end{split}$

Now, we are ready to prove Proposition 3.

###### Proof of Proposition 3.

To establish the bounded moments of
$\left\lVert{\mathbf{Q}}_{\perp}\right\rVert$, based on Lemma 4, all we need
to show is that the the drift of Lyapunov function $V_{\perp}(.)$ satisfies
the two conditions for all $\epsilon\in(0,\epsilon_{0})$. For condition (C2),
we have

$\displaystyle|\Delta V_{\perp}({\mathbf{Q}})|$ $\displaystyle=$
$\displaystyle|\left\lVert{\mathbf{Q}}_{\perp}(t_{0}+1)\right\rVert-\left\lVert{\mathbf{Q}}_{\perp}(t_{0})\right\rVert|\mathcal{I}({\mathbf{Q}}(t_{0})={\mathbf{Q}})$
$\displaystyle\mathop{\leq}\limits^{(a)}$
$\displaystyle\left\lVert{\mathbf{Q}}_{\perp}(t_{0}+1)-{\mathbf{Q}}_{\perp}(t_{0})\right\rVert\mathcal{I}({\mathbf{Q}}(t_{0})={\mathbf{Q}})$
$\displaystyle\mathop{\leq}\limits^{(b)}$
$\displaystyle\left\lVert{\mathbf{Q}}(t_{0}+1)-{\mathbf{Q}}(t_{0})\right\rVert\mathcal{I}({\mathbf{Q}}(t_{0})={\mathbf{Q}})$
$\displaystyle\mathop{\leq}\limits^{(c)}$
$\displaystyle\sqrt{N}\max(A_{\max},S_{\max})$ (35)

where (a) follows from the fact that $|\left\lVert{\bf
x}\right\rVert-\left\lVert{\bf y}\right\rVert|\leq\left\lVert{\bf x}-{\bf
y}\right\rVert$ holds for any ${\bf x}$, ${\bf y}\in\mathbb{R}^{N}$; (b)
follows from the non-expansive property of projection and the fact that
${\mathbf{Q}}_{\perp}$ is the projection onto the convex closed cone
$\mathcal{K}_{\alpha}^{\circ}$. (c) holds due to the assumptions that the
$A_{\Sigma}(t)\leq A_{\max}$ and $S_{n}(t)\leq S_{\max}$ for all $t\geq 0$ and
all $1\leq n\leq N$, and are both independent of queue lengths. This verifies
Condition (C2) in Lemma 4.

For condition (C1), we need the following result, the proof of which is
relegated to Appendix E.

######  Claim 2.

For any $t\geq 0$, we have

$\begin{split}&\mathbb{E}\left[\Delta
V_{\perp}({\mathbf{Q}})\mid{\mathbf{Q}}(t)={\mathbf{Q}}\right]\\\
\leq&\frac{1}{2\left\lVert{\mathbf{Q}}_{\perp}(t)\right\rVert}\mathbb{E}\left[\left(2\langle{\mathbf{Q}}_{\perp}(t),{\mathbf{A}}(t)-{\mathbf{S}}(t)\rangle+L\right)\mid{\mathbf{Q}}(t)={\mathbf{Q}}\right]\end{split}$

where $L\triangleq N\max(A_{\max},S_{\max})^{2}$.

Thus, based on Claim 2, in order to establish condition (C1) for all
$\epsilon\in(0,\epsilon_{0})$, it suffices to show

$\mathbb{E}\left[\langle{\mathbf{Q}}_{\perp}(t),{\mathbf{A}}(t)-{\mathbf{S}}(t)\rangle\mid{\mathbf{Q}}(t)={\mathbf{Q}}\right]\leq-c\left\lVert{\mathbf{Q}}_{\perp}(t)\right\rVert$
(36)

holds for all $\epsilon\in(0,\epsilon_{0})$, and $c$ is independent of
$\epsilon$.

To this end, first recall the permutation $\sigma_{t}(\cdot)$ of
$(1,2,\ldots,N)$ which satisfies $Q_{\sigma_{t}(1)}(t)\leq
Q_{\sigma_{t}(2)}(t)\leq\ldots Q_{\sigma_{t}(N)}(t)$ and ties are broken
randomly. In the following, for simplicity of notation, we let
$\widehat{{\mathbf{Q}}}(t)=(Q_{\sigma_{t}(1)}(t),Q_{\sigma_{t}(2)}(t),\ldots,Q_{\sigma_{t}(N)}(t))$,
and similarly the arrival process
$\widehat{{\mathbf{A}}}(t)=(A_{\sigma_{t}(1)}(t),A_{\sigma_{t}(2)}(t),\ldots,A_{\sigma_{t}(N)}(t))$
and the service vector
$\widehat{{\mathbf{S}}}(t)=(S_{\sigma_{t}(1)}(t),S_{\sigma_{t}(2)}(t),\ldots,S_{\sigma_{t}(N)}(t))$.
Now, the left-hand-side of Eq. (36) can be written as follows.

$\displaystyle\mathbb{E}\left[\langle{\mathbf{Q}}_{\perp}(t),{\mathbf{A}}(t)-{\mathbf{S}}(t)\rangle\mid{\mathbf{Q}}(t)={\mathbf{Q}}\right]$
$\displaystyle\mathop{=}\limits^{(a)}$
$\displaystyle\mathbb{E}\left[\langle\widehat{{\mathbf{Q}}}_{\perp}(t),\widehat{{\mathbf{A}}}(t)-\widehat{{\mathbf{S}}}(t)\rangle\mid{\mathbf{Q}}(t)={\mathbf{Q}}\right]$
$\displaystyle\mathop{=}\limits^{(b)}$
$\displaystyle\sum_{n=1}^{N}\widehat{Q}_{\perp
n}\left[\lambda_{\Sigma}\left(\Delta_{n}(t)+\frac{\mu_{\sigma_{t}(n)}}{\mu_{\Sigma}}\right)-\mu_{\sigma_{t}(n)}\right]$
$\displaystyle\mathop{=}\limits^{(c)}$
$\displaystyle\sum_{n=1}^{N}\widehat{Q}_{\perp
n}\Delta_{n}(t)\lambda_{\Sigma}+\sum_{n=1}^{N}\widehat{Q}_{\perp,n}\left(-\epsilon\frac{\mu_{\sigma_{t}(n)}}{\mu_{\Sigma}}\right)$
$\displaystyle\leq$ $\displaystyle\sum_{n=1}^{N}\widehat{Q}_{\perp
n}\Delta_{n}(t)\lambda_{\Sigma}+\epsilon\left\lVert\widehat{{\mathbf{Q}}}_{\perp}(t)\right\rVert_{1}$
(37)

where (a) comes from the fact that the cone $\mathcal{K}_{\alpha}$ is symmetry
with respect to the line $\mathbf{1}=(1,1,\ldots,1)$; In (b),
$\widehat{Q}_{\perp n}$ is the $n$-th component of the vector
$\widehat{{\mathbf{Q}}}_{\perp}(t)$ and (b) holds because of the definition of
$\Delta(t)$ in Eq. (7), and the fact that the service process is independent
of queue lengths; (c) follows from the fact that
$\lambda_{\Sigma}=\mu_{\Sigma}-\epsilon$.

Now, let us focus on the first term of Eq. (4.2.2). To establish an upper
bound on it, we will first establish the following important monotone property
of $\widehat{{\mathbf{Q}}}_{\perp}(t)$. That is,

$\displaystyle\widehat{Q}_{\perp 1}(t)\leq\widehat{Q}_{\perp
2}(t)\leq\cdots\leq\widehat{Q}_{\perp N}(t).$ (38)

First, in the case of $\alpha=1$, the cone $\mathcal{K}_{\alpha}$ reduces to
the line $\mathbf{1}$. Thus, it can be easily obtained that
$\widehat{Q}_{\perp n}(t)=Q_{\sigma_{t}(n)}(t)-Q_{\text{avg}}(t)$ where
$Q_{\text{avg}}(t)=\sum_{n=1}^{N}Q_{n}(t)/N$, which satisfies the monotone
property. Hence, we are only left with the task of establishing the monotone
property for the case of $\alpha\in(0,1)$.

Note that, since
$\widehat{{\mathbf{Q}}}_{\parallel}(t)\in\mathcal{K}_{\alpha}$, we have
$\widehat{{\mathbf{Q}}}_{\parallel}(t)=\sum_{n=1}^{N}w_{n}\mathbf{b}^{(n)}$,
where $w_{n}\geq 0$. Let $\mathcal{I}$ be a subset of $\\{1,2,\ldots,N\\}$
such that for any $i\in\mathcal{I}$ $w_{i}>0$ and for any
$i\notin\mathcal{I}$, $w_{i}=0$, i.e., the subset $\mathcal{I}$ contains all
the index $n$ such that $w_{n}>0$. It suffices to consider the case when
$\mathcal{I}$ is nonempty. This is because when $\mathcal{I}$ is empty, we
have $\widehat{{\mathbf{Q}}}_{\parallel}(t)=0$, which directly implies the
monotone property since
$\widehat{{\mathbf{Q}}}_{\perp}(t)=\widehat{{\mathbf{Q}}}(t)$ in this case.

Now consider the case when $\mathcal{I}$ is nonempty. First, we have

$\displaystyle\langle\widehat{{\mathbf{Q}}}_{\perp}(t),\mathbf{b}^{(i)}\rangle\leq
0$ (39)

holds for any $i\in\\{1,2,\ldots,N\\}$. Moreover, for any $i\in\mathcal{I}$

$\displaystyle\langle\widehat{{\mathbf{Q}}}_{\perp}(t),\mathbf{b}^{(i)}\rangle=0.$
(40)

The inequality in Eq. (39) follows from the fact that
$\mathbf{b}^{(i)}\in\mathcal{K}_{\alpha}$ and
$\widehat{{\mathbf{Q}}}_{\perp}(t)\in\mathcal{K}_{\alpha}^{\circ}$. The
equality in Eq. (40) follows from the fact that

$\displaystyle
0=\langle\widehat{{\mathbf{Q}}}_{\perp}(t),\widehat{{\mathbf{Q}}}_{\parallel}(t)\rangle=\sum_{i\in\mathcal{I}}w_{i}\langle\widehat{{\mathbf{Q}}}_{\perp}(t),\mathbf{b}^{(i)}\rangle,$

along with Eq. (39) and $w_{i}>0$ for all $i\in\mathcal{I}$. Eqs. (39) and
(40) enable us to establish the following claim, the proof of which is
relegated to Appendix F.

######  Claim 3.

If $m\in\mathcal{I}$ with $1\leq m<N-1$, then $m+1\in\mathcal{I}$.

Note that Claim 3 directly implies that there exists an $m_{0}$ (which depends
on ${\mathbf{Q}}(t)$) such that for all $i\geq m_{0}$, $i\in\mathcal{I}$ and
for $i<m_{0}$, $i\notin\mathcal{I}$. Hence, by Eq. (40), for all $i\geq m_{0}$

$\displaystyle
0=\langle\widehat{{\mathbf{Q}}}_{\perp}(t),\mathbf{b}^{(i)}\rangle=\alpha\sum_{n=1}^{N}\widehat{{\mathbf{Q}}}_{\perp
n}(t)+(1-\alpha)\widehat{Q}_{\perp i}(t),$

which implies that for all $i\geq m_{0}$

$\displaystyle\widehat{{\mathbf{Q}}}_{\perp i}(t)=c\geq 0$ (41)

for some constant $c$. This is because
$\sum_{n=1}^{N}\widehat{{\mathbf{Q}}}_{\perp n}(t)\leq 0$, due to the fact
that $\mathbf{1}\in\mathbf{K}_{\alpha}$ and
$\widehat{{\mathbf{Q}}}_{\perp}(t)\in\mathcal{K}_{\alpha}^{\circ}$. On the
other hand, for any $i\leq j<m_{0}$, we have

$\displaystyle\widehat{{\mathbf{Q}}}_{\perp
i}(t)\leq\widehat{{\mathbf{Q}}}_{\perp j}(t).$ (42)

This holds since $\widehat{{\mathbf{Q}}}_{\parallel
i}(t)=\widehat{{\mathbf{Q}}}_{\parallel j}(t)$ and
$\widehat{Q}_{i}(t)\leq\widehat{Q}_{j}(t)$. Moreover, we have

$\displaystyle\widehat{{\mathbf{Q}}}_{\perp
m_{0}}(t)\geq\widehat{{\mathbf{Q}}}_{\perp(m_{0}-1)}(t).$ (43)

This can be shown by contradiction. Suppose
$\widehat{{\mathbf{Q}}}_{\perp(m_{0}-1)}(t)>\widehat{{\mathbf{Q}}}_{\perp
m_{0}}(t)$, then

$\displaystyle\langle\widehat{{\mathbf{Q}}}_{\perp}(t),\mathbf{b}^{(m_{0}-1)}\rangle$
$\displaystyle=\alpha\sum_{n=1}^{N}\widehat{{\mathbf{Q}}}_{\perp
n}(t)+(1-\alpha)\widehat{Q}_{\perp(m_{0}-1)}(t)$
$\displaystyle>\alpha\sum_{n=1}^{N}\widehat{{\mathbf{Q}}}_{\perp
n}(t)+(1-\alpha)\widehat{Q}_{\perp m_{0}}(t)$
$\displaystyle=\langle\widehat{{\mathbf{Q}}}_{\perp}(t),\mathbf{b}^{(m_{0})}\rangle$
$\displaystyle=0$

which contradicts with Eq.(39). Then, combining Eqs. (41), (42) and (43),
yields the fact that $\widehat{{\mathbf{Q}}}_{\perp N}(t)\geq 0$ and the
monotone property in Eq. (38). As a result, we have
$\widehat{{\mathbf{Q}}}_{\perp 1}(t)\leq 0$ since otherwise
$\sum_{n=1}^{N}\widehat{{\mathbf{Q}}}_{\perp,n}(t)$ would be strictly
positive.

Having established the monotone property of
$\widehat{{\mathbf{Q}}}_{\perp}(t)$ and auxiliary results that
$\widehat{{\mathbf{Q}}}_{\perp N}(t)\geq 0$ and $\widehat{{\mathbf{Q}}}_{\perp
1}(t)\leq 0$, we can now proceed to obtain an upper bound on the first term in
Eq. (4.2.2). In particular, we can first bound it in terms of
$|\widehat{{\mathbf{Q}}}_{\perp 1}(t)|$ and the $\delta$ in Eq. (9). In
particular, we have

$\displaystyle\sum_{n=1}^{N}\widehat{Q}_{\perp
n}\Delta_{n}(t)\lambda_{\Sigma}\leq-\lambda_{\Sigma}\delta|\widehat{{\mathbf{Q}}}_{\perp
1}(t)|.$ (44)

This upper bound can be verified as follows. First, if
${\mathbf{Q}}(t)\in\mathcal{K}_{\alpha}$, then $\widehat{{\mathbf{Q}}}_{\perp
n}(t)=0$ for all $n$, and hence Eq. (44) holds. If
${\mathbf{Q}}(t)\notin\mathcal{K}_{\alpha}$, then $\Delta(t)$ satisfies the
two conditions in Eqs. (8) and (9) in Theorem 2, which specify the
construction process of $\Delta(t)$. In particular, each $\Delta(t)$ that
satisfies the two conditions can be constructed as follows. To begin with, all
the $\Delta_{n}(t)$ is $0$. Then, according to the condition in Eq. (9), we
should first decrease $\Delta_{N}(t)$ by the amount of $\delta$, and increase
$\Delta_{1}(t)$ by the amount of $\delta$. After this, the left-hand-side of
Eq. (44) is equal to
$\lambda_{\Sigma}\left(\delta\widehat{{\mathbf{Q}}}_{\perp
1}(t)+(-\delta)\widehat{{\mathbf{Q}}}_{\perp N}(t)\right)$, which is upper
bounded by $-\lambda_{\Sigma}\delta|\widehat{{\mathbf{Q}}}_{\perp 1}(t)|$,
since $\widehat{{\mathbf{Q}}}_{\perp N}(t)\geq 0$ and
$\widehat{{\mathbf{Q}}}_{\perp 1}(t)\leq 0$. Next, due to the condition in
Eq.(8) and the fact that $\sum_{n=1}^{N}\Delta_{n}(t)=0$, any further
procedure (if needed) for the construction of $\Delta(t)$ can only take the
following way: it decreases some $\Delta_{i}(t)$ by a certain amount (say
$c_{1}$) where $i\geq k$, and then increase some $\Delta_{j}(t)$ by the same
amount $c_{1}$ where $j\leq k$. We claim that any of this procedure cannot
increase the value of the left-hand-side of Eq. (44) due to the monotone
property of $\widehat{{\mathbf{Q}}}_{\perp}(t)$. To see this, let us denote by
$\mathcal{L}_{ij}$ the change of the value of the left-hand-side of Eq. (44)
incurred by the procedure above. Thus, we have

$\displaystyle\mathcal{L}_{ij}=-c_{1}\widehat{Q}_{\perp
i}(t)+c_{1}\widehat{Q}_{\perp j}(t)\leq 0,$

which follows from the monotone property of
$\widehat{{\mathbf{Q}}}_{\perp}(t)$. Therefore, we have verified the upper
bound in Eq. (44).

Next, we establish an upper bound on
$\|\widehat{{\mathbf{Q}}}_{\perp}(t)\rVert_{1}$ in terms of
$|\widehat{{\mathbf{Q}}}_{\perp 1}(t)|$ as follows

$\displaystyle\left\lVert\widehat{{\mathbf{Q}}}_{\perp}(t)\right\rVert_{1}\leq
2N|\widehat{{\mathbf{Q}}}_{\perp 1}(t)|.$ (45)

This follows from the monotone property of $\widehat{{\mathbf{Q}}}_{\perp}(t)$
and the fact that $\sum_{n=1}^{N}\widehat{{\mathbf{Q}}}_{\perp n}(t)\leq 0$.
Now, combining Eqs. (4.2.2), (44) and (45), we obtain that

$\displaystyle\mathbb{E}\left[\langle{\mathbf{Q}}_{\perp}(t),{\mathbf{A}}(t)-{\mathbf{S}}(t)\rangle\mid{\mathbf{Q}}(t)={\mathbf{Q}}\right]$
$\displaystyle\leq$
$\displaystyle\left(\epsilon-\frac{\lambda_{\Sigma}\delta}{2N}\right)\left\lVert\widehat{{\mathbf{Q}}}_{\perp}(t)\right\rVert_{1}$
$\displaystyle\leq$
$\displaystyle-\frac{\mu_{\Sigma}\delta}{4N}\left\lVert\widehat{{\mathbf{Q}}}_{\perp}(t)\right\rVert_{1}\text{
whenever }\epsilon\leq\frac{\mu_{\Sigma}\delta}{4N+2\delta}$
$\displaystyle\leq$
$\displaystyle-\frac{\mu_{\Sigma}\delta}{4N}\left\lVert{{\mathbf{Q}}}_{\perp}(t)\right\rVert$
(46)

where the last inequality comes from the fact that
$\lVert\widehat{{\mathbf{Q}}}_{\perp}(t)\rVert_{1}=\left\lVert{{\mathbf{Q}}}_{\perp}(t)\right\rVert_{1}$
and
$\left\lVert\mathbf{x}\right\rVert_{1}\geq\left\lVert\mathbf{x}\right\rVert$
for any $\mathbf{x}\in\mathbb{R}^{N}$. This establishes the inequality in Eq.
(36) with $c={\mu_{\Sigma}\delta}/{4N}$ and
$\epsilon_{0}={\mu_{\Sigma}\delta}/{(4N+2\delta)}.$ Hence, based on Claim 2,
we have verified the condition (C1) in Lemma 4, which directly establishes the
state-space collapse result in Proposition 3. ∎

##  5 Conclusions

We have rigorously shown that even under a multi-dimensional state-space
collapse, steady-state heavy-traffic delay optimality can be achieved for a
general load balancing system. This result suggests that the insight behind
heavy-traffic optimality conveyed by diffusion approximations is still valid
in _steady state_ , thus complementing and extending the diffusion
approximation results in [16], [23]. Moreover, our steady-state delay
optimality result might also give a possible direction for proving the
interchange of limits for the diffusion approximation results in [16], [23].
By leveraging this result, we are able to explore the greater flexibility
provided by allowing a multi-dimensional state-space collapse in designing new
load balancing policies that are both throughput optimal and heavy-traffic
delay optimal in steady state. Furthermore, the proof techniques used in this
paper are of independent interest as well.

## References

  * [1] Mor Armony.  Dynamic routing in large-scale service systems with heterogeneous servers.  Queueing Systems, 51(3-4):287–329, 2005.
  * [2] Steven L Bell and Ruth J Williams.  Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: asymptotic optimality of a threshold policy.  Annals of Applied Probability, pages 608–649, 2001.
  * [3] Maury Bramson.  State space collapse with application to heavy traffic limits for multiclass queueing networks.  Queueing Systems, 30(1-2):89–140, 1998.
  * [4] Hong Chen and David D Yao.  Fundamentals of queueing networks: Performance, asymptotics, and optimization, volume 46.  Springer Science & Business Media, 2013.
  * [5] Hong Chen and Heng-Qing Ye.  Asymptotic optimality of balanced routing.  Operations research, 60(1):163–179, 2012.
  * [6] JG Dai and Tolga Tezcan.  State space collapse in many-server diffusion limits of parallel server systems.  Mathematics of Operations Research, 36(2):271–320, 2011.
  * [7] Atilla Eryilmaz and R Srikant.  Asymptotically tight steady-state queue length bounds implied by drift conditions.  Queueing Systems, 72(3-4):311–359, 2012.
  * [8] G Foschini and JACK Salz.  A basic dynamic routing problem and diffusion.  IEEE Transactions on Communications, 26(3):320–327, 1978.
  * [9] Ian Foster, Yong Zhao, Ioan Raicu, and Shiyong Lu.  Cloud computing and grid computing 360-degree compared.  In 2008 Grid Computing Environments Workshop, pages 1–10. Ieee, 2008.
  * [10] Lars George.  HBase: the definitive guide.  ” O’Reilly Media, Inc.”, 2011.
  * [11] Varun Gupta, Mor Harchol Balter, Karl Sigman, and Ward Whitt.  Analysis of join-the-shortest-queue routing for web server farms.  Performance Evaluation, 64(9):1062–1081, 2007.
  * [12] Itay Gurvich and Ward Whitt.  Queue-and-idleness-ratio controls in many-server service systems.  Mathematics of Operations Research, 34(2):363–396, 2009.
  * [13] J Michael Harrison.  Heavy traffic analysis of a system with parallel servers: asymptotic optimality of discrete-review policies.  Annals of applied probability, pages 822–848, 1998.
  * [14] WN Kang, FP Kelly, NH Lee, RJ Williams, et al.  State space collapse and diffusion approximation for a network operating under a fair bandwidth sharing policy.  The Annals of Applied Probability, 19(5):1719–1780, 2009.
  * [15] WN Kang and RJ Williams.  Diffusion approximation for an input-queued packet switch operating under a maximum weight algorithm.  Stochastic Systems, 2012.
  * [16] FP Kelly and CN Laws.  Dynamic routing in open queueing networks: Brownian models, cut constraints and resource pooling.  Queueing systems, 13(1-3):47–86, 1993.
  * [17] Siva Theja Maguluri, Sai Kiran Burle, and R Srikant.  Optimal heavy-traffic queue length scaling in an incompletely saturated switch.  Queueing Systems, 88(3-4):279–309, 2018.
  * [18] Siva Theja Maguluri, R Srikant, et al.  Heavy traffic queue length behavior in a switch under the maxweight algorithm.  Stochastic Systems, 6(1):211–250, 2016.
  * [19] Siva Theja Maguluri, R Srikant, and Lei Ying.  Heavy traffic optimal resource allocation algorithms for cloud computing clusters.  Performance Evaluation, 81:20–39, 2014.
  * [20] Georgios S Paschos, Mathieu Leconte, and Apostolos Destounis.  Routing with blinkers: Online throughput maximization without queue length information.  In Information Theory (ISIT), 2016 IEEE International Symposium on, pages 1436–1440. IEEE, 2016.
  * [21] Martin I Reiman.  Some diffusion approximations with state space collapse.  In Modelling and performance evaluation methodology, pages 207–240. Springer, 1984.
  * [22] Alexander L Stolyar et al.  Maxweight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic.  The Annals of Applied Probability, 14(1):1–53, 2004.
  * [23] Yih-Choung Teh and Amy R Ward.  Critical thresholds for dynamic routing in queueing networks.  Queueing Systems, 42(3):297–316, 2002.
  * [24] Weina Wang, Siva Theja Maguluri, R Srikant, and Lei Ying.  Heavy-traffic delay insensitivity in connection-level models of data transfer with proportionally fair bandwidth sharing.  2017\.
  * [25] Weina Wang, Siva Theja Maguluri, R Srikant, and Lei Ying.  Heavy-traffic delay insensitivity in connection-level models of data transfer with proportionally fair bandwidth sharing.  ACM SIGMETRICS Performance Evaluation Review, 45(2):232–245, 2018\.
  * [26] 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, 24(1):190–203, 2016.
  * [27] Qiaomin Xie and Yi Lu.  Priority algorithm for near-data scheduling: Throughput and heavy-traffic optimality.  In Proceedings of IEEE International Conference on Computer Communications (INFOCOM), pages 963–972, 2015.
  * [28] Qiaomin Xie, Ali Yekkehkhany, and Yi Lu.  Scheduling with multi-level data locality: Throughput and heavy-traffic optimality.  In Proceedings of IEEE International Conference on Computer Communications (INFOCOM), pages 1–9, 2016.
  * [29] Matei Zaharia, Dhruba Borthakur, Joydeep Sen Sarma, Khaled Elmeleegy, Scott Shenker, and Ion Stoica.  Delay scheduling: a simple technique for achieving locality and fairness in cluster scheduling.  In Proceedings of the 5th European conference on Computer systems, pages 265–278. ACM, 2010.
  * [30] Xingyu Zhou, Fei Wu, Jian Tan, Yin Sun, and Ness Shroff.  Designing low-complexity heavy-traffic delay-optimal load balancing schemes: Theory to algorithms.  arXiv preprint arXiv:1710.04357, 2017.

##  Appendix A Proof of Lemma 3

###### Proof.

Let us consider the Lyapunov function
$V_{1}({\mathbf{Q}}(t))\triangleq\left\lVert{\mathbf{Q}}(t)\right\rVert_{1}^{2}$,
and the corresponding conditional mean drift is given by

$\displaystyle\mathbb{E}\left[V_{1}({\mathbf{Q}}(t+1))-V_{1}({\mathbf{Q}}(t))\mid{\mathbf{Q}}(t)={\mathbf{Q}}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\left\lVert{\mathbf{Q}}(t+1)\right\rVert_{1}^{2}-\left\lVert{\mathbf{Q}}(t)\right\rVert_{1}^{2}\mid{\mathbf{Q}}(t)={\mathbf{Q}}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[2\left\lVert{\mathbf{Q}}{}\right\rVert_{1}\left(\left\lVert{\mathbf{A}}\right\rVert_{1}-\left\lVert{\mathbf{S}}\right\rVert_{1}\right)+\left(\left\lVert{\mathbf{A}}\right\rVert_{1}-\left\lVert{\mathbf{S}}\right\rVert_{1}\right)^{2}\right.$
$\displaystyle+\left.{}2\left(\left\lVert{\mathbf{Q}}\right\rVert_{1}+\left\lVert{\mathbf{A}}\right\rVert_{1}-\left\lVert{\mathbf{S}}\right\rVert_{1}\right)\left\lVert{\mathbf{U}}\right\rVert_{1}+\left\lVert{\mathbf{U}}\right\rVert_{1}^{2}\vphantom{\left(\left\lVert{\mathbf{A}}\right\rVert_{1}-\left\lVert{\mathbf{S}}\right\rVert_{1}\right)^{2}}\mid{\mathbf{Q}}(t)={\mathbf{Q}}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[2\left\lVert{\mathbf{Q}}\right\rVert_{1}\left(\left\lVert{\mathbf{A}}\right\rVert_{1}-\left\lVert{\mathbf{S}}\right\rVert_{1}\right)+\left(\left\lVert{\mathbf{A}}\right\rVert_{1}-\left\lVert{\mathbf{S}}\right\rVert_{1}\right)^{2}\right.$
$\displaystyle+\left.{}2\left\lVert{\mathbf{Q}}(t+1)\right\rVert_{1}\left\lVert{\mathbf{U}}\right\rVert_{1}-\left\lVert{\mathbf{U}}\right\rVert_{1}^{2}\vphantom{\left(\left\lVert{\mathbf{A}}\right\rVert_{1}-\left\lVert{\mathbf{S}}\right\rVert_{1}\right)^{2}}\mid{\mathbf{Q}}(t)={\mathbf{Q}}\right].$
(47)

By the definition of throughput optimality in this paper, we have
$\mathbb{E}\left[V_{1}(\overline{{\mathbf{Q}}})\right]$ is finite. Therefore,
the mean drift of $V_{1}(.)$ is zero in steady-state. Taking expectation of
both sides of Eq. (A) with respect to the steady-state distribution
$\overline{{\mathbf{Q}}}^{(\epsilon)}$, yields

$\epsilon\mathbb{E}\left[\sum_{n=1}^{N}\overline{Q}_{n}^{(\epsilon)}\right]=\frac{\zeta^{(\epsilon)}}{2}+\mathbb{E}\left[\big{\lVert}\overline{{\mathbf{Q}}}^{(\epsilon)}(t+1)\big{\rVert}_{1}\big{\lVert}\overline{{\mathbf{U}}}^{(\epsilon)}(t)\big{\rVert}_{1}\right]-\frac{1}{2}\mathbb{E}\left[\big{\lVert}\overline{{\mathbf{U}}}^{(\epsilon)}\big{\rVert}_{1}^{2}\right]$

where
$\zeta^{(\epsilon)}=(\sigma_{\Sigma}^{(\epsilon)})^{2}+\nu_{\Sigma}^{2}+\epsilon^{2}$.
Then by utilizing the property of unused service shown in Lemma 2, we have

$\frac{\zeta^{(\epsilon)}}{2}+{\mathcal{T}}^{(\epsilon)}-\frac{1}{2}c_{1}\epsilon\leq\epsilon\mathbb{E}\left[\sum_{n=1}^{N}\overline{Q}_{n}^{(\epsilon)}\right]\leq\frac{\zeta^{(\epsilon)}}{2}+{\mathcal{T}}^{(\epsilon)},$

in which
${\mathcal{T}}^{(\epsilon)}=\mathbb{E}\left[\big{\lVert}\overline{{\mathbf{Q}}}^{(\epsilon)}(t+1)\big{\rVert}_{1}\left\lVert\overline{{\mathbf{U}}}^{(\epsilon)}(t)\right\rVert_{1}\right]$.
Since $\zeta^{(\epsilon)}$ converges to $\zeta$, from the inequality above and
the definition of heavy-traffic delay optimality, we can easily see that the
sufficient and necessary condition is $\lim_{\epsilon\downarrow
0}{\mathcal{T}}^{(\epsilon)}=0$, which completes the proof of Lemma 3. ∎

##  Appendix B Proof of Lemma 5

###### Proof.

(a) To show Eqs. (21) and (22) hold, we can directly apply FSLLN (functional
strong law of large numbers) to obtain that
$\frac{1}{x_{n_{k}}}{\mathcal{A}}_{\Sigma}^{(x_{n_{k}})}(x_{n_{k}}t)\to\lambda
t$ and
$\frac{1}{x_{n_{k}}}{\mathcal{S}}_{i}^{(x_{n_{k}})}(x_{n_{k}}t)\to\mu_{i}t$,
u.o.c, and each limiting function is Lipschitz continuous.

(b) For Eqs. (23) and (24), for any given $0\leq t_{1}\leq t_{2}$, we have

$0\leq\frac{1}{x_{n_{k}}}\left[{\mathcal{G}}_{i}^{(x_{n_{k}})}(x_{n_{k}}t_{2})-{\mathcal{G}}_{i}^{(x_{n_{k}})}(x_{n_{k}}t_{1})\right]\leq(t_{2}-t_{1}).$
(48)

Therefore, the sequence of functions
$\\{\frac{1}{x_{n_{k}}}{\mathcal{G}}_{i}^{(x_{n_{k}})}(x_{n_{k}}t)\\}$ is
uniformly bounded and uniformly equicontinuous. As a result, by the Arzela-
Ascoli theorem, there must exist a subsequence along which Eq. (23) hold. In
addition, Eq. (48) also implies that each limiting function $g_{i}$ is
Lipschitz continuous. Same argument can be used to show Eq. (24) hold and each
limiting function $b_{i}$ is Lipschitz continuous.

(c) For Eq. (18), since the sequence $\\{\frac{1}{x_{n}}Q_{i}^{x_{n}}(0)\\}$
is upper bounded by 1 as a result of Eq. (16), we have that there is a
subsequence such that $\frac{1}{x_{n_{k}}}{Q}_{i}^{(x_{n_{k}})}(0)\to
q_{i}(0)$. Hence, the convergence of Eq. (18) follows directly from Eq. (17),
and each limiting function $q_{i}$ is Lipschitz continuous.

(d) To show that Eqs. (19) and (20) hold, we utilize the fact that the arrival
and departure process are bounded. Take the arrival process for example, we
have

$0\leq\frac{1}{x_{n_{k}}}\left[{\mathcal{A}}_{i}^{(x_{n_{k}})}(x_{n_{k}}t_{2})-{\mathcal{A}}_{i}^{(x_{n_{k}})}(x_{n_{k}}t_{1})\right]\leq
A_{\max}(t_{2}-t_{1}),$

where $A_{\max}$ is the maximum number of exogenous arrivals at each time-
slot. For each server $i$, we also have

$0\leq\frac{1}{x_{n_{k}}}\left[{\mathcal{D}}_{i}^{(x_{n_{k}})}(x_{n_{k}}t_{2})-{\mathcal{D}}_{i}^{(x_{n_{k}})}(x_{n_{k}}t_{1})\right]\leq
S_{\max}(t_{2}-t_{1}),$

where $S_{\max}$ is the maximum number of offered service at each time-slot.
As a result, with the similar argument as in Eq. (48), we can easily show Eqs.
(19) and (20) hold, and each limiting function is Lipschitz continuous. ∎

##  Appendix C Proof of Lemma 6

In the proof, we will utilize the random time-change theorem in Chapter 5 of
[4], which is presented below for easy reference.

######  Theorem 3 (Random Time-Change Theorem).

Let $\\{X_{n},n\geq 1\\}$ and $\\{Y_{n},n\geq 1\\}$ be two sequences in
${D}^{J}$ (i.e., the space of $J$-dimensional real-valued functions on
$[0,\infty)$ that are right-continuous and with left limits.). Assume that
$Y_{n}$ is nondecreasing with $Y_{n}(0)=0$. If as $n\to\infty$,
$(X_{n},Y_{n})$ converges uniformly on compact sets to $(X,Y)$ with $X$ and
$Y$ in ${C}^{J}$ (i.e., the space of $J$-dimensional real-valued continuous
functions on $[0,\infty)$), then $X_{n}(Y_{n})$ converges uniformly on compact
sets to $X(Y)$, where $X_{n}(Y_{n})=X_{n}\circ Y_{n}=\\{X_{n}(Y_{n}(t)),t\geq
0\\}$ and $X(Y)=X\circ Y=\\{X(Y(t)),t\geq 0\\}$.

Now, we present the proof of Lemma 6.

###### Proof.

(a) Eqs. (28) and (29) directly follows from FSLLN under our assumptions for
the exogenous arrival process and each service process.

(b) Eq. (25) follows from the definition of the queue length dynamic. Eq. (30)
follows from the definition directly.

(c) Eqs. (26) and (27) are the results of Theorem 3. More specifically, let
$X_{n}=\frac{1}{x_{n_{k}}}{\mathcal{A}}_{\Sigma}^{(x_{n_{k}})}(x_{n_{k}}t)$
and $Y_{n}=\frac{1}{x_{n_{k}}}{\mathcal{G}}_{i}^{(x_{n_{k}})}(x_{n_{k}}t)$ and
we have $(X_{n},Y_{n})\to(\lambda t,g_{i}(t))$ uniformly on compact set, and
$Y_{n}$ is nondecreasing with $Y_{n}(0)=0$. Thus by Theorem 3, we have
$X_{n}(Y_{n}(t))=\frac{1}{x_{n_{k}}}{\mathcal{A}}_{i}^{(x_{n_{k}})}(x_{n_{k}}t)\to
X(Y(t))=\lambda g_{i}(t)=a_{i}(t)$ uniformly on compact sets. Similar argument
can be used to show Eq. (27) hold.

(d) Note that $t$ is the regular time in Eq. (31), and hence
$q_{i}^{\prime}(t)$ is well defined and exists. Therefore, the left-derivative
$q_{i}^{\prime}(t-)$ should be equal to the right-derivative
$q_{i}^{\prime}(t+)$. By the non-negativity of $q_{i}(t)$, if $q_{i}(t)=0$,
then we must have $q_{i}^{\prime}(t-)\leq 0$ and $q_{i}^{\prime}(t+)\geq 0$,
which results in $q_{i}^{\prime}(t)=0$. For the case $q_{i}(t)>0$, we need to
show $d_{i}^{\prime}(t)=\mu_{i}$. It suffices to consider the right-derivative
as it is equal to the derivative at a regular time $t$. Suppose $q_{i}(t)>0$,
then by the continuity of $q_{i}(t)$, there exists a $\delta>0$, such that
$a=\min_{t_{s}\in[t,t+\delta]}q(t_{s})>0$. Therefore, for sufficient large
$x_{n_{k}}$, we have

$\frac{1}{x_{n_{k}}}{Q}_{i}^{(x_{n_{k}})}(x_{n_{k}}t_{s})\geq\frac{a}{2},\text{for
any }t_{s}\in[t,t+\delta]\text{ and }\frac{a}{2}x_{n_{k}}\geq 1,$ (49)

which implies that ${Q}_{i}^{(x_{n_{k}})}(x_{n_{k}}t)\geq 1$ for any
$t_{s}\in[t,t+\delta]$. Therefore, we have

$\displaystyle\frac{1}{x_{n_{k}}}{\mathcal{D}}_{i}^{(x_{n_{k}})}(x_{n_{k}}t_{s})-\frac{1}{x_{n_{k}}}{\mathcal{D}}_{i}^{(x_{n_{k}})}(x_{n_{k}}t)$
$\displaystyle=$
$\displaystyle\frac{1}{x_{n_{k}}}{\mathcal{S}}_{i}^{(x_{n_{k}})}(x_{n_{k}}t_{s})-\frac{1}{x_{n_{k}}}{\mathcal{S}}_{i}^{(x_{n_{k}})}(x_{n_{k}}t).$

Then, according to the definition of derivative, we have

$\begin{split}d_{i}^{\prime}(t)&=\lim_{t_{s}\to
t}\lim_{x_{n_{k}}\to\infty}\frac{1}{x_{n_{k}}}\frac{{\mathcal{D}}_{i}^{(x_{n_{k}})}(x_{n_{k}}t_{s})-{\mathcal{D}}_{i}^{(x_{n_{k}})}(x_{n_{k}}t)}{t_{s}-t}\\\
&=\lim_{t_{s}\to
t}\lim_{x_{n_{k}}\to\infty}\frac{1}{x_{n_{k}}}\frac{{\mathcal{S}}_{i}^{(x_{n_{k}})}(x_{n_{k}}t_{s})-{\mathcal{S}}_{i}^{(x_{n_{k}})}(x_{n_{k}}t)}{t_{s}-t}\\\
&=\mu_{i}\end{split}$ (50)

As a result, Eq. (31) is true for any regular time $t$. ∎

##  Appendix D Proof of Claim 1

###### Proof.

Since $q_{\sigma_{t}(m+1)}(t)>0$, $q_{\sigma_{t}(m)}(t)=0$ and both functions
are continuous, we can choose a $\tau$ such that $a/b>4/\alpha$ where
$a=\min_{t_{s}\in[t-\tau,t+\tau]}q_{\sigma_{t}(m+1)}(t_{s})$ and
$b=\max_{t_{s}\in[t-\tau,t+\tau]}q_{\sigma_{t}(m)}(t_{s})$. By the u.o.c
convergence, for sufficient large $x_{n_{k}}$, we have for any
$t_{s}\in[t-\tau,t+\tau]$

$\frac{1}{x_{n_{k}}}{Q}_{\sigma_{t}(m+1)}^{(x_{n_{k}})}(x_{n_{k}}t_{s})\geq\frac{a}{2}\text{
and }\frac{1}{x_{n_{k}}}{Q}_{\sigma_{t}(m)}^{(x_{n_{k}})}(x_{n_{k}}t_{s})\leq
2b,$ (51)

which implies that
${{Q}_{\sigma_{t}(m+1)}^{(x_{n_{k}})}(x_{n_{k}}t_{s})}\big{/}{{Q}_{\sigma_{t}(m)}^{(x_{n_{k}})}(x_{n_{k}}t_{s})}>1/\alpha$,
for any $t_{s}\in[t-\tau,t+\tau]$. This indicates that in the interval
$[(t-\tau)x_{n_{k}}+1,(t+\tau)x_{n_{k}}-1]$, the queue-length state is outside
the cone $\mathcal{K}_{\alpha}$. In this case, according to the conditions for
the load balancing policy in Theorem 2, we have

$\displaystyle\sum_{n=m+1}^{N}$
$\displaystyle\left(\frac{1}{x_{n_{k}}}{\mathcal{G}}_{\sigma_{t}(n)}^{(x_{n_{k}})}(x_{n_{k}}(t+\frac{\tau}{2}))-\frac{1}{x_{n_{k}}}{\mathcal{G}}_{\sigma_{t}(n)}^{(x_{n_{k}})}(x_{n_{k}}(t-\frac{\tau}{2}))\right)$
$\displaystyle=\tau\sum_{n=m+1}^{N}\left(\Delta_{n}(t)+\frac{\mu_{\sigma_{t}(n)}}{\mu_{\Sigma}}\right).$

By letting $x_{n_{k}}\to\infty$ and from Eq.(23), we have

$\sum_{n=m+1}^{N}\left(g_{\sigma_{t}(n)}(t+\frac{\tau}{2})-g_{\sigma_{t}(n)}(t+\frac{\tau}{2})\right)=\tau\sum_{n=m+1}^{N}\left(\Delta_{n}(t)+\frac{\mu_{\sigma_{t}(n)}}{\mu_{\Sigma}}\right),$

which directly implies the required result of Claim 1. ∎

##  Appendix E Proof of Claim 2

###### Proof.

First, we have the following bound

$\displaystyle\mathbb{E}\left[\Delta
V_{\perp}({\mathbf{Q}})\mid{\mathbf{Q}}(t)={\mathbf{Q}}\right]$
$\displaystyle\leq$
$\displaystyle\frac{1}{2\left\lVert{\mathbf{Q}}_{\perp}\right\rVert}\mathbb{E}\left[\Delta
W({\mathbf{Q}})-\Delta
W_{\parallel}({\mathbf{Q}})\mid{\mathbf{Q}}(t)={\mathbf{Q}}\right].$ (52)

Similar to Lemma 7 in [7], this bound directly follows from the concavity of
root function and Pythagorean theorem. Next, we will bound each term in Eq.
(E), respectively. To begin with, we have an upper bound for the first term as
follows.

$\displaystyle\mathbb{E}\left[\Delta
W({\mathbf{Q}})\mid{\mathbf{Q}}(t)={\mathbf{Q}}\right]$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[\left\lVert{\mathbf{Q}}(t)+{\mathbf{A}}(t)-{\mathbf{S}}(t)+{\mathbf{U}}(t)\right\rVert^{2}-\left\lVert{\mathbf{Q}}(t)\right\rVert^{2}\mid{\mathbf{Q}}\right]$
$\displaystyle\mathop{\leq}\limits^{(a)}$
$\displaystyle\mathbb{E}\left[\left\lVert{\mathbf{Q}}(t)+{\mathbf{A}}(t)-{\mathbf{S}}(t)\right\rVert^{2}-\left\lVert{\mathbf{Q}}(t)\right\rVert^{2}\mid{\mathbf{Q}}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[2\langle{\mathbf{Q}}(t),{\mathbf{A}}(t)-{\mathbf{S}}(t)\rangle+\left\lVert{\mathbf{A}}(t)-{\mathbf{S}}(t)\right\rVert^{2}\mid{\mathbf{Q}}\right]$
$\displaystyle\mathop{\leq}\limits^{(b)}$
$\displaystyle\mathbb{E}\left[2\langle{\mathbf{Q}}(t),{\mathbf{A}}(t)-{\mathbf{S}}(t)\rangle\mid{\mathbf{Q}}\right]+L$
(53)

where (a) holds as $[\max(a,0)]^{2}\leq a^{2}$ for any $a\in\mathbb{R}$; in
(b), $L\triangleq N\max(A_{\max},S_{\max})^{2}$, which follows from the
assumptions that $A_{\Sigma}(t)\leq A_{\max}$ and $S_{n}(t)\leq S_{\max}$ for
all $t\geq 0$ and all $1\leq n\leq N$, and the fact that they are both
independent of the queue lengths.

We now turn to provide a lower bound on the second term in Eq. (E) as follows.

$\displaystyle\mathbb{E}\left[\Delta
W_{\parallel}({\mathbf{Q}})\mid{\mathbf{Q}}(t)={\mathbf{Q}}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[2\langle{\mathbf{Q}}_{\parallel}(t),{\mathbf{Q}}_{\parallel}(t+1)-{\mathbf{Q}}_{\parallel}(t)\rangle+\left\lVert{\mathbf{Q}}_{\parallel}(t+1)-{\mathbf{Q}}_{\parallel}(t)\right\rVert^{2}\mid{\mathbf{Q}}\right]$
$\displaystyle\geq$
$\displaystyle\mathbb{E}\left[2\langle{\mathbf{Q}}_{\parallel}(t),{\mathbf{Q}}_{\parallel}(t+1)-{\mathbf{Q}}_{\parallel}(t)\rangle\mid{\mathbf{Q}}\right]$
$\displaystyle=$ $\displaystyle
2\mathbb{E}\left[\langle{\mathbf{Q}}_{\parallel}(t),{\mathbf{Q}}(t+1)-{\mathbf{Q}}(t)\rangle-2\langle{\mathbf{Q}}_{\parallel}(t),{\mathbf{Q}}_{\perp}(t+1)-{\mathbf{Q}}_{\perp}(t)\rangle\mid{\mathbf{Q}}\right]$
$\displaystyle\mathop{\geq}\limits^{(a)}$
$\displaystyle\mathbb{E}\left[2\langle{\mathbf{Q}}_{\parallel}(t),{\mathbf{Q}}(t+1)-{\mathbf{Q}}(t)\rangle\mid{\mathbf{Q}}\right]$
$\displaystyle\mathop{\geq}\limits^{(b)}$
$\displaystyle\mathbb{E}\left[2\langle{\mathbf{Q}}_{\parallel}(t),{\mathbf{A}}(t)-{\mathbf{S}}(t)\rangle\mid{\mathbf{Q}}\right]$
(54)

where (a) holds because
$\langle{\mathbf{Q}}_{\parallel}(t),{\mathbf{Q}}_{\perp}(t)\rangle=0$ and
$\langle{\mathbf{Q}}_{\perp}(t+1),{\mathbf{Q}}_{\parallel}(t)\rangle\leq 0$,
since ${\mathbf{Q}}_{\parallel}(t)\in\mathcal{K}_{\alpha}$ and
${\mathbf{Q}}_{\perp}(t+1)\in\mathcal{K}_{\alpha}^{\circ}$; (b) follows from
the fact that all the components of ${\mathbf{Q}}_{\parallel}(t)$ and
${\mathbf{U}}(t)$ are nonnegative. Thus, substituting Eqs. (E) and (E) into
Eq. (E), yields the bound in Claim 2. ∎

##  Appendix F Proof of Claim 3

###### Proof.

This claim can be proved by contradiction. Suppose $m\in\mathcal{I}$ but
$m+1\notin\mathcal{I}$, then by the definition of $\mathcal{I}$, we have
$w_{m}>0$ and $w_{m+1}=0$. From the definition of $\mathbf{b}^{(i)}$ and the
fact that
$\widehat{{\mathbf{Q}}}_{\parallel}(t)=\sum_{i\in\mathcal{I}}w_{i}\mathbf{b}^{(i)}$,
we have

$\displaystyle\widehat{Q}_{\parallel m}(t)-\widehat{Q}_{\parallel
m+1}(t)=w_{m}(1-\alpha)>0,$

which implies that

$\displaystyle\widehat{Q}_{\perp m}(t)<\widehat{Q}_{\perp m+1}(t),$ (55)

since $\widehat{Q}_{m}(t)\leq\widehat{Q}_{m+1}(t)$. Then, it follows that

$\displaystyle\langle\widehat{{\mathbf{Q}}}_{\perp}(t),\mathbf{b}^{(m+1)}\rangle$
$\displaystyle=\alpha\sum_{n=1}^{N}\widehat{{\mathbf{Q}}}_{\perp
n}(t)+(1-\alpha)\widehat{Q}_{\perp m+1}(t)$
$\displaystyle\mathop{>}\limits^{(a)}\alpha\sum_{n=1}^{N}\widehat{{\mathbf{Q}}}_{\perp
n}(t)+(1-\alpha)\widehat{Q}_{\perp m}(t)$
$\displaystyle=\langle\widehat{{\mathbf{Q}}}_{\perp}(t),\mathbf{b}^{(m)}\rangle$
$\displaystyle\mathop{=}\limits^{(b)}0$

where (a) follows from Eq. (55); and (b) comes from Eq. (40). However, by Eq.
(39), we must have
$\langle\widehat{{\mathbf{Q}}}_{\perp}(t),\mathbf{b}^{(m+1)}\rangle\leq 0$.
Hence, Claim 3 is true. ∎

##  Appendix G Proof of Proposition 1

###### Proof.

It follows from Lemma 3 and the proof of Theorem 1 that the key for heavy-
traffic delay optimality is the term $\mathcal{T}^{(\epsilon)}$. Instead of
using Cauchy-Schwartz inequality, we apply Hölder inequality in Eq. (4.1) to
obtain a tighter bound of $\mathcal{T}^{(\epsilon)}$ as follows.

$\displaystyle\mathcal{T}^{(\epsilon)}$
$\displaystyle\leq\mathbb{E}\left[\langle\overline{{\mathbf{U}}},-N_{1}\overline{{\mathbf{Q}}}^{+}_{\perp}\rangle\right]$
$\displaystyle\mathop{\leq}\limits^{(a)}\frac{N}{\alpha^{(\epsilon)}}{\left(\mathbb{E}\left[\left\lVert\overline{{\mathbf{U}}}\right\rVert^{r^{\prime}}_{r^{\prime}}\right]\right)^{\frac{1}{r^{\prime}}}\left(\mathbb{E}\left[\left\lVert\overline{{\mathbf{Q}}}^{+}_{\perp}\right\rVert^{r}_{r}\right]\right)^{\frac{1}{r}}}.$
$\displaystyle\mathop{\leq}\limits^{(b)}\frac{N}{\alpha^{(\epsilon)}}\left(c_{r^{\prime}}\epsilon\right)^{\frac{1}{r^{\prime}}}\left(\mathbb{E}\left[\left\lVert\overline{{\mathbf{Q}}}^{+}_{\perp}\right\rVert^{r}_{2}\right]\right)^{\frac{1}{r}}.$
$\displaystyle\mathop{\leq}\limits^{(c)}\frac{N}{\alpha^{(\epsilon)}}\left(c_{r^{\prime}}\epsilon\right)^{\frac{1}{r^{\prime}}}\left(\mathbb{E}\left[\left\lVert\overline{{\mathbf{Q}}}_{\perp}\right\rVert^{r}_{2}\right]\right)^{\frac{1}{r}}.$
(56)

where (a) follows from Hölder inequality for random vectors, and
$r,r^{\prime}\in(1,\infty)$ satisfy $1/r+1/r^{\prime}=1$; (b) comes from Lemma
2 and the fact that if $0<r_{1}<r_{2}$, then
$\left\lVert\mathbf{x}\right\rVert_{r_{2}}\leq\left\lVert\mathbf{x}\right\rVert_{r_{1}}$
holds for any vector $\mathbf{x}$; (c) is true since the distribution of
${\mathbf{Q}}(t+1)$ and ${\mathbf{Q}}(t)$ are the same in steady-state.

Thus, in order to prove the result in Proposition 1, we are left to
characterize the moment of $\overline{{\mathbf{Q}}}_{\perp}$ in terms of the
parameter $\delta^{(\epsilon)}$. First, combining Eq. (4.2.2) and Claim 2,
yields

$\begin{split}&\mathbb{E}\left[\Delta
V_{\perp}({\mathbf{Q}})\mid{\mathbf{Q}}(t)={\mathbf{Q}}\right]\\\
\leq&\frac{1}{2\left\lVert{\mathbf{Q}}_{\perp}(t)\right\rVert}\mathbb{E}\left[\left(2\langle{\mathbf{Q}}_{\perp}(t),{\mathbf{A}}(t)-{\mathbf{S}}(t)\rangle+L\right)\mid{\mathbf{Q}}(t)={\mathbf{Q}}\right]\\\
\leq&-\frac{\mu_{\Sigma}\delta}{4N}+\frac{L}{2\left\lVert{\mathbf{Q}}_{\perp}(t)\right\rVert}\\\
\leq&-\frac{\mu_{\Sigma}\delta}{8N}\text{ for all }{\mathbf{Q}}\text{ such
that
}\left\lVert{\mathbf{Q}}_{\perp}\right\rVert\geq\frac{4NL}{\mu_{\Sigma}\delta}.\end{split}$

Thus the condition (C1) in Lemma 4 is valid with
$\eta=\frac{\mu_{\Sigma}\delta}{8N}$ and
$\kappa=\frac{4NL}{\mu_{\Sigma}\delta}$. Also, from Eq. (4.2.2), we have the
condition (C2) is valid with $D=\sqrt{N}\max(A_{\max},S_{\max})$. Then from
Eq. (15) in Lemma 4, we get for $r=1,2,\ldots,$

$\displaystyle\mathbb{E}\left[\left\lVert\overline{{\mathbf{Q}}}_{\perp}\right\rVert^{r}_{2}\right]$
$\displaystyle\leq(2\kappa)^{r}+(4D)^{r}\left(\frac{D+\eta}{\eta}\right)^{r}r!$
$\displaystyle\leq\frac{1}{\delta^{r}}K_{r}^{r}$ (57)

where
$K_{r}\triangleq\left[\left(\frac{8NL}{\mu_{\Sigma}}\right)^{r}+r!\left(\frac{32D^{2}N+4D\mu_{\Sigma}}{\mu_{\Sigma}}\right)^{r}\right]^{\frac{1}{r}}$,
which is independent of $\epsilon$. Now, substituting Eq. (G) into Eq. (G),
yields

$\displaystyle\mathcal{T}^{(\epsilon)}\leq
F_{r}\frac{\epsilon^{(1-1/r)}}{\alpha^{(\epsilon)}\delta^{(\epsilon)}}$

where $F_{r}\triangleq NK_{r}(S_{\max})^{(1/r^{2}-1/r)}$, which is independent
of $\epsilon$. Since
$\alpha^{(\epsilon)}\delta^{(\epsilon)}=\Omega(\epsilon^{\beta})$ and
$\beta\in[0,1)$, there exists a positive $\beta^{\prime}$ such that

$\displaystyle\mathcal{T}^{(\epsilon)}=O(\epsilon^{\beta^{\prime}}),$

when $r>1/(1-\beta)$. This directly implies that $\lim_{\epsilon\to
0}\mathcal{T}^{(\epsilon)}=0$. Thus from Lemma 3, the given policy is heavy-
traffic delay optimal. ∎