Parallel Server Systems with Cancel-on-Completion Redundancy

1. Introduction

We consider a parallel server system with so-called cancel-on-completion (c.o.c.) redundancy (cf. Vulimiri et al. 2013, Shah et al. 2015, Gardner et al. 2017, Shneer and Stolyar 2021), which is introduced as a means of improving reliability and/or reducing delays in data storage/processing systems. When c.o.c. redundancy is employed, an arriving job consists of multiple components placed on a randomly selected subset of servers. A job service is complete as soon as a certain number of components out of the total complete their service, at which point the unfinished service of all remaining components is immediately canceled. The key property of this model, which poses the main challenges for its analysis, is that it is in general non-work-conserving in the sense that the average amount of new workload added to the system by an arriving job is not defined a priori; therefore, for example, the system load is not defined a priori. The results of this paper concern both the system with a fixed number of servers and the mean-field asymptotic regime when the number of servers goes to infinity as the job arrival rate per server remains constant. The main question we address for the asymptotic regime is whether the steady-state asymptotic independence of server workloads holds.

A more specific definition of the model is as follows. There are n identical servers, processing work at a unit rate. New jobs arrive as a Poisson process of rate ${\lambda }^{n}n$. There is a finite set of job classes, and an arriving job is of class j with probability ${\pi }_j^n$. A class j job consists of d_j components, which are placed on d_j servers selected uniformly at random; the components’ sizes (workloads) $({\xi }_1^{(j)},\dots ,{\xi }_{d_j}^{(j)})$ are drawn according to an exchangeable distribution F_j. Each server processes its work (components of different jobs) in first-come, first-served (FCFS) order. A class j job service is complete as soon as k_j components (with $k_j\le d_j$) of the job complete their service, at which point the unfinished service of the remaining $d_j-k_j$ components of the job is “canceled.” We call this (d_j, k_j)-c.o.c. redundancy. We study both the system with a fixed n and the mean-field asymptotic regime when $n\to \infty ,\hspace{0.17em}{\lambda }^n\to \lambda$ and ${\pi }_j^n\to {\pi }_j$ for all j.

Because of cancellations, unless k_j = d_j, the actual amount of workload that a job component adds to the server on which it is placed may be smaller than the component size. As a result, the system is in general non-work-conserving in the following sense: both the distribution and the expectation of the random total workload that a class j job actually brings to the system depend on the system state at the time of arrival. Because of the non-work-conservation property of c.o.c. redundancy, even the system stochastic stability/instability in general is not known a priori. Furthermore, the non-work-conservation renders some very intuitive qualitative properties nonobvious for a c.o.c. redundancy system. For example, consider a system with fixed finite n. Let ${\overline{\lambda }}^n$ be the supremum of those λⁿ for which the system is stable. Then, it is natural to expect that, as ${\lambda }^n\uparrow {\overline{\lambda }}^n$, the system steady-state load ${\rho }^n({\lambda }^n)$ (i.e., the probability that a server is busy) increases to one. This property, which we refer to as stability for the full range of loads (stability-FRL), is not automatic for our system. But we prove that it does, in fact, hold for our model. (In Section 1.1, we discuss the non-work-conservation and related challenges in more detail.)

Another property that we prove for the systems with fixed n is the uniform (in n and ${\lambda }^n<{\overline{\lambda }}^n$) tightness of stationary distributions of the relative server workloads. Here, the “relative server workloads” refers to the empirical distribution of server workloads, centered by their average. Moreover, we show that, essentially, this uniform tightness extends to “free” systems as well, in which the server workloads are not lower bounded by (regulated at) zero; we also discuss a connection between free systems and stability of our original systems. These fixed-n results are both of independent interest and they serve as important “ingredients” of the asymptotic analysis.

Most of this paper is devoted to the mean-field asymptotic regime with the main property of interest for a given λ being the steady-state asymptotic independence (SSAI) of server workloads, namely, the property that, as $n\to \infty$ (with ${\lambda }^n\to \lambda ,\hspace{0.17em}{\pi }_j^n\to {\pi }_j, \forall j$), the steady-state workloads of servers within a fixed finite set become independent. Suppose the SSAI holds for some values of λ (we prove that it always holds for sufficiently small positive λ), and denote by $\overline{\lambda }$ the supremum of those values. Denote by $\rho (\lambda )={\lim }_n{\rho }^n({\lambda }^n)$ the limiting system load for $\lambda <\overline{\lambda }$. It is natural to expect that as $\lambda \uparrow \overline{\lambda }$, the system limiting steady-state load $\rho (\lambda )\uparrow 1$. This property, which is referred to as the steady-state asymptotic independence for the full range of loads (SSAI-FRL), is not automatic for our system. We prove that SSAI-FRL does hold under a certain uniqueness condition on the fixed points of the process mean-field limits (MLs). We further identify some sufficient conditions for that uniqueness to hold. In particular, we prove that SSAI-FRL holds in the important special case when each job class has independent and identically distributed (i.i.d.) component sizes with an increasing-hazard-rate (IHR) distribution. (Whether there exist cases when SSAI-FRL does not hold for the model in this paper is an open problem and is a subject of future research.)

The analysis of mean-field limits and their fixed points is a key part of the proofs of our asymptotic results. This part, as well as our general approach, are quite generic, relying almost exclusively on two fundamental properties of the model: (a) monotonicity and (b) the property that, on average, “the servers with lower workload receive larger expected additional workload of arriving jobs.” This is in contrast to Shneer and Stolyar (2021), who also study a model with multicomponent jobs, satisfying properties (a) and (b), but additionally satisfying the work-conservation; the analysis in Shneer and Stolyar (2021) relies on work-conservation in the crucial way.

The summary of our main results is as follows.

• Finite n model.

  • — We prove the stability-FRL property (Theorem 2).

  • — We prove uniform tightness of stationary distributions of relative server workloads (Theorem 3). Moreover, we show that this uniform tightness extends to free systems as well (Theorem 11) and discuss a connection between free systems and stability.

• Asymptotic regime: $n\to \infty ,\hspace{0.17em}{\lambda }^n\to \lambda ,\hspace{0.17em}{\pi }_j^n\to {\pi }_j, \forall j$.

  • — We derive general properties of mean-field limits and their fixed points under general assumptions on the components’ sizes distributions (these are the results in Section 10). In particular, we prove that fixed points are completely characterized as solutions of a certain functional differential equation (Lemma 19).

  • — For the special, “truncated” (“finite-frame”) model in which the workloads are “clipped” at some finite level, we prove that SSAI-FRL always holds (Theorem 1).

  • — We prove SSAI-FRL under a certain uniqueness assumption on the mean-field limit fixed points (Theorem 4). We identify sufficient conditions for that uniqueness to hold (Theorem 6). This, in particular, allows us to prove SSAI-FRL in the important special case (Theorem 5) when each job class has i.i.d. IHR component sizes (or, more generally, the joint component size distribution is a mixture of such distributions).

  • — We prove some other sufficient conditions for SSAI to hold for a given λ (Theorems 8–10). In particular, SSAI holds for any λ such that the system is inherently subcritically loaded (Theorem 9), and we provide nontrivial conditions to verify inherent subcriticality.

Prior work specifically on c.o.c. redundancy models includes Vulimiri et al. (2013), Shah et al. (2015), and Gardner et al. (2017). Hellemans et al. (2019) consider redundancy models more general than c.o.c. Cancel-on-completion is not the only form of redundancy considered in prior literature, another form being cancel-on-start (c.o.s.) redundancy when the remaining $d_j-k_j$ job components are canceled as soon as k_j (out of d_j) components start their service; under the c.o.s. redundancy, the system is work-conserving. (The extensively studied power-of-d-choices load-balancing scheme—see Vvedenskaya et al. (1996) and Bramson et al. (2012)—is a special case of c.o.s. redundancy with a single job class with $k_j=1<d_j$.) For a more extensive overview of the literature on redundancy models, which includes papers Vulimiri et al. (2013), Shah et al. (2015), Gardner et al. (2015; 2017), Adan et al. (2018), Ayesta et al. (2018a; b), Vvedenskaya et al. (1996), and Bramson et al. (2012), we refer readers to Shneer and Stolyar (2021) and references therein. (We note that, in most of the prior work, what we call job components are called job “replicas.”)

Shneer and Stolyar (2021) prove SSAI under any subcritical load for a work-conserving system with multicomponent jobs such that each job class may be of the two different types: water-filling or least-load. (Given that the system is work conserving, this automatically implies SSAI-FRL.) The least-load job classes cover the c.o.s. redundancy. The water-filling job classes cover, in particular, the c.o.c. redundancy, but only in the special case of i.i.d. exponentially distributed component sizes because, then, a c.o.c. job can be equivalently viewed as a water-filling job.

Besides the (work-conserving) special case covered in Shneer and Stolyar (2021), the author is not aware of any prior work for c.o.c. redundancy models proving the SSAI-FRL or even identifying and proving nontrivial sufficient conditions for the SSAI. This is the main distinction of the present paper from the prior work.

Whereas there are essentially no prior works proving SSAI for c.o.c. models, the SSAI conjecture is often employed to obtain estimates of the system performance metrics when the number of servers is large (cf. Vulimiri et al. 2013, Gardner et al. 2017, Hellemans et al. 2019).

1.1. Discussion of Non-Work-Conservation and Its Implications

In queueing literature, work-conservation usually refers to some form of the property that work “cannot be discarded” by a system. One way to formally define this property is as follows: the distribution of the random total amount of work brought to the system by a job of given class j is independent of the system state at the time of arrival, and the job leaves the system only when the entire amount of its associated work is completed by the system. Let us refer to this as “work-conservation in the strong sense.” In this paper, we understand work-conservation as the following weaker property: the expected total amount of work s_j brought to the system by a job of given class j does not depend on the system state at the time of arrival, and the job leaves the system only when the entire amount of its associated work is completed by the system.

As we already noted, because of cancellations, the system under c.o.c. redundancy is in general non-work-conserving (even in the specified weaker sense). This is in contrast to, for example, a system with c.o.s. redundancy (Shneer and Stolyar 2021) in which a class j job brings exactly $s_j=k_j\mathbb{E}{\xi }_1^{(j)}$ expected new workload, thus making a c.o.s. system work-conserving. (In the degenerate case when k_j = d_j for all job classes j, there is no difference between c.o.c. and c.o.s. redundancies because there are no cancellations.)

There are cases when a system, which is ostensibly non-work-conserving, in fact, is work-conserving. An example is the system with c.o.c. redundancy in the special case when, for each job class j, the component sizes are i.i.d. exponential. In this case, it is easy to observe that the total amount of work brought by a class j job happens to be equal in distribution to ${\sum }_1^{k_j}{\xi }_i^{(j)}$ regardless of the system state at the time of arrival; this is because, in this case, a c.o.c. job can be equivalently viewed as a water-filling job (see Shneer and Stolyar 2021). Therefore, $s_j=k_j\mathbb{E}{\xi }_1^{(j)}$, and the system is indeed work-conserving. (In fact, this system is work-conserving even in the strong sense.)

Consider stability properties of a multicomponent job system with a given n. Assume that, if the system is stable for λⁿ, then it is also stable for any smaller arrival rate parameter. (As we will see, this fact is straightforward for the model in this paper as well as for many other models, including that in Shneer and Stolyar (2021).) Then, the property that we call stability-FRL can be thought of as a generalization of the property that “the system is stable as long as its nominal load is less than one” for a work-conserving system. Indeed, for a work-conserving system, there is a well-defined nominal system load, namely, the steady-state probability that a server is busy, assuming stability holds. Specifically, the nominal load is simply ${\rho }^n({\lambda }^n)=[{\sum }_j{\pi }_j^n{s}_j]{\lambda }^n$. Then, the stability-FRL is equivalent to the “stability as long as ${\rho }^n({\lambda }^n)<1$, or ${\lambda }^n<{\overline{\lambda }}^n=1/[{\sum }_j{\pi }_j^n{s}_j]$.” For many work-conserving systems, including a quite general system in Shneer and Stolyar (2021), the stability for ${\lambda }^n<{\overline{\lambda }}^n$, and then, the stability-FRL, is easy to show. Let us now consider a non-work-conserving system, specifically the c.o.c. redundancy system in the present paper. In this case, there is no a priori defined nominal load ${\rho }^n({\lambda }^n)$. Instead, as we increase λⁿ and as long as the system remains stable, actual load ${\rho }^n({\lambda }^n)$ is some, generally nonlinear, unknown a priori function of λⁿ. As λⁿ approaches ${\overline{\lambda }}^n$, which is the supremum of those λⁿ for which the system is stable, the property that ${\rho }^n({\lambda }^n)\uparrow 1$, that is, the stability-FRL, is not automatic. We do prove this property for our system (and, in fact, give a characterization of ${\overline{\lambda }}^n$, although not explicit).

Let us now discuss the asymptotic regime, ${\lambda }^n\to \lambda ,\hspace{0.17em}{\pi }_j^n\to {\pi }_j,\forall j$, and the properties that we call SSAI and SSAI-FRL. The SSAI is equivalent to the property that, as $n\to \infty$, the steady-state (random) empirical distribution of the server workloads in the system converges to the single (deterministic) point $x^{*,\lambda }=(x_w^{*,\lambda }, w\ge 0),$ where $x_w^{*,\lambda }$ gives the (limiting) fraction of servers with workload greater than w. In the terminology that we introduce later, $x^{*,\lambda }$ is a fixed point of the mean-field limit (ML-FP). Consider a work-conserving system. Then, SSAI-FRL is equivalent to the property that “SSAI holds for all λ such that the (limiting) nominal load $\rho (\lambda )=[{\sum }_j{\pi }_j{s}_j]\lambda <1$, or $\lambda <\overline{\lambda }=1/[{\sum }_j{\pi }_j{s}_j]$.” The proof of this property for a (work-conserving) model in Shneer and Stolyar (2021) relies in an essential way on the facts that an ML-FP $x^{*,\lambda }$ is unique and is such that the (limiting) fraction of busy servers is exactly ρ, that is, $x_0^{*,\lambda }=\rho$; these facts are relatively easy consequences of work-conservation. Let us now consider the non-work-conserving model in this paper. Proving SSAI-FRL reduces to proving the following for any fixed $\rho <1$. Consider a converging sequence ${\lambda }^n\to \lambda$ such that, for all n, ${\rho }^n({\lambda }^n)=\rho$. (Such a sequence exists because, for each n, we have the stability-FRL.) Then, the steady-state empirical distribution of the server workloads converges to a single (deterministic) point $x^{*,\lambda }$, which is an ML-FP with $x_0^{*,\lambda }=\rho$. The key difficulty posed by the non-work-conservation is that, whereas the existence of an ML-FP, with $x_0^{*,\lambda }\le \rho$, is not hard to obtain, it is not clear that an ML-FP for a given λ is unique. In this paper, we prove that, in essence, if the uniqueness of an ML-FP for each λ holds, then the SSAI-FRL holds as well. (This fact, which is the essence of Theorem 4, is far from straightforward. A large part of this paper is devoted to and leads to the proof of Theorem 4; an informal discussion of the proof key ideas is given at the beginning of Section 13. Also, Theorem 4 is quite generic, not relying much on the specific structure of the c.o.c. redundancy model beyond the two fundamental properties (a) and (b) mentioned earlier.) We further show that the ML-FP uniqueness condition and then the SSAI-FRL hold in the important special case of the i.i.d. IHR components. (This part relies on the c.o.c. redundancy model structure to a much larger degree.)

Finally, we note that the challenge of establishing SSAI-FRL is not limited to specifically multicomponent-job models or specifically non-work-conservation. As a example, a join-the-idle-queue (JIQ) model with general job size distribution, studied in Foss and Stolyar (2017), is work-conserving and is not a multicomponent-job model. The stability-FRL for this model is straightforward. However, the SSAI for it has only been established for the loads less than 1/2, as opposed to less than 1. Therefore, SSAI-FRL for this system is still an open problem, to the best of our knowledge. We note that the JIQ model in Foss and Stolyar (2017) does not have certain monotonicity properties, which the model in our paper does have.

1.2. Paper layout

The rest of the paper is organized as follows. Basic notation and terminology used throughout the paper are introduced in Section 2. Section 3 formally defines our model and the asymptotic regime. Sections 4 and 5 state our main results for the truncated (finite-frame) and the original (infinite-frame) models, respectively. In Sections 6 and 7, we establish some monotonicity—and related to it—properties of the model, which serve as important tools of our analysis. Sections 8 and 9 contain the proofs of Theorems 2 and 3, respectively, which are our main results for a system with finite n. In Section 10, we define and study the mean-field limits, which serve as a key tool of our asymptotic analysis. Sections 13 and 14 present proofs of all asymptotic results stated in Sections 4 and 5. In Section 15, we state and prove some additional results on SSAI. Finally, in Section 16, we state and prove the tightness result for the free system.

2. Basic Notation and Terminology

We denote by $\mathbb{R}$ and ${\mathbb{R}}_{+}$ the sets of real and real nonnegative numbers, respectively, and by ${\mathbb{R}}^n$ and ${\mathbb{R}}_{+}^n$ the corresponding n-dimensional product sets. By $\overline{\mathbb{R}}\doteq \mathbb{R}\cup \{\infty \}\cup \{-\infty \}$, we denote the two-point compactification of $\mathbb{R}$, where $\infty$ and $-\infty$ are the points at infinity and minus infinity with the natural topology and a consistent with it metric so that $\overline{\mathbb{R}}$ (and $\mathbb{R}$) is complete and separable. Analogously, ${\overline{\mathbb{R}}}_{+}\doteq {\mathbb{R}}_{+}\cup \{\infty \}$ is the one-point compactification of ${\mathbb{R}}_{+}$. For a vector $q=(q_i)\in {\mathbb{R}}^n,|q|\doteq {\sum }_i|q_i|$. Inequalities applied to vectors (respectively, functions) are understood component-wise (for every value of the function argument). We say that a function is RCLL (respectively, LCRL) if it is right-continuous with left-limits (respectively, left-continuous with right-limits). A scalar function f(w) is called c-Lipschitz if it is Lipschitz continuous with constant c. The sup-norm of a scalar function f(w) is denoted $||f(·)||\doteq {\sup }_w|f(w)|$; the corresponding convergence is denoted by $\stackrel{||·||}{\to }$. U.o.c. convergence means uniform on compact sets convergence, and is denoted by $\mathit{u.}\mathit{o.}\mathit{c.}\to$. We use notation $a\vee b\doteq \max \{a,b\}$, $a\wedge b\doteq \min \{a,b\}$. Abbreviation w.r.t. means with respect to; a.e. means almost everywhere w.r.t. Lebesgue measure; WLOG means without loss of generality; RHS and LHS means right- and left-hand side, respectively.

We denote by $\tilde{\mathcal{X}}$ ($\mathcal{X}$) the set of nonincreasing RCLL functions $x=(x_w, w\in \mathbb{R})$ ($x=(x_w, w\in {\mathbb{R}}_{+})$) taking values in $[0,1]$. An element $x\in \tilde{\mathcal{X}}$ ($x\in \mathcal{X}$) is naturally interpreted as complementary distribution function on $\overline{\mathbb{R}}$ (${\overline{\mathbb{R}}}_{+}$) with $1-x_w$ being the measure of $[-\infty ,w]$ ($[0,w]$). An element $x\in \tilde{\mathcal{X}}$ is proper if $x_{\infty }\doteq {\lim }_{w\to \infty }{x}_w=0$ and $x_{-\infty }\doteq {\lim }_{w\to -\infty }{x}_w=1$ and improper otherwise; in any case, $x_{\infty }$ and $1-x_{-\infty }$ give the measures of $\{+\infty \}$ and $\{-\infty \}$, respectively. Analogously, an element $x\in \mathcal{X}$ is proper if $x_{\infty }=0$ and improper otherwise. (With some abuse of standard terminology, in this paper, we sometimes refer to elements of $\tilde{\mathcal{X}}$ and $\mathcal{X}$ as distributions.) Denote by ${\tilde{\mathcal{X}}}^{pr}$ (respectively, ${\mathcal{X}}^{pr}$) the subset of proper elements of $\tilde{\mathcal{X}}$ (respectively, $\mathcal{X}$).

We equip the space $\tilde{\mathcal{X}}$ with the topology of weak convergence of the corresponding distributions on $\overline{\mathbb{R}}$; equivalently, $y\to x$ if and only if $y_w\to x_w$ for each $w\in (-\infty ,\infty )$, where x is continuous. Furthermore, on $\tilde{\mathcal{X}}$, we consider the following metric L, consistent with the weak convergence topology. We map an element $x\in \tilde{\mathcal{X}}$ into the (proper or nonproper) distribution function $\varphi =\varphi (x)$ on $\mathbb{R}$, where ${\varphi }_s=1-x_{-\log (1-s)}$ for $0\le s<1,\hspace{0.17em}{\varphi }_s=1-x_{\log (1+s)}$ for $-1\le s<0,\hspace{0.17em}{\varphi }_s=0$ for $s<-1,\hspace{0.17em}{\varphi }_s=1$ for $s\ge 1$. Then $L(x,y)\doteq \widehat{L}(\varphi (x),\varphi (y))$, where $\widehat{L}$ is the Levy–Prohorov metric (cf. Ethier and Kurtz 1986). It is easy to see that the convergence in metric L is indeed equivalent to the weak convergence. Clearly, $\tilde{\mathcal{X}}$ is compact. Space $\mathcal{X}$ inherits the topology and metric of space $\tilde{\mathcal{X}}$; for these purposes, we view any $x\in \mathcal{X}$ as an element of $\tilde{\mathcal{X}}$ via the convention that x_w = 1 for w < 0. Clearly, $\mathcal{X}$ is also compact.

For a function $x\in \tilde{\mathcal{X}}$ ($x\in \mathcal{X}$) we denote by $x^{-1}=(x_u^{-1}, u\in [0,1]),$ its inverse, defined as

with the convention that $x_u^{-1}=-\infty$ ($x_u^{-1}=0$) if the set in $\sup$ is empty.

