then obtain

$$ \mathbb{E}(N^{\text{MRF}}) = \lambda p_S \left( \frac{1}{\mu_1} + \frac{\lambda p_S \frac{1}{2\mu_1}}{1 - \lambda p_S \frac{1}{\mu_1}} \right) + \sum_{i=1}^{K} \frac{\lambda p_{\{i\}}}{1 - \lambda p_S \frac{1}{\mu_1}} \left( \frac{1}{\mu_i} + \frac{\lambda p_{\{i\}} \frac{1}{2\mu_i} + \lambda p_S \frac{1}{2\mu_1}}{1 - \lambda p_S \frac{1}{\mu_1} - \lambda p_{\{i\}} \frac{1}{\mu_i}} \right). \quad (6) $$

For the LRF-FCFS policy, we do not have a closed-form expression for the mean number of jobs. We therefore construct an upper-bound (UB) system under the LRF-FCFS policy where a class-S job departs only when the copy in server 1 is served. One can easily verify that this system upper bounds the original system. The mean number of jobs under the upper-bound system can be easily calculated, since now class $\{i\}$ sees a single server queue and class S a priority queue where class 1 is given priority. Using [17], we then obtain

$$ \mathbb{E}(N^{\text{UB}}) = \sum_{i=1}^{K} \lambda p_{\{i\}} \left( \frac{1}{\mu_i} + \frac{\lambda p_{\{i\}} \frac{1}{2\mu_i}}{1 - \lambda p_{\{i\}} \frac{1}{\mu_i}} \right) + \frac{\lambda p_S}{1 - \lambda p_{\{1\}} \frac{1}{\mu_1}} \left( \frac{1}{\mu_1} + \frac{\lambda p_{\{1\}} \frac{1}{\mu_1} + \lambda p_S \frac{1}{\mu_1}}{2(1 - \lambda p_{\{1\}} \frac{1}{\mu_1} - \lambda p_S \frac{1}{\mu_1})} \right). \quad (7) $$

We can now compare $\mathbb{E}(N^{\text{MRF}})$ with $\mathbb{E}(N^{\text{UB}})$. We introduce some notation to make the computations easier:

$$ a = 1 - \lambda p_S \frac{1}{\mu_1}, \quad b = 1 - \lambda p_S \frac{1}{\mu_1}, \quad c = 1 - \lambda p_S \frac{1}{\mu_1} - \lambda p_S \frac{1}{\mu_1}, $$

$$ \text{and for } i = 1, \dots, K, \quad d_i = 1 - \lambda p_S \frac{1}{\mu_1} - \lambda p_{\{i\}} \frac{1}{\mu_i}, \quad e_i = 1 - \lambda p_{\{i\}} \frac{1}{\mu_i}. $$

Let us start by comparing the performance on server $i > 1$, that is, the terms multiplied by $\lambda p_{\{i\}}$, $i > 1$, in Eq. (6) and Eq. (7).

$$ \begin{aligned} \sum_{i=2}^{K} [\mathbb{E}(N_i^{\text{MRF}}) - \mathbb{E}(N_i^{\text{UB}})] &= \sum_{i=2}^{K} \left[ \frac{\lambda p_{\{i\}}}{a} \left( \frac{1}{\mu_i} + \frac{\lambda p_{\{i\}} \frac{1}{\mu_i} + \lambda p_S \frac{1}{\mu_1}}{2d_i} \right) - \lambda p_{\{i\}} \left( \frac{1}{\mu_i} + \frac{\lambda p_{\{i\}} \frac{1}{\mu_i}}{2e_i} \right) \right] \\ &= \sum_{i=2}^{K} \left[ \frac{\lambda p_{\{i\}} \frac{1}{\mu_i} (\lambda p_S \frac{1}{\mu_1})}{a} + \frac{\lambda^2 p_{\{i\}}^2 \frac{1}{\mu_i}}{2ad_i e_i} \left( \lambda p_S \frac{1}{\mu_1} (d_i + 1) \right) + \frac{\lambda^2 p_{\{i\}} p_S \frac{1}{\mu_1}}{2ad_i} \right] \\ &\ge \sum_{i=2}^{K} \left[ \frac{\lambda^2 p_{\{i\}} p_S}{a\mu_1^2} + \frac{\lambda^2 p_{\{i\}} p_S}{2ad_i e_i \mu_1} \left( \lambda p_{\{i\}} \frac{1}{\mu_1} (d_i + 1) + e_i \right) \right] > 0. \quad (8) \end{aligned} $$