Unless explicitly specified otherwise, we use the following conventions regarding random elements and processes. A measurable space is considered equipped with a Borel σ-algebra induced by the metric, which is clear from the context. A random process $Y(t), t\ge 0,$ always takes values in a complete separable metric space (clear from the context) and has RCLL sample paths; the sample paths are elements of the Skorohod J₁-space with the corresponding metric.

For a random process $Y(t), t\ge 0,$ we denote by $Y(\infty )$ the random value of Y(t) in a stationary regime (which will be clear from the context). Symbol $\Rightarrow$ signifies convergence of random elements in distribution; ${\to }^{\mathit{P}}$ means convergence in probability. W.p.1 means with probability one. I.i.d. means independent and identically distributed. Indicator of event or condition B is denoted by $\mathbf{I}(B)$. If X, Y are random elements taking values in a set on which a partial order $\le$ is defined, then the stochastic order $X{\le }_{st}Y$ means that X and Y can be coupled (constructed on a common probability space) so that $X\le Y$ w.p.1.

2.1. Fluid Limits

In several places, we rely on the fluid limit technique (Rybko and Stolyar 1992, Dai 1995, Stolyar 1995, Bramson 2008) to establish the stability (positive recurrence) of Markov processes. We now fix the corresponding definitions and terminology, which are not the most general, but suffice for the purposes of this paper.

Consider a continuous-time Markov process $Q(t)=(Q_1(t),\dots ,Q_n(t)), t\ge 0,$ in ${\mathbb{R}}^n$. Consider a sequence of processes $Q^{(r)}(·)$, indexed by $r\uparrow \infty$ with initial states such that $|Q^{(r)}(0)|=r$ and $(1/r)Q^{(r)}(0)\to q(0)$ for some fixed $q(0)\in {\mathbb{R}}^n,\hspace{0.17em}|q(0)|=1$. We say that fluid limits $q(·)$ of $Q(·)$ satisfy a set of properties A if trajectories $q(t), t\ge 0$, of any process being a distributional limit of the sequence of processes $(1/r)Q^{(r)}(rt), t\ge 0,$ along a subsequence of $r\uparrow \infty$, satisfy properties A w.p.1. If any such distributional limit is concentrated on the unique trajectory $q(·)$ (for a fixed q(0)), we say that the fluid limit is unique and is equal to this $q(·)$. If, for some fixed T > 0, fluid limits satisfy property

we say that fluid limits are stable. The fluid limit technique allows one to claim that “typically” (under mild additional conditions) the stability of fluid limits implies stability (positive recurrence) of the Markov process itself.

3. Model and Asymptotic Regime

3.1. Model. Cancel-on-Completion Redundancy

There are n identical servers, each processing its work at rate 1. The workload of a server at a given time is its unfinished work, that is, the time duration until the server becomes idle assuming no new job arrivals. There is a finite set $\mathcal{J}$ of job classes j. Jobs arrive as Poisson process of rate ${\lambda }^{n}n$ for some ${\lambda }^n\ge 0$. The probability that an arriving job is of class j is ${\pi }_j^n\ge 0,\hspace{0.17em}{\sum }_j{\pi }_j^n=1$. (Our asymptotic regime, which is introduced shortly, is such that $n\to \infty ,\hspace{0.17em}{\lambda }^n\to \lambda$ and each ${\pi }_j^n\to {\pi }_j$. That’s why we have notations λⁿ and ${\pi }_j^n$ indicating the dependence on n.) Each job class j has three parameters: integers k_j and d_j such that $1\le k_j\le d_j$ and the exchangeable probability distribution F_j on ${\mathbb{R}}_{+}^{d_j}$. (Exchangeability of F_j means that it is invariant w.r.t. permutations of components.) When a class j job arrives, d_j servers are selected uniformly at random (without replacement); these servers form the selection set of the job. The job places d_j components on the selected servers; the component sizes (workloads) $({\xi }_1^{(j)},\dots ,{\xi }_{d_j}^{(j)})$ are drawn according to distribution F_j, independently of the process history up to the job arrival time. Each server processes its work (components of different jobs) in the FCFS order. A job of class j, to be completed, requires k_j (out of d_j) components to be processed, and as soon as k_j components of the job complete their service (i.e., receive the amounts of service equal to their sizes), the unfinished service of the remaining $d_j-k_j$ components of the job is canceled and the job immediately leaves the system. (Hence, the name cancel-on-completion.) We call this (d_j, k_j)-c.o.c. redundancy. Throughout the paper, we use notation $\overline{d}\doteq {\max }_j{d}_j$.

Consider a server at time t. Let t + w be the time at which all the components (of different jobs) that are currently (at time t) in its queue leave the system either because of their service completions or cancellations. This w we call the server workload at time t. In other words, the server workload w at time t is the actual amount of its current unfinished work. Now, consider a class j job arrival at time t. Note that the workloads added to the selected servers by this arriving job depend not only on the realization of the component sizes, but also on the current workloads of the selected servers or, more specifically, on their relative workloads (i.e., workload differences). For a simple illustration, suppose d_j = 3, k_j = 2. Suppose a class j job arrives at time t with the realization of the components’ sizes being (7, 4, 3), and these components are placed on the selected severs $(S_1,S_2,S_3)$ with workloads at time t being (5, 3, 6). Then, after this job arrival, the new workloads of the selected servers are (9, 7, 9) because the service of the component placed on server S₁ is cancelled at time t + 9 upon the completion of the service of the component placed on server S₃. (Without cancellation, the new workloads would be (12, 7, 9).) Therefore, the workloads added to the selected servers by this job arrival are (4, 4, 3) as opposed to the component sizes (7, 4, 3). We see that, indeed, unless k_j = d_j, the realization of the added workloads depends on the relative workloads of selected servers as well as the realization of the component sizes. Consequently, in general, the joint distribution of the random added workloads that the job brings to the selected servers depends on the relative workloads of those servers. Moreover, both the distribution and the expectation of the total amount of added workload depend on the relative workloads of the selected servers. In this sense, the c.o.c. redundancy model is non-work-conserving. In particular, the system load—the average rate per server at which the new work arrives—is not known a priori.

In this paper, we often use “particle” language to describe the system dynamics. Namely, we identify each server with a particle, the server workload with particle location, and the workload evolution with particle movement. The basic dynamics of a particle (server workload) is as follows. If/when a job arrival adds workload $\kappa \ge 0$ to the server, the particle jumps “right” by κ. Between job arrivals, the particle (workload) moves “left” at the constant speed –1 until and unless it “hits” the “regulation boundary” at zero; if the particle does hit boundary 0, it stays at it until and unless it jumps right because of a job arrival.

Throughout this paper, we assume that the component sizes have finite mean (Assumption 1) and that a nontriviality Assumption 2 holds.

Assumption 1.

For all j,

$$\mathbb{E}{\xi }_1^{(j)}<\infty (\mathit{\text{and}} \mathit{\text{then}} \mathbb{E}{\displaystyle \sum _{i=1}^{d_j}{\xi }_i^{(j)}}=d_j\mathbb{E}{\xi }_1^{(j)}<\infty ),$$(1)

and WLOG, $\mathbb{E}{\xi }_1^{(j)}>0$.

Assumption 2.

There exists class j with F_j such that

$$\mathbb{P}\left\{{\displaystyle \sum _i\mathbf{I}}\right({\xi }_i^{(j)}=0)\ge k_j\}<1.$$(2)

Assumption 2 implies that, uniformly on the system state at the time of a class j job arrival, the expected amount of workload that the job brings to the system is at least some $\gamma >0$. If Assumption 2 does not hold, the system behavior is degenerate in that, when the system reaches the state with all workloads equal zero, it can never leave this state.

Note that, in the special case when, for each class j, either k_j = d_j or the component sizes are i.i.d. exponentially distributed, the model is within the framework of the model in Shneer and Stolyar (2021) with job classes being of either the least-load or water-filling type (in the terminology of Shneer and Stolyar 2021).

In addition to the basic model defined in this section, we also consider its truncated version, defined as follows. Let a constant $c\ge 0$ be fixed. The model is the same as the basic one except, after an arriving job adds workloads to its selected servers, the server workloads that happen to exceed c are immediately reset (truncated) to c. Note that the basic model can be viewed as a special case of the truncated one with $c=\infty$. From now on, we refer to parameter c as the frame size, to the basic (nontruncated) model as the infinite-frame model with frame $[0,\infty )$, and to the truncated model with $c<\infty$ as the finite-frame model with frame $[0,c]$. The purpose of considering the finite-frame model is twofold: it is of independent interest, and more importantly, it serves as a tool for the analysis of the infinite-frame model.

3.2. Asymptotic Regime. Mean-Field Scaled Process

We consider the sequence of systems with $n\to \infty ,\hspace{0.17em}{\lambda }^n\to \lambda \ge 0$, and ${\pi }_j^n\to {\pi }_j$ for all j, whereas all other system parameters remain fixed.

From now on, the upper index n of a variable/quantity indicates that it pertains to the system with n servers, or the nth system. Let $W_i^n(t)$ denote the workload of server i at time t in the nth system. (When $W_i^n(t)=0$, we say that server i at time t is empty.) Clearly, for each n, the process $W^n(t)=(W_1^n(t),\dots ,W_n^n(t)), t\ge 0,$ is Markov with state space ${\mathbb{R}}_{+}^n$. We adopt the convention that its sample paths are RCLL. The process state $(0,\dots ,0)$, that is, such that all servers are empty, we call the empty state. The process $W^n(·)$ is renewal with the empty state serving as a renewal atom, reachable from any other state; the renewals occur when the process enters the empty state. The process is irreducible, which follows from the reachability of the atom and the fact that the job arrival process is Poisson.

Consider also the following mean-field scaled quantities:

That is, $x_w^n(t)$ is the fraction of servers i with $W_i^n(t)>w$. Then, $x^n(t)=(x_w^n(t), w\ge 0)$ is a projection of $W^n(t)$, and $x^n(t), t\ge 0,$ is also a Markov process. Note that $x_0^n(t)$ is the fraction of busy servers (the instantaneous system load).

Clearly, for any n and t, $x^n(t)\in {\mathcal{X}}^{pr}$. Denote by ${\mathcal{X}}^{(n)}\subset {\mathcal{X}}^{pr}$ the state space ${\mathcal{X}}^{(n)}$ of the Markov process $x^n(t), t\ge 0.$ Therefore, for any n, we can and do view $x^n(t), t\ge 0$ as a Markov process with (common) state space ${\mathcal{X}}^{pr}\subset \mathcal{X}$ and with sample paths being RCLL functions of $t\ge 0$ (taking values in ${\mathcal{X}}^{pr}$). It is a renewal irreducible process with renewal atom being the empty state $x^{\varnothing }$ defined by

We say that the process $W^n(·)$ ($x^n(·)$) is stable if it is positive Harris recurrent, which, for this process, simply means that the empty state is reachable from any other state w.p.1, and the expected time to return to the empty state (after leaving it) is finite. (For a general definition of positive Harris recurrence, cf. Dai 1995, Bramson 2008.) Obviously, $W^n(·)$ is stable if and only if $x^n(·)$ is. Note that, trivially, a finite-frame system is always stable. For the infinite-frame system, because the system is non-work-conserving, the stability condition is not automatic and is nontrivial.

Stability of the process $W^n(·)$ (respectively, $x^n(·)$) implies that it has unique stationary distribution. If the process is stable, let $W^n(\infty )$ ($x^n(\infty )$) be a random element with values in ${\mathbb{R}}^n$ (respectively, in ${\mathcal{X}}^{pr}\subset \mathcal{X}$), whose distribution is the stationary distribution of the process; in other words, it is a random process state in the stationary regime. (Because of the process renewal structure, with absolutely continuous distribution of a renewal cycle duration, the stability also implies the convergence $W^n(t)\Rightarrow W^n(\infty )$ (or $x^n(t)\Rightarrow x^n(\infty )$) starting any proper initial state.) We also adopt a convention that $W^n(\infty )=(\infty ,\dots ,\infty )$ for an unstable process.

Later in the paper, we need some additional notation associated with the space $\mathcal{X}$. The infinite state $x^{**}\in \mathcal{X}$ is defined by

For an $x\in \mathcal{X}$, let us define its frame size c as follows: $c=\infty$ if $x_w>0$ for all $w<\infty$, and $c=\min \{w|x_w=0\}$ otherwise. We say that x has infinite frame $[0,\infty )$ or finite frame $[0,c]$ when $c=\infty$ and $c<\infty$, respectively. Note that $x^{\varnothing }$ is the only element with zero frame size. Let $x^{**,c}$ denote the maximum element with frame size $c\ge 0$: $x_w^{**,c}=1$ for w < c, and $x_c^{**,c}=0$.

4. Main Result for the Finite-Frame (Truncated) System

Theorem 1.

Consider a finite-frame (truncated) system with frame $[0,c],\hspace{0.17em}c<\infty$.

1. For each $\lambda \in [0,\infty )$, there exists $\rho (\lambda )\in [0,1)$ and a unique element $x^{*,\lambda }\in \mathcal{X}$ with finite frame $[0,c]$ with $x_0^{*,\lambda }=\rho (\lambda )$ such that, as $n\to \infty$ with ${\lambda }^n\to \lambda \ge 0$ and ${\pi }_j^n\to {\pi }_j$ for all j (as all other system parameters remain fixed),

   $$x^n(\infty )\Rightarrow x^{*,\lambda }.$$(6)

2. Function $\rho (\lambda )$ is a strictly increasing continuous function, mapping $[0,\infty )$ onto $[0,1)$. The dependence of element $x^{*,\lambda }$ on λ is strictly increasing continuous in $[0,\infty )$. (Strictly increasing here means that $x_w^{*,\lambda }$ is strictly increasing for each $w\ge 0$.) Furthermore, $x^{*,\lambda }\to x^{**,c}$ as $\lambda \uparrow \infty$.

As a corollary of (i), we also have the following steady-state asymptotic independence property, for any $\lambda \ge 0$ and any fixed integer $m\ge 1$:

$$[W_1^n(\infty ),\dots ,W_m^n(\infty )]\Rightarrow [W_1^{*},\dots ,W_m^{*}], n\to \infty ,$$(7)

where random variables $W_i^{*}$ are i.i.d. with $\mathbb{P}\{W_i^{*}>w\}=x_w^{*,\lambda }, w\ge 0$. (This is a corollary because, as a result of the symmetry between servers, in steady-state, the joint distribution of workloads of servers $1,\dots ,m$ is equal to that for a set of m servers chosen uniformly at random.)

The proof of Theorem 1 is in Section 11.

5. Main Results for the Infinite-Frame (Nontruncated) System

5.1. Stability Properties for a Fixed n

Our first main result for the infinite-frame system, Theorem 2, concerns its stability properties for each fixed n. For the infinite-frame system with a fixed n, consider process $W^n(·)$ with different values of λⁿ, and let us use notation $W^{n,{\lambda }^n}(·)$ to indicate the dependence on λⁿ. (Here, the value of λⁿ varies for a fixed n, whereas the probabilities ${\pi }_j^n$ remain fixed.)

Recall that the system is non-work-conserving. As a result, given the arrival rate λⁿ, the question of the process stability is nontrivial. Moreover, even some “very intuitive” properties are not automatic. Let us denote by

the system steady-state load, assuming the system is stable for a given λⁿ. Then, it is natural to expect that, as we continuously increase λⁿ from 0, the steady-state load ${\rho }^n({\lambda }^n)$ continuously increases from 0 and ${\rho }^n({\lambda }^n)\uparrow 1$ as λⁿ approaches some critical value ${\overline{\lambda }}^n$. This property, however, is not automatic. We prove it in the following Theorem 2. (In addition to being of interest in itself, we use this property in the proofs of our asymptotic results.)

Denote

Theorem 2.

For a fixed n, consider the infinite-frame system and the corresponding process $W^{n,{\lambda }^n}(·)$ with λⁿ being a parameter, and ${\overline{\lambda }}^n$ defined in (9). Then, the following hold.

1. We have $0<C_1<{\overline{\lambda }}^n<C_2<\infty$ with C₁, C₂ independent of n. Process $W^{n,{\lambda }^n}(·)$ is stable for any ${\lambda }^n<{\overline{\lambda }}^n$.

2. Function ${\rho }^n({\lambda }^n)$ is a strictly increasing continuous (one-to-one) mapping of $[0,{\overline{\lambda }}^n)$ onto $[0,1)$.

The proof of Theorem 2 is in Section 8.

5.2. Tightness of Stationary Distributions of Centered States

For some (not all) of our results, we need the following additional assumptions, namely, finite second moments of the component sizes (Assumption 3) and further (nonrestrictive) nontriviality conditions (Assumption 4).

Assumption 3.

For any j, $\mathbb{E}{[{\xi }_1^{(j)}]}^2<\infty$ (and then $\mathbb{E}{[{\sum }_i{\xi }_i^{(j)}]}^2<\infty$).

Assumption 4.

There exists a class j with k_j < d_j and the joint distribution F_j of the component sizes such that:

1. $\mathbb{P}\{{\max }_i{\xi }_i^{(j)}-{\xi }_{i_1}^{(j)}>0\}>0$, where ${\xi }_{i_1}^{(j)}$ is the k_j-th smallest among the component sizes ${\xi }_i^{(j)}$.

2. $\mathbb{P}\{{\sum }_i\mathbf{I}({\xi }_i^{(j)}=0)\ge k_j\}<1$.

Assumption 4(i) holds in most cases of interest. For example, it automatically holds when there is a class j with i.i.d. component sizes with a component size distribution not concentrated on a single point. Assumption 4(ii) is a slightly stronger version of Assumption 2 (adding that k_j < d_j holds for the class j). This assumption automatically holds, for example, when there is a class j with k_j < d_j and i.i.d. component sizes.

For an element $y\in \tilde{\mathcal{X}}$, denote by $\overline{y}$ the mean of the corresponding distribution,

with the usual convention that the mean is finite when both integrals in the RHS are finite. When $\overline{y}$ is finite, denote by $\stackrel{°}{y}=(\stackrel{°}{y}{\hspace{0.17em}}_u, u\in \mathbb{R})$ the centered version of y, namely, and denote

Denote by $\stackrel{°}{{\mathcal{X}}_1}$ the subset of those $y\in {\tilde{\mathcal{X}}}_1$ with mean $\overline{y}=0$.

Recall that ${\mathcal{X}}^{(n)}\subset {\mathcal{X}}^{pr}$ is the state space of the process $x^n(·)$. For any n, denote by $\stackrel{°}{{\mathcal{X}}^{(n)}}\subset {\tilde{\mathcal{X}}}^{pr}$ the state space of the process $\stackrel{°}{x^n}(·)$. (Process $\stackrel{°}{x^n}(·)$ is not Markov; it is a projection of Markov process $\stackrel{°}{x^n}(·)$. Of course, $\stackrel{°}{{\mathcal{X}}^{(n)}}$ is a projection of ${\mathcal{X}}^{(n)}$.) Obviously, for any n and any $\ell \ge 1$, $\stackrel{°}{{\mathcal{X}}^{(n)}}\subset \stackrel{°}{{\mathcal{X}}_1}\cap {\tilde{\mathcal{X}}}_{\ell }$.

Theorem 3.

Consider the infinite-frame system. Suppose the additional Assumptions 3 and 4 hold. Then, there exist $\overline{C}>0$ and $\overline{n}$ such that, uniformly in $n\ge \overline{n}$ and λⁿ such that the process $x^n(·)$ is stable, we have

$$\mathbb{E}{\mathrm{\Phi }}_1(\stackrel{°}{x}{\hspace{0.17em}}_n(\infty ))\le \overline{C}.$$(10)

The proof of Theorem 3 is given in Section 9. Note that the theorem implies the tightness of the family of distributions of $\stackrel{°}{x^n}(\infty )$ for $n\ge \overline{n}$ and those λⁿ for which stability holds in the space of distributions on ${\tilde{\mathcal{X}}}^{pr}$. (Hence, the title of this section.) Indeed, for any $\delta >0$, we can choose a constant C large enough so that $\mathbb{P}\{{\mathrm{\Phi }}_1(\stackrel{°}{x^n}(\infty ))\le C\}\ge 1-\delta$ uniformly within the specified family and set $\{{\mathrm{\Phi }}_1(x)\le C\}$ compact in ${\tilde{\mathcal{X}}}^{pr}$.

The proof of Theorem 3 uses a quadratic Lyapunov function ${\mathrm{\Phi }}_2(\stackrel{°}{x^n}(t))$, which is a function of the set of particle locations centered by their average. This provides the intuition for why the bound (10)—and the tightness of the family of distributions of $\stackrel{°}{x^n}(\infty )$—holds uniformly in λⁿ. Informally speaking, when ${\mathrm{\Phi }}_2(\stackrel{°}{x^n}(t))$ is large, it has a negative drift regardless of how close the particle locations are to the boundary at zero—only particle relative locations matter. (This, in turn, is due to the fundamental model property (b) referred to in the introduction: the servers with lower workload receive larger expected additional workload of arriving jobs.) In fact, a version of Theorem 3 holds for an artificial free system, in which particle locations (server workloads) are not regulated at zero; namely, they evolve in $\mathbb{R}$ rather than in ${\mathbb{R}}_{+}$ with each particle keeping moving left at constant rate –1 unless/until it jumps right because of a job arrival. The corresponding result, Theorem 11, is given in Section 16, in which we also discuss its connection to Theorem 2.

Assumption 3—the finiteness of second moments of component sizes—is employed in the proof of Theorem 3 in the estimates of the steady-state drift of the quadratic Lyapunov function ${\mathrm{\Phi }}_2(\stackrel{°}{x^n}(t))$. Informally speaking, it guarantees that the expected increment of ${\mathrm{\Phi }}_2(\stackrel{°}{x^n}(t))$ resulting from a job arrival is equal, up to a bounded additive term, to the first order approximation of the expected increment; see (26) and its proof in Section 9.2.

5.3. Steady-State Asymptotic Independence Results

The following Theorem 4 assumes a certain uniqueness condition, namely, Assumption 5 given later in Section 12. This uniqueness condition is in terms of fixed points of the system mean-field limits; these notions are defined later in the paper, which requires a fair amount of preliminaries and analysis. That is why the formal statement of Assumption 5 is postponed until the point (Section 12) at which we are in position to do so.

Theorem 4.