The last inequality holds since we have assumed that $\mu_1 = \max_{s \in S}\{\mu_s\}$. This difference is strictly positive for any parameter values. Let us compute the difference now in server 1, that is, the terms in (6) and (7) multiplied by $\lambda p_{\{1\}}$ and $\lambda p_S$.
$$
\begin{align}
& \mathbb{E}(N_1^{\text{MRF}}) - \mathbb{E}(N_1^{\text{UB}}) \nonumber \\
&= \frac{\lambda p_{\{1\}}}{a\mu_1} \left(1 + \frac{\lambda p_{\{1\}} + \lambda p_S}{2c}\right) - \frac{\lambda p_{\{1\}}}{\mu_1} \left(1 + \frac{\lambda p_{\{1\}}}{2b}\right) \nonumber \\
&\quad + \frac{\lambda p_S}{\mu_1} \left(1 + \frac{\lambda p_S}{2a}\right) - \frac{\lambda p_S}{b\mu_1} \left(1 + \frac{\lambda p_{\{1\}} + \lambda p_S}{2c}\right) \nonumber \\
&= \frac{\lambda^2 p_{\{1\}} p_S}{\mu_1^2 a} + \frac{\lambda^2 p_{\{1\}}^2}{2abc\mu_1^2} (\lambda p_S(c+1)) + \frac{\lambda^2 p_{\{1\}} p_S}{2ac\mu_1} \nonumber \\
&\quad - \frac{\lambda^2 p_{\{1\}} p_S}{b\mu_1^2} - \frac{\lambda^2 p_S^2}{2abc\mu_1^2} (\lambda p_{\{1\}}(c+1)) - \frac{\lambda^2 p_{\{1\}} p_S}{2bc\mu_1} \nonumber \\
&= (p_S - p_{\{1\}}) \left( \frac{\lambda^3 p_{\{1\}} p_S}{ab\mu_1^3} + \frac{\lambda^3 p_{\{1\}} p_S(1-c)}{2abc\mu_1^2} + \frac{\lambda^3 p_{\{1\}} p_S}{2abc\mu_1^2} \right). \tag{9}
\end{align}
$$

We note that this is nonnegative if and only if $p_S \ge p_{\{1\}}$.

We can obtain a more accurate result by summing the terms multiplied by $\lambda^3$ in Equation (8) restricted to class $\{i\}$ and the last term in Equation (9). We have then,

$$ \frac{\lambda^3 p_S}{2a\mu_1^2} \left( \frac{p_{\{i\}}^2 (d_i + 1)}{d_i e_i} + \frac{p_{\{1\}} (p_S - p_{\{1\}})}{cb} \right). $$

We note that $a, b, c, d_i$ and $e_i$ are positive. Hence, the first multiplying term is positive. The latter implies that the whole expression is positive if and only if

$$ \frac{p_{\{i\}}^2 (d_i + 1)}{d_i e_i} + \frac{p_{\{1\}} (p_S - p_{\{1\}})}{cb} > 0 \iff $$

$$ \frac{p_{\{i\}}^2 \left(2 - \frac{\lambda p_S}{\mu_1} - \frac{\lambda p_{\{i\}}}{\mu_i}\right)}{\left(1 - \frac{\lambda p_S}{\mu_1} - \frac{\lambda p_{\{i\}}}{\mu_i}\right) \left(1 - \frac{\lambda p_{\{i\}}}{\mu_i}\right)} + \frac{p_{\{1\}} (p_S - p_{\{1\}})}{\left(1 - \frac{\lambda p_{\{1\}}}{\mu_1}\right) \left(1 - \frac{\lambda p_S}{\mu_1} - \frac{\lambda p_{\{1\}}}{\mu_1}\right)} > 0 $$

We define $\rho_j = p_{\{j\}}/\mu_j$ for $j = 1, i$ and $\rho_S = p_S/\mu_1$.

$$ \iff \lambda^2(\rho_S + \rho_i)[p_{\{i\}}^2(\rho_S + \rho_i) + p_{\{1\}}(p_S - p_{\{1\}})\rho_i] $$

$$ -\lambda[p_{\{i\}}^2(2\rho_1 + 3\rho_S + \rho_i) + p_{\{1\}}(p_S - p_{\{1\}})(2\rho_i + \rho_S)] + 2p_{\{i\}}^2 + p_{\{1\}}(p_S - p_{\{1\}}) > 0. $$