Consider an infinite-frame (nontruncated) system, that is, with frame $[0,\infty )$. Suppose the additional Assumptions 3 and 4 hold. Suppose also that Assumption 5 (given later in Section 12) holds for all $\lambda \ge 0$.

Then, there exists $\overline{\lambda }\in (0,\infty )$ such that the following hold:

1. For each $\lambda \in [0,\overline{\lambda })$, there exists $\rho (\lambda )\in [0,1)$ and a unique proper element $x^{*,\lambda }\in \mathcal{X}$ with $x_0^{*,\lambda }=\rho (\lambda )$ such that, as $n\to \infty$, with ${\lambda }^n\to \lambda \ge 0$ and ${\pi }_j^n\to {\pi }_j$ for all j (as all other system parameters remain fixed),

   $$x^n(\infty )\Rightarrow x^{*,\lambda }.$$(11)

2. Function $\rho (\lambda )$ is strictly increasing continuous, mapping $[0,\overline{\lambda })$ into $[0,1)$. Function $x^{*,\lambda }$ (of λ) is strictly increasing continuous in $[0,\overline{\lambda })$ and such that $x^{*,\lambda }\to x^{**}$ as $\lambda \uparrow \overline{\lambda }$.

3. If $\lambda \ge \overline{\lambda }$,

   $$x^n(\infty )\Rightarrow x^{**}, n\to \infty .$$(12)

   As corollaries of (ii) and (iii), we also have the following steady-state asymptotic independence properties for any fixed integer $m\ge 1$:

   • ii'. If $\lambda <\overline{\lambda }$,

     $$[W_1^n(\infty ),\dots ,W_m^n(\infty )]\Rightarrow [W_1^{*},\dots ,W_m^{*}], n\to \infty ,$$(13)
     where random variables $W_i^{*}$ are i.i.d. with $\mathbb{P}\{W_i^{*}>w\}=x_w^{*,\lambda }, w\ge 0$.

   • iii'. If $\lambda \ge \overline{\lambda }$,

     $$[W_1^n(\infty ),\dots ,W_m^n(\infty )]\Rightarrow [\infty ,\dots ,\infty ], n\to \infty .$$(14)

     (Property (ii') follows from (ii) because, as a result of the symmetry between servers, in steady-state, the joint distribution of workloads of servers $1,\dots ,m$ is equal to that for a set of m servers chosen uniformly at random. Property (iii') follows from (iii) by an analogous argument, which includes the possibility of prelimit systems being either stable or unstable.)

The proof of Theorem 4 is in Section 13.

The next main result on the steady-state asymptotic independence is Theorem 5. It shows that the conclusions of Theorem 4 hold for an important wide class of systems in which, for each class j, the component sizes are i.i.d. with a distribution H_j having an increasing hazard rate (IHR, see Definition 1). Theorem 5 is proved by showing that, in essence, such systems satisfy the conditions of Theorem 4. Most importantly, an i.i.d. IHR condition on component sizes implies Assumption 5, via an “intermediate” condition that we call D-monotonicity; see Definition 2 and Theorem 6 in Section 5.4.

Definition 1

(IHR). A distribution $H(·)$ on ${\mathbb{R}}_{+}$ has an IHR if

$$\frac{H(y_1+\mathrm{\Delta })-H(y_1)}{1-H(y_1)}\le \frac{H(y_2+\mathrm{\Delta })-H(y_2)}{1-H(y_2)}, \forall 0\le y_1\le y_2 \text{such} \text{that} H(y_2)<1, \forall \mathrm{\Delta }\ge 0.$$(15)

An IHR distribution $H(·)$ necessarily has the following structure. Let $y_{\mathit{max}}=\sup \{y\ge 0|H(y)<1\}\le \infty$ (with y_max = 0 if $H(0)=1$). Then, there exists a nonnegative nondecreasing hazard rate function $h(y), y\in [0,y_{\mathit{max}})$ such that

$$1-H(y)=\exp \{-{\displaystyle {\int }_0^{y}h}(u)du\}, y<y_{\mathit{max}}.$$

Thus, $H(·)$ has density $[1-H(y)]h(y)$ in $[0,y_{\mathit{max}})$; when $y_{\mathit{max}}<\infty$, the distribution may have an atom at y_max with mass $1-H(y_{\mathit{max}}-)=\exp \{-{\int }_0^{y_{\mathit{max}}}h(u)du\}$.

Examples of IHR distributions include the exponential distribution (which, in fact, has a constant hazard rate), a deterministic distribution concentrated on a single point $a\ge 0$, and a uniform distribution on a finite interval $[0,a]$. Also, if a random variable A has an IHR distribution and $a\ge 0$ is a constant, then the truncated random variable $A\wedge a$ also has an IHR distribution.

We say that a distribution H is a mixture of distributions $H_{\chi }$, parameterized by χ, if H is obtained by averaging $H_{\chi }$ w.r.t. some probability measure on the values of χ.

Theorem 5.

Consider an infinite-frame (nontruncated) system, that is, with frame $[0,\infty )$. Suppose the distribution F_j for each class j is such that the component sizes are i.i.d. with an IHR distribution $H_j(·)$ (in which case Assumption 3 holds automatically), or more generally, F_j may be a mixture of such distributions, in which case we make Assumption 3. (In this theorem we do not make Assumption 5 or additional Assumption 4.) Then, the conclusions of Theorem 4 hold.

The proof of Theorem 5 is in Section 14.

Some additional results on the steady-state asymptotic independence for infinite-frame systems are presented in Section 15.

5.4. Conditions Sufficient for Assumption 5 to Hold

For each job class j with its parameters $k_j,d_j,F_j$, and each integer $m\le d_j$, let us define a customer subclass j^m as follows: it is an (artificial) class with parameters $k_j^m,d_j^m,F_j^m$, where $k_j^m=k_j\wedge m,\hspace{0.17em}{d}_j^m=d_j\wedge m$, and the exchangeable m-dimensional distribution $F_j^m$ is the projection of distribution F_j on the first m coordinates. In words, subclass j^m is the same as class j except that only m components out of d_j are considered arrived, whereas the remaining $d_j-m$ components are “ignored.” The cancellation of the residual job service occurs when any $k_j\wedge m$ job components complete service. Note that, when m = d_j, the subclass j^m is equal to the class j itself; when m = 0, j^m is the “empty subclass”—nothing happens in the system when such job arrives.

Consider an infinite frame system. Consider a fixed job class j (or subclass j^m). Let $(Z_1,\dots ,Z_{d_j})$ be the ordered workload vector for a selection set (of a class j job); namely, Z_i are the workloads of selected servers, ordered to form a nondecreasing sequence, $Z_i\le Z_{i+1}$. Denote by $D=(D_1,\dots ,D_{d_j})$ the workload-differential vector, where $D_1=0,\hspace{0.17em}{D}_i=Z_i-Z_{i-1}, i=2,\dots ,d_j$. Denote by ${\eta }_j(D)$ the (random) total workload brought by a class j job given the selection set workload-differential vector is D. It is easy to see that

Definition 2

(D-Monotonicity). Consider an infinite frame system. A class j (or subclass j^m) is called D-monotone decreasing if its distribution F_j of component sizes is such that $\mathbb{E}{\eta }_j(D)$ is nonincreasing in D, that is, $D\ge D\prime$ implies $\mathbb{E}{\eta }_j(D)\le \mathbb{E}{\eta }_j(D\prime )$.

Theorem 6.

1. If all classes j and all their subclasses j^m are D-monotone decreasing, then Assumption 5 holds for all $\lambda \ge 0$.

2. Suppose the distribution F_j for a class j is such that the component sizes are i.i.d. with an IHR distribution $H_j(·)$. (Or, more generally, F_j may be a mixture of such distributions.) Then, class j and all its subclasses j^m are D-monotone decreasing.

The proof of Theorem 6 is in Section 12.

Further discussion of Assumption 5 and related additional results on the steady-state asymptotic independence for infinite-frame systems are presented in Section 15.

6. Monotonicity and Continuity Properties

In this section, we consider a system with fixed finite n and describe basic monotonicity and continuity properties of our model. For that, as in, for example, Stolyar (2015) and Shneer and Stolyar (2021), it is convenient to adopt a more general view of the model that allows some of the server workloads to be infinite. Obviously, this generalization is only relevant for infinite-frame systems (because, in finite-frame systems, the workloads are uniformly upper bounded by definition). Specifically, if the server i workload is initially infinite, $W_i^n(0)=\infty$, then, by convention, it remains infinite at all times, $W_i^n(t)=\infty ,\hspace{0.17em}t\ge 0$. The same workload placement rules apply with the convention that an infinite workload remains infinite when “more” workload is added to it. Under this more general view of the model, $W^n(·)$ is still a well-defined Markov process, but its state space is ${\overline{\mathbb{R}}}_{+}^n$, not ${\mathbb{R}}_{+}^n$. Similarly, $x^n(·)$ is still a well-defined Markov process, but its state space is a subset of $\mathcal{X}$, not a subset of ${\mathcal{X}}^{pr}$.

Note that the fraction of infinite-workload servers remains constant at all times: $x_{\infty }^n(t)=x_{\infty }^n(0),\hspace{0.17em}t\ge 0$. This means that, if the initial state $x^n(0)$ is proper, that is, $x_{\infty }^n(0)=0$, the process “lives” on proper states thereafter. The version of the process confined to proper states (in ${\mathcal{X}}^{pr}$), is the process as we defined it originally, and we sometimes refer to it as standard. The version of the process allowing improper states in $\mathcal{X}$ (that is, allowing infinite server workloads) is referred to as generalized. In the rest of the paper, unless explicitly stated otherwise, we refer to the standard version of the process.

All continuity and monotonicity properties that we need stem from the following simple fact. (Its proof is very straightforward, so we skip it.)

Lemma 1.

Consider a fixed set of servers, selected by a class-j job, labeled WLOG by $1,2,\dots ,d_j$ with (deterministic) workloads given by vector $W=(W_1,\dots ,W_{d_j})$. Let ${\xi }^{(j)}=({\xi }_1^{(j)},\dots ,{\xi }_{d_j}^{(j)})$ be the (deterministic) vector of the component sizes of the job. Denote by $\widehat{W}=({\widehat{W}}_1,\dots ,{\widehat{W}}_{d_j})$ the vector of the server workloads after the job is added. Then, $\widehat{W}$ is monotone nondecreasing and continuous in both W and ${\xi }^{(j)}$.

As a corollary of Lemma 1, we obtain the following fact.

Lemma 2.

For a given n, consider two versions of the generalized process. The first version $W^n(·)$ has the frame size cⁿ, the arrival rate parameter λⁿ, and the job class probability distribution ${\pi }^n=({\pi }_j^n)$ as defined in our model. The second version $W^{n,(\ell )}(·)$ has the frame size $c^{n,(\ell )}$, the arrival rate parameter ${\lambda }^{n,(\ell )}$, and a possibly different job class probability distribution ${\pi }^{n,(\ell )}=({\pi }_j^{n,(\ell )})$. Suppose $c^n\le c^{n,(\ell )}$ and ${\lambda }^n{\pi }^n\le {\lambda }^{n,(\ell )}{\pi }^{n,(\ell )}$. Suppose $W^n(0)\le W^{n,(\ell )}(0)$. Then, processes $W^n(·)$ and $W^{n,(\ell )}(·)$ can be coupled so that, w.p.1,

$$W^n(t)\le W^{n,(\ell )}(t), \forall t\ge 0.$$(17)

Proof.

We couple the job arrival processes in the natural way so that, when there is a job arrival in the former system, there is also the same class job arrival in the latter system with the same selection set and same component sizes. It is easy to see that, if (17) holds just before (any) job arrival, it holds right after the job arrival as well and also in the time interval until the next arrival. By induction on the job arrival times, we see that (17) prevails at all times. □

Another corollary of Lemma 1 is the following Lemma 3, which is, in essence, a more general version of Lemma 2. It is formulated in terms of the processes’ sample path for convenience. In Lemma 3, we take a still more general view of the system. Namely, we allow that the left regulation boundary (point), which particles cannot cross, is not necessarily zero and not necessarily fixed. Instead, this regulation point, denoted by $B^n(t)$, is a function of time $t\ge 0$.

Lemma 3.

For a given n, consider two versions of the generalized process realizations, $W^n(·)$ and $W^{n,(\ell )}(·)$, corresponding to two systems with infinite frame sizes. The realizations are such that both systems receive the same sequence of common job arrivals (same job arrival times, job classes, selections sets, and component sizes). In addition, the realization of $W^{n,(\ell )}(·)$ is such that additional amounts of workload may be added to any servers at any times. The initial states (particle locations in the two systems) are such that $W^n(0)\le W^{n,(\ell )}(0)$, and the initial regulation boundaries (points) $B^n(0)$ and $B^{n,(\ell )}(0)$ are such that $B^n(0)\le B^{n,(\ell )}(0)$. Assume that one or both regulation points may move left in a way such that their instantaneous speeds are either –1 or 0; however, $B^n(t)\le B^{n,(\ell )}(t)$ holds at all times. Then, $W^n(t)\le W^{n,(\ell )}(t)$ holds for all $t\ge 0$.

Yet another corollary of Lemma 1 is the following.

Lemma 4.

For a given n, consider a generalized process $W^n(·)$ corresponding to the system with frame size cⁿ and arrival rate λⁿ. Consider also a sequence of generalized processes $W^{n,(\ell )}(·)$ indexed by $\ell \to \infty$ with the frame sizes $c^{n,(\ell )}$ and arrival rates ${\lambda }^{n,(\ell )}$. (For all these processes, the probabilities ${\pi }_j^n$ are the same.) Suppose, as $\ell \to \infty ,\hspace{0.17em}{W}^{n,(\ell )}(0)\to W^n(0),\hspace{0.17em}{c}^{n,(\ell )}\to c^n$ and arrival rates ${\lambda }^{n,(\ell )}\to {\lambda }^n$. Then, these processes can be coupled so that, w.p.1,

$$W^{n,(\ell )}(t)\to W^n(t), \forall t\ge 0, \text{and} W^{n,(\ell )}(·)\stackrel{J_1}{\to }{W}^n(·).$$(18)

Proof.

We use natural coupling of process $W^n(·)$ and all processes $W^{n,(\ell )}(·)$ so that, w.p.1, on any finite time interval $[0,T]$ for all sufficiently large $\ell$, the number of job arrivals, the job arrival times and classes, and component sizes, of the $W^{n,(\ell )}(·)$ process are equal to those of the $W^n(·)$ process. Then, w.p.1, $W^{n,(\ell )}(t)\to W^n(t)$ for any $t\ge 0$, and moreover, on any finite time interval $[0,T]$, for all sufficiently large $\ell$, trajectory $W^{n,(\ell )}(·)$ has jumps at the same times as $W^{n,(\ell )}(·)$. This implies (18). □

It follows from Lemma 2 that the following properties hold for a fixed n. For any λⁿ, the generalized process $W^{n,\varnothing }(·)$ starting from the empty initial state is stochastically increasing in time, that is,

Indeed, $W^{n,\varnothing }(0)=(0,\dots ,0){\le }_{st}{W}^{n,\varnothing }(t_2-t_1)$, and (19) follows by applying Lemma 2 with t = t₁. The monotonicity property (19) is used extensively in our analysis. In particular, it implies that

where the distribution of the random element $W^n(\infty )$ in ${\overline{\mathbb{R}}}_{+}^n$ is the lower invariant measure of the generalized process $W^n(·)$, that is, it is the (uniquely defined) stationary distribution of $W^n(·)$, which is stochastically dominated by any other stationary distribution. Note that, as already discussed, the process $W^n(·)$ for a finite-frame system is trivially stable, and therefore, the lower invariant measure is its unique stationary distribution. For the infinite-frame system, clearly, (standard) process $W^n(·)$ is stable if and only if the lower invariant measure is proper, meaning that $W_i^n(\infty )$ is finite w.p.1. for all i; if so, the lower invariant measure is the unique stationary distribution of the standard process. Also note that, formally speaking, whether the standard process $W^n(·)$ is stable or not, the distribution concentrated on the point $(\infty ,\dots ,\infty )$ is always a stationary distribution of the generalized process. Finally, note that, clearly, if the (standard) process $W^n(·)$ is stable for arrival rate λⁿ, it is also stable for any smaller arrival rate.

Lemma 5.

1. The (standard) process $W^n(·)$ ( $x^n(·)$) is stable if and only if the lower invariant measure is proper.

2. The (standard) process $W^n(·)$ ($x^n(·)$) is unstable if and only if the lower invariant measure is concentrated on the point at infinity, $(\infty ,\dots ,\infty )$. In other words, the instability is equivalent to the property that, for any initial state $W^n(0)$, we have

   $$W^n(t)\Rightarrow (\infty ,\dots ,\infty ), t\to \infty .$$(20)

Proof.

1. This is already observed in the discussion preceding the lemma.

2. The sufficiency is obvious: (20) directly contradicts the existence of a proper stationary distribution. Let us prove the necessity. Suppose, the process $W^n(·)$ is unstable. We need to prove (20) for the process starting from the empty initial state $W^n(0)$. Recall that $W^n(t)$ is stochastically monotone increasing in t, converging in distribution to $W^n(\infty )$, whose distribution is the lower invariant measure. By instability, the lower invariant measure is not proper, that is $\mathbb{P}\{W_i^n(\infty )=\infty \}=\delta >0$ for some i. In fact, by symmetry, the constant $\delta \in (0,1]$ is the same for all i. Proceeding exactly as in the proof of lemma 4 in Stolyar (2015), we show that this δ must satisfy $\delta (1-\delta )\le 0$, and therefore, δ = 1. Thus, $W^n(\infty )=(\infty ,\dots ,\infty )$. □

Lemma 5 justifies our earlier convention in Section 3.2 by which $W^n(\infty )=(\infty ,\dots ,\infty )$ for an unstable process.

From Lemmas 2, 4, and 5, we obtain the following

Lemma 6.

Recall the definition of ${\overline{\lambda }}^n$ in (9). For a fixed n and ${\lambda }^n<{\overline{\lambda }}^n$, the (standard) process $W^{n,{\lambda }^n}(·)$ is stable; denote by $W^{n,{\lambda }^n}(\infty )$ a random element whose distribution is the stationary distribution (equal to the lower invariant measure) of the process. Then, $W^{n,{\lambda }^n}(\infty )$ is continuous (in the sense of convergence in distribution) and stochastically nondecreasing for ${\lambda }^n\in [0,{\overline{\lambda }}^n)$. Furthermore, ${\rho }^n({\lambda }^n)\doteq \mathbb{P}\{W_1^{n,{\lambda }^n}(\infty )>0\}$ is a nondecreasing continuous function of ${\lambda }^n\in [0,{\overline{\lambda }}^n)$.

Proof.

The fact that $W^{n,{\lambda }^n}(\infty )$ is stochastically nondecreasing follows from the process monotonicity in λⁿ and the distribution of $W^{n,{\lambda }^n}(\infty )$ being the lower invariant measure. If we have a sequence ${\lambda }^{n,\ell }\to {\lambda }^n\in [0,{\overline{\lambda }}^n)$, the corresponding processes can be coupled so that w.p.1 we have the convergence of their busy periods and idle periods; this implies the convergence $W^{n,{\lambda }^{n,\ell }}(\infty )\Rightarrow W^{n,{\lambda }^n}(\infty )$. □

Finally, we need the following fact, which easily follows from Lemma 2 and the stochastic monotonicity (19) of the process starting from the empty state.

Lemma 7.

For a fixed n, denote by $W^{n,{\lambda }^n,\varnothing }(t), t\ge 0,$ the process with parameter λⁿ, starting from the empty state. Denote by ${\rho }^n({\lambda }^n,t)\doteq \mathbb{P}\{W_1^{n,{\lambda }^n,\varnothing }(t)>0\}$ the system expected load at time t. Then, ${\rho }^n({\lambda }^n,t)$ is continuous, strictly increasing in both λⁿ and t. We also have ${\rho }^n({\lambda }^n,0)=0$ for any λⁿ; ${\rho }^n(0,t)=0$ and ${\rho }^n({\lambda }^n,t)\uparrow 1$ as ${\lambda }^n\to \infty$ for any t. If the process is stable for λⁿ, then ${\rho }^n({\lambda }^n,t)\uparrow {\rho }^n({\lambda }^n)$ as $t\to \infty$.

7. An Equivalent View of a Generalized Process

In this section, we observe that a generalized process (for a system with some servers having infinite workload) can be equivalently viewed as a standard process for the corresponding “reduced” system, which includes only those servers with finite workloads and in which the set of job classes is expanded to include all subclasses of each class j. We use this equivalent view in the proofs of our main results.

Suppose our system with index n is such that, initially (and then at any time), ${\varphi }^{n}n$ servers have infinite workloads; the remaining $(1-{\varphi }^n)n$ servers—let us call them standard—have initially (and then at any finite time) finite workloads. Clearly, as far as behavior of the standard servers is concerned, this system is equivalent to the following one, which we call a ${\varphi }^n$-reduced system. The system contains $(1-{\varphi }^n)n$ servers, all of which are standard; the total job arrival rate is ${\lambda }^{n}n$, the same as in the original system, which means the rate per server is ${\lambda }^n/(1-{\varphi }^n)$; the set of job classes includes all subclasses j^m of all original classes j; and the probability that an arriving job is of subclass j^m is ${\pi }_{j^m}^n={\pi }_j^n{\gamma }_{j^m}^n$, where ${\gamma }_{j^m}^n$ is the probability that if d_j servers are selected uniformly at random from n servers, exactly m of them are within the subset of $(1-{\varphi }^n)n$ regular servers. Clearly, the process describing the behavior of the reduced system is standard.

Now, suppose the asymptotic regime that we consider is such that ${\varphi }^n\to \varphi \in [0,1)$. Then, for each subclass j^m, we have

Clearly, as far as behavior of the standard servers is concerned, considering such sequence of systems is equivalent to considering the corresponding sequence of ${\varphi }^n$-reduced systems. The sequence of reduced systems fits into the same asymptotic regime as our original sequence of systems but has a different number of servers ($(1-{\varphi }^n)n$ instead of n), a different per server job arrival rate ${\lambda }^n/(1-{\varphi }^n)\to \lambda /(1-\varphi )$, a different set of classes (which includes all subclasses j^m of all classes j), and different probabilities ${\pi }_{j^m}^n$ of class occurrence such that ${\pi }_{j^m}^n\to {\pi }_{j^m}$.