For ease of notation, let

$$ \tilde{a}_i = (\rho_S + \rho_i)[p_{\{i\}}^2(\rho_S + \rho_i) + p_{\{1\}}(p_S - p_{\{1\}})\rho_i], $$

$$ \tilde{b}_i = p_{\{i\}}^2(2\rho_1 + 3\rho_S + \rho_i) + p_{\{1\}}(p_S - p_{\{1\}})(2\rho_i + \rho_S), $$

$$ \tilde{c}_i = 2p_{\{i\}}^2 + p_{\{1\}}(p_S - p_{\{1\}}). $$

Hence, if $\lambda$ is either smaller than $\lambda_{0,i}$ or larger than $\lambda^{0,i}$, then the mean number of jobs under the MRF system is strictly larger than that under UB (and hence under LRF), where

$$ \lambda_{0,i} = \frac{\tilde{b}_i - \sqrt{\tilde{b}_i^2 - 4\tilde{a}_i\tilde{c}_i}}{2\tilde{a}_i}, \quad \text{and} \quad \lambda^{0,i} = \frac{\tilde{b}_i + \sqrt{\tilde{b}_i^2 - 4\tilde{a}_i\tilde{c}_i}}{2\tilde{a}_i}, \qquad (10) $$

Thus, we define

$$ \lambda_0 = \max_{i=2}^{K} \{\lambda_{0,i}\} = \max_{i=2}^{K} \left\{ \frac{\tilde{b}_i - \sqrt{\tilde{b}_i^2 - 4\tilde{a}_i\tilde{c}_i}}{2\tilde{a}_i} \right\}. \qquad (11) $$
In particular, if the arrival rate $\lambda$ is smaller than $\lambda_0$, then the mean number of jobs under the MRF system is strictly larger than that under UB (and hence under LRF). $\square$

**Proof of Proposition 18:** We actually show a stronger result: we prove that the system with i.i.d. copies is optimal when for each job, we can choose either independent or identical copies.

We consider a policy $\pi$ where servers are required to follow $\Pi_1$-FCFS and idling is allowed. Under policy $\pi$, whenever a server starts serving a first copy of a job, that server determines whether the service times of the copies of that job are identical or i.i.d.. This decision is independent of the history of the process. We show that for this policy $\pi$, if at time $t$ it idles or schedules identical copies for a job in service for the first time, we can construct a policy $\pi'$ with a coupled sample path, such that at time $t$ $\pi'$ does not idle or samples i.i.d. copies, and such that $\{N'(s)\}_{s \ge 0} \le \{N(s)\}_{s \ge 0}$ with probability 1, where $N(N')$ denotes the number of jobs in the system under policy $\pi$ ($\pi'$). The result follows by starting at time 0 and repeating the argument each time a policy deviates from the policy $\pi$, until we have the non-idling $\Pi_1$-FCFS policy with i.i.d. copies.

One can easily verify that the non-idling $\Pi_1$-FCFS policy is better than idling $\Pi_1$-FCFS for a fixed choice of independent versus identical copies, by following the steps in the second part of the proof of Proposition 3.

Therefore let us assume that $\pi$ never idles but that at some time $t$, $\pi$ starts serving the first copy of some job, call it job 1, and $\pi$ chooses identical copies for that job. We let $\pi'$ agree with $\pi$ before time $t$ and let it choose i.i.d. copies for job 1. We denote by $\tau$ the time that job 1 completes service under $\pi$, say at server 1. Because the copies are identical, server 1 has done the most work on job 1 between times $t$ and $\tau$. We couple the service time of job 1 on server 1 under $\pi'$ to that under $\pi$. Then, $\pi'$ samples i.i.d. copies for the rest of the copies of job 1. We let all other service times and all arrival times be coupled under both policies. We let $\pi'$ agree with $\pi$ until job 1 departs under $\pi'$, at time $\tau'$. From our coupling, $\tau' \le \tau$. Let $\pi'$ idle any server that serves job 1 under $\pi$ between times $\tau'$ and $\tau$ and let it otherwise agree with $\pi$ from time $\tau'$ on. From our argument above, a policy that agrees with $\pi'$ but does not idle will have even earlier departures than $\pi'$. The argument can be repeated, each time reducing the number-in-system process, until we have all i.i.d. copies and no idling. $\square$

## B: Proofs of Section 4

### Proof of Proposition 22 and Proposition 23

In order to prove both propositions, we analyze the fluid-scaled system. We recall that the redundancy structure is nested and that $N_c(t)$ denotes the number of class-c jobs at time $t$. For $r > 0$, we denote by $N_c^r(t)$ the system where the initial state satisfies $N_c^r(0) = rn_c(0)$, for all $c \in C$. We write the fluid-scaled number of jobs per class by using standard arguments, see [9],

$$ \frac{N_c^r(rt)}{r} = n_c(0) + \frac{1}{r}\tilde{A}_c(rt) - \frac{1}{r}\tilde{S}_c(T_c^r(rt)), \quad (12) $$

where $\tilde{A}_c(t)$ and $\tilde{S}_c(t)$ are independent Poisson processes having rates $\lambda p_c$ and 1, respectively. $T_c^r(t)$ is the cumulative amount of capacity spent in serving class-c jobs, which strongly depends upon the correlation structure among the copies, that is,

$$ T_c^r(t) = g((T_{s,c}^r(t))_{s \in c}), $$

where $T_{s,c}^r(t)$ is the cumulative amount of capacity spent on serving class-c jobs in server $s \in c$ during the time interval $(0, t]$ and $g$ is characterized by the correlation structure of the copies. We
note that when copies are i.i.d. $T_c^r(t) = \sum_{s \in c} T_{s,c}^r(t)$ and when copies are identical, $T_c^r(t) = \max_{s \in c}\{T_{s,c}^r(t)\}$.

In the following result, we obtain the general characterization of a fluid limit. The existence of fluid limits can be proved following the same steps as in [9], so the proof is omitted.

**Lemma 25.** For almost all sample paths $\omega$ and sequences $r_k \to \infty$, there exists a subsequence $r_{k_j} \to \infty$ such that for all $c \in C$ and $t \ge 0$,

$$ \lim_{j \to \infty} \frac{N_c^{r_{k_j}}(r_{k_j} t)}{r_{k_j}} = n_c(t) \quad \text{uniformly on compact sets} \qquad (13) $$

and

$$ \lim_{j \to \infty} \frac{T_c^{r_{k_j}}(r_{k_j} t)}{r_{k_j}} = \tau_c(t) \quad \text{uniformly on compact sets,} \qquad (14) $$

with $(n_c(\cdot), \tau_c(\cdot))$ continuous functions. In addition,

$$ n_c(t) = n_c(0) + \lambda p_c t - \tau_c(t), \qquad (15) $$

where $n_c(t) \ge 0$, $\tau_c(0) = 0$, $\tau_c(t) \le t \max_{s \in c}\{\mu_s\}$, and $\tau_c(\cdot)$ is a non-decreasing and Lipschitz continuous function for all $c \in C$.

In order to provide the characterization of the fluid limit, we first introduce some notation. Let us group the classes with respect to their number of copies. We denote by $\mathcal{L}_i$ the set of classes with $i$ copies, that is, for $i = 2, \dots, |C|,$

$$ \mathcal{L}_i = \{c \in C : |c| = i\}. $$

From the nested structure of the system, we note that for each $c \in \mathcal{L}_i$ and $\tilde{c} \in \mathcal{L}_j$ with $j < i$, either $\tilde{c} \subset c$ or $\tilde{c} \cap c = \emptyset$. For all $c \in \mathcal{L}_i$, let us denote by $\mathcal{L}_i(c) = \{\tilde{c} \in C : \tilde{c} \subset c\}$ the job classes that are subsumed in class $c$, for $i = 1, \dots, |C|$.

We denote by $P_s(\vec{N})$, the probability that, given $\vec{N}(0) = \vec{N}$, at time $t = 0$ a given server $s$ is serving a copy that is not in service in any other server. Then, the following lemma is true.

**Lemma 26.** Consider a redundancy system with a nested topology and where servers implement $\Pi_1$-ROS. For any server $s \in S$ and $\vec{N}^r(0) = r\vec{n}^r$, such that $\lim_{r \to \infty} \sum_{c \in \mathcal{C}(s)} rn_c^r > 0$, then

$$ \lim_{r \to \infty} P_s(r\vec{n}^r) = 1. \qquad (16) $$

*Proof:* Assume at time 0, server $s$ idles and that we are in state $\vec{N}^r(0) = \vec{N}$. At this moment, under $\Pi_1$-ROS server $s$ can only serve a single class in the system, say class $c$. Let us consider servers $l \in c$ that are serving a class-$c$ job at time $t = 0$, say servers $S(c)$. We denote by $-\tilde{T}_l^r < 0$ the time at which server $l$ started serving a new class-$c$ job, regardless of whether another job departed from the server, or the class-$c$ job preempted a copy with lower priority in that server. We note that $\frac{N_c(-\tilde{T}_l^r) - 1}{N_c(-\tilde{T}_l^r)}$ is the probability that server $l$ is not serving the copy of the same job that is now in service in server $s$. Hence,

$$ P_s(\vec{N}) = \Pi_{l \in S(c), l \neq s} \frac{N_c^r(-\tilde{T}_l^r) - 1}{N_c^r(-\tilde{T}_l^r)}. \qquad (17) $$

We set $\vec{N}(0) = r\vec{n}^r$. Since the transition rates $\mu_s$ and $\lambda$ are of order $O(1)$, it follows directly that $\tilde{T}_s^r$ and $\vec{N}(-\tilde{T}_s^r) - \vec{N}(0)$ are of order $O(1)$ as well, so that

$$ \lim_{r \to \infty} \frac{N_c^r(-\tilde{T}_l^r) - 1}{N_c^r(-\tilde{T}_l^r)} = \lim_{r \to \infty} \frac{N_c^r(0) - 1}{N_c^r(0)} = 1. \qquad (18) $$
It hence follows from (17) that $\lim_{r \to \infty} P_s(r\vec{n}^r) = 1$. $\square$

Let us characterize the instantaneous departure rate of a class-tilde job. Let us denote by $C_{\tilde{c}}$ the classes that are a subsumed in class $\tilde{c}$. That is,

$$C_{\tilde{c}} = \{c \in \mathcal{C} : c \subseteq \tilde{c}\}.$$

Note that if $\tilde{c} \in \mathcal{L}_i$, then $C_{\tilde{c}} = \mathcal{L}_i(\tilde{c})$.

**Lemma 27.** Assume that jobs have exponential service times and

* if copies are i.i.d. copies, assume LRF-$\Pi_2$, with LRF non-preemptive and $\Pi_2$ non-idling,

* if copies follow some general correlation structure, assume LRF-ROS.

For each class $\tilde{c} \in \mathcal{C}$, the fluid limit $\sum_{c \in C_{\tilde{c}}} n_c(t)$ satisfies the following:

$$\frac{d \sum_{c \in C_{\tilde{c}}} n_c(t)}{dt} = \sum_{c \in C_{\tilde{c}}} \lambda p_c - \sum_{s \in \tilde{c}} \mu_s, \quad \text{if } n_{\tilde{c}}(t) > 0.$$

*Proof:* We first consider a general correlation structure among the copies and LRF-ROS. When starting in state $\tilde{N}(0) = r\vec{n}^r$, the drift function is

$$\tilde{f}(r \sum_{c \in C_{\tilde{c}}} n_c^r) = \sum_{c \in C_{\tilde{c}}} \lambda p_c - \sum_{s \in \tilde{c}} \mu_s \left( \prod_{l \in \tilde{c}} P_l(r\vec{n}^r) - g_{\tilde{c}}(r\vec{n}^r) \left(1 - \prod_{l \in \tilde{c}} P_l(r\vec{n}^r)\right) \right) \quad (19)$$

for $n_{\tilde{c}} > 0$, where $g_{\tilde{c}}$ is a function that captures the instantaneous departure rate of the system when more than one copy (with any correlation structure) of the same job is in service, and note that $g_{\tilde{c}} = O(1)$ as $r \to \infty$. Assuming that $n_{\tilde{c}} > 0$, due to LRF and the nested structure, each server $s \in \tilde{c}$'s jobs of a single class $c$, with $c \subseteq \tilde{c}$ which is the class with least redundant copies in that server $s$. We note that the first departure term in Eq. (19) represents departures from servers $s \in \tilde{c}$ of class-c jobs $c \in \tilde{c}$, who were served in one unique server. Since these jobs have no other copies in service, the total departure rate from the servers in $\tilde{c}$ equals $\sum_{s \in \tilde{c}} \mu_s$. The second departure term in (19) represents departures due to a class-c job that is being served in more than one server simultaneously.

Therefore, from equation (19) together with Lemma 26, we obtain

$$\lim_{r \to \infty} \tilde{f}(r \sum_{c \in C_{\tilde{c}}} n_c^r) = \lambda \sum_{c \in C_{\tilde{c}}} p_c - \sum_{s \in \tilde{c}} \mu_s. \quad (20)$$

Now assume copies are i.i.d. copies and servers implement LRF-$\Pi_2$ with LRF non-preemptive and $\Pi_2$ non-idling. Under these assumptions, the drift function is given by

$$\tilde{f}(r \sum_{c \in C_{\tilde{c}}} n_c^r) = \lambda \sum_{c \in C_{\tilde{c}}} p_c - \sum_{s \in \tilde{c}} \mu_s, \quad \text{when } n_{\tilde{c}} > 0. \quad (21)$$

This can be seen as follows. When there are class-c jobs present, $c \in \tilde{c}$, each server in class $\tilde{c}$ is working on such a job, possibly the same job. Because of the i.i.d. copies assumption, the departure rate of these jobs is simply the sum of all the capacities. $\square$
In order to prove Proposition 22 and Proposition 23, we introduce the redundancy degree per class. Let us assume w.l.o.g. that $\mathcal{L}_1$ is non-empty. For each class $c \in \mathcal{L}_1$, the fluid limit $n_c(t)$ is given by the following due to Lemma 27:

$$ \frac{dn_c(t)}{dt} = \lambda p_c - \sum_{s \in c} \mu_s, \quad \text{if } n_c(t) > 0. $$

We note that $\lambda p_c - \sum_{s \in c} \mu_s < 0$, by assumption. This coincides with the fluid limit of an $M/M/1$ system with arrival rate $\lambda p_c$ and server capacity $\sum_{s \in c} \mu_s$. Hence, for all $c \in \mathcal{L}_1$, $n_c(t)$ reaches zero in finite time, say at time $T_1$, and stays zero.

The proof follows now by induction. Assume that there is a time $T_j$, such that $n_c(t) = 0$ for $t > T_j$, for all $c \in \mathcal{L}_i$ and $i \le j$. In the following we show that for $\mathcal{L}_{j+1}$, there is a $T_{j+1} > T_j$, such that $n_c(t) = 0$ for $t > T_{j+1}$ and for all $c \in \mathcal{L}_{j+1}$.

For a class $c \in \mathcal{L}_{j+1}$, the fluid drift of $\sum_{\tilde{c} \in \mathcal{L}_{j+1}(c)} n_{\tilde{c}}(t)$ is given by the following due to Lemma 27:

$$ \frac{d \sum_{\tilde{c} \in \mathcal{L}_{j+1}(c)} n_{\tilde{c}}(t)}{dt} = \sum_{\tilde{c} \in \mathcal{L}_{j+1}(c)} \lambda p_{\tilde{c}} - \sum_{s \in c} \mu_s, \quad \text{if } n_c(t) > 0. \qquad (22) $$

From the induction hypothesis, we note that there exists time $T_j$ such that $n_{\tilde{c}}(t) = 0$ for all $\tilde{c} \in \mathcal{L}_i$ with $i \le j$. Hence, $\frac{d \sum_{\tilde{c} \in \mathcal{L}_{j+1}(c)} n_{\tilde{c}}(t)}{dt} = \frac{dn_c(t)}{dt}$, for $t \ge T_j$. Together with Eq. 22,

$$ \frac{dn_c(t)}{dt} = \sum_{\tilde{c} \in \mathcal{L}_{j+1}(c)} \lambda p_{\tilde{c}} - \sum_{s \in c} \mu_s, \quad \text{if } n_c(t) > 0, $$

for all $t \ge T_j$. We note that $\lambda \sum_{\tilde{c} \in \mathcal{L}_{j+1}(c)} p_{\tilde{c}} - \sum_{s \in c} \mu_s < 0$, by assumption. This coincides with the fluid limit of an $M/M/1$ system with arrival rate $\lambda \sum_{\tilde{c} \in \mathcal{L}_{j+1}(c)} p_{\tilde{c}}$ and server capacity $\sum_{s \in c} \mu_s$. Hence, for all $c \in \mathcal{L}_{j+1}$, $n_c(t)$ reaches zero in finite time, say at time $T_{j+1}$, and stays zero. Hence, there exists time $\tilde{T} > 0$ when the fluid process is empty. Together with [29], we conclude that the system is stable. $\square$