Note that, if all subclasses of the original system are D-monotone, the same is obviously true for any reduced system.

Finally, when we consider a reduced system, its frame size c may be finite as well as infinite. Recall that, if frame size $c<\infty$, the workloads of (standard) servers are truncated at level c.

8. Proof of Theorem 2

This proof relies on the basic monotonicity properties (in Section 6) and on the fluid limit technique for establishing stability. (The proof does not use the material in Section 7.)

Recall that we consider a system with a fixed n and the process $W^{n,{\lambda }^n}(·)$ with the superscript λⁿ indicating the dependence on the arrival rate. Also recall the notation $W^{n,{\lambda }^n,\varnothing }(·)$ for the process starting specifically from the empty initial state $W^{n,{\lambda }^n,\varnothing }(0)=(0,\dots ,0)$.

1. The uniform upper and lower bounds on ${\overline{\lambda }}^n$ follow from the fact that the expected total amount of new workload brought by an arriving job is both upper and lower bounded uniformly in n and uniformly in system states at the arrival time. The stability for any ${\lambda }^n<{\overline{\lambda }}^n$ follows from the basic monotonicity properties in Section 6; specifically, the stability for a given λⁿ implies stability for any smaller arrival rate as well.

2. Recall notation ${\rho }^n({\lambda }^n)=\mathbb{P}\{W_1^{n,{\lambda }^n}(\infty )>0\}$. By Lemma 6, as λⁿ increases in the interval $[0,{\overline{\lambda }}^n),\hspace{0.17em}{\rho }^n({\lambda }^n)$ strictly increases, continuously, from zero to some value $\nu \le 1$. It remains to prove that ν = 1. The proof is by contradiction. Suppose $\nu <1$.

As the first step, we prove that (if $\nu <1$ were to hold) the process $W^{n,{\overline{\lambda }}^n}(·)$ is stable, and

Consider a sequence of times $t_{\ell }\to \infty$. For each $t_{\ell }$, by Lemma 7, there exists unique ${\beta }^{(\ell )}$ such that $\mathbb{P}\{W_1^{n,{\beta }^{(\ell )},\varnothing }(t_{\ell })>0\}=\nu$. Again by Lemma 7, ${\beta }^{(\ell )}$ is nonincreasing in $t_{\ell }$. We must have ${\lim }_{\ell }{\beta }^{(\ell )}\ge {\overline{\lambda }}^n$. Indeed, if some ${\beta }^{(\ell )}<{\overline{\lambda }}^n$, then for a small $\mathrm{ϵ}>0,\hspace{0.17em}\mathbb{P}\{W_1^{n,{\overline{\lambda }}^n-\mathrm{ϵ},\varnothing }(t_{\ell })>0\}>\mathbb{P}\{W_1^{n,{\beta }^{(\ell )},\varnothing }(t_{\ell })>0\}=\nu$; this is, however, not possible because $W^{n,{\overline{\lambda }}^n-\mathrm{ϵ}}(·)$ is stable, and then $\mathbb{P}\{W_1^{n,{\overline{\lambda }}^n-\mathrm{ϵ},\varnothing }(t_{\ell })>0\}\le \mathbb{P}\{W_1^{n,{\overline{\lambda }}^n-\mathrm{ϵ}}(\infty )>0\}<\nu$. Now, because ${\beta }^{(\ell )}\ge {\overline{\lambda }}^n$ for all $t_{\ell }$, we have $\mathbb{P}\{W_1^{n,{\overline{\lambda }}^n,\varnothing }(t_{\ell })>0\}\le \mathbb{P}\{W_1^{n,{\beta }^{(\ell )},\varnothing }(t_{\ell })>0\}=\nu$ for all $t_{\ell }$. Recall that $t_{\ell }\to \infty$, which implies that $W^{n,{\overline{\lambda }}^n}(·)$ is stable and ${\rho }^n({\overline{\lambda }}^n)\le \nu$, where the strict inequality is impossible by the definition of ${\overline{\lambda }}^n$. Thus, we obtain (21).

The second step is to show that (21), with $\nu <1$, leads to a contradiction. This is the key step. The basic intuition for it is as follows. If the system with λⁿ exactly equal to ${\overline{\lambda }}^n$ is stable, with the load equal to $\nu <1$, the process hits the empty state (when all workloads are at the regulation boundary at zero) at a positive rate. Using monotonicity arguments, this implies that the maximum of the workloads has a strictly negative drift. (More precisely, the process fluid limit is such that the maximum of workloads, when away from zero, has a negative, bounded away from zero derivative.) Then, we observe that a system with ${\lambda }^n=\mu$ being slightly larger than ${\overline{\lambda }}^n$, is equivalent, up time rescaling, to the system with ${\overline{\lambda }}^n={\overline{\lambda }}^n$ and the speed at which workloads move to the left being slightly larger (i.e., smaller in absolute value) than –1. (Note that a time rescaling does not affect system stability/instability.) Using this, we can show that, when ${\lambda }^n=\mu$ is sufficiently close to ${\overline{\lambda }}^n$, the maximum of workloads in the equivalent system also must have a strictly negative drift. This applies the stability of the equivalent system and then also the stability of the system with ${\lambda }^n=\mu >{\overline{\lambda }}^n$—a contradiction with the definition of ${\overline{\lambda }}^n$.

We now proceed with the formal argument leading to a contradiction. Suppose (21) holds with $\nu <1$. We start with constructing a process that dominates $W^{n,{\overline{\lambda }}^n}(·)$ and is easily seen to be also stable. Consider the process, let us call it ${\widehat{W}}^{n,{\overline{\lambda }}^n}(·)$, such that, initially, all ${\widehat{W}}_i^{n,{\overline{\lambda }}^n}(0)$ are set to be equal to ${\max }_i{W}_i^{n,{\overline{\lambda }}^n}(0)$, and the left regulation boundary is reset from zero to that maximum. Using Lemma 3, the processes ${\widehat{W}}^{n,{\overline{\lambda }}^n}(·)$ and $W^{n,{\overline{\lambda }}^n}(·)$ can be coupled so that, w.p.1, $W^{n,{\overline{\lambda }}^n}(t)\le {\widehat{W}}^{n,{\overline{\lambda }}^n}(t)$ for all t; thus, ${\widehat{W}}^{n,{\overline{\lambda }}^n}(·)$ is a stochastic upper bound of $W^{n,{\overline{\lambda }}^n}(·)$. Because ${\widehat{W}}^{n,{\overline{\lambda }}^n}(·)$ is just a (shifted to the right) version of the stable process $W^{n,{\overline{\lambda }}^n}(·)$, it is also stable, and then the steady-state probability of all workloads being at the regulation boundary is some $\delta >0$. Now consider yet another version of process $W^{n,{\overline{\lambda }}^n}(·)$; let us call it ${\tilde{W}}^{n,{\overline{\lambda }}^n}(·)$. This version is the same as ${\widehat{W}}^{n,{\overline{\lambda }}^n}(·)$ with the same regulation except the following: in the time intervals when all workloads are at the regulation boundary, the regulation boundary itself moves left at the constant rate –1 until and unless it hits 0, starting that time the regulation boundary stays at zero. By Lemma 3, the process ${\tilde{W}}^{n,{\overline{\lambda }}^n}(·)$ is also a stochastic upper bound of $W^{n,{\overline{\lambda }}^n}(·)$. Comparing ${\tilde{W}}^{n,{\overline{\lambda }}^n}(·)$ to ${\widehat{W}}^{n,{\overline{\lambda }}^n}(·)$, we observe that the regulation boundary of the former has the average drift $-\delta <0$ until the boundary hits zero. Indeed, if the points in time when all workloads are at the regulation boundary are the process “renewals,” the process ${\tilde{W}}^{n,{\overline{\lambda }}^n}(·)$ has the “same” renewal cycles as ${\widehat{W}}^{n,{\overline{\lambda }}^n}(·)$ except that, when it stays in the renewal state and the regulation boundary is away from zero, the regulation boundary itself—along with all workloads—moves left at rate –1. Note that the expected duration of a renewal cycle is finite (by the stability of ${\widehat{W}}^{n,{\overline{\lambda }}^n}(·)$). Thus, he average drift of the regulation boundary of ${\tilde{W}}^{n,{\overline{\lambda }}^n}(·)$ is $-\delta$.

Consider now the version of process $W^{n,\mu }(·)$ with the arrival rate parameter $\mu >{\overline{\lambda }}^n+{\delta }_1$. Specifically consider μ being close to ${\overline{\lambda }}^n$; we specify later how close. Consider the process $W^{n,\mu }(·)$, slowed down by the factor $\gamma ={\overline{\lambda }}^n/\mu <1$, namely, the process

Obviously, $W^{n,\mu ,(\mathit{slow})}(·)$ is stable if and only if $W^{n,\mu }(·)$ is. The process $W^{n,\mu ,(\mathit{slow})}(·)$ is the same as $W^{n,{\overline{\lambda }}^n}(·)$ with the same job arrival rates and the same regulation boundary at zero but with workloads decreasing at rate $-\gamma$ (instead of –1) between the job arrivals. Consider the following process ${\tilde{W}}^{n,\mu ,(\mathit{slow})}(·)$. (Roughly speaking, it has the same relation to $W^{n,\mu ,(\mathit{slow})}(·)$ as ${\tilde{W}}^{n,{\overline{\lambda }}^n}(·)$ does to $W^{n,{\overline{\lambda }}^n}(·)$.) Initially, ${\tilde{W}}_i^{n,\mu ,(\mathit{slow})}(0)={\max }_s{W}_s^{n,\mu ,(\mathit{slow})}(0)$, and the regulation boundary is at zero. Unless all workloads are at the regulation boundary, the boundary moves right at the constant positive speed $1-\gamma$; note that, with respect to the boundary, the workloads that are not on it move at the rate –1. When and only when all workloads are at the regulation boundary, the boundary (along with all workloads) moves left at speed $-\gamma$; the regulation boundary can never go to the left of zero. Process ${\tilde{W}}^{n,\mu ,(\mathit{slow})}(·)$ is a stochastic upper bound of $W^{n,\mu ,(\mathit{slow})}(·)$. Note that the renewal cycles of ${\tilde{W}}^{n,\mu ,(\mathit{slow})}(·)$ with respect to the regulation boundary, again, have the same structure as those of ${\widehat{W}}^{n,{\overline{\lambda }}^n}(·)$; in particular, the steady-state probability of all workloads being at the boundary is δ. What is different is the movement of the regulation boundary itself. Combining all these observations, we conclude that the regulation boundary of the process ${\tilde{W}}^{n,\mu ,(\mathit{slow})}(·)$ has the average drift

as long as the boundary is away from zero. We now choose μ sufficiently close to ${\overline{\lambda }}^n$, that is, γ sufficiently close to 1 so that $-{\delta }_1<0$. This, along with the finite expectation of a renewal cycle duration, implies the stability of ${\tilde{W}}^{n,\mu ,(\mathit{slow})}(·)$. For example, the fluid limit technique for stability (Rybko and Stolyar 1992, Dai 1995, Stolyar 1995, Bramson 2008) can be applied; indeed, in this case, the fluid limit $q(·)=(q_i(·))$ of the process ${\tilde{W}}^{n,\mu ,(\mathit{slow})}(·)$ is easily seen to be unique and such that all $q_i(t)$ are equal at all times and $q{\prime }_i(t)=-{\delta }_1<0$ when $q_i(t)>0$; this implies the stability of the fluid limit and then the stability of ${\tilde{W}}^{n,\mu ,(\mathit{slow})}(·)$. Then, by the stochastic dominance, $W^{n,\mu ,(\mathit{slow})}(·)$ is also stable. Finally, this implies the stability of $W^{n,\mu }(·)$, which, because $\mu >{\overline{\lambda }}^n$, contradicts the definition of ${\overline{\lambda }}^n$. This contradiction, obtained from the assumption $\nu <1$, proves that ν = 1, which completes the proof. □

9. Proof of Theorem 3

This proof is mostly self-contained. It does use the basic continuity properties in Section 6. (The proof does not use the material in Sections 7 and 8.) The basic intuition for this proof is given in the discussion of Theorem 3 following its statement in Section 5.2.

If $x^n(t)$ is the state at t, it can be equivalently described as $p^n(t)=(w_1(t),w_2(t),\dots ,w_n(t);z(t))$, where $z(t)=-{\overline{\mathit{x}}}^n(t)\le 0$ is the location of the origin w.r.t. to the mean ${\overline{\mathit{x}}}^n(t)$, and $w_1,w_2,\dots ,w_n\ge z$ are the locations of the n particles (not necessarily ordered in any way) w.r.t. the mean ${\overline{\mathit{x}}}^n(t)$. Slightly abusing notation by defining ${\mathrm{\Phi }}_{\ell }(p^n(t))$ as ${\mathrm{\Phi }}_{\ell }(\stackrel{°}{x^n}(t))$ for the corresponding $\stackrel{°}{x^n}(t)$, that is

The evolution of $p^n(t)$ is as follows. Note that here the particle locations $w_i(t)$ may be negative as well as nonnegative. Point z(t) serves as a regulation boundary, which evolves in time; $z(t)\le 0$ at all times. Denote by $I_z(t)$ the (possibly empty) subset of particles, which are located exactly at the regulation boundary z(t) at time t. Between the times of the particle jumps (job arrivals), the boundary z(t) moves right at the constant nonnegative speed $(n-|I_z(t)|)/n$; the particles in $I_z(t)$ (those located exactly at the boundary z(t)) stay at the boundary and, therefore, move with it right at constant nonnegative speed $(n-|I_z(t)|)/n$; each particle that is not at z(t) (i.e., not within subset $I_z(t)$) moves left at the constant nonpositive speed $-|I_z(t)|/n$; and when a particle hits boundary z(t), it joins the set $I_z(t)$. (The average of the particle locations stays at zero as it should by the p(t) definition.) It is easy to see that, for any $\ell \ge 1,\hspace{0.17em}{\mathrm{\Phi }}_{\ell }(p^n(t))$ is absolutely continuous with the derivative (existing almost everywhere) $(d/dt){\mathrm{\Phi }}_{\ell }(p^n(t))\le 0$, and moreover, $(d/dt){\mathrm{\Phi }}_{\ell }(p(t))<0$ as long as $0<|I_z(t)|<n$. At a time when one or more particles jump (upon a job arrival), the following occurs. Let ${\kappa }_i(t)$ be the amount of new workload added to server i by the job arriving at time t (which may be nonzero only for the servers within the selection set of the job). Then, particle i jump size at t is ${\zeta }_i={\kappa }_i(t)-{\sum }_s{\kappa }_s(t)/n$ (which may be positive or negative); the point z(t) jumps (left) by $-{\sum }_s{\kappa }_s(t)/n$.

Consider the following function $G^{(n)}(\stackrel{°}{x^n}), \stackrel{°}{x^n}\in \stackrel{°}{{\mathcal{X}}^{(n)}},$

where ${\zeta }_i^{(\stackrel{°}{x^n})}$ is the random jump size (which can have any sign) of particle i upon a job arrival when the state is $\stackrel{°}{x^n}$. (The sizes ${\zeta }_i^{(\stackrel{°}{x^n})}$ are dependent across i of course.) As we see, function $G^{(n)}(p^n)$ can be thought of as the first order approximation of the generator of process $p^n(·)$, applied to function ${\mathrm{\Phi }}_2(p^n)$, but we do not even claim that ${\mathrm{\Phi }}_2(p^n)$ is within the generator domain.

For future reference, note that, for each n, $G^{(n)}(\stackrel{°}{x^n})$ is continuous in $\stackrel{°}{x^n}\in \stackrel{°}{{\mathcal{X}}^{(n)}}$. Also note that each $\mathbb{E}{\zeta }_i^{(\stackrel{°}{x^n})}$ is the quantity of the order $O(1/n)$, which motivates the definition

We can then write

We define the function ${\overline{\zeta }}^{(\stackrel{°}{x^n})}(w), w\in \mathbb{R},$ as follows: ${\overline{\zeta }}^{(\stackrel{°}{x^n})}(w)={\overline{\zeta }}_i^{(\stackrel{°}{x^n})}$, where i is the particle whose location w_i is the closest to w on the left; we also adopt a conventions that, if w_i is the location of the leftmost particle, then ${\overline{\zeta }}^{(\stackrel{°}{x^n})}(w)={\overline{\zeta }}_i^{(\stackrel{°}{x^n})}$ for all $w<w_i$. Clearly, function ${\overline{\zeta }}^{(\stackrel{°}{x^n})}(w)$ is a piecewise constant nonincreasing function, and we can write

where the inequality in (23) follows because

${\overline{\zeta }}^{(\stackrel{°}{x^n})}(w)-{\overline{\zeta }}^{(\stackrel{°}{x^n})}(0)$ is nonincreasing with value zero at zero, and $\stackrel{°}{x^n}\in \stackrel{°}{{\mathcal{X}}_1}$ (and then ${\int }_{-\infty }^{\infty }wd[-\stackrel{\hspace{0.17em}}{x°}{ }_w^n]=0$).

Next, we claim the following property: there exists a sufficiently large C > 0 and some $\mathrm{ϵ}>0$ such that, uniformly in all sufficiently large n and all $\stackrel{°}{x^n}\in \stackrel{°}{{\mathcal{X}}^{(n)}}$ with ${\mathrm{\Phi }}_1(\stackrel{°}{x^n})\ge C$,

The proof of (24) is given in Section 9.1.

From (24) and (23), we obtain that, uniformly in all sufficiently large n,

Denote by ${\mathrm{\Phi }}_2^{(C_2)}(p^n)={\mathrm{\Phi }}_2(p^n)\wedge C_2$ the function ${\mathrm{\Phi }}_2$ truncated at level C₂. Given that this is a continuous bounded function and using Lemma 1, the continuity in pⁿ of the workload amounts added by a job, it is not hard to see that it is within the domain of the generator $A^{(n)}$ of process $p^n(·)$.

Next, we claim the following fact: there exists $C_1>0$ such that for any fixed $C_2>0$, uniformly in all large n and pⁿ such that ${\mathrm{\Phi }}_2(p^n)\le C_2$, we have

and then with $C_3=\mathrm{ϵ}C+C_1$. The proof of (26) is given in Section 9.2.

Bound (27), in turn, implies that, for any fixed $C_2>0$,

Recalling that $p^n(\infty )$ is the random value of $p^n(t)$ in the stationary regime, we have for all large n,

and then

Letting $C_2\uparrow \infty$, we finally obtain that

for all sufficiently large n, and then holds for all n for some large $\overline{C}>0$. □

9.1. Proof of (24)

The definition of ${\overline{\zeta }}_i={\overline{\zeta }}_i^{(\stackrel{°}{x^n})}$ in (22) can be interpreted as follows: ${\overline{\zeta }}_i$ is the expected amount of new workload $\mathbb{E}[{\kappa }_i|i\in S]$ the server i receives, conditioned on it being selected by a job, multiplied by constant $[n\mathbb{P}\{i\in S\}]$ (which is close to the constant ${\sum }_j{\pi }_j{d}_j$ for all large n), and then centered by the total expected amount of new workload $\mathbb{E}{\sum }_s{\kappa }_s$ brought by a job.

The proof is by contradiction. Suppose Property (24) does not hold. Then, we can and do choose a subsequence of $n\to \infty$ and corresponding $\stackrel{}{x^n°}$ so that, along this subsequence $c_n={\mathrm{\Phi }}_1(\stackrel{°}{x^n})\uparrow \infty$ and

Using the continuity of $G^{(n)}(\stackrel{°}{x^n})$ in $\stackrel{}{x^n°}\in \stackrel{°}{{\mathcal{X}}^{(n)}}$, we also can and do choose this subsequence so that all particle locations w_i are distinct (i.e., $\stackrel{°}{x^n}$ has exactly n jumps; at points w_i, each jump is by $1/n$). For a fixed $\nu \in (0,1/4)$ and each n, denote

It is easy to see that, for a sufficiently small fixed $\delta >0$, uniformly in n and $\nu \in (0,1/4)$,

(Otherwise, ${\int }_{-\infty }^0|w|d[-\stackrel{\hspace{0.17em}}{x°}{ }_w^n]={\int }_0^{\infty }wd[-\stackrel{\hspace{0.17em}}{x°}{ }_w^n]=c_n/2$ cannot hold.) Denote

It is easy to see that, for any ${\delta }_1>0$, we can fix a sufficiently small $\nu >0$ such that, uniformly in all large n,

(If not, because both $a_{\nu ,n}^{+}/c_n$ and $a_{\nu ,n}^{-}/c_n$ are bounded away from zero, ν could not be small.) Let us fix any ${\delta }_1\in (0,1/2)$ and then choose a corresponding ν.

Observe that the following holds for each large n. The distance between the particles located at $a_{\nu ,n}^{-}$ and $a_{\nu ,n}^{+}$—let us label them i⁻ and i⁺—is at least $2\delta c_n$, and there is at least $(1-2{\delta }_1)n/2$ (i.e., a nonzero fraction) of particles, located strictly between particles i⁻ and i⁺.

Using coupling and Assumption 4 (this is the only place where this assumption is used), we obtain that there exists ${\delta }_2>0$ such that

Indeed, when a job arrival selects both i⁻ and i⁺, then, conditioned on this event, by monotonicity, i⁻ receives at least as much average new workload as i⁺. Also, clearly, the probability that both i⁻ and i⁺ are selected by an arriving job, under the condition that i⁻ (i⁺) is selected, vanishes as $n\to \infty$. Thus, to show (30), is suffices to consider two probability spaces, E⁻ and E⁺, obtained by conditioning on the two nonintersecting events, when, respectively, i⁻ (but not i⁺) and i⁻ (but not i⁺) is selected by a job. We can couple the constructions of the spaces E⁻ and E⁺ so that w.p.1 i⁻ (on E⁻) and i⁺ (on E⁺) receive equal component sizes, whereas all other selected servers and their component sizes are equal. Consider an arrival of a job of class j, satisfying Assumption 4. At least one of the following two conditions holds for $\stackrel{°}{x^n}$: (a) at least $[(1-2{\delta }_1)n/2]/2$ particles are located in $[0,a_{\nu ,n}^{+})$ or (b) at least $[(1-2{\delta }_1)n/2]/2$ particles are located in $(a_{\nu ,n}^{-},0]$. In case (a), with probability bounded away from zero, all other selected particles are in $[0,a_{\nu ,n}^{+})$; then, Assumption 4(i) easily implies (30) because, with bounded away from zero probability, i⁻ receives a new workload equal to its component size, whereas i⁺ receives a strictly smaller (by a bounded away from zero quantity) new workload. In case (b), with probability bounded away from zero, all other selected particles are in $(a_{\nu ,n}^{-},0]$; then, Assumption 4(ii) easily implies (30) because, with bounded away from zero probability, i⁻ receives some positive (bounded away from zero) new workload, whereas i⁺ receives zero new workload. This completes the proof of (30).

From (30), we see that

In either case, $G^{(n)}(\stackrel{°}{x^n})\ge ({\delta }_2/2)\nu c_n$, which contradicts (29). □

9.2. Proof of (26)

First, consider a fixed state pⁿ and consider the expected increment Δ of ${\mathrm{\Phi }}_2(p^n)$ upon a job arrival in this state. Denote by ${\zeta }_i={\zeta }_i^{(\stackrel{°}{x^n})}$ the (random) displacement of w_i because of a job arrival. Then,

where expectation $\mathbb{E}$ is with respect to the distribution of the job class, selection set, and component sizes. For ζ_i, we have where ${\kappa }_i={\kappa }_i^{(\stackrel{°}{x^n})}$, the (random) amount of workload added to server i because of a job arrival. Note that $\mathbb{E}{\zeta }_i$ is the quantity of the order $O(1/n)$ because ${\sum }_s{\kappa }_s$ is of order O(1) and $\mathbb{E}{\kappa }_i$ is of order $O(1/n)$ (because $\mathbb{P}\{i\in S\}=O(1/n)$). Therefore, ${\overline{\zeta }}_i=n\mathbb{E}{\zeta }_i=O(1)$, and we can write

Next,

because ${\sum }_i\mathbb{E}{\kappa }_i^2$ is uniformly upper bounded by the maximum (job among classes) second moment of the total size of all components. Assembling these bounds, we obtain where, recall, Δ is the expected increment of ${\mathrm{\Phi }}_2$ upon a job arrival into a fixed state pⁿ such that ${\mathrm{\Phi }}_2(p^n)\le C_2$.

Now, consider the value of the generator $A^{(n)}{\mathrm{\Phi }}_2^{(C_2)}(p^n)$ at point pⁿ. For that, consider the expected increment of ${\mathrm{\Phi }}_2^{(C_2)}(p^n(t))$ over a small interval $[0,t/n]$ with $p^n(0)=p^n$. First, note that, as $t\downarrow 0$, the contribution into this expected increment of the event that more than one job arrives, is o(t). (Because jobs arrive as a Poisson process of rate ${\lambda }^{n}n$ and ${\mathrm{\Phi }}_2^{(C_2)}$ is bounded.) With probability ${\lambda }^{n}t+o(t)$, there is exactly one job arrival in $[0,t/n]$. Moreover, note that the state into which this arrival occurs is close to pⁿ, and recall (Lemma 1) the continuity in pⁿ of the workload amounts added by a job. Finally, notice that, if a job arrival occurs into a state pⁿ such that ${\mathrm{\Phi }}_2(p^n)\le C_2$, the expected increment of ${\mathrm{\Phi }}_2^{(C_2)}$ does not exceed that of ${\mathrm{\Phi }}_2$. Using these observations and the estimate (31), we obtain (26), where C₁ is a constant such that $C_1>{\lambda }^n{C}^{\prime }{\mathrm{\hspace{0.17em}}}_1$ for all n; we omit the straightforward $\mathrm{ϵ}/\delta$ formalities. □

10. Mean-Field Limits

10.1. Mean-Field Limits and Their Fixed Points

In this section, we consider a system with infinite or finite frame size c and study the limits of the process $x^n(·)$ as $n\to \infty$. Recall that, for each n, ${\lambda }^{n}n$ is the arrival rate and ${\pi }_j^n$ are job-class occurrence probabilities, and we consider the asymptotic regime such that ${\lambda }^n\to \lambda$ and ${\pi }_j^n\to {\pi }_j, \forall j,$ as $n\to \infty$.

Theorem 7.

Assume that the initial conditions are such that $x^n(0)\to x(0)$ for some fixed $x(0)\in \mathcal{X}$. Then, there exists a deterministic trajectory $x(t), t\ge 0,$ with values in $\mathcal{X}$ and initial state x(0), such that

$$(x^n(t), t\ge 0) \stackrel{P}{\to }(x(t), t\ge 0).$$(32)

(That is, the sequence of processes $x^n(·)$ with trajectories in the Skorohod space of functions taking values in $\mathcal{X}$ converges in probability to the deterministic trajectory $x(·)$.) As a function of t (i.e., as an element of Skorohod space), x(t) is continuous.

Definition 3

(ML). The limiting deterministic trajectory $x(·)$ in Theorem 7 is called the mean-field limit (ML) with initial state $x(0)\in \mathcal{X}$.

Proof of Theorem 7.

This proof closely follows the development in section 8 of Shneer and Stolyar (2021). (The limiting trajectory $x(·)$, which we call a mean-field limit $x(·)$ in this paper, is called a fluid sample path (FSP) $x^c(·)$ in Shneer and Stolyar (2021), where c explicitly indicates the frame size.) There are some differences that we highlight here.

Just as in Shneer and Stolyar (2021), we can and do assume that, for each n, the server indices $1,\dots ,n$ are assigned to the servers randomly according to a permutation of $(1,\dots ,n)$ chosen uniformly at random. In our case, however, the initial states $x^n(0)$ and x(0) are arbitrary (as opposed to having a special form as in Shneer and Stolyar (2021)), satisfying the convergence $x^n(0)\to x(0)$. Just as in Shneer and Stolyar (2021), we have the convergence of the arrival rates, ${\lambda }^n\to \lambda$. (In Shneer and Stolyar (2021), to avoid clogging notation, the construction is given under the assumption that ${\lambda }^n=\lambda$ and ${\pi }_j^n={\pi }_j$ for all n. In this paper, the fact that λⁿ and ${\pi }_j^n$ may depend on n is crucial, so we do not make this exposition-simplifying assumption to avoid confusion.)

As in Shneer and Stolyar (2021), let us denote ${\alpha }_j=\lambda {\pi }_j{d}_j$ and $\alpha ={\sum }_j{\alpha }_j=\lambda {\sum }_j{\pi }_j{d}_j$. (Note that $\alpha \le \lambda \overline{d}$.) Parameter α_j is naturally interpreted as the limiting rate at which a given server is selected by arriving jobs of class j, and then α is the limiting total rate at which a server is selected. We also use notation ${\hat{\pi }}_j={\alpha }_j/\alpha ={\pi }_j{d}_j/[{\sum }_{\ell }{\pi }_{\ell }{d}_{\ell }]$ for the limiting probability that an arriving job selecting a server is of class j.

The definition of the formal single-server workload process $U_1(t)$ in the artificial “infinite-server system” via the dependence set ${\overline{D}}_1(t)$ is same as in Shneer and Stolyar (2021) (except, of course, for the fact that the job workload placement rule is different). We denote $x_w(t)\doteq \mathbb{P}\{U_1(t)>w\}, w\ge 0$. Let $W_i^n(t)$ be the workload of server i at time t. (We drop the superscript λⁿ because, in the setting of this lemma, λⁿ is fixed for each n.) Then, we can use exactly the same coupling as in Shneer and Stolyar (2021), under which, w.p.1, for all sufficiently large n, the dependence sets ${\overline{D}}_1(t)$ and $D_1^n(t)$ are equivalent (as defined in Shneer and Stolyar 2021), and the component size vectors for each job are same. Furthermore, given that, in the construction of $U_1(t)$, the initial workloads $W_i(0)$ of the servers in the dependence set ${\overline{D}}_1(t)$ are i.i.d. drawn from distribution x(0), and the initial workloads $W_i^n(0)$ of the servers in the dependence set $D_1^n(t)$ are chosen uniformly at random (without replacement) from the set of workloads described by $x^n(0)$, the coupling can be such that, w.p.1, $W_i^n(0)\to W_i(0)$ for each server in ${\overline{D}}_1(t)=D_1^n(t)$. Then, using Lemma 1, we conclude that, under the described coupling, w.p.1, for every $t\ge 0$,

$$\underset{n\to \infty }{\lim }{W}_1^n(t)=U_1(t),$$

implying, in particular,

$$W_1^n(t)\Rightarrow U_1(t).$$

Therefore, for any fixed t, at any point w of continuity of $\mathbb{P}\{U_1(t)>w\}=x_w(t)$ (which is almost any w w.r.t. Lebesgue measure),

$$\underset{n\to \infty }{\lim }\mathbb{P}\{W_1^n(t)>w\}=\mathbb{P}\{U_1(t)>w\}.$$

(This is slightly different from Shneer and Stolyar (2021), in which the preceding convergence holds for any $w\ge 0$.) Then, for any fixed t, for almost any w, we obtain (exactly as in lemma 12 of Shneer and Stolyar 2021)

$$x_w^n(t)\stackrel{P}{\to }{x}_w(t).$$

Recalling that x(t) and all $x^n(t)$ are elements of $\mathcal{X}$, we obtain that, for any fixed t

$$x^n(t)\stackrel{P}{\to }x(t).$$(33)

From this point on, the proof is different from the development in Shneer and Stolyar (2021). (In Shneer and Stolyar (2021), it suffices to consider only FSPs starting from special initial states x(0). In this paper, we need FSPs starting from arbitrary initial state $x(0)\in \mathcal{X}$.)

The next step is to show that

$$x(t)\hspace{0.17em}\text{is} \text{continuous} \text{in} t.$$(34)

This is equivalent to showing that $x_w(t)$ is continuous in t at every point w at which $x_w(t)$ is continuous in w. This is true; here, we use the structure of process $U_1(·)$, namely, that, for a fixed w, increase or decrease of $x_w(t)$ in a small interval $[t,t+\delta ]$ corresponds to the probabilities that the workload crosses point w in the interval $[t,t+\delta ]$ from left to right or from right to left, respectively. (More precisely, crossing point w from left to right means entering interval $(w,\infty ]$. Similarly, crossing from right to left means leaving interval $(w,\infty ]$.) As a result, $x_w(t)$, as a function of t, can never jump up, simply because the jobs selecting the server arrive according to a finite rate Poisson process. Function $x_w(t)$, of t, also cannot jump down at a point of continuity (in w) of $x_w(t)$. So we obtain (34).

Finally, from the structure of process $x^n(·)$, it is easy to see that

$$\forall \mathrm{ϵ}>0, \exists \delta >0, \forall t, \underset{n}{\lim }\mathbb{P}\{\underset{\tau \in [t,t+\delta ]}{\sup }L(x^n(\tau ),x^n(t))>\mathrm{ϵ}\}=0.$$

From this, (34), and (33), we obtain (32). □

It follows from the proof of Theorem 7 that $U_1(t), t\ge 0,$ as a random process, can be viewed as the following evolution of a single server workload (or movement of a single particle). As t increases, $U_1(t)$ and the dependence set ${\overline{D}}_1(t)$ evolve in the following fashion. At initial time 0, $U_1(0)$ is chosen randomly according to the distribution x(0), and ${\overline{D}}_1(0)=\{1\}$. Let ${\tau }_1,{\tau }_2,\dots$ be the points of the rate α Poisson process of the (artificial) job arrivals selecting server 1. In the interval $[0,{\tau }_1]$, the workload (particle location) $U_1(t)$ decreases at constant rate –1 unless and until it hits zero, and ${\overline{D}}_1(t)=\{1\}$. We can and do adopt a (nonessential) convention that ${\overline{D}}_1(t)$ and $U_1(t)$ are LCRL. (After $U_1(t)$ is defined as an LCRL process, it can always be replaced by its RCLL version if necessary.) The job arriving and selecting server 1 at time τ₁ is of some class j, and it selects $d_j-1$ servers besides server 1; for illustration purposes, suppose those are servers 2 and 3. Then,

where ${\overline{D}}_2({\tau }_1)$ and ${\overline{D}}_3({\tau }_1)$ are the random dependence sets of servers 2 and 3 at time τ₁. The dependence sets ${\overline{D}}_2({\tau }_1)$ and ${\overline{D}}_3({\tau }_1)$ do not intersect with each other, do not contain server 1, and are constructed the same way as described in Shneer and Stolyar (2021) (for ${\overline{D}}_1(t)$ with $t={\tau }_1$). Moreover, ${\overline{D}}_2({\tau }_1)$ and ${\overline{D}}_3({\tau }_1)$ are independent and identically distributed with their distribution depending only on the time τ₁. (The independence and equality of distributions here are in the sense that they would hold if the servers in both ${\overline{D}}_2({\tau }_1)$ and ${\overline{D}}_3({\tau }_1)$ use, independently, the same set of labels.) This means, in turn, that $U_2({\tau }_1)$ and $U_3({\tau }_1)$ are i.i.d. with the distribution $x({\tau }_1)$. Therefore, the value of $U_1({\tau }_1+)$ is determined by $U_1({\tau }_1)$ and the realizations of $U_2({\tau }_1),\hspace{0.17em}{U}_3({\tau }_1)$ and those of the arriving job component sizes. Then, in $({\tau }_1,{\tau }_2]$, the workload (particle location) $U_1(t)$ again decreases at constant rate –1 unless and until it hits zero. At time τ₂, another job selecting server 1 arrives, which also selects some additional servers, say, 4, 5, 6. The values of $U_4({\tau }_2),U_5({\tau }_2),U_6({\tau }_2)$ are i.i.d. with the distribution $x({\tau }_2)$. The value of $U_1({\tau }_2+)$ is determined by $U_1({\tau }_2)$ and the realizations of $U_4({\tau }_2),U_5({\tau }_2),U_6({\tau }_2)$ and those of the arriving job relica sizes. And so on. We use this interpretation of the process $U(·)$ later. One may say that $U_1(·)$ describes the random movement of a single particle in the mean-field environment defined by the time-varying distribution $x(·)$.

The following Lemma 8 easily follows from the construction of ML in Theorem 7 and the monotonicity of the prelimit process.

Lemma 8.

1. Continuity: ML $x(·)$ is continuous w.r.t. the initial state x(0).

2. Shift (“Markov”) property: If $x(·)$ is an ML, then for any $\theta \ge 0$, the trajectory $\widehat{x}(t)=x(\theta +t), t\ge 0,$ is the ML with initial state $\widehat{x}(0)=x(\theta )$.

3. Monotonicity: If $x(0)\le \widehat{x}(0)$, then the ML $x(·)$ and $\widehat{x}(·)$ with these initial conditions are such that $x(t)\le \widehat{x}(t)$ for all $t\ge 0$.

Definition 4.

Point $x\in \mathcal{X}$ is called a fixed point of the mean-field limit (ML-FP), if $x(t)\equiv x$ is an ML.

Note that, trivially, $x^{**}$ is an ML-FP for the infinite-frame system, and $x^{\varnothing }$ is the only ML-FP for the zero-frame system. ($x^{**}$ and $x^{\varnothing }$ are defined in (5) and (4).)

Lemma 9.

Consider the ML $x(·)$, starting with the empty initial state $x(0)=x^{\varnothing }$. Then, x(t) is monotone nondecreasing and $x(t)\to x^{*}$, where $x^{*}$ is an ML-FP, and moreover it is the minimum ML-FP (ML-MFP). (That is, $x^{*}\le x$ for any ML-FP x.) If $x^{*}\ne x^{**}$, then $x^{*}$ is proper.

Proof.

ML x(t) is obviously monotone nondecreasing, and so the convergence $x(t)\to x^{*}$ for some element $x^{*}\in \mathcal{X}$ does hold. That $x^{*}$ must be an ML-FP follows from Lemma 8. Indeed, the shifted versions of $x(·)$, namely, $x(\theta +t), t\ge 0,$ are ML. A sequence of such ML, with $\theta \uparrow \infty$, is such that $x(\theta +t)\to x^{*}$ at any fixed $t\ge 0$; in particular, the initial states $x(\theta )\to x^{*}$. We also have that the entire ML $x(\theta +·)$ converges to the stationary trajectory at point $x^{*}$. The latter, by Lemma 8, is an ML. Thus, $x^{*}$ is an ML-FP.

The ML-FP $x^{*}$ must be the minimum ML-FP, which follows by comparing the ML x(t) starting from the empty state with the stationary FL $\widehat{x}(t)=x$ for any ML-FP x. Because $x(t)\le x$ for all t, and $x(t)\to x^{*}$, we have $x^{*}\le x$.

Suppose $x^{*}$ is not proper, but $x^{*}\ne x^{**}$, that is, $x_{\infty }^{*}={\mathrm{ϵ}}^{*}\in (0,1)$. This leads to a contradiction by the following argument based on the monotonicity. For any $\mathrm{ϵ}<{\mathrm{ϵ}}^{*}$ arbitrarily close to ${\mathrm{ϵ}}^{*}$, the following property holds for the prelimit processes starting from the empty state:

$$\forall C>0, \exists T>0, \hspace{0.17em}\text{for}\hspace{0.17em}\text{all}\hspace{0.17em}\text{sufficiently}\hspace{0.17em}\text{large}\hspace{0.17em}n, \mathbb{P}\{W_1^n(T)\ge C\}\ge \mathrm{ϵ}.$$(35)

Note that Property (35) cannot hold when $\mathrm{ϵ}>{\mathrm{ϵ}}^{*}$. On the other hand, if we choose T₁ large enough so that (35) holds with C and T replaced by C + T and T₁, consider the time interval $[0,T_1+T]$, and use the monotonicity, we obtain

$$\text{for}\hspace{0.17em}\text{all}\hspace{0.17em}\text{sufficiently}\hspace{0.17em}\text{large}\hspace{0.17em}n, \mathbb{P}\{W_1^n(T_1+T)\ge C\}\ge \mathrm{ϵ}+(1-\mathrm{ϵ})\mathrm{ϵ}.$$

This means that (35) holds with ϵ replaced by $\mathrm{ϵ}+(1-\mathrm{ϵ})\mathrm{ϵ}$, which is greater than ${\mathrm{ϵ}}^{*}$ when ϵ is close to ${\mathrm{ϵ}}^{*}$—a contradiction. □

10.2. ML-FP as a Solution to a Functional Differential Equation

In this section, we show that an element $x\in \mathcal{X}$ is an ML-FP if and only if it is a solution to a certain functional differential equation (FDE), and we derive some properties of such solutions that we need later. It is not hard to guess the basic form of the FDE. It is also not hard to define the FDE formally and show that any ML-FP must satisfy the FDE. But, proving the converse (that any FDE solution is an ML-FP) and establishing the FDE solution properties require more involved analysis.

We start with some definitions. For any element $x\in \mathcal{X}$, let us use a slightly abusive notation $x_{[0,w]}$ for $(x_u, u\in [0,w])$, that is, for function $x_{·}$ with the domain truncated to $[0,w]$. Suppose we randomly choose a job class j according to the distribution $({\pi }_j)$, and then place the class j job on some abstract d_j servers, whose workloads are chosen randomly and independently according to distribution x. Then, let

denote the expected number of those servers whose workload, as a result, crosses level w from left to right or, more precisely, enters the interval $(w,\infty ]$. Clearly, the values of x_u for u > w have no effect on this expectation—that is why the expectation depends only on $x_{[0,w]}$.

There is an alternative, equivalent way to define functional h, which is also useful. Recall our notation $\alpha =\lambda {\sum }_j{\pi }_j{d}_j,\hspace{0.17em}{\hat{\pi }}_j={\pi }_j{d}_j/[{\sum }_{\ell }{\pi }_{\ell }{d}_{\ell }]$. For a fixed $x\in \mathcal{X},\hspace{0.17em}w\ge 0$, and a job class j, consider a cumulative distribution function (CDF) $J_j^{(x,w)}(u), u\ge 0,$ defined as follows. Consider an (abstract) “tagged” server with workload w, selected by a class j job; suppose the remaining $d_j-1$ servers, selected by this job, have random independent workloads chosen according to distribution x; then, $J_j^{(x,w)}(·)$ is the CDF of the random amount of workload that is added to the tagged server. Denote ${\overline{J}}_j^{(x,w)}(u)=1-J_j^{(x,w)}(u)$. Then, it is easy to check that

or

Denote further

Then,

It very intuitive that any ML-FP should, speaking informally at this point, satisfy the following FDE:

with the LHS being the steady-state scaled rate at which particles cross point w from right to left (leave the interval $(w,\infty ]$) and the RHS being the steady-state scaled rate at which particles cross point w from left to right (enter the interval $(w,\infty ]$). The definitions and results that follow give a precise meaning of the FDE (36) and show that, indeed, x is an ML-FP if and only if it is a solution to this equation.

Let us define the following operator A that maps $\mathcal{X}$ into itself. Let a distribution (“environment”) $x\in \mathcal{X}$ be fixed; x may or may not be proper. Consider a single particle moving in ${\mathbb{R}}_{+}$ as follows. Unless and until the particle jumps, it moves left at speed 1; if/when the particle hits the left boundary 0, it stays there until the next jump. There is a Poisson process, rate α, of time points when the particle jumps forward; if the jump occurs when the particle location is w, the jumps size distribution is $J^{(x,w)}(·)$, independent of the process history (besides current location w). Then, $Ax\in \mathcal{X}$ is the stationary distribution of the particle. Note that, if a particle is located at infinity, it stays there forever. Consequently, if x is not proper, that is, $x_{\infty }>0$, then ${(Ax)}_{\infty }=x_{\infty }$.

Definition 5.

A fixed point x of the operator A we call an OP-FP.

Lemma 10.

If x is an ML-FP, then it is an OP-FP. (We show later in Lemma 19 that, in fact, x is an ML-FP if and only if it is an OP-FP.)

Proof.

Consider the ML construction given in Theorem 7 and the interpretation of the process $U_1(·)$ given after the proof of Theorem 7. This construction defines the distribution of a single particle location at any time t. Because x is an ML-FP, x(t) = x is a stationary ML, and therefore, the distribution of the particle location is x for any t. This means that, if the particle is selected by a job at time t, then the locations of other selected particles are i.i.d. having distribution x. This, in turn, means exactly that x is a fixed point of the operator A, that is, it is a stationary distribution of a particle moving within environment x. □

Definition 6.

An element $x=(x_w)\in \mathcal{X}$ with infinite or finite frame size c we call a DE-FP if it is an α-Lipschitz (and then $(\lambda \overline{d})$-Lipschitz) function, satisfying the FDE (36) at every point $0<w<c$, where the derivative $x_w^{\prime }$ exists (which is a.e. w.r.t. the Lebesgue measure).

Lemma 11.

Any OP-FP $x=(x_w)$ is a DE-FP. Its frame size c is equal to the truncation parameter c of the model. Unless $c=\infty$ and OP-FP $x=x^{**}$ or c = 0 and OP-FP $x=x^{\varnothing }$, we have $x_0\in (0,1)$.

Proof.

By definition, OP-FP x is the stationary distribution of the location of a single particle evolving in the (stationary) environment x. Obviously, when c = 0, OP-FP $x=x^{\varnothing }$ is the unique OP-FP, and it trivially satisfies the definition of DE-FP. Similarly, when $c=\infty$, OP-FP $x=x^{**}$ trivially satisfies the definition of DE-FP. So, in the rest of the proof, it suffices to—and we do—consider an OP-FP x such that either $c\in (0,\infty )$ or {$c=\infty$ and $x\ne x^{**}$}.

We can immediately observe that $x_0\in (0,1)$ must hold because, in steady state, the particle must spend a nonzero fraction of time both at the left boundary 0 and away from it. Function x_w is α-Lipschitz because, in steady state, for any interval $[u,w]\subset [0,c)$ and any Δ-long time interval, the average amount of time the particle spends in $[u,w]$ is at most $\alpha (w-u)\mathrm{\Delta }$, and therefore, $x_u-x_w\le \alpha (w-u)$. It is also easy to see that $c\prime =\min \{w|x_w=0\}<c$ is impossible because, otherwise, in steady state, the particle must spend a nonzero fraction of time to the right of point $c\prime$—a contradiction. Therefore, $x_w>0$ for all w < c, which means that the frame size (of x) is equal to c.

Finally, consider any point $w\in (0,c)$ at which the derivative $x_w^{\prime }$ exists (which is almost any point w.r.t. the Lebesgue measure). Then, (36) must hold because its LHS is the steady-state rate at which the particle crosses point w from right to left (more precisely, leaves $(w,\infty ]$), whereas the RHS is the steady-state rate at which the particle crosses point w from left to right (more precisely, enters $(w,\infty ]$). □

Lemma 12.

For any fixed $w\ge 0$, the functional $h(x_{[0,w]})$ on $\mathcal{X}$ is ${\overline{d}}^2$-Lipschitz, w.r.t. the sup-norm on $x_{[0,w]}$, namely,

$$|h(x_{[0,w]})-h(y_{[0,w]})|\le {\overline{d}}^2\underset{0\le u\le w}{\sup }|x_u-y_u|, \forall x,y\in \mathcal{X}.$$

(Note that here x_u and y_u are not necessarily continuous.)

Proof.

It suffices to prove the following. Consider any fixed $x_{[0,w]}$ and any fixed $\delta >0$. Consider $y_{[0,w]}$ defined by: y_w = x_w and $y_u=(x_u+\delta )\wedge 1$ for u < w so it is x_u shifted up by δ, but not above one in the interval $[0,w)$. Comparing $h(x_{[0,w]})$ and $h(y_{[0,w]})$, we see that, by monotonicity (Lemma 1), the latter cannot be smaller, and recalling the definition of h (as the level w up-crossing rate) and using coupling, we see that the maximum possible up-crossing rate difference is ${\overline{d}}^2\delta$. Indeed, $\overline{d}\delta$ is the upper bound on the probability that a job arrival selects at least one server from the subset of scaled size δ; then, even if we assume that, when it happens for $h(y_{[0,w]})$, all components—at most $\overline{d}$—of this job cause their selected servers to up-cross level w, the increase in the expected number of up-crossings compared with that for $h(x_{[0,w]})$ is at most $(\overline{d}\delta )\overline{d}$. □

Lemma 13.

A DE-FP $x=(x_w)$ for a given initial condition x₀, exists and is unique, and the dependence of this DE-FP on x₀ is continuous.

Proof.

Suppose $x_0>0$. Note that (36) is equivalent to the integral equation

$$x_w=x_0-\lambda {\displaystyle {\int }_0^{w}h}(x_{[0,u]})du.$$(37)

A solution x of (37) is a fixed point of the operator

$$y_w=x_0-\lambda {\displaystyle {\int }_0^{w}h}(x_{[0,u]})du.$$(38)

In a small interval $[0,\mathrm{\Delta }]$, Operator (38) maps the space of α-Lipschitz nonincreasing functions with initial condition x₀ into itself. Using the Lipschitz property (Lemma 12) of the functional $h(x_{[0,w]})$, we see that Operator (38) is a contraction. This, by the standard Picard iterations method, establishes the existence and uniqueness of solutions to (37) in $[0,\mathrm{\Delta }]$ and then in the entire interval $[0,c]$, where c is the value of w at which the solution hits the w-axis. (In other words, c is the frame of the solution.) This also establishes the continuity of the solution in x₀ as long as $x_0>0$. For $x_0=0$, trivially, the solution to (37) is unique, equal to $x^{\varnothing }$. It is straightforward to check that the solution to (37) is continuous w.r.t. x₀ at $x_0=0$ as well. □

It immediately follows from Lemma 13 that $x^{**}$ is the unique DE-FP for $x_0=1$, and $x^{\varnothing }$ is the unique DE-FP for $x_0=0$.

Consider any DE-FP x with infinite frame size. From (37), we have

Recall the definition of $h(x_{[0,u]})$ as the average number of particles up-crossing level u upon a job arrival such that the locations of particles within its selection set are i.i.d. with distribution x. (Note that, if $x_{\infty }>0$, with probability $x_{\infty }>0$ a selected particle is at infinity.) Then, the RHS of (39) is equal the expected total amount of new workload added by such a job arrival to those selected servers whose workload is finite.

Lemma 14.

Consider any DE-FP $x=(x_w)\ne x^{**}$ with (finite or infinite) frame size c > 0. (Note that, necessarily, $x_0<1$.) Then, x satisfies the following additional properties. Function x_w is strictly decreasing in $[0,c)$. The right derivative $x_w^{\prime +}$ exists at every point $w\in [0,c)$. The left derivative $x_w^{\prime -}$ exists, and $x_w^{\prime -}\le x_w^{\prime +}$ at every point $w\in (0,c)$. (These derivatives are nonpositive.) Equation (36) holds for the right derivative $x_w^{\prime +}$ at every point $w\in [0,c)$. The right derivative $x_w^{\prime +}$ is RCLL, the left derivative $x_w^{\prime -}$ is LCRL, and each is negative bounded away from zero on any set $[0,a]$, where a < c.

Proof.

Consider a DE-FP x. It suffices to—and we do—consider the case $x_0\in (0,1)$. (If $x_0=0$, then $x=x^{\varnothing }$, and the result trivially holds.) It is easy to see that, when x_w is continuous in w (and it is), $h(x_{[0,w]})$ is RCLL as a function of w. Moreover, the left limit of $h(x_{[0,w]})$ at any point u > 0 is greater than or equal to the right limit. (The left limit at point u may be strictly greater than the right limit when there is a nonzero probability that the particle jumping forward from point 0 lands exactly at point u. Function $h(x_{[0,w]})$ is RCLL, as opposed to LCRL, because of our convention that up-crossing level w means entering $(w,c]$ as opposed to $[w,c]$.) Given that x_w is Lipschitz, and then $x_w^{\prime -}=x_w^{\prime +}$ a.e., we obtain that the left derivative is LCRL and $x_w^{\prime -}\le x_w^{\prime +}$ must hold at every $w\in (0,c)$. Then, $h(x_{[0,w]})$ must be positive, bounded away from zero on any interval $[0,a]\subset [0,c)$; otherwise, by the right-continuity of $h(x_{[0,w]})$, there exists the smallest point $u\ge 0$ such that $h(x_{[0,w]})=0$, which is impossible, as easily follows from the $h(x_{[0,w]})$ definition. □

Consider a DE-FP $x\ne x^{**}$. Its frame size c can be finite or infinite. Denote by ${\varphi }_u=x_u^{-1}, u\in [0,1]$ its inverse function. The inverse ${\varphi }_u$ has the following structure: ${\varphi }_u=0$ for $1\ge u\ge x_0$; ${\varphi }_u$ is strictly decreasing for $x_{\infty }<u\le x_0$; ${\varphi }_{x_{\infty }}={\lim }_{u\downarrow x_{\infty }}{\varphi }_u$; and ${\varphi }_u=\infty$ for $u<x_{\infty }$ (if $x_{\infty }>0$). Moreover, on any interval, $[\kappa ,x_0]\subset (x_{\infty },x_0],\hspace{0.17em}{\varphi }_u$ is Lipschitz. (This follows from x_w having negative, bounded away from zero derivative in any interval $[0,a]\subset [0,c)$.)

Lemma 15.

Consider any two DE-FP, x and $\widehat{x}$, neither equal to $x^{**}$. (They may have different frame sizes, finite or infinite, in general.) Denote by ${\varphi }_u, u\in [0,1],$ and ${\widehat{\varphi }}_u, u\in [0,1],$ their corresponding inverse functions. Denote $b=\max \{x_{\infty },{\widehat{x}}_{\infty }\}<1$, and consider the difference ${\psi }_u\doteq {\widehat{\varphi }}_u-{\varphi }_u$ for $u\in (b,1]$. Then, if for some $\chi \in (b,1]$,

$${\psi }_{\chi }=\underset{u\in [\chi ,1]}{\max }{\psi }_u>0,$$

the difference ψ_u is nonincreasing in $(b,\chi ]$.

Proof.

The proof is by contradiction. If the lemma does not hold, then the following holds for some ζ satisfying $\zeta \le \chi$ and $\zeta \in (b,1]$ and some $\beta \in (b,\zeta )$:

$${\psi }_{\zeta }=\underset{u\in [\zeta ,1]}{\max }{\psi }_u>0$$(40)

and

$${\psi }_u<{\psi }_{\zeta }, \forall u\in (\beta ,\zeta ).$$(41)

Note that, in this case, we must have $\zeta \le \min \{{\widehat{x}}_0,x_0\}$. Denote $w\doteq {\varphi }_{\zeta }<\widehat{w}\doteq {\widehat{\varphi }}_{\zeta }$. From the definition of point ζ, we have

$${\widehat{\varphi }}_{\zeta }-{\widehat{\varphi }}_u\le {\varphi }_{\zeta }-{\varphi }_u, \forall \zeta \le u\le 1.$$(42)

Recall the definition of functional h and compare $h({\widehat{x}}_{[0,\widehat{w}]})$ and $h(x_{[0,w]})$. By (42) and monotonicity (Lemma 1), we obtain

$$h({\widehat{x}}_{[0,\widehat{w}]})\le h(x_{[0,w]}).$$(43)

Let us denote by $s_{*}$ the essential lower bound on the positive component sizes:

$$s_{*}=\underset{s\ge 0}{\inf }\{\exists j, \mathbb{P}\{0<{\xi }_1<s\}>0\}.$$(44)

Consider two cases: $s_{*}<\widehat{w}$ and $s_{*}\ge \widehat{w}$.

Note that the left derivative of ${\varphi }_u^{\prime -}=1/x_z^{\prime +}$, where u = x_z. So the left derivative of ${\varphi }_u$ is determined by the right derivative of x_z.

If $s_{*}<\widehat{w}$, it is easy to observe that Inequality (43) must be strict, $h({\widehat{x}}_{[0,\widehat{w}]})<h(x_{[0,w]})$, implying ${\widehat{x}}_{\widehat{w}}^{\prime +}>x_w^{\prime +}$ and then ${\widehat{\varphi }}_{\zeta }^{\prime -}<{\varphi }_{\zeta }^{\prime -}$. Therefore ${\psi }_{\zeta }^{\prime -}<0$, which contradicts (41).

If $s_{*}\ge \widehat{w}$, it is easy to see that, at points $u<\zeta$ sufficiently close to ζ, inequality ${\widehat{\varphi }}_u^{\prime -}\le {\varphi }_u^{\prime -}$ must hold, and we, again, obtain a contradiction to (41).

We see that the Assumptions (40) and (41) lead to contradictions, which completes the proof. □

As a corollary of Lemma 15, we obtain the following

Lemma 16.

Suppose we have two DE-FP $\widehat{x}$ and x, neither equal to $x^{**}$, with ${\widehat{x}}_0>x_0$. Then, the difference of their inverses, ${\widehat{x}}_u^{-1}-x_u^{-1}$, is nonincreasing in $u\in [0,1]$ (if we adopt the convention that $+\infty -z=+\infty$ for any $z\le +\infty$). In particular, these two DE-FP cannot intersect: if x has a finite frame $[0,c]$, then ${\widehat{x}}_w>x_w$ for all $w\in [0,c]$; if x has infinite frame, then ${\widehat{x}}_w>x_u$ for all $w\in [0,\infty )$.

The next Lemma 17 also easily follows from Lemma 15.

Lemma 17.

For any $0\le c<\infty$ (and a given λ), a DE-FP x with finite frame $[0,c]$ is unique.

Proof.

Suppose not; that is, two different DE-FP $\widehat{x}$ and x with the same finite frame $[0,c]$ exist. WLOG, suppose ${\widehat{x}}_u^{-1}>x_u^{-1}$ for some u. Then, by the continuity of the inverses, the difference ${\widehat{x}}_u^{-1}-x_u^{-1}$ attains a positive maximum at some point u > 0, whereas ${\widehat{x}}_0^{-1}-x_0^{-1}=0$. This is impossible because of Lemma 15. □

Lemma 18.

For any $0\le c<\infty$ (and a given λ), consider the system with finite frame $[0,c]$. Then, the following hold.

1. The ML-FP $x^{*}=x^{*,\lambda }$ (with finite frame $[0,c]$) is unique and is equal to the unique DE-FP and unique OP-FP with this frame.

2. The convergence $x(t)\to x^{*}$ holds uniformly in all initial states x(0).

Proof.

1. Consider the $x^{*}$, which is the ML-MFP for the finite frame $[0,c]$. It is an ML-FP and then OP-FP and then DE-FP. The latter is unique by Lemma 17.

2. Any ML $x(·)$ is “sandwiched” between the MLs starting from the minimum ($x^{\varnothing }$) and maximum ($x^{**,c}$) initial states x(0). The former is monotone nondecreasing, converging to the ML-MFP $x^{*}$. The latter is monotone nonincreasing, converging to some ${\widehat{x}}^{*}\ge x^{*}$. But the limit ${\widehat{x}}^{*}$ is also an ML-FP and, therefore, is equal to the unique ML-FP $x^{*}$. □

Lemma 19.

An element $x\in \mathcal{X}$ is an ML-FP if and only if it is a DE-FP (and then an OP-FP as well).

Proof.

The “only if” part is already proved. Let us prove the “if” part. Consider the following truncated version $\widehat{x}$ of this DE-FP. Namely, fix any $\varphi >x_{\infty }$ and consider the unique finite c such that $x_c=\varphi$; then, $\widehat{x}=x_{[0,c]}$. This $\widehat{x}$ is the unique ML-FP (= OP-FP) for the $\varphi$-reduced system (as defined in Section 7) with finite frame c. Let us compare the ML $x(·)$ for the original system with initial state $x(0)=x$ and the ML $\widehat{x}(·)$ for the $\varphi$-reduced truncated system with initial state $\widehat{x}(0)=\widehat{x}=x_{[0,c]}$. From the ML construction, we see that, for any $t\in [0,c/2]$ and any $w\in [0,c/2]$, we must have $x_w(t)={\widehat{x}}_w(t)$. Because $\widehat{x}(t)\equiv \widehat{x}$ and c can be made arbitrarily large by choosing δ sufficiently close to $x_{\infty }$, we must have $x(t)\equiv x$, that is, x is an ML-FP. □

The results given so far in this section are for any fixed parameter λ and any fixed distribution $\pi =({\pi }_j)$ of job classes. We also need the following extension of Lemma 13.

Lemma 20.

The dependence of a DE-FP $x=(x_w)$ on $(x_0,\lambda ,\pi )$ is continuous.

Proof.

First, note that, if for a fixed $x_{[0,w]}$ and λ, we consider the dependence of $h(x_{[0,w]})$ on π, this dependence is $\overline{d}$-Lipschitz. (This is easy to see using coupling.) From this and Lemma 12, $h(x_{[0,w]})$ is Lipschitz in $(x_{[0,w]},\pi )$.

Consider a converging sequence $(x_0^{(\ell )},{\lambda }^{(\ell )},{\pi }^{(\ell )})\to (x_0,\lambda ,\pi )$. The corresponding sequence of (uniformly Lipschitz) DE-FP solutions $x^{(\ell )}$ is such that its any subsequence has a further subsequence along which $x^{(\ell )}\to x$. Using the fact that (37) holds for each $x^{(\ell )}$ and the properties of $h(·)$, it is straightforward to see that x must satisfy (37) for the triple $(x_0,\lambda ,\pi )$. □

11. Proof of Theorem 1

This proof relies on the properties of the mean-field limits and their fixed points that we derived in Section 10. Most importantly, it uses Lemma 18, the uniqueness of ML-FP $x^{*,\lambda }$ for a finite-frame system and the attraction to it, $x(t)\to x^{*,\lambda }$, for any ML $x(·)$.

1. Consider any subsequence of n along which the stationary distributions converge, that is, $x^n(\infty )\Rightarrow x(\infty )$, where $x(\infty )$ is some random element in $\mathcal{X}$. We know that the convergence of initial states $x^n(0)\to x(0)$ implies convergence $x^n(·)\to x(·)$ to the ML $x(·)$ with initial state x(0), and the dependence of an ML on its initial state is continuous. Then, by theorem 8.5.1 in Liptser and Shiryaev (1989), the distribution of $x(\infty )$ is stationary for the deterministic process evolving along the ML trajectories. But, by Lemma 18, all MLs converge to the ML-MFP $x^{*,\lambda }$.

2. The continuity of $x^{*,\lambda }$ in λ easily follows from the facts that the ML starting from the empty state (and converging up to $x^{*,\lambda }$) on any finite time interval is continuous with respect to λ. It is also easy to see that, as $\lambda \uparrow \infty$, the $x^{*,\lambda }$ cannot converge to anything except $x^{**,c}$. □

12. A DE-FP/ML-FP Uniqueness Condition. Proof of Theorem 6

We are now in position to formally state the following DE-FP/ML-FP uniqueness condition, which appears in the statements of Theorems 4 and 6.

Assumption 5

(DE-FP/ML-FP Uniqueness). We say that this assumption holds for a fixed $\lambda \ge 0$ if, for any sufficiently small $b\ge 0$, there is at most one DE-FP x with infinite frame and $x_{\infty }=b$.

12.1. Proof of Theorem 6(i)

This proof relies on the properties of the mean-field limits and their fixed points that we derive in Section 10.

Fix any $\lambda \ge 0$. Let us prove that Assumption 5 holds. In fact we prove that it holds for any (not necessarily small) $b\in [0,1)$. The proof is by contradiction. Suppose, there exist two different DE-FP, x and $\widehat{x}$, both with infinite frames, and such that $x_{\infty }={\widehat{x}}_{\infty }=b\in [0,1)$. Because these DE-FP are different, $x_0\ne {\widehat{x}}_0$. Let $x_0<{\widehat{x}}_0$ for concreteness. Then, by Lemma 16, the difference of the inverses ${\widehat{x}}_u^{-1}-x_u^{-1}$ is nonincreasing in $u\in (b,1]$, where $b=x_{\infty }={\widehat{x}}_{\infty }$. Therefore, by D-monotonicity, the average amount of new workload brought by job arrival selecting servers with the workloads being i.i.d. with distribution $\widehat{x}$ does not exceed that corresponding to distribution x. On the other hand, by (39), those average new workload amounts corresponding to $\widehat{x}$ and x are $({\widehat{x}}_0-{\widehat{x}}_{\infty })/\lambda$ and $(x_0-x_{\infty })/\lambda$, respectively, with the former being strictly greater than the latter. The contradiction completes the proof. □

12.2. Proof of Theorem 6(ii)

This proof is self-contained in that it does not use any other results or proofs in this paper.

It suffices to prove the theorem’s statement (ii) for the class j itself, because each subclass also has i.i.d. component sizes and the same proof applies.

Consider the servers $1,\dots ,d_j$ in the selection set in the order of their appearance in vector D. Consider the nontrivial case when k_j < d_j. (Otherwise, $\mathbb{E}{\eta }_j(D)=\mathbb{E}{\sum }_{i=1}^{d_j}{\xi }_i^{(j)}$ is the expected total size; it does not depend on D.) In the rest of the proof, we drop job index j and write $d,k,H,\eta (D),{\xi }_i,\xi$ instead of $d_j,k_j,H_j,{\eta }_j(D),{\xi }_i^{(j)},{\xi }^{(j)}$ to simplify notation.

Fix vector D and $1<m\le d$. Denote

It suffices to show that, for any D, any fixed $1<m\le d$,

Consider deterministic function $\tilde{\eta }(y), y\ge 0,$ for a fixed realization $\xi =({\xi }_1,\dots ,{\xi }_d)$ of component sizes; we write $\tilde{\eta }(y,\xi )$ to indicate the dependence on ξ. It is elementary to see that $|\tilde{\eta }(y+\mathrm{\Delta },\xi )-\tilde{\eta }(y,\xi )|\le \mathrm{\Delta }d$ for any $D,y,\xi$ and $\mathrm{\Delta }\ge 0$, and therefore, function $\tilde{\eta }(y,\xi ), y\ge 0,$ is d-Lipschitz. This immediately implies that

We prove (45) first in the special case when $H(·)$ is absolutely continuous and then in the general case.

• Case (a): $H(·)$ is absolutely continuous. This condition is equivalent to $H(·)$ not having an atom at $y_{\mathit{max}}<\infty$, where y_max is the essential upper bound of the distribution support. (When $y_{\mathit{max}}=\infty$, the condition automatically holds.) We show that, for any D, any fixed $1<m\le d$,

  $$\frac{d\mathbb{E}\tilde{\eta }(y)}{dy}\le 0, \forall y\ge 0.$$(47)

  Fix $y\ge 0$. Denote: ${\tilde{D}}_i=D_i$ for $i\ne m$ and ${\tilde{D}}_i=D_i+y$ for i = m; ${\tilde{Z}}_i={\sum }_1^i{\tilde{D}}_{\ell }$. Because $H(·)$ is absolutely continuous,

  $$\text{W}.\text{p}.1,\xi \text{is} \text{such} \text{that} {\tilde{Z}}_{i_1}+{\xi }_{i_1}\ne {\tilde{Z}}_{i_2} \text{and} {\tilde{Z}}_{i_1}+{\xi }_{i_1}\ne {\tilde{Z}}_{i_2}+{\xi }_{i_2} \text{for} \text{all} i_1\ne i_2.$$(48)

  It suffices to consider only those realizations of ξ satisfying (48). Denote by $E(i_1,i_2)$ the following event: $\{$ server i₁ is such that the value ${\tilde{Z}}_{i_1}+{\xi }_{i_1}$ is the kth smallest among values ${\tilde{Z}}_i+{\xi }_i, i=1,\dots ,d$, and ${\tilde{Z}}_{i_1}+{\xi }_{i_1}\in ({\tilde{Z}}_{i_2},{\tilde{Z}}_{i_2}+{\xi }_{i_2})\}$. We refer to event $E(i_1,i_2)$ as $\{i_1$ cancels $i_2\}$. Then, it is elementary to see that function $\tilde{\eta }(y,\xi ), y\ge 0,$ is such that

  $$\frac{d\tilde{\eta }(y,\xi )}{dy}={\displaystyle \sum _{i_1=1}^{m-1}}{\displaystyle \sum _{i_2=m}^d}[-\mathbf{I}(E(i_1,i_2)+\mathbf{I}(E(i_2,i_1)].$$(49)

  Then, by the bounded convergence theorem,

  $$\frac{d\mathbb{E}\tilde{\eta }(y)}{dy}=\mathbb{E}\frac{d\tilde{\eta }(y,\xi )}{dy}={\displaystyle \sum _{i_1=1}^{m-1}}{\displaystyle \sum _{i_2=m}^d}[-\mathbb{P}(E(i_1,i_2))+\mathbb{P}(E(i_2,i_1))].$$(50)

  Observe that, in (50), we always have

  $$\mathbb{P}(E(i_1,i_2))\ge \mathbb{P}(E(i_2,i_1)).$$(51)

  Indeed, for a pair of indices $i_1<i_2$, consider the event

  $$E=E(i_1,i_2)\cup E(i_2,i_1)=\{\text{either} i_1 \text{cancels} i_2 \text{or} i_2 \text{cancels} i_1\}.$$
  Then,
  $$\mathbb{P}(E(i_1,i_2)|E)\ge \mathbb{P}(E(i_2,i_1)|E),$$

  because, when both components i₁ and i₂ are served simultaneously and the elapsed service time of i₂ is τ₂, the elapsed service time of i₁ is ${\tau }_1={\tau }_2+({\tilde{Z}}_{i_1}-{\tilde{Z}}_{i_2})\ge {\tau }_2$, and therefore, by IHR, conditioned on one of these two components completing service, the probability that it is i₁ is $h({\tau }_1)/[h({\tau }_1)+h({\tau }_2)]\ge 1/2$. From (50) and (51), we obtain (47).

• Case (b): General. It remains to consider the case when $H(·)$ has an atom at $y_{\mathit{max}}<\infty$. For any D, there exists its arbitrarily small perturbation such that Condition (48) holds for all $y\ge 0$ except maybe a finite set of points $\{y_{\ell }\}$. Then, for such a perturbed D, repeating the argument given for case (a), we can show that $\frac{d\mathbb{E}\tilde{\eta }(y)}{dy}\le 0$ for any $y\notin \{y_{\ell }\}$, and then, $\mathbb{E}\tilde{\eta }(y)$ is nonincreasing. (Recall that $\mathbb{E}\tilde{\eta }(y)$ is absolutely continuous.) It remains to use the continuity (16) to obtain that (45) holds for any D. □

13. Proof of Theorem 4

This proof relies—in essential way—on both the properties of systems with finite n (Theorems 2 and 3) and the properties of the mean-field limits derived in Section 10. (The proof does not use Theorems 1 and 6.)

We now informally describe the key ideas of the proof. In essence, it reduces to proving the following for any fixed $\rho <1$. Consider a converging sequence ${\lambda }^n\to \lambda$ such that, for all n, the system is stable and its load is exactly ${\rho }^n({\lambda }^n)=\rho$. (Such a sequence exists by Theorem 2.) Moreover, we can choose this sequence so that the convergence of stationary distributions holds, $x^n(\infty )\Rightarrow x(\infty )$, where $x(\infty )$ is some random element. Recall that an ML trajectories $(x(t),t\ge 0)$, which are deterministic, closely approximate the random trajectories of process $(x^n(t),t\ge 0)$ when n is large. In fact, the distribution of $x(\infty )$ is invariant for the deterministic process evolving along ML trajectories. Using monotonicity, it is not hard to see that, w.p.1, $x(\infty )\ge x^{*,\lambda }$, where $x^{*,\lambda }$ is the ML-MFP for the parameter λ, and $x_0^{*,\lambda }\le \rho$. We need to show that, in fact, $x^n(\infty )\Rightarrow x^{*,\lambda }$ and $x_0^{*,\lambda }=\rho$. (The latter easily follows from the former.) The ML-FP/DE-FP uniqueness (Assumption 5) is employed to show that any ML $x(·)$ with proper initial state x(0) dominating $x^{*,\lambda }$ must converge to $x^{*,\lambda }$ as $t\to \infty$. The intuition here is that, because of Assumption 5, we can always pick an improper DE-FP ${\tilde{x}}^{*}$ that is just slightly larger than $x^{*,\lambda }$. Then, any proper x(0) is dominated by $\widehat{x}(0)$, which is ${\tilde{x}}^{*}$ shifted sufficiently far to the right. If we consider the ML $\widehat{x}(·)$ starting from $\widehat{x}(0)$, it is nonincreasing (by monotonicity), and it must converge down to ${\tilde{x}}^{*}$ because, otherwise, the limit ${\lim }_{t\to \infty }\widehat{x}(t)$ is a DE-FP different from ${\tilde{x}}^{*}$, thus violating Assumption 5. Now, if any ML $x(·)$, starting from any proper x(0) dominating $x^{*,\lambda }$ is attracted to $x^{*,\lambda }$, this implies that the probability of $x(\infty )$ being proper is equal to the probability of $x(\infty )=x^{*,\lambda }$. Then we show that the probability of $x(\infty )$ being improper is equal to the probability of $x(\infty )=x^{**}$. The intuition here is that, by Theorem 3, for any n, in steady state, the “relative distances between particles are of the order O(1)”; therefore, if, say, the 0.99th quantile of the distribution given by $x^n(t)$ is very large, then with high probability, any other fixed quantile is very large as well. This allows us to show that $x(\infty )$ is concentrated on at most two points: $x^{*,\lambda }$ and the infinite element $x^{**}$. It still remains to show that $x^{**}$ cannot have a positive probability. This is done by contradiction. Namely, assuming $x(\infty )=x^{**}$ has some positive probability, we obtain that, uniformly in all large n, in steady state, a fixed, say, 0.99th, quantile of $x^n(0)$ is very large with some positive probability. Using the mentioned convergence of ML $\widehat{x}(·)$ down to DE-FP ${\tilde{x}}^{*}$, we are able to conclude that, with high probability, a lower, say, 0.98th, quantile of $x^n(T_1)$ (at some large time T₁) has to be “far to the left” from the 0.99th quantile of $x^n(0)$. This implies that, for large n, in steady state, the expected distance between the 0.98th and 0.99th quantiles of $x^n(\infty )$ could be arbitrarily large; that contradicts Theorem 3.

The formal proof starts here.

Consider our asymptotic regime with $n\to \infty$. Fix $0<\rho <1$. For each n, by Theorem 2, we can and do choose λⁿ such that the steady-state load is equal to exactly ρ, that is, $\mathbb{E}{x}_0^n(\infty )=\rho$. We can always choose a subsequence of n, along which ${\lambda }^n\to \lambda$, where, necessarily, $\lambda \in (0,\infty )$; consider any such subsequence.

Consider any further subsequence of n along which the stationary distributions converge, that is, $x^n(\infty )\Rightarrow x(\infty )$, where $x(\infty )$ is some random element in $\mathcal{X}$. We know that the convergence of initial states $x^n(0)\to x(0)$ implies convergence $x^n(·)\to x(·)$ to the ML $x(·)$ with initial state x(0), and the dependence of an ML on its initial state is continuous. Then, by theorem 8.5.1 in Liptser and Shiryaev (1989), the distribution of $x(\infty )$ is stationary for the deterministic process evolving along the ML trajectories. Then, we must have that, w.p.1, $x(\infty )\ge x^{*}$, where $x^{*}=x^{*,\lambda }$ is the ML-MFP because, for any ML, $x(t)\ge x^{\varnothing }(t)$ and $x^{\varnothing }(t)\uparrow x^{*}$. Moreover, $x_0^{*}\le \rho$. (Otherwise, ${\lim \inf }_n\mathbb{E}{x}_0^n(\infty )>\rho$.) Let us prove that, in fact,

First, we prove that

that is, almost surely, a proper state is equal to $x^{*}$. To demonstrate (53), we prove that ML with any proper initial state x(0) (dominating $x^{*}$) is such that to $x(t)\to x^{*}$; moreover, we prove uniform convergence, in the following sense. For any $\mathrm{ϵ}>0$ and C > 0, there exists $\delta =\delta (\mathrm{ϵ},C)>0$ such that for any A > 0 there exists $T=T(\mathrm{ϵ},C,\delta ,A)>0$ such that, for any ML with $x_A(0)\le \delta$,

Indeed, pick a sufficiently small $\delta >0$, and for it DE-FP ${\tilde{x}}^{*}$ with ${\tilde{x}}_{\infty }^{*}=\delta$ and ${\tilde{x}}_w^{*}<x_w^{*}+\mathrm{ϵ}/2, w\le C$. Then, x(0) is dominated by the state $\widehat{x}(0)$, which is equal to ${\tilde{x}}^{*}$ shifted right by A. (That is, ${\widehat{x}}_w(0)=1$ for w < A, and ${\widehat{x}}_w(0)={\tilde{x}}_{w-A}^{*}$ for $w\ge A$.) The ML $\widehat{x}(·)$, starting from $\widehat{x}(0)$, is monotone nonincreasing because, by construction, if we have a left regulation boundary at A, $\widehat{x}(0)$ is a stationary ML. Moreover, $\widehat{x}(t)\downarrow {\tilde{x}}^{*}$. (It must converge to something, which is an ML-FP = DE-FP, and this DE-FP must be equal to ${\tilde{x}}^{*}$ because, otherwise, we have two DE-FPs with the same limit δ at $w=\infty$, which is impossible by Assumption 5.) Therefore, $x_w(t)\le {\widehat{x}}_w(t)<{\tilde{x}}_w^{*}+\mathrm{ϵ}/2, w\le C,$ for all $t\ge T$ for a sufficiently large T, which proves (54). In turn, (54) in particular implies that any ML $\widehat{x}(·)$ with proper initial state $\widehat{x}(0)\ge x^{*}$ converges to $x^{*}$. This, combined with $x(\infty )\ge x^{*}$, proves (53).

Next, we claim that

The proof of (55) is given in Section 13.1.

The combination of (53) and (55) shows that the limit $x(\infty )$ is concentrated on two points, $x^{*}$ and $x^{**}$. To prove (52), it remains to show that ${\mathrm{ϵ}}_1\doteq \mathbb{P}\{x=x^{**}\}=0$. Indeed, this implies that $x(\infty )=x^{*}$ w.p.1, and $x_0^{*}=\rho$ must hold (because, otherwise, we have ${\lim }_n\mathbb{E}{x}_0^n=x_0^{*}<\rho$.) We prove that ${\mathrm{ϵ}}_1=0$ by contradiction. Suppose not: ${\mathrm{ϵ}}_1=\mathbb{P}\{x=x^{**}\}>0$.

Pick a sufficiently small $\delta >0$ and, for it, DE-FP ${\tilde{x}}^{*}$ with ${\tilde{x}}_{\infty }^{*}=\delta$; ${\tilde{x}}^{*}$ is close to and dominates $x^{*}$. For a given A > 0, consider, as we already did, the ML $\widehat{x}(·)$ starting from $\widehat{x}(0)$, which is equal to ${\tilde{x}}^{*}$ shifted right by A. Recall that $\widehat{x}(t)$ converges down to ${\tilde{x}}^{*}$. Also, using monotonicity, it is easy to see that, if we increase A, it can only decrease $\widehat{x}(t)-\widehat{x}(0)$ for any t. (Because increasing A means moving the regulation boundary 0 to the left w.r.t. A.) These observations imply that, for any $A_1>0$, we can find a sufficiently large $T_1>0$ and a sufficiently large A such that we have the following property. Denote $q_1^n(t)={[x^n(t)]}_{\delta }^{-1}$ and $q_2^n(t)={[x^n(t)]}_{2\delta }^{-1}$. (These are, respectively, the $(1-\delta )$ th and $(1-2\delta )$ th quantiles of the distribution $x^n(t)$.) Then, as $n\to \infty$,

Consider the process $x^n(·)$ in the stationary regime in the interval $[0,T_1]$. When n is large, (a) with probability close to ϵ₁, $q_1^n(0)$ is large and $q_2^n(T_1)-q_1^n(0)<-A_1$; (b) with probability close to $1-{\mathrm{ϵ}}_1,\hspace{0.17em}{q}_2^n(T_1)-q_1^n(0)$ is close to ${[x^{*}]}_{2\delta }^{-1}-{[x^{*}]}_{\delta }^{-1}\le 0$. Then,

assuming that where V_n is a family of nonnegative uniformly integrable random variables. The proof of (57) is given in Section 13.2. Thus, (56) indeed holds. But, because A₁ can be arbitrarily large, this implies $\mathbb{E}[q_1^n(\infty )-q_2^n(\infty )]\to \infty$ as $n\to \infty$, which is impossible. (It follows from Theorem 3 that, for any fixed $0<\eta <1$, $\mathbb{E}|{[x^n(\infty )]}_{\eta }^{-1}-{\overline{\mathit{x}}}^n(\infty )|$ is uniformly bounded in n.) The contradiction completes the proof of (52).

Thus, we proved that $x^n(\infty )\Rightarrow x^{*}$ for the scenario in which ${\rho }^n=\mathbb{E}{x}_0^n(\infty )=\rho$ for a subsequence of n along which ${\lambda }^n\to \lambda$ for some λ, and $x^{*}=x^{*,\lambda }$ being the ML-MFP for this λ, with $x_0^{*,\lambda }=\rho$.

It is easy to see that the dependence of the ML-MFP $x^{*,\lambda }$ on λ is strictly increasing continuous; in particular, the dependence of $x_0^{*,\lambda }$ on λ is strictly increasing continuous. From here, we obtain that the limiting λ in the above scenario is uniquely determined by ρ, and the dependence $\lambda =\lambda (\rho )$ is strictly increasing continuous in $[0,1)$. Denote $\overline{\lambda }={\lim }_{\rho \to 1}\lambda (\rho )$, and denote by $\rho =\rho (\lambda )$ the function inverse to $\lambda (\rho )$. If we fix any $\lambda \in [0,\overline{\lambda })$ and let ${\lambda }^n\to \lambda$, it is easy to see, using the properties of the functions $\rho (\lambda )$ and $\lambda (\rho )$, along with monotonicity, that the convergence $x^n(\infty )\Rightarrow x^{*,\lambda }$ is the only possibility.  □

13.1. Proof of (55)

The intuition for this fact is rather simple. If $x_{\infty }(\infty )>0$ with positive probability ϵ₁, then for a very small fixed $\eta >0$ and all large n, the inverse (quantile) ${[x^n(\infty )]}_{\eta }^{-1}$ is very large with probability close to ϵ₁. However, by Theorem 3, the inverses ${[x^n(\infty )]}_{\eta }^{-1}$ and ${[x^n(\infty )]}_{1-\eta }^{-1}$ are within distance O(1) with high probability, and therefore, ${[x^n(\infty )]}_{1-\eta }^{-1}$ is also very large with probability close to ϵ₁. The formal proof is as follows.

By Theorem 3, for any $\mathrm{ϵ}>0$ and $\eta >0$, there exists a sufficiently large C > 0 such that, for any fixed $0<\eta <1$, for any n, $x^n(\infty )$ is such that

We only need to consider the case when

(Otherwise, (55) is trivial.) We need to show that this implies

Indeed, pick any positive ${\mathrm{ϵ}}_2<{\mathrm{ϵ}}_1$ arbitrarily close to ϵ₁. Pick u > 0 sufficiently small so that $\mathbb{P}\{x_{\infty }(\infty )>u\}>{\mathrm{ϵ}}_2$. Pick a small $\mathrm{ϵ}>0$ (compared with ϵ₂), pick $\eta \in (0,u)$, and then the corresponding C > 0, so that Property (58) holds. Observe that, for an arbitrarily large $C_1>0$, for all sufficiently large n, $\mathbb{P}\{x_{C_1}^{(n)}(\infty )>u\}>{\mathrm{ϵ}}_2$ (where we use the fact that $\{x_a>u\}$ is an open set in $\mathcal{X}$), which means that $\mathbb{P}\{{[x^n(\infty )]}_{\eta }^{-1}\ge C_1\}>{\mathrm{ϵ}}_2$. But this means that $\mathbb{P}\{{[x^n(\infty )]}_{1-\eta }^{-1}\ge C_1-C\}>{\mathrm{ϵ}}_2-\mathrm{ϵ}$. From here, $\mathbb{P}\{x_w(\infty )\ge 1-\eta , 0\le w<C_1-C\}\ge {\mathrm{ϵ}}_2-\mathrm{ϵ}$ (where we use the fact that $\{x_w\ge u, 0\le w<a\}$ is a closed set in $\mathcal{X}$). Because this is true for an arbitrarily large C₁, $\mathbb{P}\{x_{\infty }(\infty )\ge 1-\eta \}\ge {\mathrm{ϵ}}_2-\mathrm{ϵ}$. Because this is true for an arbitrarily small positive η, arbitrarily small positive ϵ, and ϵ₂ arbitrarily close to ϵ₁, we obtain (59).  □

13.2. Proof of (57)

The intuition for the proof is that we upper bound the value of $q_2^n(T_1)$ at T₁ by considering the “worst case” scenario when xⁿ is “maximum possible” subject to $q_1^n(0)=A$ and neither services nor cancellations occur in $[0,T_1]$. For this worst case, we show that the increase of the appropriately defined “mean” of $x^n(t)$ in $[0,T_1]$ is uniformly integrable; then, $q_2^n(T_1)-A$ must be uniformly integrable as well. The formal argument is as follows.

We construct the stochastic upper bound V_n as follows. Suppose $q_1^n(0)=A$. Then, $q_2^n(T_1)-q_1^n(0)=q_2^n(T_1)-A$ is stochastically dominated by the random variable $V_n={[x^n(T_1)]}_{2\delta }^{-1}-{[x^n(0)]}_{\delta }^{-1}={[x^n(T_1)]}_{2\delta }^{-1}-A$ in the “worst case” when (a) $x^n(0)$ is such that there are δn servers with infinite workload and the remaining $(1-\delta )n$ servers have workload A, that is, $x_w^n(0)=1$ for w < A, and $x_w^n(0)=\delta$ for $w\ge A$; (b) no service occurs in $[0,T_1]$; (c) there is no cancellation in $[0,T_1]$—the component sizes of each arriving job are the actual amounts of workload added by the job. Denote by ${\overline{\overline{\mathit{x}}}}^n(t)\doteq {\int }_0^{\infty }[x_w^n(t)-\delta ]dw$ the “mean” of $x^n(t)$, which only takes into account the servers with finite workloads and “ignores” the infinite-workload servers. Then, using the fact that the arrival process is Poisson and the component sizes have a finite second moment, we see that, as $n\to \infty$, the increase ${\overline{\overline{\mathit{x}}}}^n(T_1)-{\overline{\overline{\mathit{x}}}}^n(0)={\overline{\overline{\mathit{x}}}}^n(T_1)-A$ (for the worst case process) has a converging mean and vanishing variance. Therefore, the family ${\overline{\overline{\mathit{x}}}}^n(T_1)-A$ is uniformly integrable. From here, we easily obtain that (for the worst case process) the family $V_n={[x^n(T_1)]}_{2\delta }^{-1}-A$ is uniformly integrable because, otherwise, ${\overline{\overline{\mathit{x}}}}^n(T_1)-A$ could not be uniformly integrable. □

14. Proof of Theorem 5

The proof relies on Theorems 4 and 6. Under the theorem assumptions, Assumption 5 holds for all $\lambda \ge 0$ by Theorem 6, and Assumption 3 holds as well. Assumption 4(ii) also holds automatically. Note that Assumption 4(i) does not necessarily hold. (For example, in the case when, for all job classes w.p.1 all component sizes are equal.) So we cannot apply Theorem 4 immediately. However, it is easy to “get around” a situation when Assumption 4(i) does not hold and still use Theorem 4, using the following argument based on monotonicity and continuity.

In addition to the original system, consider the following modified system. We add an artificial class $\tilde{j}$, which has a small probability ${\pi }_{\tilde{j}}^{(\mathrm{ϵ})}=\mathrm{ϵ}>0$, whereas all other classes j probabilities are ${\pi }_j^{(\mathrm{ϵ})}=(1-\mathrm{ϵ}){\pi }_j$; class $\tilde{j}$ has $k_{\tilde{j}}<d_{\tilde{j}}$, and has, say, i.i.d. exponential component sizes. With this artificial class added, the modified system does satisfy Assumption 4(i) while still satisfying Assumption 5 (for all $\lambda \ge 0$) and Assumptions 3 and 4(ii). For the modified system, we do have Theorem 4.

We consider a sequence of modified systems, parameterized by $\mathrm{ϵ}\downarrow 0$. For each fixed ϵ, let ${\tilde{\rho }}^{(\mathrm{ϵ})}(\lambda ), \lambda \in [0,{\tilde{\lambda }}^{(\mathrm{ϵ})})$ be the corresponding function $\rho (\lambda )$ from Theorem 4, where we deliberately use notations ${\tilde{\rho }}^{(\mathrm{ϵ})}$ and ${\tilde{\lambda }}^{(\mathrm{ϵ})}$ instead of ρ and $\overline{\lambda }$. If we use the convention ${\tilde{\rho }}^{(\mathrm{ϵ})}(\lambda )=1$ for $\lambda \ge {\tilde{\lambda }}^{(\mathrm{ϵ})}$, the function ${\tilde{\rho }}^{(\mathrm{ϵ})}(·)$ is continuous in $[0,\infty )$. Now, for each ϵ, we use the change of variable $\beta =(1-\mathrm{ϵ})\lambda$ and consider the function

where ${\overline{\lambda }}^{(\mathrm{ϵ})}=(1-\mathrm{ϵ}){\tilde{\lambda }}^{(\mathrm{ϵ})}$. (Function ${\rho }^{(\mathrm{ϵ})}(·)$ is continuous in $[0,\infty )$.) The reason for this change of variable is that, for a fixed β, is decreasing as $\mathrm{ϵ}\to 0$. Then, it follows from the monotonicity properties in Lemma 2 that the sequence of functions ${\rho }^{(\mathrm{ϵ})}(·)$ is nonincreasing as $\mathrm{ϵ}\to 0$, with ${\overline{\lambda }}^{(\mathrm{ϵ})}$ nondecreasing and such that ${\overline{\lambda }}^{(\mathrm{ϵ})}\uparrow {\overline{\lambda }}^{(0)}<\infty$. The functions ${\rho }^{(\mathrm{ϵ})}(·)$ converge down to some nondecreasing RCLL function ${\rho }^{(0)}(·)$, in the sense of convergence at every point of continuity.

The next step is to observe that function ${\rho }^{(0)}(·)$ is in fact continuous, including at point ${\overline{\lambda }}^{(0)}$, which means ${\rho }^{(0)}(\beta )\uparrow 1$ as $\beta \uparrow {\overline{\lambda }}^{(0)}$. Indeed, recall that, for each $\mathrm{ϵ}>0$, each $\beta \in [0,{\overline{\lambda }}^{(\mathrm{ϵ})})$, and corresponding $\lambda =\beta /(1-\mathrm{ϵ})\in [0,{\tilde{\lambda }}^{(\mathrm{ϵ})})$, we have a well-defined DE-FP x for the modified system, with $x_0<1$. If ${\rho }^{(0)}(·)$ has a positive jump at some point $a\in [0,{\overline{\lambda }}^{(\mathrm{ϵ})}]$, then using Lemma 20, we are able to obtain two different proper infinite-frame DE-FP, x and y, for the original system. This contradicts Assumption 5. Thus, ${\rho }^{(0)}(·)$ is indeed continuous. Moreover, for each $\lambda \in [0,{\overline{\lambda }}^{(0)})$, again using Lemma 20, for the original system with parameter λ, we obtain a DE-FP x with $x_0={\rho }^{(0)}(\lambda )$, which must be the unique ML-MFP because of Assumption 5.

Given the continuity of ${\rho }^{(0)}(·)$, we have the uniform convergence ${\rho }^{(\mathrm{ϵ})}(·)\stackrel{||·||}{\to }{\rho }^{(0)}(·)$. Fix $\lambda \in [0,{\overline{\lambda }}^{(0)})$ and a small $\mathrm{ϵ}>0$. Compare the original system with parameter λ and the modified system with parameter $\lambda /(1-\mathrm{ϵ})$. Any limit of stationary distributions of the original system must be “sandwiched” between its ML-MFP (below) and the ML-MFP for the modified system (above). But those two ML-MFP can be made arbitrarily close to each other by making ϵ small. We conclude that the limit of stationary distributions for the original system is concentrated on its ML-MFP. Then, conclusion of Theorem 4 for the original system easily follows, with the function $\rho (·)$ being ${\rho }^{(\mathrm{ϵ})}(·)$. □

15. Further Discussion of the DE-FP/ML-FP Uniqueness Condition (Assumption 5) and Additional Steady-State Asymptotic Independence Results for Infinite-Frame Systems

The following Theorem 8 gives a “majorization” sufficient condition for Assumption 5 to hold for a given λ. Informally speaking, it states the following. Suppose, a nontrivial (i.e., not equal to $x^{**}$) infinite-frame DE-FP exists for a system with strictly larger arrival rates for all classes and subclasses, then those in the original system with given λ. Then, Assumption 5 holds for the original system with the given λ.

Theorem 8.

Consider our model with the arrival rate parameter λ and the job classes’ probability distribution $\pi =({\pi }_j)$ as defined for the model. WLOG, assume that the set of classes j includes all the classes of the original system and all their subclasses (where some or all subclasses may have zero probability of occurrence). Suppose there exist other parameters, $\widehat{\lambda }$ and $\widehat{\pi }=({\widehat{\pi }}_j)$ such that (a) ${\widehat{\pi }}_j>0$ for all classes and subclasses, (b) $\lambda \pi <\widehat{\lambda }\widehat{\pi }$, (c) for parameters $\widehat{\lambda }$ and $\widehat{\pi }$ there exists an infinite-frame DE-FP $\widehat{x}\ne x^{**}$. Then, Assumption 5 holds for this λ (and π).

Proof.

It suffices to consider the nonvacuous case when the ML-MFP $x^{*}$ for λ (and π) is proper; this $x^{*}$ is a DE-FP with infinite frame and $x_{\infty }^{*}=0$. Let us now fix a small $b\ge 0$ and consider a b-reduced system (see Section 7). Then, for the b-reduced system, ${\tilde{\lambda }}^{(b)}=\lambda /(1-b)$ is the arrival rate parameter, and let ${\tilde{\pi }}^{(b)}=({\tilde{\pi }}_j^{(b)})$ denote the job class distribution. Clearly, when b is small, we have

$${\tilde{\lambda }}^{(b)}{\tilde{\pi }}^{(b)}<\widehat{\lambda }\widehat{\pi }.$$

Because $\widehat{x}$ is a DE-FP for $\widehat{\lambda }$ and $\widehat{\pi }$, by monotonicity, we obtain that ML-MFP ${\tilde{x}}^{*,(b)}$ is proper (because it must be dominated by $\widehat{x}$). Moreover, the dependence of ${\tilde{x}}^{*,(b)}$, which is also a DE-FP, on b is continuous, with ${\tilde{x}}^{*,(0)}=x^{*}$. But, then,

$$x^{*,(b)}=b+(1-b){\tilde{x}}^{*,(b)}$$

is an infinite-frame DE-FP for parameters λ and π, and the dependence of $x^{*,(b)}$ on b is continuous, with $x^{*,(0)}=x^{*}$. Therefore, as b is increasing from zero while remaining small, $x^{*,(b)}$ is the family of DE-FP for λ and π, parameterized by the initial condition $x_0^{*,(b)}$ increasing from $x_0^{*}$. Therefore, for all sufficiently small $b\ge 0,\hspace{0.17em}{x}^{*,(b)}$ is the only infinite-frame DE-FP x for λ and π with $x_{\infty }=b$. □

Using Theorem 8, along with adjusted versions of the proof of Theorem 4, we can obtain some additional steady-state asymptotic independence results.

First, consider the case when the system has an inherently subcritical load. Suppose, for each class j, there is some upper bound ${\overline{s}}_j$ on the expected amount of work $\mathbb{E}{\eta }_j(D)$ brought by a class j job, which is uniform in the workload-differential vector D of the selection set. (The definition of ${\eta }_j(D)$ is in Section 5.4.) Note that this does not assume some uniform stochastic upper bound on ${\eta }_j(D)$, only a uniform upper bound on the expectation. We say that the system is inherently subcritical if

Trivially, the expected total size of all components, $d_j\mathbb{E}{\xi }_1^{(j)}$, can always be chosen as ${\overline{s}}_j$ for any class j. One example of a nontrivial bound ${\overline{s}}_j$ is for a class j that is D-monotone decreasing. Then,

is the tight upper bound on $\mathbb{E}{\eta }_j(D)$, which can be found, at least numerically. This includes the case when the distribution of component sizes is such that they are i.i.d. with IHR. (Or, more generally, it may be a mixture of such distributions.)

Now, analogously to Definition 2, a class j is called D-monotone increasing, if its distribution F_j of component sizes is such that $\mathbb{E}{\eta }_j(D)$ is nondecreasing in D. For such a class j,

is the tight upper bound on $\mathbb{E}{\eta }_j(D)$. A distribution $H(·)$ on ${\mathbb{R}}_{+}$ is said to have a decreasing hazard rate (DHR) if Condition (15) holds with “$\le$” replaced by “$\ge$.” Then, a proof analogous to that of Theorem 6(ii) applies to show that a class j is D-monotone increasing when its distribution F_j is such that the component sizes are i.i.d. DHR. (Or, more generally, F_j may be a mixture of such distributions.) Thus, the bound (61) applies for a class j with i.i.d. DHR component sizes.

Theorem 9.

Suppose that the infinite-frame system with parameters λ and π is inherently subcritical and Assumption 3 holds. Then, the ML-MFP $x^{*}$ is the unique proper infinite-frame DE-FP, and $x^n(\infty )\Rightarrow x^{*}$.

Proof.

Given (60), it is straightforward to observe that ML-MFP $x^{*}$ is proper (with $x_0^{*}\le \overline{\rho }$). Let us first suppose that Assumption 4 holds. (We later show how to remove this assumption.) Consider the sequence $x^n(\infty )$. For all large n, ${\rho }^n=\mathbb{E}{x}_0^n(\infty )\le \overline{\rho }+\mathrm{ϵ}<1$. Consider any subsequence along which $x^n(\infty )\Rightarrow x(\infty )$ for some $x(\infty )$; denote $\rho =\mathbb{E}{x}_0(\infty )=\lim \mathbb{E}{x}_0^n(\infty )<1$. Clearly, $x(\infty )\ge x^{*}$. Now, given (60), clearly, $\widehat{\lambda }$ and $\widehat{\pi }$ exist for which the system is also inherently subcritical with the corresponding proper ML-MFP $\widehat{x}$, and the conditions of Theorem 8 hold. We conclude that Assumption 5 holds for λ (and π). From this point on, we can repeat the proof of Theorem 4 to show that $x(\infty )=x^{*}$ must hold.

If Assumption 4 does not necessarily hold, we can consider a modified system in which we augment the set of job classes by adding a class $\tilde{j}$ (say, with i.i.d. exponential component sizes), and pick parameters $\tilde{\lambda }$ and $\tilde{\pi }$ so that: $\lambda \pi \le \tilde{\lambda }\tilde{\pi }$; $|\lambda \pi -\tilde{\lambda }\tilde{\pi }|$ is small so that the inherent subcriticality holds for the modified system as well; and the ML-MFP ${\tilde{x}}^{*}$ for the modified system is close to (and dominates) $x^{*}$. For the modified system, the theorem statement does hold. We see that, for our original system, any subsequential distributional limit $x(\infty )$ of $x^n(\infty )$ must be “sandwiched” between $x^{*}$ and ${\tilde{x}}^{*}$. Because ${\tilde{x}}^{*}$ can be arbitrarily close to $x^{*}$, we must have $x^n(\infty )\Rightarrow x^{*}$. □

Theorem 10.

Consider an infinite-frame (nontruncated) system. Assume that the set of job classes is such that, along with each class, it contains all its subclasses, and moreover, ${\pi }_j>0$ for all classes (and subclasses). Suppose the additional Assumptions 3 and 4 hold. Denote

$$\begin{array}{l}\overline{\lambda }=\sup \{\lambda \ge 0|\mathit{\text{corresponding}} \mathit{\text{ML}}-\mathit{\text{MFP}} x^{*,\lambda } \mathit{\text{is}} \mathit{\text{proper}}\},\\ \overline{\rho }=\underset{\lambda \uparrow \overline{\lambda }}{\lim }{x}_0^{*,\lambda }.\end{array}$$

(Note that the case $\overline{\rho }<1$ is not excluded here.) Then, as $n\to \infty$,

$$x^n(\infty )\Rightarrow x^{*,\lambda } \mathit{\text{for}} 0\le \lambda <\overline{\lambda }$$(62)

and

$$x^n(\infty )\Rightarrow x^{**} \mathit{\text{for}} \lambda >\overline{\lambda }.$$(63)

Proof.

The proof is an adjusted version of that of Theorem 4. We only provide a sketch here. We pick a $\rho \in [0,\overline{\rho })$, and as in the proof of Theorem 4, for each n consider the unique λⁿ under which ${\rho }^n=\mathbb{E}{x}_0^n(\infty )=\rho$. Then, we consider a subsequence along which ${\lambda }^n\to \lambda$ for some λ. For this λ, as in the proof of Theorem 4, we must have that any subsequential distributional limit $x(\infty )$ of $x^n(\infty )$ is such that $x^{*,\lambda }\le x(\infty )$ and $x_0^{*,\lambda }\le \mathbb{E}{x}_0(\infty )=\rho$. By Theorem 8, Assumption 5 holds for $x^{*,\lambda }$. (Indeed, for a $\tilde{\lambda }$ slightly greater than λ, proper $x^{*,\tilde{\lambda }}$ exists because $x_0^{*,\lambda }\le \rho <\overline{\rho }$.) From this point on, we can repeat the proof of Theorem 4 to show that $x(\infty )=x^{*,\lambda }$ must hold. We then easily see that λ is determined by ρ uniquely, and the corresponding function $\lambda (\rho )$ is strictly increasing, mapping $[0,\overline{\rho })$ onto $[0,\overline{\lambda })$. From here, we obtain Claim (62). Claim (63) follows from the fact that, for $\lambda >\overline{\lambda }$, the ML-MFP is the infinite element $x^{**}$, and the ML-MFP is always a lower bound on any subsequential limit $x(\infty )$ of $x^n(\infty )$. □

16. A Free Particle System: Tightness of Stationary Distributions of Centered States

For a fixed n, consider an artificial free system, in which particle locations (server workloads) are not regulated at zero; namely, they evolve in $\mathbb{R}$ rather than in ${\mathbb{R}}_{+}$, with each particle keeping moving left at constant rate –1 unless/until it jumps right because of a job arrival. Clearly, for such system, the centered process $\stackrel{°}{x^n}(·)$, taking values in $\stackrel{°}{{\mathcal{X}}^{(n)}}$, is well-defined and is itself a Markov process (not just a projection of Markov process $x^{(n)}(·)$). This process only changes its state (jumps) upon job arrivals. Therefore, the arrival rate λⁿ—as long as it is positive—only determines the rate at which changes take place and has no impact on the existence/nonexistence/form of the process stationary distributions. A version of Theorem 3 holds for the free system under an additional technical condition that needs to be introduced to be able to demonstrate stability (positive Harris recurrence). Recall that the stability for a given λⁿ is assumed in Theorem 3. For the free system, λⁿ—as long as it is positive—is irrelevant for stability/instability and the form of a stationary distribution, but the stability does need to be shown.

State $\stackrel{°}{x^n}(·)$ can be equivalently described as $p^n(t)=(w_1(t),\dots ,w_n(t))\in {\mathbb{R}}^n$, the same way as in Section 9, except here $p^n(t)$ does not contain component $z^n(t)$, which is irrelevant for the free process. A subset $B\subset R^n$ is called small (see, e.g., Bramson 2008) for the process $p^n(·)$ if there exists $\tau >0$ and a finite measure $\mathcal{M}$ on Rⁿ, such that, uniformly on the initial state $p^n(0)\in B$, the distribution of $p^n(\tau )$ dominates $\mathcal{M}$. (Existence of a small set allows one to use Nummelin splitting to view the process as having a renewal atom.) Note that the property of a set being small for $p^n(·)$ does not depend on λⁿ as long as ${\lambda }^n>0$.

Theorem 11.

Suppose the additional Assumptions 3 and 4 hold. Suppose further that, for all large n,

$$\mathit{\text{for}} \mathit{\text{any}} C>0 \mathit{\text{the}} (\mathit{\text{closed}}) \mathit{\text{set}} \{|p^n|\le C\} \mathit{\text{is}} \mathit{\text{small}} \mathit{\text{for}} p^n(·).$$(64)

Then, there exist $\overline{C}>0$ and $\overline{n}$ such that, for all $n\ge \overline{n},\hspace{0.17em}\stackrel{°}{x^n}(·)$ (with any ${\lambda }^n>0$) is positive recurrent and, moreover,

$$\mathbb{E}{\mathrm{\Phi }}_1(\stackrel{°}{x^n}(\infty ))\le \overline{C}.$$(65)

Condition (64) is not very restrictive; it can be verified in many cases of interest. For example, it holds in the case when there exists a class j and $\delta >0$ such that the component size distribution F_j dominates a scaled (by a small constant) Lebesgue measure on ${[0,\delta ]}^{d_j}$. It is easy to check that the set $\{|p^n|\le C\}$ is small, with any $\tau >0$ and measure $\mathcal{M}$ defined as follows. Fix $\mathrm{ϵ}>0$, and consider set

Then, $\mathcal{M}$ is restricted to Sⁿ and is defined by a scaled (by a small constant) Lebesgue measure on $(\mathrm{\Delta }{w}_1,\dots ,\mathrm{\Delta }{w}_{n-(d_j-k_j)-1})\in {[0,\mathrm{ϵ}]}^{n-(d_j-k_j)}$.

Proof of Theorem 11.

The proof is a version of that of Theorem 3. We only provide a sketch, highlighting the differences.

Let n (and any ${\lambda }^n>0$) be fixed. Consider a sequence of processes $p^{n,(r)}(·)$ indexed by $r\uparrow \infty$, with initial states such that $|p^{n,(r)}(0)|=r$ and $(1/r)p^{n,(r)}(0)\to q(0)$, where $|q(0)|=1$. (This is a sequence of processes that defines fluid limits of $p^n(·)$.) Then, there exists T > 0 such that

$$\frac{1}{r}|p^{n,(r)}(rT)|\Rightarrow 0.$$(66)

Property (66) follows from the following properties of the fluid limits $q(·)$ of $p^n(·)$: $q(·)$ is Lipschitz; as long as $q_i(t)>q_{\ell }(t)$, the difference $q_i(t)-q_{\ell }(t)$ cannot increase; as long as $|q(t)|>0$ or, equivalently, ${\min }_i{q}_i(t)<0$ and ${\max }_i{q}_i(t)>0$,

$$\frac{d}{dt}\underset{i}{\min }{q}_i(t)-\frac{d}{dt}\underset{i}{\max }{q}_i(t)\le -\mathrm{ϵ},$$(67)

for some fixed $\mathrm{ϵ}>0$ (which may depend on n); and, therefore, the fluid limits are such that $|q(t)|=0$ for all $t\ge 1/\mathrm{ϵ}$. In turn, the fluid limit properties, except (67), are straightforward to obtain. Property (67) is obtained using Assumption 4, for example, as follows. Denote the sets $I_{\mathit{min}}(t)={\text{arg}\hspace{0.17em}\text{min}}_i{q}_i(t)$ and $I_{\mathit{max}}(t)={\text{arg}\hspace{0.17em}\text{max}}_i{q}_i(t)$. At any time within a sufficiently small fixed (scaled) time interval $[t,t+\mathrm{\Delta }t]$, the prelimit process $(1/r)p^{n,(r)}(rs)$ is such that, if we randomly uniformly pick a pair of particles $i_{\mathit{min}}\in I_{\mathit{min}}$ and $i_{\mathit{max}}\in I_{\mathit{max}}$, the distribution of the jump size of the former (upon a job arrival) always dominates that of the latter, with the expectation of the former exceeding that of the latter at least by some positive constant; this, in turn, follows from the fact that, with nonzero probability, the picked particle i_min is one of the leftmost particles (in the prelimit process) and i_max is one of the rightmost particles (in the prelimit process), and we can use Assumption 4 to show that, in this case, the expected jump size of i_min must be greater than that of i_max by at least some positive constant.

Property (66), along with Condition (64), implies (cf. Dai 1995, Bramson 2008) that $p^n(·)$ is positive Harris recurrent (stable) and, therefore, has unique stationary distribution.

Finally, given the stability of $p^n(·)$, the proof of the uniform bound (65) is essentially same as that of (10) in Section 9. In fact, it is simpler because the dynamics of $p^n(·)$ for the free system is simpler; there is no regulation boundary z(t) on the left (and, therefore, the particles never hit it), and the only process transitions are those occurring upon job arrivals. □

The free system, in addition to being of independent interest, has the following natural connection to the stability (Theorem 2) of our original infinite-frame system. Suppose the conditions of Theorem 11 hold, including Condition (64). Denote by ${\overline{\lambda }}^n$ the unique value of λⁿ, for which the steady-state average drift of the mean ${\overline{\mathit{x}}}^n(·)$ of the (noncentered) free process $x^n(·)$ is zero. (Such value is indeed unique because, clearly, the drift has the form $-1+a{\lambda }^n$, where constant a > 0 is determined by the stationary distribution of $\stackrel{°}{x^n}(·)$; so ${\overline{\lambda }}^n=1/a$.) Then, it is not hard to show that this ${\overline{\lambda }}^n$ is exactly equal to the ${\overline{\lambda }}^n$ in Theorem 2. (This can be done by combining arguments in the proofs of Theorems 2 and 11.) We note, however, that this conclusion requires the additional technical Condition (64), whereas Theorem 2 does not require it.