# Matching Queues with Abandonments in Quantum Switches: Stability and
Throughput Analysis

Martin<EMAIL_ADDRESS>[ Prakirt R.
<EMAIL_ADDRESS>[ Siva Theja
<EMAIL_ADDRESS>[  University of Minnesota,  Georgia
Institute of Technology,  Georgia Institute of Technology,

###### Abstract

Inspired by quantum switches, we consider a discrete-time multi-way matching
system with two classes of arrivals: requests for entangled pair of qubits
between two nodes, and qubits from each node that can be used to serve the
requests. An important feature of this model is that qubits decohere and so
abandon over time. In contrast to classical server-based queueing models, the
combination of queueing, server-less multi-way matching, and abandonment make
the analysis a challenging problem. The primary focus of this paper is to
study a simple system consisting of two types of requests and three types of
qubits operating under a Max-Weight policy.

In this setting, we characterize the stability region under the Max-Weight
policy by adopting a two-time scale fluid limit to get a handle on the
abandonments. In particular, we show that Max-Weight is throughput optimal and
that it can achieve throughputs larger than the ones that can be achieved by
non-idling policies when the requests are infinitely backlogged. Moreover,
despite the use of the Max-Weight policy, we show that there can be a counter-
intuitive behavior in the system: the longest requests queue can have a
positive drift for some time even if the overall system is stable.

Stochastic Matching Networks,

Abandonments,

Quantum Switches,

###### keywords:

, , and

###### Contents

  1. 1 Introduction
    1. 1.1 Our contribution
    2. 1.2 Previous work
    3. 1.3 Notation
  2. 2 Three-way matching in a Y-topology
    1. 2.1 Two-way matching system
      1. 2.1.1 No Abandonment
      2. 2.1.2 Abandonments on one side
      3. 2.1.3 Abandonments on both sides
    2. 2.2 Model for three-way matching in a Y-topology
      1. 2.2.1 Infinitely backlogged case
      2. 2.2.2 Non-infinitely backlogged case
  3. 3 Three-way matching in a W-topology
    1. 3.1 Infinitely backlogged case
    2. 3.2 Partially infinitely backlogged case
    3. 3.3 Stability of the non infinitely backlogged case
    4. 3.4 Transient analysis
      1. 3.4.1 Fluid approximation
      2. 3.4.2 Convergence of sample paths to a fluid solution
      3. 3.4.3 Transient analysis of the fluid solutions
  4. 4 Conclusions and future work
  5. A Proof of Lemma 1
  6. B Proof of Lemma 2
  7. C Proof of Theorem 1
    1. C.1 Positive recurrence
    2. C.2 Transience
  8. D Proof of Proposition 1
  9. E Proof of Theorem 4
  10. F Proof of Theorem 3
    1. F.1 Tightness of sample paths
    2. F.2 Derivatives of the limit points
    3. F.3 Completing the proof of Theorem 3
  11. G Proof of Theorem 2

##  1 Introduction

During the last century, telecommunication networks’ theoretical analysis,
design, and control have evolved together with the underlying technology.
Starting with the circuit-switched telephone networks of the early twentieth
century, through the boom of the packet-switched network that is the Internet,
the advent of quantum computers requires a new type of switched network [18,
34, 37]. In quantum computers, the qubit replaces the bit as the minimum unit
of information. Qubits act as a richer unit of information that allows new
computational applications and a new way of communicating by _entangling_ the
state of qubits at different nodes. This _entanglement_ is a fundamental
feature of quantum mechanics that has no counterpart in classical mechanics.
When two qubits are entangled, altering the state of one alters the state of
the other. A Quantum network enables distribution of entangled qubits between
users, and several architectures propose implementing such networks [1, 4, 19,
20, 23, 24].

In this paper, we focus on the most fundamental component of a quantum
communication network: a single quantum switch that connects two or more nodes
in a star topology. In this kind of switches, connections between nodes are
established in two steps: a preparation step, and a connection step. First, to
prepare for connection requests, pairs of maximally entangled qubits (also
know as Bell pairs, or EPR states) are constantly being generated between the
switch and each of the connected nodes. Generated pairs are stored in quantum
memories, with one qubit of each pair stored at the switch and the other one
at the corresponding node. Due to a phenomenon called _quantum decoherence_ ,
the stored entangled qubits become useless after some time, and are thus
deleted. Second, when a request for a connection between two nodes is made, if
the switch has qubits entangled with each of the nodes, then it performs a
Bell-state measurement between those two qubits, entangling them with positive
probability (otherwise, the qubits are lost and the request is not served). If
the entanglement is successful, this also results in the entanglement of the
corresponding two qubits at the nodes, enabling quantum communication between
them. On the other hand, if the switch has no such two qubits stored, the
request must wait for their generation.

A model for a Quantum switch based on a network of matching queues was
introduced in [39]. In this model, the quantum memory in each node is modeled
as a queue with random arrivals (the continuous generation of entangled
qubits) and abandonments (due to decoherence). We allow for general arrival
distributions and assume that the abandonments are geometric. Furthermore,
since the requests for connections between two nodes arrive randomly and wait
for completion, they are also modeled as jobs in a queue (which has no
abandonments). Finally, the entanglement attempt of two qubits through a Bell-
state measurement in response to a request for a connection corresponds to a
three-way matching among the request and the pair of qubits if the
entanglement is successful and to a two-way matching between the pair qubits
if the entanglement is not successful. In the latter case, the request remains
unfulfilled. The central control problem in a Quantum switch is the following.
When a new entangled qubit is generated, and there is more than one type of
request waiting, the switch needs to decide which connection to create. This
is a matching problem among all involved queues.

Our goal in this paper is to find the stability region of a quantum switch in
a W-topology, which corresponds to a switch with three nodes, but where there
are only requests for connections for two out of the three possible pairs.
Here, when qubits arrive, and there is more than one three-way matching
possible, we use a Max-Weight policy on the requests queue lengths to decide
which matching to attempt.

In scheduling of classical queues, the stability region of a system operating
under a Max-Weight policy is generally determined by the convex hull of the
set of service schedules, that is, of the set of possible departure vectors
from the different queues. If the set of schedules is randomized in each time
slot (even in a Markovian way), independently of which one is actually used,
the stability region can still be determined by considering the steady-state
expectation of the available schedules. A quantum switch in contrast involves
matching queues, where the “service schedules” in each time slot are
determined by the available qubits, which can be stored over time to fulfill
future requests until they decohere and abandon the system. Therefore, the set
of possible schedules is determined by a Markov chain with dynamics that
depend on which schedule is used. In particular, this means that there is no
straightforward way of taking expectations and obtaining the stability region,
as the steady-state distribution of the schedules now depends on the arrival
rates in an unknown way. Also, the stability region cannot be obtained by
“saturating” the queues as in the queueing networks introduced in [3].

###  1.1 Our contribution

The main contribution of our paper is to show that the stability region of a
quantum switch in a W-topology under Max-Weight can be characterized in terms
of the convex hull of the throughputs when the requests are either completely
or partially infinitely backlogged. In a completely backlogged system, both
kinds of requests are infinitely backlogged and the qubit queues make all
possible matchings in all slots, simplifying the throughput analysis. In the
partially backlogged system, one type of requests are infinitely backlogged,
while the other type are not. This backlogged system is equivalent to a lower
dimensional system, viz., a Quantum Switch in a Y-topology. Therefore, we
first characterize the stability region under a Y-topology and use it as a
stepping stone to study the W-topology. The contributions of our paper are as
follows:

  1. 1.

Y-topology: A Y-topology consists of two qubit queues and one request queue.
This corresponds to a quantum switch with only two nodes.

     * (i)

Studying the capacity of the Y-topology further reduces to the case when the
requests are infinitely backlogged, leading to a two-way matching system. We
obtain the stability region and average matching rate (throughput) of a two-
way matching queue with abandonments, and explore its connections to a single-
server queue.

     * (ii)

For the Y-topology, we obtain the stability region and the system’s
throughput. In particular, we show system’s stability whenever the arrival
rate of connection requests is lower than the throughput of an appropriate
two-sided queue with abandonments.

  2. 2.

W-topology: For the system in the W-topology, in order to keep the problem
tractable, we assume that both the abandonment probabilities and the three-way
matching success probabilities are homogeneous. In this setting, we show the
following:

     * (i)

When both requests queues are infinitely backlogged, we characterize the sum
of the throughputs of both types of requests, which is the same for all non-
idling matching policies. Moreover, we show that the throughput of each
request is uniformly bounded away from zero under any non-idling matching
policy.

     * (ii)

When only one request queue is infinitely backlogged, we obtain the capacity
region for the other queue when we give strict priority to the infinitely
backlogged one. Moreover, we obtain the throughput of the infinitely
backlogged one, as a function of the arrival rate of the other one.

     * (iii)

When none of the requests queues are infinitely backlogged, we show that the
Max-Weight policy is throughput optimal, and that its stability region is the
convex hull of all throughputs obtained in the completely and partially
infinitely backlogged cases. This implies that considering only the infinitely
backlogged system doesn’t give the capacity region in quantum switches.

     * (iv)

We use a two time-scale fluid limit approximation to characterize the
transient behaviors. In particular, we show that, in some cases, the drift of
the largest requests queue can be positive for some time under the Max-Weight
policy, even when the system is stable.

  3. 3.

Methodological contribution: We obtain the above results using two different
proof techniques, both of which may be of independent interest to study more
general matching networks.

     * (i)

We obtain the results on the Y-topology using a multi-step variant of the
Foster-Lyapunov theorem. To overcome the challenge of the “service schedules”
being dependent on the requests queues, we construct two coupled processes. In
one of the processes matchings are always attempted regardless of requests,
and in the other, no matchings are attempted (pure abandonment). We show that
these processes stochastically dominate the original one. We then use the
multi-step Lyapunov argument to show stability of the coupled processes,
implying the stability of the original process.

     * (ii)

We obtain the results on the W-topology using fluid limit arguments. The key
challenge is in establishing the fluid limit for two reasons. The first one is
that we have a discontinuous drift, and thus we cannot apply the well-known
fluid limit theorems that rely upon the Lipschitz continuity of the drift. The
second one is that we have an averaging effect in the drift, as the qubit
queues evolve in a faster time scale than the requests queues. We overcome
these two challenges by first establishing tightness of the scaled processes,
and showing that the limit points of these processes are Lipschitz. Exploiting
this Lipschitz property enables us to provide an ODE characterization of the
fluid limit that includes the averaging effect.

###  1.2 Previous work

As previously mentioned, the first queueing theoretic analysis for a quantum
switch was done in [39]. In this seminal paper, as well as in the follow-up
work [30, 38, 40], the authors assume that there is always a request for
connections to be made, and they use a continuous time Markov chain as a
tractable approximation of the discrete-time nature of the quantum switches.
Under these assumptions, they obtain throughput in a heterogeneous network,
with/without decoherence and connections among two or three nodes.

In a slightly different line of work [41, 12] that is the closest to this
paper, the authors consider a discrete-time queueing model where requests for
connections are indeed stored in a queue until enough entangled qubits are
available to match with them. In particular, in [41] they consider the case
where any node can store only one qubit and where each qubit decoheres after a
single time slot. In this setting, they show that a Max-Weight policy on the
length of the requests queues is throughput optimal. On the other hand, in
[12] they assume that there is an infinite quantum memory for qubits but that
these do not decohere. In this case, they also show that Max-Weight is
throughput optimal but with a weaker notion of stability that only involves
the requests queues. To the best of our knowledge, we are first to provide a
theoretical analysis of a model with queueing on both the requests and the
qubits and with a non-trivial distribution for the decoherence time.

The matching queueing model used for quantum switches is akin to the models
for assemble-to-order systems. However, assemble-to-order systems and their
models rarely involve abandonments. Without abandonments, optimal policies
often involve waiting for some time before performing a more informed matching
(e.g., the so-called discrete-review policies [25, 32, 17]). These policies
are unsuitable for systems with abandonments, as they allow for unnecessary
abandonments to occur. When incorporating abandonments, policies that wait
before performing matchings can only be asymptotically optimal if the
abandonment rate is asymptotically negligible [2, 5]. Other recent works in
the matching system that considers abandonments do so in continuous time and
with a mix of items with zero and infinite patience [13, 16]. There, their
optimal policies are also unsuitable for the case where all items can abandon,
as they make the infinitely patient items wait unnecessarily.

Many other recent papers tackle the analysis and control of matching queueing
systems. Some focus on finding general conditions for the stability [7, 33] or
instability [29] of such systems. Others focus on throughput optimality and
reward maximization in the long-term average [31] or in a discounted setting
[8]. In particular, in [22] they show that greedy policies can be optimal in
hindsight. Finally, some also focus on finding structural properties, such as
showing that the steady-state queue length distribution has product form when
the matching policy is First-Come-First-Served [28] (even when there are
abandonments [10]), or that adding flexibility can hurt performance [9].
Finally, a recent work [21] consider a bipartite two-way matching queueing
network with abandonments under a Max-Weight policy. While they obtain the
stability region and other stochastic properties, they do not show optimality
in any way.

###  1.3 Notation

Given a real number $q$, we denote $q^{-}=-\min\big{\\{}q,\,0\big{\\}}$ and
$q^{+}=\max\big{\\{}0,\,q\big{\\}}$. Analogously, given a real-valued
stochastic process $Q(\cdot)$, we denote
$Q^{-}(\cdot)=-\min\big{\\{}Q(\cdot),\,0\big{\\}}$ and
$Q^{+}(\cdot)=\max\big{\\{}0,\,Q(\cdot)\big{\\}}$. We also denote
$\mathbb{R}_{+}=[0,\infty)$ and $\mathbb{Z}_{+}=\\{0,1,2,\dots\\}$. Moreover,
we denote

$D^{2}[0,T]:=\left\\{f:[0,T]\to\mathbb{R}_{+}^{2},\text{ c\\`{a}dl\\`{a}g, and
piece-wise constant}\right\\}.$

Finally, we denote as $\text{proj}_{A}(x)$ the projection of $x$ onto the set
$A$, and we denote vectors with bold face fonts.

##  2 Three-way matching in a Y-topology

In this section, we first introduce and analyze a two-way matching model
(Subsection 2.1). Then, we build upon this when we introduce and analyze our
first model for a quantum switch consisting of a three-way matching network in
a Y-topology (Subsection 2.2).

###  2.1 Two-way matching system

$\mu_{1}$$\gamma_{1}$$\mu_{2}$$\gamma_{2}$ Figure 1: System with two-way
matchings and abandonments in both queues.

We consider a discrete-time system consisting of two FIFO queues with infinite
buffers, where items arrive at each of the queues according to i.i.d.
exogenous arrival processes denoted by $A_{1}(\cdot)$ and $A_{2}(\cdot)$. A
pictorial representation is presented in Figure 1. We assume that the two
arrival processes are independent of each other, with
$\mathbb{E}[A_{i}(1)]=\mu_{i}$ and
$\mathbb{E}\big{[}A_{i}(1)^{2}\big{]}<\infty$ for $i\in\\{1,2\\}$. Items of
type $i$ depart either via immediate matching with the other type or via
abandonment, where each item in the $i$-th queue abandons with probability
$\gamma_{i}$ independent of other items in the queue, at each time slot. We
assume that the abandonments are realized at the beginning of the time slot,
then the arrivals come in and join the queue, and finally, the items in the
queues are matched with each other and depart the system. We also assume that
the system is non-idling, which implies that at least one of the queues is
empty at the end of any time slot. This system can be modeled as a discrete-
time Markov chain $(Q_{1}(\cdot),Q_{2}(\cdot))$ over the state space
$\mathbb{Z}_{+}\times\mathbb{Z}_{+}$ defined recursively by

$\displaystyle Q_{i}(t+1)$
$\displaystyle=Q_{i}(t)+A_{i}(t)-D_{i}(t)-M(t),\quad\text{ for
}i\in\\{1,2\\},$ (1)

for all $t\geq 0$, where $D_{1}(t)\sim Bin\big{(}Q_{1}(t),\gamma_{1}\big{)}$
and $D_{2}(t)\sim Bin\big{(}Q_{2}(t),\gamma_{2}\big{)}$ denote the
abandonments from the first and second queues, respectively, and
$M(t)=\min_{i\in\\{1,2\\}}\big{\\{}Q_{i}(t)-D_{i}(t)+A_{i}(t)\big{\\}}$ is the
number of matchings in the $t$-th time slot. Note that $M(t)$ is defined in
such a way that ensures that at least one of the queues is equal to zero at
all times. Therefore, we can also model this system as the one-dimensional
Markov chain $Q(\cdot)=Q_{1}(\cdot)-Q_{2}(\cdot).$ In particular, we have that
$Q^{+}(\cdot)=Q_{1}(\cdot)$ and $Q^{-}(\cdot)=Q_{2}(\cdot)$, and that
$Q(\cdot)$ can also be defined recursively by
$Q(t+1)=Q(t)+A_{1}(t)-A_{2}(t)-D_{1}(t)+D_{2}(t),$ for all $t\geq 0$. In this
setting, we define the _throughput_ as the rate of successful matchings, given
by

$\text{Throughput}:=\liminf\limits_{t\to\infty}\frac{1}{t}\sum\limits_{k=1}^{t}M(k).$

Furthermore, if the Markov chain $Q(\cdot)$ is ergodic, then the throughput is
simply given by $\mathbb{E}[M(\cdot)]$, where the expectation is taken with
respect to the steady-state distribution.

####  2.1.1 No Abandonment

When the abandonment probabilities for both queues are zero, that is, when
$\gamma_{1}=\gamma_{2}=0$, the system acts as a one-dimensional random walk.
Therefore, it is transient when $\mu_{1}\neq\mu_{2}$, and null recurrent when
$\mu_{1}=\mu_{2}$. However, in both cases, the throughput is equal, almost
surely, to $\min\\{\mu_{1},\mu_{2}\\}$. More details on this can be found in
[26].

####  2.1.2 Abandonments on one side

We now consider the case of the two-way matching system where there are no
abandonments in one of the queues, that is, where $\gamma_{1}=0$. For ease of
exposition, we denote $\mu_{1}=\lambda$, $\mu_{2}=\mu$, and
$\gamma_{2}=\gamma$ in Figure 1. The queue on the right-hand side acts as a
service queue, and the queue on the left-hand side acts as a request queue.

Although this is a server-less two-way matching system, it is closely related
to the single-sever queue. Note that the service queue is stable for any
$\gamma\in(0,1]$. In the extreme case that $\gamma=1$, arrivals to the service
queue that are not immediately matched are lost. Therefore, the request queue
behaves exactly as a discrete-time GI/GI/1 queue where the services are the
arrivals to the service queue. In particular, this implies that the request
queue (and thus the whole system) is stable when $\lambda<\mu$. On the other
hand, when $\gamma<1$, arrivals to the service queue that are not immediately
matched stay in the queue for a geometrically distributed amount of time, or
until they are matched. In relation to the single-server queue, this means
that the unused “services” are stored for future use instead of being lost.
Even though this does not exactly behave like a single server queue, the extra
stored up services can only help in decreasing the queue length of the request
queue. Therefore, the overall system is stable when $\lambda<\mu$. However,
when $\lambda>\mu$, the storing of services are not enough to make the request
queue stable. In Lemma 1 given below, we formalize the above argument and
establish that the stability and throughput of this system, which turn out to
be the same as in a single-server queue, and do not depend on the value of
$\gamma$.

######  Lemma 1.

For any $\gamma\in(0,1]$, we have the following.

  * (i)

If $\lambda<\mu$, then $Q(\cdot)$ is positive recurrent and the throughput is
equal to $\lambda$.

  * (ii)

If $\lambda>\mu$, then $Q(\cdot)$ is transient and the throughput is equal to
$\mu$.

The positive recurrence when $\lambda<\mu$ can be shown by using a coupling
argument, by considering a single server queue with ‘arrivals’ as the arrivals
to the request queue and ‘services’ as the arrivals to the service queue.
Then, the queue length in the request queue is always smaller than the queue
length of the single server queue, and the result in Part (i) follows simply
by using the stability of the single server queue. In Part (ii), we use a
similar coupling to show that the overall queue length $Q(\cdot)$ is lower
bounded by a transient random walk.

Another way to prove Part (i) is to consider $L(x)=|x|$ as a Lyapunov
function, and show that the drift of this Lyapunov function is negative
outside a finite subset of the state space whenever $\lambda<\mu$. Then, the
Foster-Lyapunov theorem [27] implies system’s stability. A necessary
technicality to use the Foster-Lyapunov theorem is that the underlying Markov
chain should be irreducible and aperiodic. This can be shown by using the fact
that abandonments follow a binomial distribution. Mathematical details for
this is provided in Appendix A.

######  Remark.

While the request queue requires $\lambda<\mu$ to be stable, the service queue
is always stable thanks to the abandonments. However, as seen in Lemma 1, the
magnitude of the abandonments plays no role in the request queue’s stability
region nor in the system’s throughput.

####  2.1.3 Abandonments on both sides

We now consider the case where there are abandonments in both queues, that is,
$\gamma_{1},\gamma_{2}>0$. This system is depicted in Figure 1. In this case,
the system’s stability follows due to abandonments on both sides. However,
unlike the case where only one side has abandonments, in this case, throughput
does depend on the value of $\gamma_{1}$ and $\gamma_{2}$. This is formalized
in the Lemma 2 below.

######  Lemma 2.

For any $\gamma_{1},\gamma_{2}\in(0,1]$, the process $Q(\cdot)$ is positive
recurrent with unique invariant distribution $\pi$, and the throughput is
almost surely equal to

$\displaystyle
C_{Y}=\mathbb{E}_{\pi}[M]=\mu_{1}-\gamma_{1}\mathbb{E}_{\pi}\big{[}Q^{+}\big{]}=\mu_{2}-\gamma_{2}\mathbb{E}_{\pi}\big{[}Q^{-}\big{]},$
(2)

where
$M=\min\big{\\{}Q^{+}-D_{1}(Q^{+})+A_{1}(1),\,Q^{-}-D_{2}(Q^{-})+A_{2}(1)\big{\\}}.$

Note that $M$ denotes the number of matchings for the two-dimensional
representation of the two-way matching system. Thus, the first equality in
Equation (2) follows simply by the definition of throughput and using the
ergodicity and positive recurrence of the Markov chain. For second (or third)
equality, one should note that $\mu_{1}$ (or $\mu_{2}$) is the average rate of
arrivals to the first (or second) queue, and using the binomially distributed
nature of the abandonments, the rate of abandonment in steady-state is
$\gamma_{1}\mathbb{E}_{\pi}\big{[}Q^{+}\big{]}$ (or
$\gamma_{2}\mathbb{E}_{\pi}\big{[}Q^{-}\big{]}$). Finally, since the system is
ergodic, $\mathbb{E}_{\pi}[M]$ is the average matching rate in the system.
Since items can only leave the system via matching or abandonment, and as the
rate of arrivals equals the rate of departures in steady-state, we have
$\mu_{1}=\gamma_{1}\mathbb{E}_{\pi}\big{[}Q^{+}\big{]}+\mathbb{E}_{\pi}[M]$.
This can be formally shown by equating the drift of $Q_{1}(\cdot)$ (or
$Q^{+}(\cdot)$) in Equation (1) to zero in steady-state. The proof uses the
Foster-Lyapunov theorem with $L(x)=|x|$ as the Lyapunov function once more,
and it is given in Appendix B.

######  Remark.

The results from subsections 2.1.1, 2.1.2 and 2.1.3 can be combined to say
that, for any value of $\gamma_{1},\gamma_{2}\in[0,1]$, the throughput is
given by $\mu_{i}-\gamma_{i}\mathbb{E}_{\pi}[Q_{i}]$ when the system is
stable, and by $\min\\{\mu_{1},\mu_{2}\\}$ when the system is unstable.

###  2.2 Model for three-way matching in a Y-topology

We now consider a discrete-time system consisting of three FIFO queues with
infinite buffers, where requests arrive to one of the queues as an i.i.d.
process $A(\cdot)$, with $\mathbb{E}[A(1)]=\lambda$ and
$\mathbb{E}\big{[}A(1)^{2}\big{]}<\infty$, and qubits are generated and join
each one of the other two queues as i.i.d. processes $S_{1}(\cdot)$ and
$S_{2}(\cdot)$, independent of each other, with $\mathbb{E}[S_{i}(1)]=\mu_{i}$
and $\mathbb{E}\big{[}S_{i}(1)^{2}\big{]}<\infty$ for $i\in\\{1,2\\}$. Qubits
can depart from their respective queues at each time slot via abandonments
with positive probabilities $\gamma_{1}$ and $\gamma_{2}$, respectively. This
system is depicted in Figure 2.

Requests$\lambda$$\mu_{1}$$\gamma_{1}$$\mu_{2}$$\gamma_{2}$Qubits Figure 2:
Three-way matching system in Y-topology.

A request waiting in its queue can only depart from the system if it is
matched with one qubit from each type. However, even if qubits are present in
both qubit queues, the matching (request fulfillment) can fail. We assume that
a request fulfillment is successful with probability $p>0$, and fails with
probability $(1-p)$. In other words, if there is at least one item in each of
the three queues, they depart immediately as a three-way matching with
probability $p$, and as a two-way matching between the qubits with probability
$1-p$ (with the request staying in its queue). If the request queue is empty,
there is no two-way matching between the qubits. We also assume that the
system is non-idling, in the sense that matching requests with pairs of qubits
are attempted until one of the three queues becomes empty. Finally, we assume
that there is no bound on the number of matches that can be made in any time
slot.

We model this system as a discrete-time Markov chain $\big{(}N(\cdot),{\bf
Q}(\cdot)\big{)}$ over the state space $\big{\\{}(n,{\bf
q})\in\mathbb{Z}_{+}\times\mathbb{Z}_{+}^{2}:n.q_{1}.q_{2}=0\big{\\}},$ where
$N(\cdot)$ is the number of requests, and $Q_{1}(\cdot)$ and $Q_{2}(\cdot)$
are the number of qubits. Let
$\mathbf{Y}(t)=\big{\\{}Y_{\ell}(t):\ell,t\in\mathbb{Z}_{+}\big{\\}}$ be a
sequence of i.i.d. Bernoulli random variables with probability $p$, such that
$Y_{\ell}(t)$ is the indicator that the $\ell$-th attempted three-way matching
in the $t$-th time slot is successful. Then, we have

$\displaystyle N(t+1)$
$\displaystyle=N(t)+A(t)-\sum_{\ell=1}^{M(t)}Y_{\ell}(t),$ and $\displaystyle
Q_{i}(t+1)=Q_{i}(t)-D_{i}(t)+S_{i}(t)-M(t)$

for $i\in\\{1,2\\}$, where $D_{i}(t)\sim Bin\big{(}Q_{i}(t),\gamma_{i}\big{)}$
is the number of abandonments from the $i$-th qubits’ queue, and $M(t)$ is the
number of attempted three-way matchings. By the definition of $\mathbf{Y}(t)$,
the term $\sum_{\ell=1}^{M(t)}Y_{\ell}(t)$ is a binomial random variable that
represents the number of successful three-way matchings in the $t$-th time
slot after $M(t)$ attempts. Further, by denoting

$U(t)=\min\left\\{m:\sum\limits_{\ell=1}^{m}Y_{\ell}(t)\geq
N(t)+A(t)\right\\},$ (3)

we have that the total number of three-way matchings attempted in the $t$-th
slot is given by
$M(t)=\min\left\\{Q_{1}(t)-D_{1}(t)+S_{1}(t),\,\,Q_{2}(t)-D_{2}(t)+S_{2}(t),\,\,U(t)\right\\}.$
The term $U(t)$ in the definition of $M(t)$ is a negative binomial random
variable that represents the number of three-way matching attempts needed to
obtain $N(t)+A(t)$ successful ones. By the definition of $M(t)$, three-way
matchings are attempted in each slot until there are either no more requests
or any of the types of qubits. Thus, similar to that for the two-way matching
system, $M(t)$ is defined to ensure that at least one of the queues is always
empty. Finally, for this system, the throughput is defined as

$\text{Throughput}:=\liminf\limits_{t\to\infty}\frac{1}{t}\sum\limits_{k=1}^{t}\sum\limits_{\ell=1}^{M(k)}Y_{\ell}(k).$

Unlike in the definition of throughput of the two-way matching system, we now
only consider the three-way matchings as part of the throughput, as two-way
matchings in this system are failed attempts. If the Markov chain $Q(\cdot)$
is ergodic, then the throughput is simply be given by
$\mathbb{E}\big{[}\sum_{\ell=1}^{M(\cdot)}Y_{\ell}(\cdot)\big{]}=p\mathbb{E}[M(\cdot)]$,
where the expectation is taken with respect to the steady-state distribution.

####  2.2.1 Infinitely backlogged case

We first consider a simplified case where the requests are infinitely
backlogged, i.e., where $N(t)=\infty$ for all $t\geq 0$. In this case, the
processes $Q_{1}(\cdot)$ and $Q_{2}(\cdot)$ behave the same as the two-way
matching system of Subsection 2.1.3. That is, there exists a coupling such
that, almost surely, we have $Q_{1}(t)=Q^{+}(t)$ and $Q_{2}(t)=Q^{-}(t)$ for
all $t\geq 0$. Therefore, since $\gamma_{1},\gamma_{2}>0$, Lemma 2 implies
that the process ${\bf Q}(\cdot)$ is positive recurrent with invariant
distribution $\pi$, and thus, $\mathbb{E}[M(\cdot)]=C_{Y}$. Therefore, since
any matching is successful with probability $p$, the throughput of the
Y-topology in the infinitely backlogged case is equal to
$p\mathbb{E}[M(\cdot)]=pC_{Y}$.

####  2.2.2 Non-infinitely backlogged case

When the request queue $N(\cdot)$ is not infinitely backlogged, the stability
of the system is no longer guaranteed by the abandonments. However, the
stability region is closely related to the throughput in the infinitely
backlogged case, as follows.

######  Theorem 1.

Let $C_{Y}$ be the throughput defined in Equation (2). We have the following.

  * (i)

If $\lambda<pC_{Y}$, then $\big{(}N(\cdot),{\bf Q}(\cdot)\big{)}$ is positive
recurrent, and the throughput is equal to $\lambda$.

  * (ii)

If $\lambda>pC_{Y}$, then $\big{(}N(\cdot),{\bf Q}(\cdot)\big{)}$ is
transient, and the throughput is equal to $pC_{Y}$.

In the previous subsection we observed that the rate of successful matchings
is at most $pC_{Y}$. Thus, when the requests come at a rate higher than
$pC_{Y}$, the system behaves like it is in the infinitely backlogged case, and
the number of requests diverges with time. This gives us Theorem 1 Part (ii).

Proving the positive recurrence for the Y-topology in Part (i) is more
challenging than proving the positive recurrence of the two-way matching
system. Depending on the values of $\lambda$, $\mu_{1}$, and $\mu_{2}$, the
drift of the request queue might be positive for infinitely many states. This
means that a straightforward argument that uses $L(x)=|x|$ as a Lyapunov
function (as in previous sections) does not work here. One might be able to
find a suitable Lyapunov function and show that the one-step drift is negative
if queue lengths are large, or one might prove stability using fluid limits,
as we do for the W-topology in the upcoming section (Section 3). However, we
use a multi-step Lyapunov drift argument here to prove positive recurrence.

Note that, while the request queue is positive, the qubit queues behave like a
two-way matching system, where the average rate of attempted matchings is
$pC_{Y}$. Therefore, if $\lambda<pC_{Y}$, the drift of the request queue is
negative during this time. To formally prove Part (i), we couple the system
with two simpler ones.

  1. 1.

In one of them, qubits attempt two-way or three-way matchings irrespective of
whether a request is present or not. In particular, if both qubit queues are
non-empty, a matching between the qubits occurs, and they depart the system.
Further, if a request is also present at that time, it is fulfilled with
probability $p$. In this case, as qubits do not wait for a request, the
request queue stochastically dominates the original request queue.

  2. 2.

In the other one, no matchings are ever attempted. As a result, the qubit
queues behave as two independent $GI/M/\infty$ queues, which stochastically
dominate the original qubit queues.

The main advantage of these two processes is that the evolution of the qubit
queues does not depend on the state of the requests queue. Therefore, we use a
multi-step Lyapunov argument on these new coupled processes to establish their
positive recurrence. In particular, we use a number of steps $T$ large enough
so that the multi-step drift for the request queue is close enough to
$T(\lambda-pC_{Y})$ when the queues are large enough. Finally, since the
original processes were stochastically dominated by the new ones, the positive
recurrence of the former follows. The complete proof for Theorem 1 is given in
Appendix C.

######  Remark.

Contrary to the two-way matching case, here the stability region of the system
depends on the abandonment probabilities, as qubits of one type sometimes have
to wait for the other type of qubits to match with a request. Therefore,
qubits can be lost to abandonments even if there are outstanding requests.
Moreover, the stability threshold is $pC_{Y}$, which is obtained as an
expectation with respect to the steady-state distribution of a Markov chain.
This is because while the requests queue is positive, it behaves as a single
server queue with Markov modulated services.

##  3 Three-way matching in a W-topology

Before going into the mathematical details of the W-topology, we motivate the
model using a simple example. Suppose Alex and Jun go to a fast food
restaurant. Alex orders a combo of items A and B, and Jun orders a combo of
items B and C. Now, as this is a fast food chain, it tries to fulfill the
first order that it can. It is simple to observe that, if items A and B are
available before item C, Alex will be served first, even if Jun orders first.
In fact, many customers might get served before Jun, depending on the time
that it takes to prepare item C. Further, the restaurant might have to throw
items away if they get too cold. These kinds of systems are called assemble-
to-order systems [32], with the extra condition that inventories contain
perishable items [15]. In a quantum switch, we have qubits instead of items,
and requests instead of customers. We present the model for the W-topology in
terms of a quantum switch.

Consider a discrete-time system consisting of five FIFO queues with infinite
buffers, where requests arrive to two of the queues as i.i.d. process
$A_{1}(\cdot)$ and $A_{2}(\cdot)$, with $\mathbb{E}[A_{i}(1)]=\lambda_{i}$ and
$\mathbb{E}\big{[}A_{i}(1)^{2}\big{]}<\infty$, and qubits are generated and
join each one of the other three queues as i.i.d. processes $S_{1}(\cdot)$,
$S_{2}(\cdot)$, and $S_{3}(\cdot)$ with $\mathbb{E}[S_{i}(1)]=\mu_{i}$ and
$\mathbb{E}\big{[}S_{i}(1)^{2}\big{]}<\infty$. All these five processes are
independent of each other. Moreover, qubits can depart from the system at each
time slot via abandonments with probability $\gamma$. This system is depicted
in Figure 3.

$\lambda_{1}$$\lambda_{2}$Requests$\mu_{1}$$\gamma$$\mu_{2}$$\gamma$$\mu_{3}$$\gamma$Qubits
Figure 3: Three-way matchings in a W-topology.

Similar to the Y-topology, we assume that a request fulfillment is successful
with probability $p$ and fails with probability $(1-p)$. This means that if
there is at least one item in each of three queues connected according to
Figure 3, they depart immediately as a three-way matching with probability
$p$, or as a two-way matching between the qubits with probability $1-p$ (with
the request staying in its queue). And if the request queue is empty, there is
no matching between the qubits. Here we also assume that there is not bound on
the number of matches that can be made in any time slot.

In the context of a quantum switch, this queueing system corresponds to the
case where there are three nodes but only requests for connections between the
first and second, and between the second and third. If a qubit for the second
node is generated, and there are qubits for the other two nodes stored in the
switch and outstanding requests for both types of connections (i.e., if there
are more than one possible three-way matchings), a control policy (to be
specified later) decides which connection to attempt first. We assume that the
control policy is non-idling, that is, if there are qubits present to fulfill
a request, then the system must attempt a three-way matching. The control
policy only decides the priority between the requests queues.

We model this system as a discrete-time Markov chain $\big{(}{\bf
N}(\cdot),{\bf Q}(\cdot)\big{)}$, where $N_{1}(\cdot)$ and $N_{2}(\cdot)$ are
the number of requests, and $Q_{1}(\cdot)$, $Q_{2}(\cdot)$, and $Q_{3}(\cdot)$
are the number of qubits. Let
$\mathbf{Y}_{i}(t)=\big{\\{}Y^{(i)}_{\ell}(t):\ell,t\in\mathbb{Z}_{+}\big{\\}}$
for $i\in\\{1,2\\}$ be two sets of i.i.d. Bernoulli random variables with
probability $p$, such that $Y^{(i)}_{\ell}(t)$ is the indicator that the
$\ell$-th attempted three-way matching of type $i$ at time $t$ is successful.
We define the Markov chain recursively as follows.

$\displaystyle N_{1}(t+1)$
$\displaystyle=N_{1}(t)+A_{1}(t)-\sum\limits_{\ell=1}^{M_{1}(t)}Y_{\ell}^{(1)}(t)\allowdisplaybreaks$
(4) $\displaystyle N_{2}(t+1)$
$\displaystyle=N_{2}(t)+A_{2}(t)-\sum\limits_{\ell=1}^{M_{2}(t)}Y_{\ell}^{(2)}(t)\allowdisplaybreaks$
(5) $\displaystyle Q_{1}(t+1)$
$\displaystyle=Q_{1}(t)-D_{1}(t)+S_{1}(t)-M_{1}(t)\allowdisplaybreaks$ (6)
$\displaystyle Q_{2}(t+1)$
$\displaystyle=Q_{2}(t)-D_{2}(t)+S_{2}(t)-M_{1}(t)-M_{2}(t)\allowdisplaybreaks$
(7) $\displaystyle Q_{3}(t+1)$
$\displaystyle=Q_{3}(t)-D_{3}(t)+S_{3}(t)-M_{2}(t)$ (8)

where $D_{i}(t)\sim Ber\big{(}Q_{i}(t),\gamma\big{)}$ are the number of
abandonments from the $i$-th qubits’ queue, and $M_{i}(t)$ is the number of
attempted matchings of type $i$ at time $t$. By definition of
$\mathbf{Y}^{(i)}(t)$, the term $\sum_{\ell=1}^{M_{i}(t)}Y_{\ell}^{(i)}(t)$ is
a binomial random variable that represents the number of successful three-way
matchings in the $t$-th slots after $M_{i}(t)$ attempts. Further, by denoting

$U_{i}(t)=\min\left\\{m:\sum\limits_{\ell=1}^{m}Y_{\ell}^{(i)}(t)\geq
N_{i}(t)+A_{i}(t)\right\\}\quad\text{for}\ i\in\\{1,2\\},$ (9)

we have that the number of two-way and three-way matchings of each type are
given by

$\displaystyle M_{1}(t)$
$\displaystyle=\min\big{\\{}Q_{1}(t)-D_{1}(t)+S_{1}(t),\,\,Q_{2}(t)-D_{2}(t)+S_{2}(t)-X(t)M_{2}(t),\,\,U_{1}(t)\big{\\}}$
(10) $\displaystyle M_{2}(t)$
$\displaystyle=\min\big{\\{}Q_{2}(t)-D_{2}(t)+S_{2}(t)-[1-X(t)]M_{1}(t),\,\,Q_{3}(t)-D_{3}(t)+S_{3}(t),\,\,U_{2}(t)\big{\\}}.$
(11)

where $X(t)\in\\{0,1\\}$ is a (possibly randomized) control signal and the
term $U_{i}(t)$ in the definition of $M_{i}(t)$ is similar as in Equation (3).
This definition implies that, in each time slot, three-way matchings are
attempted until there are either no more requests, or no more of any of the
types of qubits to fulfil any request. Thus, the state space of the Markov
chain is $\left\\{({\bf n},{\bf
q})\in\mathbb{Z}_{+}^{2}\times\mathbb{Z}_{+}^{3}:n_{1}.q_{1}.q_{2}=0,\,\,n_{2}.q_{2}.q_{3}=0\right\\}.$
Finally, for the W-topology, the throughput of the $i$-th type of requests is
defined as

$\text{Throughput}_{i}:=\liminf\limits_{t\to\infty}\frac{1}{t}\sum\limits_{k=1}^{t}\sum\limits_{\ell=1}^{M_{i}(k)}Y^{(i)}_{\ell}(k).$

The model for the W-topology can also be thought of as two three-way matching
systems in a Y-topology stitched together. The process
$(N_{1}(\cdot),Q_{1}(\cdot),Q_{2}(\cdot))$ represents the first Y-topology and
the process $(N_{2}(\cdot),Q_{2}(\cdot),Q_{3}(\cdot))$ represents the second
Y-topology, where the two Y-topologies share the resource in the qubit queue
$Q_{2}(\cdot)$. If we consider one of the requests queues, say $N_{1}(\cdot)$,
to be always empty ($\lambda_{1}=0$), then the Y-topology corresponding to the
other request queue, that is $(N_{2}(\cdot),Q_{2}(\cdot),Q_{3}(\cdot))$,
behaves exactly like a three-way matching system in Section 2. Due to this
relationship, the analysis of the W-topology is heavily based on the results
in Section 2.

######  Remark.

The policies that can be implemented using the control signal $X(t)$ are “non-
idling” in the sense that matchings are attempted whenever matchings are
possible. In particular, if $X(t)=0$, all possible matchings amongst queues
involving requests of type $1$ are attempted first, and then all possible
matchings amongst queues involving requests of type $2$ are attempted with the
remaining requests and qubits. If $X(t)=1$, the priority is reversed.

###  3.1 Infinitely backlogged case

We start with the simplified case where both requests queues are infinitely
backlogged, that is, where $N_{1}(t)=N_{2}(t)=\infty$, for all $t\geq 0$. In
this case, the process ${\bf Q}(\cdot)$ is recursively defined as in equations
(6), (7) and (8). Further, as $N_{1}(t)=N_{2}(t)=\infty$, we have that
$U_{1}(t)=U_{2}(t)=\infty$ in Equation (9). Then the three-way matchings
attempted are given by $M_{1}(t)$ and $M_{2}(t)$ in Equation (10) and Equation
(11), respectively, by substituting $U_{1}(t)=U_{2}(t)=\infty$. In this case,
we can model the system as a two-sided queue as in the following proposition.

######  Proposition 1.

Regardless of the control policy, the process
$\tilde{Q}(\cdot)=Q_{1}(\cdot)+Q_{3}(\cdot)-Q_{2}(\cdot)$ behaves (path-wise)
exactly as a two sided queue in Subsection 2.1.3, with arrivals
$S_{1}(\cdot)+S_{3}(\cdot)$ and $S_{2}(\cdot)$, and both the abandonment
probabilities equal to $\gamma$.

The proof of Proposition 1 (given in Appendix D) simply follows by rewriting
the recursive equation for $\tilde{Q}(\cdot)$ and making the observation that,
in infinitely backlogged case, $M_{1}(t)+M_{2}(t)$ does not depend on the
value of the control signal $X(t)$. By the non-idling assumption, whenever
$Q_{2}(\cdot)>0$, we have $Q_{1}(\cdot)+Q_{3}(\cdot)=0$, as otherwise two-way
matchings are possible. Thus, we have
$\tilde{Q}^{+}(\cdot)=Q_{1}(\cdot)+Q_{3}(\cdot)$ and
$\tilde{Q}^{-}(\cdot)=Q_{2}(\cdot)$ with the condition
$\tilde{Q}^{+}(\cdot).\tilde{Q}^{-}(\cdot)=0$. This describes the two-way
matching system of Subsection 2.1 with $\gamma>0$. The only difference here is
in terms of the definition of the throughput. In Subsection 2.1, the
throughput is defined as the average number of matchings, while here, we
define throughput as the average number of ‘successful’ matchings, with
success probability $p>0$. Due to this, the throughput for $\tilde{Q}(\cdot)$
is equal to $p$ times the throughput of the two-way matching system in
Subsection 2.1. Using this equivalence, and the stability and throughput
results in Lemma 2, we have the following.

######  Corollary 1.1.

For any non-idling control policy, the process $\tilde{Q}(\cdot)$ is positive
recurrent, with unique invariant distribution $\pi_{1,2}$, and the total
throughput of the system is

$C_{1,2}:=p\left(\mu_{2}-\gamma\mathbb{E}_{\pi_{1,2}}[Q_{2}]\right)=p\left(\mu_{1}+\mu_{3}-\gamma\mathbb{E}_{\pi_{1,2}}[Q_{1}+Q_{3}]\right).$
(12)

Moreover, the individual throughputs are upper bounded by
$\overline{C}_{1}:=p\left(\mu_{1}-\gamma\mathbb{E}_{\pi^{(0)}_{1,2}}[Q_{1}]\right)$
and
$\overline{C}_{2}:=p\left(\mu_{3}-\gamma\mathbb{E}_{\pi^{(1)}_{1,2}}[Q_{3}]\right)$,
and lower bounded by
$\underline{C}_{1}:=C_{1,2}-\overline{C}_{2}=p\left(\mu_{1}-\gamma\mathbb{E}_{\pi^{(1)}_{1,2}}[Q_{1}]\right)$
and
$\underline{C}_{2}:=C_{1,2}-\overline{C}_{1}=p\left(\mu_{3}-\gamma\mathbb{E}_{\pi^{(0)}_{1,2}}[Q_{3}]\right)$.
where $\pi^{(0)}_{1,2}$ and $\pi^{(1)}_{1,2}$ are the steady-state
distributions of the process ${\bf Q}(\cdot)$ when $X(t)=0$ and $X(t)=1$ for
all $t\geq 0$, respectively.

Note that, Proposition 1 and Lemma 2 imply that the process $\tilde{Q}(\cdot)$
is positive recurrent. As for the throughputs, we make the following
observations:

  * -

Since the evolution of $\tilde{Q}(\cdot)$ does not depend on the control
signal, the steady-state distributions of $Q_{2}(\cdot)=\tilde{Q}^{-}(\cdot)$
and $Q_{1}(\cdot)+Q_{3}(\cdot)=\tilde{Q}^{+}(\cdot)$ also do not depend on the
control signal. Then, by the same argument as in Lemma 2, Equation (12)
follows.

  * -

Even though the steady-state distribution of $Q_{1}(\cdot)+Q_{3}(\cdot)$ does
does not depend on the control policy, the marginal distributions of
$Q_{1}(\cdot)$ and $Q_{3}(\cdot)$ do. Among the non-idling policies, the
throughput of $Q_{1}(\cdot)$ is maximized when it is given strict priority,
that is when $X(t)=0$ for all $t\geq 0$. This gives us the upper bound
$\overline{C}_{1}$.

  * -

Similarly, the throughput for $Q_{1}(\cdot)$ is minimized when $Q_{2}(\cdot)$
is given strict priority, that is when $X(t)=1$ for all $t\geq 0$. This gives
us the lower bound $\underline{C}_{1}$.

  * -

Finally, as the total throughput remains the same for any policy,
$\underline{C}_{1}+\overline{C}_{2}=\overline{C}_{1}+\underline{C}_{2}=C_{1,2}.$

######  Remark.

Unsurprisingly, the upper and lower bounds for the individual throughputs are
obtained when our control policy gives strict priority to one of them.
However, the throughput of the non prioritized matching is not zero because
our non-idling condition forces us to match low priority items when there are
no high priority items to be matched, which is a frequent occurrence due to
abandonments.

###  3.2 Partially infinitely backlogged case

Suppose that we have $N_{1}(t)=\infty$ and $N_{2}(t)<\infty$, for all $t\geq
0$. Since the first request queue is infinite, we set $X(t)=0$ for all $t\geq
0$, giving it strict priority. In this case, the process $(N_{2}(\cdot),{\bf
Q}(\cdot))$ is defined recursively as in equations (5), (6), (7), and (8).
Further, as $N_{1}(t)=\infty$, we have that $U_{1}(t)=\infty$ in Equation (9).
Then the three-way matchings attempted are given by $M_{1}(t)$ and $M_{2}(t)$
in Equation (10) and Equation (11), respectively, by substituting
$U_{1}(t)=\infty$. Here, the second requests queue (and thus the whole system)
can be unstable if its arrival rate is too large. Its stability region is
provided in the following lemma.

######  Lemma 3.

If $\lambda_{2}<\underline{C}_{2}$, then the process $\big{(}N_{2}(\cdot),{\bf
Q}(\cdot)\big{)}$ is positive recurrent, with unique invariant distribution
$\pi_{1}$. Moreover, the throughputs of the first and second requests queues
are
$C_{1}(\lambda_{2}):=p\left(\mu_{1}-\gamma\mathbb{E}_{\pi_{1}}[Q_{1}]\right)$
and $\lambda_{2}$, respectively.

This result can be established by using the same multi-step Lyapunov argument
as for the single three-way matching system in the Y-topology (Theorem 1). The
only difference is that, instead of having the throughput of the Y-topology
when it is infinitely backlogged ($pC_{Y}$), here we have the throughput of a
completely backlogged W-topology with strict priority to the first type of
requests ($\underline{C}_{2}$). Finally, the throughput is obtained using the
same argument as in the proof of Lemma 2.

######  Remark.

It is easy to see that $C_{1}(\lambda_{2})$ is maximized when $\lambda_{2}=0$,
as this implies $M_{2}(t)=0$ for all $t\geq 0$. In that case, the throughput
of the first requests queue is equal to
$C_{1}(0):=p\left(\mu_{1}-\gamma\mathbb{E}_{\overline{\pi}_{1}}[Q_{1}]\right),$
where $\overline{\pi}_{1}$ is the steady-state distribution of the system with
$\lambda_{2}=0$. In particular, this is equal to $p$ times the throughput of
the system in a Y-topology of Subsection 2.2 with $\lambda=\lambda_{1}$ and
$\gamma_{1}=\gamma_{2}=\gamma$. Analogously, we can obtain
$C_{2}(\lambda_{1})$ and its upper bound $C_{2}(0)$.

###  3.3 Stability of the non infinitely backlogged case

In this subsection we consider the case where none of the requests queues are
infinitely backlogged. In this case, the control policy plays a central role
in the stability of these queues. We consider the special case of the Max-
Weight control policy with random tie-breakers, where the control signal is
given by

$X(t)=\begin{cases}0,&\text{ if }N_{1}(t)+A_{1}(t)>N_{2}(t)+A_{2}(t)\\\
Ber(1/2),&\text{ if }N_{1}(t)+A_{1}(t)=N_{2}(t)+A_{2}(t)\\\ 1,&\text{ if
}N_{1}(t)+A_{1}(t)<N_{2}(t)+A_{2}(t).\end{cases}$

Note that our Max-Weight policy compares the size of the requests queues and
ignores the qubits’ queues. This is because, making an analogy with a server-
based queueing system, qubits play the role of “services”, while the requests
play the role of “jobs”. Furthermore, abandonments make the queues of qubits
always stable, while only matching with qubits can stabilize the queues of
requests. Max-Weight scheduling was also used in [41, 12].

Recall that, in the Y-topology of Section 2, the throughput in the infinitely
backlogged case determined the stability region of the non-infinitely
backlogged case. In particular, the stability region was the set of all
arrival rates lower than the throughput in the infinitely backlogged case.
Analogously, here in the W-topology, the throughputs obtained in the either
completely or partially infinitely backlogged case serve as upper bounds for
the individual arrival rates in the stability region. With this in mind, we
expect the stability region of the Max-Weight policy to be the green shaded
part in Figure 4. Moreover, since the upper bounds for the throughputs are
independent of the control policy, we expect any non-idling policy to be
unstable outside the green shaded part in Figure 4. This is formalized in
Theorem 2.

$\lambda_{1}$$\lambda_{2}$$\underline{C}_{1}$$\overline{C}_{1}$$C_{1}(0)$$\underline{C}_{2}$$\overline{C}_{2}$$C_{2}(0)$$\lambda_{2}=C_{2}(\lambda_{1})$$\lambda_{1}=C_{1}(\lambda_{2})$$\lambda_{1}+\lambda_{2}=C_{1,2}$
Figure 4: Max-Weight is stable in the green shaded area, and all non-idling
policies are unstable outside of it.

######  Theorem 2.

We have the following.

  * (i)

If $\lambda_{1}+\lambda_{2}<C_{1,2}$, $\lambda_{1}<C_{1}(\lambda_{2})$, and
$\lambda_{2}<C_{2}(\lambda_{1})$ (green shaded region in Figure 4), then the
process $\big{(}{\bf N}(\cdot),{\bf Q}(\cdot)\big{)}$ is positive recurrent
under the Max-Weight policy.

  * (ii)

If $\lambda_{1}+\lambda_{2}>C_{1,2}$, $\lambda_{1}>C_{1}(\lambda_{2})$, or
$\lambda_{2}>C_{2}(\lambda_{1})$ (non shaded region in Figure 4), then the
process $\big{(}{\bf N}(\cdot),{\bf Q}(\cdot)\big{)}$ is transient under any
non-idling policy.

In particular, this theorem implies that Max-Weight is throughput optimal, as
it is under the simplifying assumptions of [41, 12].

######  Remark.

In order to prove Theorem 2, we use the stability of the Y-topology given by
Theorem 1. Therefore, we cannot obtain Theorem 1 as a special case of Theorem
2 (when $\lambda_{2}=0$), as this would create a circular argument.

######  Remark.

It can be shown that the capacity region defined in Theorem 2 is convex by
exploiting the same fluid limit approach as for this theorem. Indeed, given
two arrival rates for which Max-Weight is stable, we can construct a policy
that alternates between the stochastic behaviors of Max-Weight for each stable
arrival rate (and use the fluid limit approach to prove its stability).

###### Proof.

Proof sketch of Theorem 2: To establish the positive recurrence of
$\big{(}{\bf N}(\cdot),\,{\bf Q}(\cdot)\big{)}$ under Max-Weight policy in its
stability region, we use a fluid limit approach. This is obtained in six
steps, with some intermediate results being of independent interest and stated
later as standalone results.

  1. 1.

Re-scaling the process: The first step is to define the scaling for the
processes ${\bf N}(\cdot)$ and ${\bf Q}(\cdot)$ under which we take the fluid
limit. Since our objective is to prove stability, we accelerate time by some
scaling factor $k$ and scale down space by the same scaling factor $k$. To
obtain a meaningful limit, the initial condition is also scaled up by $k$. The
fluid limit for single server queues typically uses this scaling. Still, it is
not appropriate for infinite server queues, as the sample paths would collapse
to zero regardless of the initial condition. In our setting, since the qubit
queues have abandonments (which gives them a similar behavior to infinite
server queues), the re-scaled process of qubits collapses to zero. Therefore,
we focus on the fluid limit of ${\bf N}(\cdot)$.

  2. 2.

Tightness of sample paths: If the arrival processes to all queues were
uniformly bounded, then a linear interpolation of the discrete time processes
would yield uniformly Lipschitz functions. In that case, the tightness of
sample paths would follow immediately by Arzelà-Ascoli’s theorem. However,
since we only have a bound on the second moments of the arrival processes, we
use the fact that the sample paths are approximately uniformly Lipschitz to
show that there exists a measurable set $\mathcal{C}$, with
$\mathbb{P}(\mathcal{C})=1$, such that for all $\omega\in\mathcal{C}$, any
sequence of sample paths of the re-scaled processes $\left\\{{\bf
N}^{(k)}(\omega,\cdot)\right\\}_{k=1}^{\infty}$ contains a further subsequence
that converges uniformly over compacts to a uniformly Lipschitz trajectory
${\bf n}(\cdot)$, as $k\to\infty$. In particular, this argument relies on the
Lipschitz continuity of the limiting trajectories and does not need further
regularity assumptions on the drift. Therefore, it allows us to obtain
tightness even when the drift is discontinuous.

  3. 3.

Derivatives of the limit points: We characterize the derivative of any limit
point ${\bf n}(\cdot)$ at any regular point, and show that it is identical to
the drift of a certain differential equation (cf. Definition 1). If
$n_{1}(t)>0$ and $n_{2}(t)>0$, the derivatives are characterized by obtaining
bounds on how much the process can change in an $\epsilon$ amount of (re-
scaled) time, and taking the limit as $k\to\infty$. This gives us bounds on
how much the fluid solution changes in an $\epsilon$ amount of time, which
reflect the averaging effect of the qubit processes. Then, we divide this
change by $\epsilon$ and take the limit as $\epsilon\to 0$ to obtain the
derivatives. If either $n_{1}(t)=0$ or $n_{2}(t)=0$, the derivatives are
obtained by exploiting the previous case, and the continuity of derivatives at
the regular times. In particular, we obtain that the limit point ${\bf
n}(\cdot)$ must be a solution of the differential equation, yielding also, as
a corollary, the existence of its solutions.

  4. 4.

Uniqueness of limit points: Since the drift is not continuous, the uniqueness
of limit points cannot be obtained by Picard’s theorem for differential
equations. Therefore, this uniqueness needs to be established in an ad-hoc
way, by concatenating a finite number of trajectories that are provably unique
by Picard’s Theorem.

  5. 5.

Stability of the fluid solutions: We exploit the structure of the derivatives
of the fluid limits to show that all fluid trajectories converge to $0$ in
finite time. In particular, we show that this time is upper bounded by an
affine function of the norm of the initial condition. This finite-time
convergence is crucial for the purposes of obtaining positive recurrence of
the original processes.

  6. 6.

From fluid stability to stochastic stability: Finally, we obtain the positive
recurrence of the original Markov chain $\big{(}{\bf N}(\cdot),\,{\bf
Q}(\cdot)\big{)}$ by combining the finite time convergence of the fluid limit
of ${\bf N}(\cdot)$ to zero with the collapse of ${\bf Q}(\cdot)$ to zero in
the limit, and applying known results [11].

Step 1 is explained in more detail in Subsection 3.4.2. Steps 2-4 establish
the almost sure convergence of the re-scaled processes $\left\\{{\bf
N}^{(k)}(\omega,\cdot)\right\\}_{k=1}^{\infty}$, uniformly over compacts, to
their fluid limit. This is stated as a standalone result in Theorem 3. The
stability of the fluid limits implied by Step 5 is stated in Theorem 4.
Finally, the details of Step 6 and the proof of the second part of Theorem 2
are given in Appendix G. $\square$∎

###  3.4 Transient analysis

In this subsection, we will study the transient behavior of the system through
a fluid approximation. Moreover, this approximation is also used to establish
the positive recurrence of the system when none of the requests queues are
infinitely backlogged.

####  3.4.1 Fluid approximation

We first define the (deterministic) fluid model for our system.

######  Definition 1 (Fluid model).

Given an initial condition ${\bf n^{0}}\in\mathbb{R}_{+}^{2}$ with
$\left\|{\bf n^{0}}\right\|_{1}>0$, a continuous function ${\bf
n}:[0,\infty)\to\mathbb{R}_{+}^{2}$ is said to be a solution to the fluid
model (or fluid solution) if:

  * (i)

${\bf n}(0)={\bf n^{0}}$.

  * (ii)

For all $t\geq 0$, outside of a set of Lebesgue measure zero, ${\bf n}(t)$ is
differentiable and satisfies

$\displaystyle\frac{dn_{1}(t)}{dt}=\lambda_{1}-R_{1}({\bf n}(t)),\ \text{ and
}\ \frac{dn_{2}(t)}{dt}=\lambda_{2}-R_{2}({\bf n}(t)),$

where $R_{i}({\bf n})$ is as follows:

    * (a)

If $n_{i}>n_{j}>0$, then $R_{i}({\bf n})=\overline{C}_{i}\ \text{ and }\
R_{j}({\bf n})=\underline{C}_{j}.$

    * (b)

If $n_{i}=n_{j}>0$, then

$\displaystyle R_{i}({\bf
n})=\text{proj}_{\big{[}\underline{C}_{i},\,\overline{C}_{i}\big{]}}\left(\frac{C_{1,2}+\lambda_{i}-\lambda_{j}}{2}\right)\
\text{ and }\ R_{j}({\bf
n})=\text{proj}_{\big{[}\underline{C}_{j},\,\overline{C}_{j}\big{]}}\left(\frac{C_{1,2}+\lambda_{j}-\lambda_{i}}{2}\right).$

    * (c)

If $n_{i}>n_{j}=0$, then

$\displaystyle R_{i}({\bf
n})=\overline{C}_{i}\mathds{1}_{\\{\lambda_{j}\geq\underline{C}_{j}\\}}+C_{i}(\lambda_{j})\mathds{1}_{\\{\lambda_{j}<\underline{C}_{j}\\}}\
\text{ and }\ R_{j}({\bf
n})=\underline{C}_{j}\mathds{1}_{\\{\lambda_{j}\geq\underline{C}_{j}\\}}+\lambda_{j}\mathds{1}_{\\{\lambda_{j}<\underline{C}_{j}\\}}.$

    * (d)

If $n_{i}=n_{j}=0$, then $R_{i}({\bf n})=\lambda_{i}\ \text{ and }\ R_{j}({\bf
n})=\lambda_{j}.$

These rates have a very close connection with the throughputs in the
infinitely backlogged systems, which we explore below.

  * (a)

If $n_{i}(t)>n_{j}(t)>0$, then both queues will remain positive and the $i$-th
queue will remain the largest one for some time after time $t$. As a result,
both requests queues will behave as if they were infinitely backlogged during
that period, while giving full priority to the $i$-th queue. Thus, the fluid
rates $R_{i}({\bf n}(t))$ and $R_{j}({\bf n}(t))$ are exactly the throughputs
of that case.

  * (b)

If $n_{i}(t)=n_{j}(t)>0$, then both queues will remain positive for some time
after time $t$. As a result, both requests queues will behave as if they were
infinitely backlogged. Since we have $n_{1}(t)=n_{2}(t)$ and we are using Max-
Weight, the control signal gives priority to one or the other queue with the
goal of equalizing them. In particular, the drifts of the queues are equalized
if

$\displaystyle R_{i}({\bf n}(t))=\frac{C_{1,2}+\lambda_{i}-\lambda_{j}}{2}\
\text{ and }\ R_{j}({\bf n}(t))=\frac{C_{1,2}+\lambda_{j}-\lambda_{i}}{2}.$

However, the individual throughputs are lower and upper bounded by constants,
so these rates might be infeasible. Hence, the fluid rates will be the
projection of these ideal rates onto the set of possible rates.

  * (c)

If $n_{i}(t)>n_{j}(t)=0$, then the $i$-th queue will remain positive and will
remain the largest one for some time after time $t$. Since the other request’s
queue length is zero (at least at the fluid scale), the fluid model will
behave as the partially infinitely backlogged system. If
$\lambda_{j}<\underline{C}_{j}$, then this system is stable, and the fluid
rates are equal to the throughputs in that case. However, if
$\lambda_{j}>\underline{C}_{j}$, then the partially backlogged system is not
stable, and the smaller queue will become positive (and hence have the same
fluid rate as if both were positive). In the case
$\lambda_{j}=\underline{C}_{j}$ we also have
$\overline{C}_{i}=C_{i}(\lambda_{j})$, and the fluid rate follows by
continuity of the rates as a function of ${\bf\lambda}$.

  * (d)

Since $\|{\bf n}(0)\|_{1}>0$, then the case $n_{i}(t)=n_{j}(t)=0$ can only
occur for some $t>0$, and only if the overall system is stable. Hence, the
fluid rates are what make ${\bf n}$ stay at zero.

######  Remark.

As it was the case for the throughputs in the infinitely backlogged system,
when $n_{1},n_{2}>0$, it can be checked that we have $R_{i}({\bf
n})\in\big{[}\underline{C}_{i},\,\overline{C}_{i}\big{]}$ and $R_{1}({\bf
n})+R_{2}({\bf n})=C_{1,2}$. This means that the fluid rates are in a segment
within a $2$-dimensional space, drawn in red in Figure 5. In the parlance of
the Max-Weight policies, this means that the possible “schedules” for this
policy lie on this segment when both queues are positive.

####  3.4.2 Convergence of sample paths to a fluid solution

We now formally justify the use of the fluid model as an approximation of the
stochastic system. In order to obtain a fluid approximation, we accelerate
time and contract the state by some common scaling factor $k$. That is, we
consider the sequence of scaled processes $\left\\{\left({\bf
N}^{(k)}(\cdot),{\bf Q}^{(k)}(\cdot)\right)\right\\}_{k=1}^{\infty}$ such that

${\bf N}^{(k)}(t)=\frac{{\bf N}(kt)}{k}\qquad\text{and}\qquad{\bf
Q}^{(k)}(t)=\frac{{\bf Q}(kt)}{k},$

for all $t\geq 0$ and $k\geq 1$. Moreover, to obtain a meaningful limit, the
initial condition also needs to be of order $k$.

Since time is accelerated by a factor of $k$, then the scaled abandonment rate
is initially $\mathcal{O}\big{(}k^{2}\big{)}$, emptying the queues in $o(1)$
units of (re-scaled) time. Formally, since the $Q_{i}(\cdot)$ processes are
upper bounded by GI/M/$\infty$ queues (where qubits only depart due to
abandonments), we have

$\displaystyle\lim\limits_{k\to\infty}\frac{1}{k}\mathbb{E}\Big{[}Q_{i}(kt)\Big{]}$
$\displaystyle\leq\lim\limits_{k\to\infty}\frac{1}{k}\left[\left(kQ_{i}(0)-\frac{\mu_{i}}{\gamma}\right)(1-\gamma)^{kt}+\frac{\mu_{i}}{\gamma}\right]=0,$
(13)

for all $t>0$. Therefore, for the fluid limit, we only consider the case where
$\left\|{\bf Q}^{(k)}(0)\right\|_{1}=0$, for all $k\geq 1$. In this case, we
have the following sample path convergence result.

######  Theorem 3 (Convergence of sample paths).

Fix $T>0$, and ${\bf n^{0}}\in\mathbb{R}_{+}^{2}$ with $\left\|{\bf
n^{0}}\right\|_{1}>0$. If $\left\|{\bf
Q}^{(k)}(0)\right\|_{1}=0,\quad\forall\,k\geq 1,\text{ and
}\lim\limits_{k\to\infty}\left\|{\bf N}^{(k)}(0)-{\bf
n^{0}}\right\|_{1}=0,\quad a.s.,$ then
$\lim\limits_{k\to\infty}\sup\limits_{t\in[0,T]}\left\|{\bf N}^{(k)}(t)-{\bf
n}(t)\right\|_{1}=0,a.s.,$ where ${\bf n}(\cdot)$ is a fluid solution with
initial condition ${\bf n^{0}}$. Furthermore, such solution is unique.

######  Remark.

In light of this theorem, a solution to the fluid model, ${\bf n}(\cdot)$, can
be thought of as a deterministic approximation to the sample paths of the
stochastic process ${\bf N}(\cdot)$ when all coordinates of ${\bf N}(0)$ are
very large and time is accelerated proportionally to $\|{\bf N}(0)\|_{1}$.
Note that the fluid model does not include a variable associated with the
different number of qubits ${\bf Q}(\cdot)$. This is because the qubits
process ${\bf Q}(\cdot)$ evolves on a faster time scale than the requests
process ${\bf N}(\cdot)$. We thus have a process with two different time
scales: on the one hand, the qubits’ queues evolve on a fast time scale, and
from its perspective, the requests process ${\bf N}(\cdot)$ appears static; on
the other hand, the requests process ${\bf N}(\cdot)$ evolves on a slower time
scale and from its perspective, the qubits’ queues appear to be at stochastic
equilibrium. This latter property is manifested in the drift of the fluid
model through $R_{1}({\bf n})$ and $R_{2}({\bf n})$, which can be interpreted
as the long-term average three-way matching rates of the first and second
types of requests, respectively, when the requests processes are fixed at the
state ${\bf n}$.

On the technical side, the proof is challenging for two reasons:

  1. 1.

Discontinuity of the drift: Since the drift is discontinuous, and in
particular not Lipschitz continuous, we cannot apply well-known fluid limit
theorems that rely the Lipschitz continuity of the drift (such as Kurtz’s
theorem for density dependent Markov processes). Furthermore, this
discontinuity also prevents us from applying Picard’s theorem to establish the
existence and uniqueness of fluid solutions, which need to be proved in an ad-
hoc way.

  2. 2.

Infinite-state averaging effect: Since the ${\bf Q}(\cdot)$ process evolves on
a faster time scale than ${\bf N}(\cdot)$, the evolution of the latter at the
fluid scale depends on an averaged version of ${\bf Q}(\cdot)$, which is also
non-standard. Moreover, the fact that the ${\bf Q}(\cdot)$ process has an
infinite state space further complicates the proof.

In order to overcome these two challenges, we prove this theorem by adapting
the approach used in [14]. The complete proof is given in Appendix F.

####  3.4.3 Transient analysis of the fluid solutions

We now analyze the transient behavior of the fluid solutions. In particular we
show that, if the arrival rates are small enough, then fluid solutions
converge to zero in finite time. This is formalized in the following
statement.

######  Theorem 4 (Stability of fluid solutions).

Let ${\bf n}(t)$ be the unique fluid solution with initial condition ${\bf
n^{0}}$. If $\lambda_{1}+\lambda_{2}<C_{1,2}$,
$\lambda_{1}<C_{1}(\lambda_{2})$, and $\lambda_{2}<C_{2}(\lambda_{1})$, then
there exists a constant $B$ that does not depend on the initial condition
${\bf n^{0}}$ such that $\|{\bf n}(t)\|_{1}=0,\qquad\forall\,t\geq
B\left\|{\bf n^{0}}\right\|_{1}.$

The proof involves exploiting the fact that the drift is piece-wise constant
to obtain bounds on the times when the first and second coordinates of ${\bf
n}(\cdot)$ hit zero, and it is given in Appendix E.

When the assumptions of Theorem 4 hold (i.e., when the system is stable under
Max-Weight), there are three qualitatively different cases for the transient
behavior of the fluid solutions, depending on the values of $\lambda_{1}$ and
$\lambda_{2}$. These are depicted in Figure 5 in the shaded green (Case 1),
turquoise (Case 2), and blue (Case 3) areas.

$\lambda_{1}$$\lambda_{2}$$\underline{C}_{1}$$\overline{C}_{1}$$C_{1}(0)$$\underline{C}_{2}$$\overline{C}_{2}$$C_{2}(0)$$\lambda_{1}+\lambda_{2}=C_{1,2}$Case
1Case 2Case 2Case 3Case 3 Figure 5: Pictorial representation of the three
different cases.

Case 1: Suppose that the assumptions of Theorem 4 hold, and that
$\lambda_{1}+\lambda_{2}-C_{1,2}\geq
2\max\left\\{\lambda_{1}-\overline{C}_{1},\,\,\lambda_{2}-\overline{C}_{2}\right\\}.$
This corresponds to the case where the arrival rates $\lambda_{1}$ and
$\lambda_{2}$ are relatively close to each other (area shaded in green in
Figure 5), and implies

$\displaystyle\frac{\lambda_{1}+\lambda_{2}-C_{1,2}}{2}\geq\lambda_{1}-\overline{C}_{1},\quad\text{
and
}\quad\frac{\lambda_{1}+\lambda_{2}-C_{1,2}}{2}\geq\lambda_{2}-\overline{C}_{2}.$

(a) Case 1

(b) Case 2

Figure 6: Sample trajectories of the number of requests in Case 1 and Case 2,
both for the fluid limit and for the appropriately scaled stochastic system
(with $k=1000$)

Note that the right-hand side in the two equations above are the minimum
drifts that $n_{1}(\cdot)$ and $n_{2}(\cdot)$ can ever achieve while they are
both positive, and the left hand side is the average of their drifts when they
are both positive. Thus, when $n_{1}(t)=n_{2}(t)$, these conditions imply that
both coordinates have the same drift, so
$\frac{dn_{1}(t)}{dt}=\frac{dn_{2}(t)}{dt}=\frac{\lambda_{1}+\lambda_{2}-C_{1,2}}{2}.$
While the largest coordinate will always decrease in this case, the smaller
one can either increase or decrease. The key feature of this case is that
if/when they intersect, they will remain together until they hit zero (as in
Figure 6(a)). This is perhaps the typical behavior that one would expect of a
pair of queues scheduled by a Max-Weight policy.

Case 2: Suppose that the assumptions of Theorem 4 hold, and that either for
$i=1$ or for $i=2$,
$\lambda_{1}+\lambda_{2}-C_{1,2}<2\left(\lambda_{i}-\overline{C}_{i}\right)\text{
and }\lambda_{i}<\overline{C}_{i}.$ This corresponds to the case where one of
the arrival rates is relatively larger than the other, but not extremely large
(area shaded in turquoise in Figure 5). The first equation implies that both
coordinates can never have the same drift while they are both positive.
Therefore, if the coordinates become equal and positive at some point, they
will not remain equal. Moreover, the second equation implies that the minimum
drift while they are both positive is still negative, and thus the largest
queue will always be decreasing. The trajectories of the processes
$n_{1}(\cdot)$ and $n_{2}(\cdot)$ in this case look like the ones in Figure
6(b). Since $n_{1}(0)>n_{2}(0)$, at the beginning $n_{1}(\cdot)$ will be
decreasing and $n_{2}(\cdot)$ will be increasing. When they intersect, instead
of remaining together as in Case 1, $n_{2}(\cdot)$ decreases at a slower rate
than $n_{1}(\cdot)$. Finally, after $n_{1}(\cdot)$ hits zero, $n_{2}(\cdot)$
decreases at a higher rate until it hits zero as well.

Case 3: Suppose that the assumptions of Theorem 4 hold, and that for $i=1$ or
$i=2$,
$\lambda_{1}+\lambda_{2}-C_{1,2}<2\left(\lambda_{i}-\overline{C}_{i}\right)\text{
and }\lambda_{i}\geq\overline{C}_{i}.$

Figure 7: Sample trajectories of the number of requests in Case 3, both for
the fluid limit and for the appropriately scaled stochastic system (with
$k=1000$).

This corresponds to the case where one of the arrival rates is almost as large
as it can be while being stable, and therefore also relatively larger than the
other arrival rate (area shaded in blue in Figure 5). These equations imply
that both coordinates cannot have the same drift while they are both positive,
and that the minimum drift for either $n_{2}(\cdot)$ or $n_{1}(\cdot)$ is non-
negative while both coordinates are positive. Therefore, even if the
coordinates become equal and positive at some point, they will not remain
equal. Moreover, one of the coordinates is non-decreasing as long as the other
is also positive, even when it is the largest one, and thus given the highest
priority by our Max-Weight policy. For example. the trajectories of the
processes $n_{1}(\cdot)$ and $n_{2}(\cdot)$ in this case could look like the
ones in Figure 7. Until they intersect, the trajectories behave the same as in
cases 1 and 2. However, after they intersect, $n_{2}(\cdot)$ does not
decrease, and it fact it increases if the inequality in the second equation is
strict. This goes on until $n_{1}(\cdot)$ hits zero, at which point
$n_{1}(\cdot)$ starts to decrease until it hits zero as well. This happens
because, even when the first requests queue has strict priority, the non-
idling condition forces the system into performing matchings involving the
second request queue when there are not enough qubits to match with the first
one, thus reducing the overall throughput of the latter. This is surprising
because, when Max-Weight is used, the largest queue is usually decreasing
instead of increasing as in this case.

##  4 Conclusions and future work

In this paper we presented a general queueing model for a quantum switch. Due
to its complexity, we only analyzed it for a couple of simple topologies. We
showed that the Max-Weight policy is throughput optimal, and that its
stability region is larger than the convex hull of the throughputs obtained
when the requests queues are infinitely backlogged, a setting that was studied
in the literature. Moreover, using a fluid limit approximation we showed that
the decoherence of the qubits can produce the counter-intuitive phenomenon
where the largest queue has positive drift under a Max-Weight policy, even
when the overall system is stable.

There are several avenues of future work that we may pursue. The main one
would be to extend our analysis to more complex networks. We conjecture that,
in such networks, the stability region can still be obtained as the convex
hull of all throughputs obtained by partially infinitely backlogging the
system, in all possible ways. Therefore, this presents a combinatorial
challenge that needs to be solved. The other directions would involve
generalizing our model to include other features, such as the following.

  * (i)

Heterogeneous abandonment and/or multi-way matching success probabilities.

  * (ii)

The possibility for more than two nodes to be simultaneously connected through
a more complex entanglement process with more than two qubits.

  * (iii)

More general abandonment (decoherence) distributions, and the impact of
different scheduling disciplines in that case.

## Acknowledgements

This work was partially supported by NSF Grant CMMI-2140534.

## References

  * Armstrong et al. [2012] [author] Armstrong, SeijiS., Morizur, Jean-FrançoisJ.-F., Janousek, JiriJ., Hage, BorisB., Treps, NicolasN., Lam, Ping KoyP. K. and Bachor, Hans-AH.-A. (2012). Programmable multimode quantum networks. Nature Communications 3 1–8.
  * Aveklouris, DeValve and Ward [2021] [author] Aveklouris, AngelosA., DeValve, LeviL. and Ward, Amy R.A. R. (2021). Matching Impatient Heterogeneous Demand and Supply. arXiv:2102.02710v3.
  * Baccelli and Foss [1995] [author] Baccelli, FrancoisF. and Foss, SergeiS. (1995). On the Saturation Rule for the Stability of Queues. Journal of Applied Probability 32 494-507.
  * Bhaskar et al. [2020] [author] Bhaskar, Mihir KM. K., Riedinger, RalfR., Machielse, BartholomeusB., Levonian, David SD. S., Nguyen, Christian TC. T., Knall, Erik NE. N., Park, HongkunH., Englund, DirkD., Lončar, MarkoM., Sukachev, Denis DD. D. et al. (2020). Experimental demonstration of memory-enhanced quantum communication. Nature 580 60–64.
  * Blanchet et al. [2022] [author] Blanchet, Jose HJ. H., Reiman, Martin IM. I., Shah, ViragV., Wein, Lawrence ML. M. and Wu, LinjiaL. (2022). Asymptotically optimal control of a centralized dynamic matching market with general utilities. Operations Research.
  * Bramson [1998] [author] Bramson, MauryM. (1998). State space collapse with application to heavy traffic limits for multiclass queueing networks. Queueing Systems 30 89-148.
  * Bušić, Gupta and Mairesse [2013] [author] Bušić, AnaA., Gupta, VarunV. and Mairesse, JeanJ. (2013). Stability of the bipartite matching model. Advances of Applied Probability 45 351–378.
  * Cadas, Bušić and Doncel [2019] [author] Cadas, ArnaudA., Bušić, AnaA. and Doncel, JosuJ. (2019). Optimal control of dynamic bipartite matching models. In Proceedings of the 12th EAI International Conference on Performance Evaluation Methodologies and Tools 39–46.
  * Cadas et al. [2022] [author] Cadas, ArnaudA., Doncel, JosuJ., Fourneau, Jean-MichelJ.-M. and Busic, AnaA. (2022). Flexibility can hurt dynamic matching system performance. 49 37–42. ACM New York, NY, USA.
  * Castro, Nazerzadeh and Yan [2020] [author] Castro, FranciscoF., Nazerzadeh, HamidH. and Yan, ChiweiC. (2020). Matching queues with reneging: a product form solution. Queueing Systems 96 359–385.
  * Dai and Harrison [2020] [author] Dai, Jim G.J. G. and Harrison, Michael J.M. J. (2020). Processing Networks: Fluid Models and Stability. Cambridge University Press.
  * Dai, Rinaldi and Towsley [2021] [author] Dai, WenhanW., Rinaldi, AnthonyA. and Towsley, DonD. (2021). Entanglement Swapping in Quantum Switches: Protocol Design and Stability Analysis. arXiv:2110.04116v1.
  * Diamant and Baron [2019] [author] Diamant, AdamA. and Baron, OpherO. (2019). Double-sided matching queues: Priority and impatient customers. Operations Research Letters 47 219-224.
  * Gamarnik, Tsitsiklis and Zubeldia [2018] [author] Gamarnik, DavidD., Tsitsiklis, John N.J. N. and Zubeldia, MartinM. (2018). Delay, memory, and messaging tradeoffs in distributed service systems. Stochastic Systems 8 45–74.
  * Graves [1982] [author] Graves, Stephen CS. C. (1982). The application of queueing theory to continuous perishable inventory systems. Management Science 28 400–406.
  * Gupta [2022] [author] Gupta, VarunV. (2022). Greedy Algorithm for Multiway Matching with Bounded Regret. arXiv:2112.04622v3.
  * Gurvich and Ward [2014] [author] Gurvich, ItaiI. and Ward, Amy R.A. R. (2014). On the Dynamic Control of Matching Queues. Stochastic Systems 4 479–523.
  * Gyongyosi and Imre [2022] [author] Gyongyosi, LaszloL. and Imre, SandorS. (2022). Advances in the Quantum Internet. Communications of the ACM 65 52–63.
  * Hall, Altepeter and Kumar [2011] [author] Hall, Matthew AM. A., Altepeter, Joseph BJ. B. and Kumar, PremP. (2011). Ultrafast switching of photonic entanglement. Physical review letters 106 053901\.
  * Herbauts et al. [2013] [author] Herbauts, IsabelleI., Blauensteiner, BibianeB., Poppe, AndreasA., Jennewein, ThomasT. and Hübel, HannesH. (2013). Demonstration of active routing of entanglement in a multi-user network. Optics Express 21 29013–29024.
  * Jonckheere et al. [2022] [author] Jonckheere, MatthieuM., Moyal, PascalP., Ramírez, ClaudiaC. and Soprano-Loto, NahuelN. (2022). Generalized max-weight policies in stochastic matching. Stochastic Systems.
  * Kerimov, Ashlagi and Gurvich [2021] [author] Kerimov, SuleymanS., Ashlagi, ItaiI. and Gurvich, ItaiI. (2021). On the Optimility of Greedy Policies in Dynamic Matching. https://web.stanford.edu/ kerimov/GreedyKAG.pdf.
  * Lee et al. [2022] [author] Lee, YuanY., Bersin, EricE., Dahlberg, AxelA., Wehner, StephanieS. and Englund, DirkD. (2022). A quantum router architecture for high-fidelity entanglement flows in quantum networks. npj Quantum Information 8 1–8.
  * Li et al. [2018] [author] Li, RuoyuR., Petit, LucaL., Franke, David PD. P., Dehollain, Juan PabloJ. P., Helsen, JonasJ., Steudtner, MarkM., Thomas, Nicole KN. K., Yoscovits, Zachary RZ. R., Singh, Kanwal JK. J., Wehner, StephanieS. et al. (2018). A crossbar network for silicon quantum dot qubits. Science Advances 4\.
  * Maglaras [2000] [author] Maglaras, ConstantinosC. (2000). Discrete-review policies for scheduling stochastic networks: trajectory tracking and fluid-scale asymptotic optimility. Annals of Applied Probability 10 897–929.
  * Menshikov, Popov and Wade [2016] [author] Menshikov, MikhailM., Popov, SergueiS. and Wade, AndrewA. (2016). Non-homogeneous random walks: Lyapunov function methods for near-critical stochastic systems 209\. Cambridge University Press.
  * Meyn and Tweedie [1992] [author] Meyn, Sean P.S. P. and Tweedie, R. L.R. L. (1992). Stability of Markovian processes I: criteria for discrete-time Chains. Advances in Applied Probability 24 542–574. 10.2307/1427479
  * Moyal, Bušić and Mairesse [2021] [author] Moyal, PascalP., Bušić, AnaA. and Mairesse, JeanJ. (2021). A product form for the general stochastic matching model. Journal of Applied Probability 58 449–468.
  * Moyal and Perry [2017] [author] Moyal, PascalP. and Perry, OhadO. (2017). On the instability of matching queues. Annals of Applied Probability 27 3385–3434.
  * Nain et al. [2022] [author] Nain, PhilippeP., Vardoyan, GayaneG., Guha, SaikatS. and Towsley, DonD. (2022). Analysis of a tripartite entanglement distribution switch. Queueing Systems 101 291–328.
  * Nazari and Stolyar [2018] [author] Nazari, MohammadrezaM. and Stolyar, Alexander L.A. L. (2018). Reward maximization in general dynamic matching systems. Queueing Systems 91 143–170.
  * Plambeck and Ward [2006] [author] Plambeck, Erica LE. L. and Ward, Amy RA. R. (2006). Optimal control of a high-volume assemble-to-order system. Mathematics of Operations Research 31 453–477.
  * Rahme and Moyal [2021] [author] Rahme, YoussefY. and Moyal, PascalP. (2021). A stochastic matching model on hypergraphs. Advances in Applied Probability 53 951–980.
  * Schoute et al. [2016] [author] Schoute, EddieE., Mancinska, LauraL., Islam, TanvirulT., Kerenidis, IordanisI. and Wehner, StephanieS. (2016). Shortcuts to Quantum Network Routing Technical Report, Cornell University.
  * Shanthikumar and Yao [1989] [author] Shanthikumar, J. GeorgeJ. G. and Yao, David D.D. D. (1989). Stochastic monotonicity in general queueing networks. Journal of Applied Probability 26 413–417.
  * Tsitsiklis and Xu [2012] [author] Tsitsiklis, John N.J. N. and Xu, KuangK. (2012). On the power of (even a little) resource pooling. Stochastic Systems 2 1-66.
  * van Meter [2014] [author] van Meter, RodneyR. (2014). Quantum Networking. John Wiley & Sons.
  * Vardoyan et al. [2020] [author] Vardoyan, GayaneG., Guha, SaikatS., Nain, PhilippeP. and Towsley, DonD. (2020). On the exact analysis of an idealized quantum switch. Performance Evaluation 144 102–141.
  * Vardoyan et al. [2021] [author] Vardoyan, GayaneG., Guha, SaikatS., Nain, PhilippeP. and Towsley, DonD. (2021). On the stochastic analysis of a quantum entanglement distribution switch. IEEE Transactions on Quantum Engineering 2 1–16.
  * Vardoyan et al. [2022] [author] Vardoyan, GayaneG., Guha, SaikatS., Nain, PhilippeP. and Towsley, DonD. (2022). On the Capacity Region of Bipartite and Tripartite Entanglement Switching. ACM SIGMETRICS Performance Evaluation Review 49 79-80.
  * Vasantam and Towsley [2021] [author] Vasantam, ThirupathaiahT. and Towsley, DonD. (2021). Stability analysis of a Quantum network with Max-Weight scheduling. arXiv:2106.00831v1.

##  Appendix A Proof of Lemma 1

  * (i)

First note that, when $\lambda<\mu$, a negative state is accessible from any
positive state. Moreover, abandonments make sure that $0$ is accessible from
any negative state. Therefore, the Markov chain $Q(\cdot)$ is irreducible.
Since abandonments, as they are binomially distributed, can also make the
chain go from any negative state to $0$ in one step, $Q(\cdot)$ is also
aperiodic.

Consider the Lyapunov function $L(Q)=|Q|$. Then, using the triangular
inequality and the law of total probability, we have

$\displaystyle\mathbb{E}[L(Q(t+1))-L(Q(t))\mid Q(t)=q]$
$\displaystyle\qquad\qquad\qquad=\mathbb{E}[|Q(t)+A_{1}(t)-A_{2}(t)+D_{2}(t)|-|Q(t)|\mid
Q(t)=q]$
$\displaystyle\qquad\qquad\qquad\leq\mathbb{E}[A_{1}(t)+|Q(t)-A_{2}(t)+D_{2}(t)|-|Q(t)|\mid
Q(t)=q]$
$\displaystyle\qquad\qquad\qquad=\lambda+\mathbb{E}[|Q(t)-A_{2}(t)|-|Q(t)|\mid
Q(t)=q]\mathds{1}_{\\{q\geq 0\\}}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad+\mathbb{E}[|Q(t)-A_{2}(t)+D_{2}(t)|-|Q(t)|\mid
Q(t)=q]\mathds{1}_{\\{q<0\\}}$
$\displaystyle\qquad\qquad\qquad\leq\lambda+\mathbb{E}[|Q(t)-A_{2}(t)|-|Q(t)|\mid
Q(t)=q]\mathds{1}_{\\{q\geq 0\\}}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad+\mathbb{E}[A_{2}(t)+|Q(t)+D_{2}(t)|-|Q(t)|\mid
Q(t)=q]\mathds{1}_{\\{q<0\\}}$
$\displaystyle\qquad\qquad\qquad=\lambda+\Big{(}\mathbb{E}[-A_{2}(t)\mid
Q(t)=q,\,\,A_{2}(t)\leq q]\mathbb{P}(A_{2}(t)\leq q)$
$\displaystyle\qquad\qquad\qquad\qquad+\mathbb{E}[A_{2}(t)-2Q(t)\mid
Q(t)=q,\,\,A_{2}(t)>q]\mathbb{P}(A_{2}(t)>q)\Big{)}\mathds{1}_{\\{q\geq 0\\}}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad+\mathbb{E}[A_{2}(t)-D_{2}(t)\mid
Q(t)=q]\mathds{1}_{\\{q<0\\}}$
$\displaystyle\qquad\qquad\qquad\leq\lambda-\Big{(}\mathbb{E}[A_{2}(t)\mid
A_{2}(t)\leq q]\mathbb{P}\big{(}A_{2}(t)\leq q\big{)}-\mathbb{E}[A_{2}(t)\mid
A_{2}(t)>q]\mathbb{P}\big{(}A_{2}(t)>q\big{)}\Big{)}\mathds{1}_{\\{q\geq
0\\}}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad+(\mu-\gamma|q|)\mathds{1}_{\\{q<0\\}}.$

Since $\mathbb{E}[A_{2}(t)]=\mu>\lambda$, there exists $\bar{A}$ large enough
such that

$\mathbb{E}\left[A_{2}(t)\mid
A_{2}(t)\leq\bar{A}\right]\mathbb{P}\left(A_{2}(t)\leq\bar{A}\right)-\mathbb{E}\left[A_{2}(t)\mid
A_{2}(t)>\bar{A}\right]\mathbb{P}\left(A_{2}(t)>\bar{A}\right)\geq\frac{\mu+\lambda}{2}.$

If $|q|\geq\max\left\\{\bar{A},2\mu/\gamma\right\\}$, we have

$\displaystyle\mathbb{E}\big{[}L(Q(t+1))-L(Q(t))\mid Q(t)=q\big{]}$
$\displaystyle\leq-\left(\frac{\mu-\lambda}{2}\right)<0.$

Combining this with the facts that there are only finitely many states with
$|q|<\max\left\\{\bar{A},2\mu/\gamma\right\\}$, and that $Q(\cdot)$ is
irreducible and aperiodic, we conclude that $Q(\cdot)$ is positive recurrent
by the Foster-Lyapunov theorem [27].

Finally, since $Q(\cdot)$ is positive recurrent, and since the throughput is
equal to the time average departure rate of the queue with no abandonments,
then the throughput is also equal to its arrival rate $\lambda$.

  * (ii)

Note that

$\displaystyle Q(t)$
$\displaystyle=Q(0)+\sum\limits_{k=0}^{t-1}A_{1}(k)-A_{2}(k)+D_{2}(k)$
$\displaystyle\geq Q(0)+\sum\limits_{k=0}^{t-1}A_{1}(k)-A_{2}(k).$

Therefore, $Q(\cdot)$ is lower bounded by a random walk. Since $\lambda>\mu$,
this is a positively biased random walk that diverges to $+\infty$ a.s., and
thus so does $Q(\cdot)$. In particular, this implies that for almost every
sample path $\omega$, there exists a time $T(\omega)$ such that
$Q(\omega,t)>0$ for all $t\geq T(\omega)$. It follows that
$M(\omega,t)=A_{2}(\omega,t)$ for all $t\geq T(\omega)$, and thus

Throughput
$\displaystyle=\liminf\limits_{t\to\infty}\frac{1}{t}\sum\limits_{k=1}^{t}M(\omega,k)$
$\displaystyle=\liminf\limits_{t\to\infty}\frac{1}{t}\sum\limits_{k=1}^{T(\omega)}M(\omega,k)+\frac{1}{t}\sum\limits_{k=T(\omega)+1}^{t}A_{2}(\omega,k),$

which converges to $\mu_{2}$ for almost every sample path $\omega$.

##  Appendix B Proof of Lemma 2

The irreducibility and aperiodicity of this chain follows from the same
argument as in the proof of Lemma 1. Consider the Lyapunov function
$L(Q)=|Q|$. Then, using the triangular inequality, we get

$\displaystyle\mathbb{E}[L(Q(t+1))-L(Q(t))\mid Q(t)=q]$
$\displaystyle\leq(\mu_{1}+\mu_{2}-\gamma_{1}|q|)\mathds{1}_{\\{q\geq
0\\}}+(\mu_{1}+\mu_{2}-\gamma_{2}|q|)\mathds{1}_{\\{q<0\\}}.$

If

$|q|\geq\frac{\mu_{1}+\mu_{2}+\epsilon}{\min\\{\gamma_{1},\gamma_{2}\\}},$
(14)

for some $\epsilon>0$, we have

$\displaystyle\mathbb{E}\big{[}L(Q(t+1))-L(Q(t))\,\big{|}\,Q(t)=q\big{]}$
$\displaystyle\leq-\epsilon<0.$

Combining this with the fact that there are finitely many states where
Equation (14) does not hold, and with the irreducibility and aperiodicity of
$Q(\cdot)$, it follows that $Q(\cdot)$ is positive recurrent with unique
invariant distribution $\pi$ by the Foster-Lyapunov theorem [27]. Finally, the
recursive definition of $Q(\cdot)$ implies that

$M(t)=Q^{+}(t)-Q^{+}(t+1)+A_{1}(t)-D_{1}(t).$

Moreover, when $Q(\cdot)$ starts in steady-state, we have
$\mathbb{E}_{\pi}[Q^{+}(t+1)]=\mathbb{E}_{\pi}[Q^{+}(t+1)]<\infty$. Therefore,
in steady-state, we have

$\displaystyle\mathbb{E}_{\pi}[M(t)]$
$\displaystyle=\mathbb{E}_{\pi}[Q^{+}(t)-Q^{+}(t+1)+A_{1}(t)-D_{1}(t)]$
$\displaystyle=\mathbb{E}_{\pi}[A_{1}(t)-D_{1}(t)]$
$\displaystyle=\mu_{1}-\gamma_{1}\mathbb{E}_{\pi}[Q^{+}].$

It follows that

Throughput
$\displaystyle=\liminf\limits_{t\to\infty}\frac{1}{t}\sum\limits_{k=1}^{t}M(k)$
$\displaystyle=\mathbb{E}_{\pi}[M(1)]$
$\displaystyle=\mu_{1}-\gamma_{1}\mathbb{E}_{\pi}[Q^{+}].$

The argument for $Q^{-}$ is analogous.

##  Appendix C Proof of Theorem 1

Since this proof involves constructing a pair of coupled processes, it is
convenient to write the abandonements as

$D_{i}(t)=\sum\limits_{\ell=1}^{Q_{i}(t)}Z^{(i)}_{\ell}(t),$

where $Z^{(i)}_{\ell}(t)\sim Ber(\gamma_{i})$ are i.i.d., and independent from
everything else. Now, we present the proof of each part of Theorem 1.

###  C.1 Positive recurrence

The positive recurrence is established in two steps. First, we construct a
pair of coupled stochastic processes, and show that these new processes
stochastically dominate the original one. Second, we establish the positive
recurrence of these new processes through a multi-step Lyapunov drift
argument. Combining the two steps, the positive recurrence of the original
process follows. The two processes used for coupling are defined below.

Process I: We first consider a coupled process
$\left(\overline{N}(\cdot),\underline{\bf Q}(\cdot)\right)$, where qubits are
always matched regardless of whether there are requests or not. In particular,
this means that the qubit queues behave as if the requests were infinitely
backlogged, regardless of the number of requests in their queue. Thus, the
qubits’ queues act as a two-way matching system. The coupling with the
original processes is done in a way so that these new ones have the same
initial condition, i.e., with $\left(\overline{N}(0),\underline{\bf
Q}(0)\right)=\big{(}N(0),{\bf Q}(0)\big{)}$, and so that they have the same
arrival processes $A(\cdot)$, $S_{1}(\cdot)$ and $S_{2}(\cdot)$, and the same
abandonment primitives $Z_{\ell}^{(i)}(\cdot)$. These new processes are
defined recursively as

$\displaystyle\overline{N}(t+1)$
$\displaystyle=\overline{N}(t)+A(t)-\sum\limits_{\ell=1}^{\overline{M}(t)}Y_{\ell}(t)$
$\displaystyle\underline{Q}_{1}(t+1)$
$\displaystyle=\underline{Q}_{1}(t)-\underline{D}_{1}(t)+S_{1}(t)-\overline{\overline{M}}(t)$
$\displaystyle\underline{Q}_{2}(t+1)$
$\displaystyle=\underline{Q}_{2}(t)-\underline{D}_{2}(t)+S_{2}(t)-\overline{\overline{M}}(t),$

where

$\overline{\overline{M}}(t)=\min\left\\{\underline{Q}_{1}(t)-\underline{D}_{1}(t)+S_{1}(t),\,\,\underline{Q}_{2}(t)-\underline{D}_{2}(t)+S_{2}(t)\right\\},$

is the total number of two-way and three-way matchings made in the $t$-th slot
(including the ones that do not involve a request) and

$\overline{M}(t)=\min\left\\{\overline{\overline{M}}(t),\min\left\\{m:\sum\limits_{\ell=1}^{m}Y_{\ell}(t)\geq\overline{N}(t)+A(t)\right\\}\right\\}$

is the number of successful three-way matchings in the $t$-th slot. Also, we
couple the abandonment of this process with the original one using

$\underline{D}_{i}(t)=\sum\limits_{\ell=1}^{\underline{Q}_{i}(t)}Z^{(i)}_{\ell}(t).$

Note that this new system effectively discards qubits that could have been
matched to a request in the future if there are no pending requests in the
present. This stands in contrast with the original system, where the qubits
are stored until a new request arrives. Intuitively, there should be less
qubits in the queues for this new system, and the number of queued requests
should higher in this new system. This intuition is formalized in the
following two lemmas.

######  Lemma 4.

We have $Q_{i}(t)\geq\underline{Q}_{i}(t)$, for all $t\geq 0$ and
$i\in\\{1,2\\}$.

###### Proof.

Proof: Note that, for each sample path, $\underline{Q}_{i}(\cdot)$ can be
obtained from $Q_{i}(\cdot)$ by simply shortening the “service time” of qubits
so that they depart earlier. Therefore, [35, Proposition 2] implies that
$Q_{i}(t)\geq\underline{Q}_{i}(t)$, for all $t\geq 0$. $\square$
∎

Suppose that $p=1$, that is, suppose that three-way matchings succeed with
probability one. Then, it can be checked that, for each sample path,
$\overline{N}(\cdot)$ can be obtained from $N(\cdot)$ by simply adding request
arrivals so that they match with the extra qubits. In this case, [35,
Proposition 2] implies that $\overline{N}(t)\geq N(t)$, for all $t\geq 0$.
However, when $p<1$ this is no longer the case, as added requests could remain
in the system after exhausting all extra qubits. As a result, we prove this
stochastic dominance in the following lemma.

######  Lemma 5.

We have $\overline{N}(t)\geq N(t)$, for all $t\geq 0$.

###### Proof.

Proof: First note that it is enough to prove that

$\displaystyle\overline{N}(t)-\underline{Q}_{1}(t)\geq
N(t)-Q_{1}(t)\qquad\text{and}\qquad\overline{N}(t)-\underline{Q}_{2}(t)\geq
N(t)-Q_{2}(t)$ (15)

for all $t\geq 0$. This can be seen as follows.

  * -

When $N(t)=0$, we always have $\overline{N}(t)\geq 0$. Thus,
$\overline{N}(t)\geq N(t)$ trivially holds.

  * -

When $N(t)>0$, then by the definition of the original process, at least one of
the qubit queues is empty. For ease of notation, we assume $Q_{1}(t)=0$. Then,
by above equation, $\overline{N}(t)-\underline{Q}_{1}(t)\geq
N(t)-Q_{1}(t)=N(t)$. This implies that $\overline{N}(t)\geq N(t)$ as
$\underline{Q}_{1}(t)\geq 0$.

Thus, we only need to prove that Equation (15) holds. We prove this using
induction. At $t=0$, the condition holds by assumption
$\left(\overline{N}(0),\underline{\bf Q}(0)\right)=\big{(}N(0),{\bf
Q}(0)\big{)}$. Now, assume Equation (15) hold at time $t$. Then,

$\displaystyle\overline{N}(t+1)-\underline{Q}_{i}(t+1)-\big{[}N(t+1)-Q_{i}(t+1)\big{]}$
$\displaystyle\qquad=\overline{N}(t)-\sum\limits_{\ell=1}^{\overline{M}(t)}Y_{\ell}(t)-\underline{Q}_{i}(t)+\underline{D}_{i}(t)+\overline{\overline{M}}(t)-\left[N(t)-\sum\limits_{\ell=1}^{M(t)}Y_{\ell}(t)-Q_{i}(t)+D_{i}(t)+M(t)\right]$
$\displaystyle\qquad\geq\left[\overline{N}(t)-N(t)\right]+\left[\overline{\overline{M}}(t)-\sum\limits_{\ell=1}^{\overline{\overline{M}}(t)}Y_{\ell}(t)\right]-\left[M(t)-\sum\limits_{\ell=1}^{M(t)}Y_{\ell}(t)\right]+\left[Q_{i}(t)-\underline{Q}_{i}(t)\right]-\left[D_{i}(t)-\underline{D}_{i}(t)\right]$
$\displaystyle\qquad=\left[\overline{N}(t)-N(t)\right]+\left[\overline{\overline{M}}(t)-\sum\limits_{\ell=1}^{\overline{\overline{M}}(t)}Y_{\ell}(t)\right]-\left[M(t)-\sum\limits_{\ell=1}^{M(t)}Y_{\ell}(t)\right]+\left[Q_{i}(t)-\underline{Q}_{i}(t)\right]$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad-\left[\sum\limits_{\ell=1}^{Q_{i}(t)}Z^{(i)}_{\ell}(t)-\sum\limits_{\ell=1}^{\underline{Q}_{i}(t)}Z^{(i)}_{\ell}(t)\right],$

where the inequality follows by using
$\overline{M}(t)\geq\overline{\overline{M}}(t)$ by construction. Since
$Q_{i}(t)\geq\underline{Q}_{i}(t)$ by Lemma 4, then

$\sum\limits_{\ell=1}^{Q_{i}(t)}Z^{(i)}_{\ell}(t)-\sum\limits_{\ell=1}^{\underline{Q}_{i}(t)}Z^{(i)}_{\ell}(t)=\sum\limits_{\ell=\underline{Q}_{i}(t)+1}^{Q_{i}(t)}Z^{(i)}_{\ell}(t)\leq
Q_{i}(t)-\underline{Q}_{i}(t)$

and

$\displaystyle M(t)$
$\displaystyle=\min\left\\{Q_{1}(t)-D_{1}(t)+S_{1}(t),\,\,Q_{2}(t)-D_{2}(t)+S_{2}(t),\,\,U(t)\right\\}$
$\displaystyle\leq\min\left\\{Q_{1}(t)-D_{1}(t)+S_{1}(t),\,\,Q_{2}(t)-D_{2}(t)+S_{2}(t)\right\\}$
$\displaystyle=\min\left\\{\underline{Q}_{1}(t)-\underline{D}_{1}(t)+S_{1}(t),\,\,\underline{Q}_{2}(t)-\underline{D}_{2}(t)+S_{2}(t)\right\\}$
$\displaystyle\qquad\qquad\qquad+\left[Q_{1}(t)-D_{1}(t)-\underline{Q}_{1}(t)+\underline{D}_{1}(t)\right]\mathds{1}_{\left\\{Q_{1}(t)-D_{1}(t)+S_{1}(t)<Q_{2}(t)-D_{2}(t)+S_{2}(t)\right\\}}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad+\left[Q_{2}(t)-D_{2}(t)-\underline{Q}_{2}(t)+\underline{D}_{2}(t)\right]\mathds{1}_{\left\\{Q_{1}(t)-D_{1}(t)+S_{1}(t)\geq
Q_{2}(t)-D_{2}(t)+S_{2}(t)\right\\}}$
$\displaystyle=\overline{\overline{M}}(t)+\left[Q_{1}(t)-D_{1}(t)-\underline{Q}_{1}(t)+\underline{D}_{1}(t)\right]\mathds{1}_{\left\\{Q_{1}(t)-D_{1}(t)+S_{1}(t)<Q_{2}(t)-D_{2}(t)+S_{2}(t)\right\\}}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad+\left[Q_{2}(t)-D_{2}(t)-\underline{Q}_{2}(t)+\underline{D}_{2}(t)\right]\mathds{1}_{\left\\{Q_{1}(t)-D_{1}(t)+S_{1}(t)\geq
Q_{2}(t)-D_{2}(t)+S_{2}(t)\right\\}}$
$\displaystyle\leq\overline{\overline{M}}(t)+\left[Q_{1}(t)-\underline{Q}_{1}(t)\right]\mathds{1}_{\left\\{Q_{1}(t)-D_{1}(t)+S_{1}(t)<Q_{2}(t)-D_{2}(t)+S_{2}(t)\right\\}}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad+\left[Q_{2}(t)-\underline{Q}_{2}(t)\right]\mathds{1}_{\left\\{Q_{1}(t)-D_{1}(t)+S_{1}(t)\geq
Q_{2}(t)-D_{2}(t)+S_{2}(t)\right\\}},$

and thus, using the inductive hypothesis, we obtain

$\displaystyle\overline{N}(t+1)-\underline{Q}_{i}(t+1)-\big{[}N(t+1)-Q_{i}(t+1)\big{]}$
$\displaystyle\qquad\qquad\qquad\geq\left[\overline{N}(t)-N(t)\right]+\left[Q_{1}(t)-\underline{Q}_{1}(t)\right]\mathds{1}_{\left\\{Q_{1}(t)-D_{1}(t)+S_{1}(t)<Q_{2}(t)-D_{2}(t)+S_{2}(t)\right\\}}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad+\left[Q_{2}(t)-\underline{Q}_{2}(t)\right]\mathds{1}_{\left\\{Q_{1}(t)-D_{1}(t)+S_{1}(t)\geq
Q_{2}(t)-D_{2}(t)+S_{2}(t)\right\\}}$
$\displaystyle\qquad\qquad\qquad\geq\left(\overline{N}(t)-\underline{Q}_{1}(t)-\left[N(t)-Q_{1}(t)\right]\right)\mathds{1}_{\left\\{Q_{1}(t)-D_{1}(t)+S_{1}(t)<Q_{2}(t)-D_{2}(t)+S_{2}(t)\right\\}}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\left(\overline{N}(t)-\underline{Q}_{2}(t)-\left[N(t)-Q_{2}(t)\right]\right)\mathds{1}_{\left\\{Q_{1}(t)-D_{1}(t)+S_{1}(t)\geq
Q_{2}(t)-D_{2}(t)+S_{2}(t)\right\\}}$ $\displaystyle\qquad\qquad\qquad\geq 0.$

$\square$
∎

Process II: We now consider a pair of coupled processes
$\overline{Q}_{1}(\cdot)$ and $\overline{Q}_{2}(\cdot)$, where qubits are
never matched and so they only depart when they abandon. In particular, these
processes are independent GI/M/$\infty$ queues. The coupling with the original
processes is done in a way so that these new ones have the same initial
conditions, i.e., with $\overline{Q}_{1}(0)=Q_{1}(0)$ and
$\overline{Q}_{2}(0)=Q_{2}(0)$, and so that they have the same arrival
processes $S_{1}(\cdot)$ and $S_{2}(\cdot)$, and the same abandonment
primitives $Z_{\ell}^{(i)}(\cdot)$. These new processes are defined
recursively as

$\displaystyle\overline{Q}_{1}(t+1)$
$\displaystyle=\overline{Q}_{1}(t)-\overline{D}_{1}(t)+S_{1}(t)$
$\displaystyle\overline{Q}_{2}(t+1)$
$\displaystyle=\overline{Q}_{2}(t)-\overline{D}_{2}(t)+S_{2}(t),$

where

$\overline{D}_{i}(t)=\sum\limits_{\ell=1}^{\overline{Q}_{i}(t)}Z^{(i)}_{\ell}(t).$

######  Lemma 6.

We have $\overline{Q}_{i}(t)\geq Q_{i}(t)$ and
$\overline{Q}_{i}(t)\geq\underline{Q}_{i}(t)$, for all $t\geq 0$, for all $i$.

###### Proof.

Proof: Suppose that the inequalities hold at time $t$. Then

$\displaystyle\overline{Q}_{i}(t+1)-Q_{i}(t+1)$
$\displaystyle=\left[\overline{Q}_{i}(t)-\overline{D}_{i}(t)\right]-\big{[}Q_{i}(t)-D_{i}(t)\big{]}+M(t)$
$\displaystyle\geq\left[\overline{Q}_{i}(t)-Q_{i}(t)\right]-\left[\sum\limits_{\ell=1}^{Q_{i}(t)}Z^{(i)}_{\ell}(t)-\sum\limits_{\ell=1}^{\overline{Q}_{i}(t)}Z^{(i)}_{\ell}(t)\right]$
$\displaystyle\geq 0.$

Moreover,

$\displaystyle\overline{Q}_{i}(t+1)-\underline{Q}_{i}(t+1)$
$\displaystyle=\left[\overline{Q}_{i}(t)-\overline{D}_{i}(t)\right]-\left[\underline{Q}_{i}(t)-\underline{D}_{i}(t)\right]+\overline{\overline{M}}(t)$
$\displaystyle\geq\left[\overline{Q}_{i}(t)-\underline{Q}_{i}(t)\right]-\left[\sum\limits_{\ell=1}^{\underline{Q}_{i}(t)}Z^{(i)}_{\ell}(t)-\sum\limits_{\ell=1}^{\overline{Q}_{i}(t)}Z^{(i)}_{\ell}(t)\right]$
$\displaystyle\geq 0.$

$\square$
∎

Lyapunov-Drift: It follows from the previous two lemmas that the positive
recurrence of $\big{(}\overline{N}(\cdot),\underline{\bf
Q}(\cdot),\overline{\bf Q}(\cdot)\big{)}$ implies the positive recurrence of
$\big{(}N(\cdot),{\bf Q}(\cdot)\big{)}$. To establish the positive recurrence
of this new process, we define the Lyapunov function

$L\left(\overline{n},\underline{\bf q},\overline{\bf
q}\right)=\overline{n}+\overline{q}_{1}+\overline{q}_{2}.$

######  Lemma 7.

There exists constants $K,T,\delta>0$ such that, if

$L\left(\overline{N}(t),\underline{\bf Q}(t),\overline{\bf Q}(t)\right)>3KT.$

then

$\mathbb{E}\left[L\left(\overline{N}(t+T),\underline{\bf Q}(t+T),\overline{\bf
Q}(t+T)\right)-L\left(\overline{N}(t),\underline{\bf Q}(t),\overline{\bf
Q}(t)\right)\,\Big{|}\,\overline{N}(t),\underline{\bf Q}(t),\overline{\bf
Q}(t)\right]\leq-\delta T.$

###### Proof.

Proof: Since $\underline{\bf Q}(\cdot)$ behaves path-wise the same as a two-
sided queue with abandonments (which is ergodic and has throughput $C_{Y}$ in
steady-state), for every $\epsilon>0$ there exists a constant $T_{\epsilon}$
large enough such that

$\displaystyle\mathbb{E}\left[\left.\sum\limits_{k=0}^{T_{\epsilon}-1}\sum\limits_{\ell=1}^{\overline{\overline{M}}(t+k)}Y_{\ell}(t+k)\,\right|\,\overline{N}(t),\underline{\bf
Q}(t),\overline{\bf Q}(t)\right]$
$\displaystyle=p\mathbb{E}\left[\left.\sum\limits_{k=0}^{T_{\epsilon}-1}\overline{\overline{M}}(t+k)\,\right|\,\left(\underline{Q}_{1}(t),\underline{Q}_{2}(t)\right)\right]$
$\displaystyle\geq T_{\epsilon}\Big{(}pC_{Y}-\epsilon\Big{)}.$ (16)

Moreover, if $\overline{Q}_{1}(t)+\overline{Q}_{2}(t)\leq KT$, we have

$\displaystyle\sum\limits_{k=0}^{T-1}\sum\limits_{\ell=1}^{\overline{\overline{M}}(t+k)}Y_{\ell}(t+k)$
$\displaystyle\leq\sum\limits_{k=0}^{T-1}\overline{\overline{M}}(t+k)$
$\displaystyle=\sum\limits_{k=0}^{T-1}\min\left\\{\underline{Q}_{1}(t+k)-\underline{D}_{1}(t+k)+S_{1}(t+k),\,\,\underline{Q}_{2}(t+k)-\underline{D}_{2}(t+k)+S_{2}(t+k)\right\\}$
$\displaystyle\leq\sum\limits_{k=0}^{T-1}\min\left\\{\underline{Q}_{1}(t+k)+S_{1}(t+k),\,\,\underline{Q}_{2}(t+k)+S_{2}(t+k)\right\\}$
$\displaystyle\leq\underline{Q}_{1}(t)+\underline{Q}_{2}(t)+\sum\limits_{k=0}^{T-1}S_{1}(t+k)+S_{2}(t+k)$
$\displaystyle\leq\overline{Q}_{1}(t)+\overline{Q}_{2}(t)+\sum\limits_{k=0}^{T-1}S_{1}(t+k)+S_{2}(t+k)$
$\displaystyle\leq KT+\sum\limits_{k=0}^{T-1}S_{1}(t+k)+S_{2}(t+k),$

where the second to last inequality is due to Lemma 6. Therefore, for every
$\epsilon>0$ there exists a constant $K_{\epsilon}$ large enough such that

$\displaystyle\mathbb{E}\left[\left.\min\left\\{\sum\limits_{k=0}^{T-1}\sum\limits_{\ell=1}^{\overline{M}(t+k)}Y_{\ell}(t+k),\,\,2K_{\epsilon}T\right\\}\,\right|\,\overline{N}(t),\underline{\bf
Q}(t),\overline{\bf Q}(t)\right]$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\geq\mathbb{E}\left[\left.\sum\limits_{k=0}^{T-1}\sum\limits_{\ell=1}^{\overline{\overline{M}}(t+k)}Y_{\ell}(t+k)\,\right|\,\overline{N}(t),\underline{\bf
Q}(t),\overline{\bf Q}(t)\right]-T\epsilon.$ (17)

If $\overline{Q}_{1}(t)+\overline{Q}_{2}(t)\leq K_{\epsilon}T_{\epsilon}$ and
$\overline{N}(t)\geq 2K_{\epsilon}T_{\epsilon}$, for all $\epsilon$ small
enough, we have

$\displaystyle\mathbb{E}\left[\overline{N}(t+T_{\epsilon})-\overline{N}(t)\,\Big{|}\,\overline{N}(t),\underline{\bf
Q}(t),\overline{\bf Q}(t)\right]$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad=\sum\limits_{k=0}^{T_{\epsilon}-1}\mathbb{E}\left[A(t+k)-\sum\limits_{\ell=1}^{\overline{M}(t+k)}Y_{\ell}(t+k)\,\Big{|}\,\overline{N}(t),\underline{\bf
Q}(t),\overline{\bf Q}(t)\right]$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad=\lambda
T_{\epsilon}-\mathbb{E}\left[\left.\sum\limits_{k=0}^{T_{\epsilon}-1}\sum\limits_{\ell=1}^{\overline{M}(t+k)}Y_{\ell}(t+k)\,\right|\,\overline{N}(t),\underline{\bf
Q}(t),\overline{\bf Q}(t)\right]$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\leq\lambda
T_{\epsilon}-\mathbb{E}\left[\left.\min\left\\{\sum\limits_{k=0}^{T_{\epsilon}-1}\sum\limits_{\ell=1}^{\overline{M}(t+k)}Y_{\ell}(t+k),\overline{N}(t)\right\\}\,\right|\,\overline{N}(t),\underline{\bf
Q}(t),\overline{\bf Q}(t)\right]$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\overset{(a)}{=}\lambda
T_{\epsilon}-\mathbb{E}\left[\left.\min\left\\{\sum\limits_{k=0}^{T_{\epsilon}-1}\sum\limits_{\ell=1}^{\overline{\overline{M}}(t+k)}Y_{\ell}(t+k),\overline{N}(t)\right\\}\,\right|\,\overline{N}(t),\underline{\bf
Q}(t),\overline{\bf Q}(t)\right]$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\leq\lambda
T_{\epsilon}-\mathbb{E}\left[\left.\min\left\\{\sum\limits_{k=0}^{T_{\epsilon}-1}\sum\limits_{\ell=1}^{\overline{\overline{M}}(t+k)}Y_{\ell}(t+k),2K_{\epsilon}T_{\epsilon}\right\\}\,\right|\,\overline{N}(t),\underline{\bf
Q}(t),\overline{\bf Q}(t)\right]$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\overset{(b)}{\leq}\lambda
T_{\epsilon}-\mathbb{E}\left[\left.\sum\limits_{k=0}^{T_{\epsilon}-1}\sum\limits_{\ell=1}^{\overline{\overline{M}}(t+k)}Y_{\ell}(t+k)\,\right|\,\overline{N}(t),\underline{\bf
Q}(t),\overline{\bf Q}(t)\right]+T_{\epsilon}\epsilon$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\overset{(c)}{\leq}\lambda
T_{\epsilon}-T_{\epsilon}(pC_{Y}-\epsilon)+T_{\epsilon}\epsilon$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad=-(pC_{Y}-2\epsilon-\lambda)T_{\epsilon},$
(18)

where (a) is because, when

$\sum\limits_{k=0}^{T_{\epsilon}-1}\sum\limits_{\ell=1}^{\overline{M}(t+k)}Y_{\ell}(t+k)<\overline{N}(t),$

then the third term in the definition of $\overline{M}(\cdot)$ never is the
minimum, and thus its definition coincides with
$\overline{\overline{M}}(\cdot)$, (b) is due to Equation (17), and (c) is due
to Equation (16). Moreover, we always have

$\displaystyle\mathbb{E}\left[\overline{N}(t+T_{\epsilon})-\overline{N}(t)\,\Big{|}\,\overline{N}(t),\underline{\bf
Q}(t),\overline{\bf Q}(t)\right]$
$\displaystyle=\sum\limits_{k=0}^{T_{\epsilon}-1}\mathbb{E}\left[A(t+k)-\sum\limits_{\ell=1}^{\overline{M}(t+k)}Y_{\ell}(t+k)\,\Big{|}\,\overline{N}(t),\underline{\bf
Q}(t),\overline{\bf Q}(t)\right]$
$\displaystyle\leq\sum\limits_{k=0}^{T_{\epsilon}-1}\mathbb{E}\left[A(t+k)\,\Big{|}\,\overline{N}(t),\underline{\bf
Q}(t),\overline{\bf Q}(t)\right]$ $\displaystyle=\lambda T_{\epsilon}.$ (19)

On the other hand, since $\overline{Q}_{1}(\cdot)$ and
$\overline{Q}_{2}(\cdot)$ are independent GI/M/$\infty$ queues, we have

$\displaystyle\mathbb{E}\Big{[}\overline{Q}_{1}(t+T)+\overline{Q}_{2}(t+T)-\overline{Q}_{1}(t)-\overline{Q}_{2}(t)\,\Big{|}\,\overline{N}(t),\underline{\bf
Q}(t),\overline{\bf Q}(t)\Big{]}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad=\left(\overline{Q}_{1}(t)-\frac{\mu_{1}}{\gamma_{1}}\right)\left[(1-\gamma_{1})^{T}-1\right]+\left(\overline{Q}_{2}(t)-\frac{\mu_{2}}{\gamma_{2}}\right)\left[(1-\gamma_{2})^{T}-1\right]$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\leq\frac{\mu_{1}}{\gamma_{1}}+\frac{\mu_{2}}{\gamma_{2}}-\overline{Q}_{1}(t)\left[1-(1-\gamma_{1})^{T}\right]-\overline{Q}_{2}(t)\left[1-(1-\gamma_{2})^{T}\right]$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\leq\frac{\mu_{1}}{\gamma_{1}}+\frac{\mu_{2}}{\gamma_{2}}-\frac{\overline{Q}_{1}(t)+\overline{Q}_{2}(t)}{2},$
(20)

for all $T$ large enough.

Finally, let $\epsilon$ be small enough, and $T$ and $K$ be large enough so
that equations (18), (19), and (20) hold. If
$\overline{Q}_{1}(t)+\overline{Q}_{2}(t)\leq KT$ and $\overline{N}(t)\geq
2KT$, then equations (18) and (20) imply

$\displaystyle\mathbb{E}\left[L\left(\overline{N}(t+T),\underline{\bf
Q}(t+T),\overline{\bf Q}(t+T)\right)-L\left(\overline{N}(t),\underline{\bf
Q}(t),\overline{\bf Q}(t)\right)\,\Big{|}\,\overline{N}(t),\underline{\bf
Q}(t),\overline{\bf Q}(t)\right]$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\leq-(pC_{Y}-2\epsilon-\lambda)T+\frac{\mu_{1}}{\gamma_{1}}+\frac{\mu_{2}}{\gamma_{2}}-\frac{\overline{Q}_{1}(t)+\overline{Q}_{2}(t)}{2}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\leq-(pC_{Y}-2\epsilon-\lambda)T+\frac{\mu_{1}}{\gamma_{1}}+\frac{\mu_{2}}{\gamma_{2}},$

which is negative for all $T$ large enough and $\epsilon$ small enough.
Furthermore, if $\overline{Q}_{1}(t)+\overline{Q}_{2}(t)\geq KT$, equations
(19) and (20) imply

$\displaystyle\mathbb{E}\left[L\left(\overline{N}(t+T),\underline{\bf
Q}(t+T),\overline{\bf Q}(t+T)\right)-L\left(\overline{N}(t),\underline{\bf
Q}(t),\overline{\bf Q}(t)\right)\,\Big{|}\,\overline{N}(t),\underline{\bf
Q}(t),\overline{\bf Q}(t)\right]$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\leq\lambda
T+\frac{\mu_{1}}{\gamma_{1}}+\frac{\mu_{2}}{\gamma_{2}}-\frac{\overline{Q}_{1}(t)+\overline{Q}_{2}(t)}{2}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\leq\lambda
T+\frac{\mu_{1}}{\gamma_{1}}+\frac{\mu_{2}}{\gamma_{2}}-\frac{KT}{2},$

which is also negative for all $T$ large enough. $\square$
∎

Note that, since $\overline{Q}_{i}(t)\geq\underline{Q}_{i}(t)$ for all $t\geq
0$ (Lemma 6), there are finitely many states such that
$\overline{n}+\overline{q}_{1}+\overline{q}_{2}\leq 3KT$. Moreover, the $T$
time-step drift of $L$ is negative for all $T$ and $K$ large enough, and
affine in $T$, outside this finite set. Thus, the positive recurrence follows
from a multi-step version of the Foster-Lyapunov theorem [11, Theorem C.27].

###  C.2 Transience

Let us define the process $\underline{N}(\cdot)$, with
$\underline{N}(0)=N(0)$, and defined recursively as

$\underline{N}(t+1)=\underline{N}(t)+A(t)-\sum\limits_{\ell=1}^{\overline{\overline{M}}(t)}Y_{\ell}(t).$

This is equivalent to always attempting three-way matchings, even if the
requests queue is not positive. Therefore, the process $\underline{N}(\cdot)$
can become negative. It is easy to check that $N(t)\geq\underline{N}(t)$ for
all $t\geq 0$. We then have

$\displaystyle N(t)$ $\displaystyle\geq\underline{N}(t)$
$\displaystyle=N(0)+\sum\limits_{k=0}^{t-1}A_{1}(k)-\sum\limits_{k=0}^{t-1}\sum\limits_{\ell=1}^{\overline{\overline{M}}(k)}Y_{\ell}(k)$

Since $\lambda>pC_{Y}$, the right hand side diverges to $+\infty$ almost
surely as $t\to+\infty$, and thus so does $N(t)$. In particular, this means
that $N(\cdot)$ is transient. Finally, the throughput is shown to be $pC_{Y}$
in this case using the same argument as in the proof of Lemma 2.

##  Appendix D Proof of Proposition 1

We have

$\displaystyle Q_{1}(t+1)+Q_{3}(t+1)$
$\displaystyle=Q_{1}(t)+Q_{3}(t)-D_{1}(t)-D_{3}(t)+S_{1}(t)+S_{3}(t)-M_{1}(t)-M_{2}(t)$
$\displaystyle Q_{2}(t+1)$
$\displaystyle=Q_{2}(t)-D_{2}(t)+S_{2}(t)-M_{1}(t)-M_{2}(t),$

where

$\displaystyle M_{1}(t)$
$\displaystyle=\min\big{\\{}Q_{1}(t)-D_{1}(t)+S_{1}(t),\,\,Q_{2}(t)-D_{2}(t)+S_{2}(t)-X(t)M_{2}(t)\big{\\}}$
$\displaystyle M_{2}(t)$
$\displaystyle=\min\big{\\{}Q_{2}(t)-D_{2}(t)+S_{2}(t)-[1-X(t)]M_{1}(t),\,\,Q_{3}(t)-D_{3}(t)+S_{3}(t)\big{\\}}.$

If $X(t)=0$, we have

$\displaystyle M_{1}(t)$
$\displaystyle=\min\big{\\{}Q_{1}(t)-D_{1}(t)+S_{1}(t),\,\,Q_{2}(t)-D_{2}(t)+S_{2}(t)\big{\\}}$
$\displaystyle M_{2}(t)$
$\displaystyle=\min\big{\\{}Q_{2}(t)-D_{2}(t)+S_{2}(t)-M_{1}(t),\,\,Q_{3}(t)-D_{3}(t)+S_{3}(t)\big{\\}},$

and thus

$\displaystyle M_{1}(t)+M_{2}(t)$
$\displaystyle=\min\big{\\{}Q_{2}(t)-D_{2}(t)+S_{2}(t),\,\,Q_{3}(t)-D_{3}(t)+S_{3}(t)+M_{1}(t)\big{\\}}$
$\displaystyle\qquad=\min\Big{\\{}Q_{2}(t)-D_{2}(t)+S_{2}(t),\,\,Q_{3}(t)-D_{3}(t)+S_{3}(t)$
$\displaystyle\qquad\qquad\qquad\qquad\qquad+\min\big{\\{}Q_{1}(t)-D_{1}(t)+S_{1}(t),\,\,Q_{2}(t)-D_{2}(t)+S_{2}(t)\big{\\}}\Big{\\}}$
$\displaystyle\qquad=\min\big{\\{}Q_{2}(t)-D_{2}(t)+S_{2}(t),\,\,Q_{1}(t)+Q_{3}(t)-D_{1}(t)-D_{3}(t)+S_{1}(t)+S_{3}(t)\big{\\}}.$

The same holds if $X(t)=1$. Finally, since the departure rates of the first
and third queues are equal to $\gamma$, we have $D_{1}(t)\sim
Bin\big{(}Q_{1}(t),\gamma\big{)}$ and $D_{2}(t)\sim
Bin\big{(}Q_{2}(t),\gamma\big{)}$, and thus $D_{1}(t)+D_{2}(t)\sim
Bin\big{(}Q_{1}(t)+Q_{2}(t),\gamma\big{)}$.

##  Appendix E Proof of Theorem 4

Suppose that $n_{1}(0)>0$ and $n_{2}(0)>0$. Since
$\lambda_{1}+\lambda_{2}<C_{1,2}$, cases (a) and (b) in the drift imply that

$\frac{dn_{1}(t)}{dt}+\frac{dn_{2}(t)}{dt}=\lambda_{1}+\lambda_{2}-C_{1,2}<0.$

Thus, at least one of the coordinates hits zero at a time

$T_{1}\leq\frac{\|{\bf n}(0)\|_{1}}{C_{1,2}-\lambda_{1}-\lambda_{2}}.$

Note that, if both coordinates hit zero at the same time, they stay there
forever (case (d) in the drift). If only the $i$-th trajectory hits zero while
the other one is positive, then we must have $\lambda_{i}<\underline{C}_{i}$
(otherwise it would not had hit zero while the other one was positive).
Therefore, the $i$-th trajectory stays at zero forever.

At time $T_{1}$, we have

$\max\big{\\{}n_{1}(T_{1}),\,n_{2}(T_{1})\big{\\}}\leq\|{\bf
n}(0)\|_{\infty}+\max\left\\{\lambda_{1}-\underline{C}_{1},\,\lambda_{2}-\underline{C}_{2}\right\\}T_{1}.$

Moreover, when one of the coordinates is zero, we have

$\frac{dn_{1}(t)}{dt}+\frac{dn_{2}(t)}{dt}\leq\max\big{\\{}\lambda_{1}-C_{1}(\lambda_{2}),\,\lambda_{2}-C_{2}(\lambda_{1})\big{\\}}<0.$

Then, the second coordinate hits zero (and also stays there forever) after

$T_{2}\leq\frac{\|{\bf
n}(0)\|_{\infty}+\max\left\\{\lambda_{1}-\underline{C}_{1},\,\lambda_{2}-\underline{C}_{2}\right\\}T_{1}}{\min\big{\\{}C_{1}(\lambda_{2})-\lambda_{1},\,C_{2}(\lambda_{1})-\lambda_{2}\big{\\}}}.$

units of time after $T_{1}$. We conclude that $\|{\bf n}(t)\|_{1}=0$ for all
$t$ larger than

$\displaystyle T_{1}+T_{2}$ $\displaystyle\leq\frac{\|{\bf
n}(0)\|_{1}}{C_{1,2}-\lambda_{1}-\lambda_{2}}+\frac{\|{\bf
n}(0)\|_{\infty}+\max\left\\{\lambda_{1}-\underline{C}_{1},\,\lambda_{2}-\underline{C}_{2}\right\\}T_{1}}{\min\big{\\{}C_{1}(\lambda_{2})-\lambda_{1},\,C_{2}(\lambda_{1})-\lambda_{2}\big{\\}}}$
$\displaystyle\leq\|{\bf
n}(0)\|_{1}\left[\frac{1}{C_{1,2}-\lambda_{1}-\lambda_{2}}+\frac{1}{\min\big{\\{}C_{1}(\lambda_{2})-\lambda_{1},\,C_{2}(\lambda_{1})-\lambda_{2}\big{\\}}}\left(1+\frac{\max\left\\{\lambda_{1}-\underline{C}_{1},\,\lambda_{2}-\underline{C}_{2}\right\\}}{C_{1,2}-\lambda_{1}-\lambda_{2}}\right)\right].$

##  Appendix F Proof of Theorem 3

Without loss of generality, we assume that $T\in\mathbb{Z}_{+}$. Moreover, we
use a slight abuse of notation and assume that our stochastic processes are
càdlàg functions over the real line, piece-wise constant over all intervals
$[t,t+1)$.

###  F.1 Tightness of sample paths

First, using a simple comparison with appropriately coupled discrete-time
GI/M/$\infty$ queues (cf. Equation (13)), it follows that

$\mathbb{P}\left(\lim\limits_{k\to\infty}\left\|{\bf
Q}^{(k)}(\omega,t)\right\|_{1}=0,\,\,\forall\,t\in[0,T]\right)=1.$ (21)

We define the family of coupled processes $\left\\{\left({\bf
Q}^{[x]}(\cdot),{\bf N}^{[x]}(\cdot),X^{[x]}(\cdot),{\bf
M}^{[x]}(\cdot)\right):x\in\\{0,1,2,3\\}\right\\}$ such that they are
constructed using the same stochastic primitives as the original processes
${\bf Q}(\cdot)$, ${\bf N}(\cdot)$, $X(\cdot)$, and ${\bf M}(\cdot)$, except
the following modifications:

  * -

Case $x=0$: We have $N^{[0]}_{1}(t)=N^{[0]}_{2}(t)=\infty$ and $X^{[0]}(t)=0$
for all $t\geq 0$.

  * -

Case $x=1$: We have $N^{[1]}_{1}(t)=N^{[1]}_{2}(t)=\infty$ and $X^{[1]}(t)=1$
for all $t\geq 0$.

  * -

Case $x=2$: We have $N^{[2]}_{1}(t)=\infty$ for all $t\geq 0$.

  * -

Case $x=3$: We have $N^{[3]}_{2}(t)=\infty$ for all $t\geq 0$.

Cases $2$ and $3$ are only considered when $\lambda_{2}<\underline{C}_{2}$ and
$\lambda_{1}<\underline{C}_{1}$, respectively.

######  Lemma 8.

Fix $T>0$. There exists a measurable set $\mathcal{C}$ such that
$\mathbb{P}(\mathcal{C})=1$ and such that, for all $\omega\in\mathcal{C}$, we
have

$\displaystyle\lim\limits_{k\to\infty}\left\|Q^{(k)}(\omega,t)\right\|_{1}=0,\qquad\forall\,t\in[0,T],$
(22)
$\displaystyle\lim\limits_{k\to\infty}\sup\limits_{t\in[0,T]}\left|\frac{1}{k}\sum\limits_{s=1}^{\lfloor
kt\rfloor}A_{i}(\omega,s)-\lambda_{i}t\right|=0$ (23)
$\displaystyle\lim\limits_{k\to\infty}\sup\limits_{t\in[0,T]}\left|\frac{1}{k}\sum\limits_{s=1}^{\lfloor
kt\rfloor}S_{j}(\omega,s)-\mu_{j}t\right|=0,$ (24)

and, for any $0\leq t_{1}<t_{2}\leq T$, we have

$\displaystyle\lim\limits_{k\to\infty}\frac{1}{k}\sum\limits_{j=\lfloor
kt_{1}\rfloor+1}^{\lfloor
kt_{2}\rfloor}\sum\limits_{\ell=1}^{M^{[x]}_{1}(\omega,j)}Y_{\ell}^{(1)}(\omega,t)=(t_{2}-t_{1})\Big{(}\overline{C}_{1}\mathds{1}_{\\{x=0\\}}+C_{1}(\lambda_{2})\mathds{1}_{\left\\{x=2\right\\}}+\underline{C}_{1}\mathds{1}_{\\{x=1\\}}+\lambda_{1}\mathds{1}_{\\{x=3\\}}\Big{)}$
(25) $\displaystyle\lim\limits_{k\to\infty}\frac{1}{k}\sum\limits_{j=\lfloor
kt_{1}\rfloor+1}^{\lfloor
kt_{2}\rfloor}\sum\limits_{\ell=1}^{M^{[x]}_{2}(\omega,j)}Y_{\ell}^{(2)}(\omega,t)=(t_{2}-t_{1})\Big{(}\overline{C}_{2}\mathds{1}_{\\{x=1\\}}+C_{2}(\lambda_{1})\mathds{1}_{\left\\{x=3\right\\}}+\underline{C}_{2}\mathds{1}_{\\{x=0\\}}+\lambda_{2}\mathds{1}_{\\{x=2\\}}\Big{)},$
(26)

for all $x\in\\{0,1\\}$, and for $x=2$ with $\lambda_{2}<\underline{C}_{2}$
and $x=3$ with $\lambda_{1}<\underline{C}_{1}$.

###### Proof.

Proof: The first three equations hold in a set of probability one due to
Equation (21), and the Functional Strong Law of Large Numbers.

We have

$\displaystyle M^{[x]}_{1}(t)$
$\displaystyle=\min\left\\{Q^{[x]}_{1}(t)-\sum\limits_{\ell=1}^{Q^{[x]}_{1}(j)}Z_{\ell}^{(1)}(j)+S_{1}(t),\,\,Q^{[x]}_{2}(t)-\sum\limits_{\ell=1}^{Q^{[x]}_{2}(j)}Z_{\ell}^{(2)}(j)+S_{2}(t)-X^{[x]}(t)M^{[x]}_{2}(t)\right\\}$
$\displaystyle M^{[x]}_{2}(t)$
$\displaystyle=\min\left\\{Q^{[x]}_{2}(t)-\sum\limits_{\ell=1}^{Q^{[x]}_{2}(j)}Z_{\ell}^{(2)}(j)+S_{2}(t)-[1-X^{[x]}(t)]M^{[x]}_{1}(t),\,\,Q^{[x]}_{3}(t)-\sum\limits_{\ell=1}^{Q^{[x]}_{3}(j)}Z_{\ell}^{(3)}(j)+S_{3}(t)\right\\},$

where $Z_{\ell}^{(1)}(j)$, $Z_{\ell}^{(2)}(j)$, and $Z_{\ell}^{(3)}(j)$ are
i.i.d. Bernoulli random variables with probability $\gamma$. For
$x\in\\{1,2\\}$, since each of the coordinates of ${\bf Q}^{[x]}(\cdot)$ is
upper bounded by a GI/M/$\infty$ queue (Lemma 6), then the process
$\big{(}{\bf N}^{[x]}(\cdot),{\bf Q}^{[x]}(\cdot)\big{)}$ is ergodic. For
$x=2$ with $\lambda_{2}<\underline{C}_{2}$ and $x=3$ with
$\lambda_{1}<\underline{C}_{1}$, Lemma 3 implies that the process $\big{(}{\bf
N}^{[x]}(\cdot),{\bf Q}^{[x]}(\cdot)\big{)}$ is ergodic.

Fix $t_{1},t_{2}\in\mathbb{Q}\cap[0,T]$. Since $\big{(}{\bf
N}^{[x]}(\cdot),{\bf Q}^{[x]}(\cdot)\big{)}$ is ergodic, for all sample paths
in a set $\mathcal{C}_{\\{t_{1},t_{2}\\}}$ such that
$\mathbb{P}\big{(}\mathcal{C}_{\\{t_{1},t_{2}\\}}\big{)}=1$, equations (25)
and (26) hold for times $t_{1}$ and $t_{2}$. Thus, equations (25) and (26)
hold for all $t_{1},t_{2}\in\mathbb{Q}\cap[0,T]$ for all sample paths in the
set

$\mathcal{C}_{\mathbb{Q}\cap[0,T]}=\bigcap\limits_{t_{1},t_{2}\in\mathbb{Q}\cap[0,T]}\mathcal{C}_{\\{t_{1},t_{2}\\}},$

which also has probability one because it is a countable intersection.
Finally, it is easily checked that these equations (25) and (26) also hold for
all $t_{1},t_{2}\in[0,T]$ over the same set by the monotonicity of the sum and
the continuity of the limit. $\square$
∎

Let us fix an arbitrary ${\bf x^{0}}\in\mathbb{R}_{+}^{2}$, sequences
$B_{k}\downarrow 0$ and $\beta_{k}\downarrow 0$, and a constant $L>0$. For
$k\geq 1$, we define the following subsets of $D^{2}[0,T]$. Let

$E_{k}(B_{k},\beta_{k})=\Big{\\{}{\bf x}\in D^{2}[0,T]:\,\left\|{\bf
x}(0)-{\bf x^{0}}\right\|_{1}\leq B_{k},\text{ and }\|{\bf x}(a)-{\bf
x}(b)\|_{1}\leq L|a-b|+\beta_{k},\,\,\forall\,a,b\in[0,T]\Big{\\}}$

be the set of all càdlàg, piece-wise constant functions that are
$\beta_{k}$-approximate $L$-Lipschitz continuous, and that their initial
conditions are at most $B_{k}$ away from ${\bf x^{0}}$. We also define

$E_{c}=\Big{\\{}{\bf x}\in D^{2}[0,T]:\,{\bf x}(0)={\bf x^{0}},\,\,\|{\bf
x}(a)-{\bf x}(b)\|_{1}\leq L|a-b|,\,\,\forall\,a,b\in[0,T]\Big{\\}},$

which is the set of $L$-Lipschitz continuous functions with initial condition
${\bf x^{0}}$, which is known to be sequentially compact by the Arzelà-Ascoli
theorem.

######  Lemma 9.

Fix $T>0$, $\omega\in\mathcal{C}$, and some ${\bf
n^{0}}\in\mathbb{R}_{+}^{2}$. Suppose that

$\left\|{\bf N}^{(k)}(\omega,0)-{\bf n^{0}}\right\|_{1}\leq B_{k},$

for some sequence $B_{k}\downarrow 0$. Then, there exists a sequence
$\beta_{k}\downarrow 0$ such that

${\bf N}^{(k)}(\omega,\cdot)\in
E_{k}\left(B_{k},\beta_{k}\right),\quad\forall\ k\geq 1,$

with the constant $L$ in the definition of $E_{k}$ equal to
$\lambda_{1}+\lambda_{2}+\mu_{1}+2\mu_{2}+\mu_{3}$.

###### Proof.

Proof: By construction, and the triangular inequality, we have

$\displaystyle\left|N^{(k)}_{1}(\omega,a)-N^{(k)}_{1}(\omega,b)\right|$
$\displaystyle\leq\frac{1}{k}\left|\sum\limits_{s=\lfloor
kb\rfloor+1}^{\lfloor
ka\rfloor}A_{1}(s)\right|+\frac{1}{k}\left|\sum\limits_{s=\lfloor
kb\rfloor+1}^{\lfloor ka\rfloor}S_{1}(s)+S_{2}(s)\right|$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad+\frac{1}{k}\Big{|}Q_{1}(ka)-Q_{1}(kb)+Q_{2}(ka)-Q_{2}(kb)\Big{|}$

Since $\omega\in\mathcal{C}$, Lemma 8 implies that there exists sequences
$\beta_{k}^{1}\downarrow 0$, $\beta_{k}^{2}\downarrow 0$, and
$\beta_{k}^{3}\downarrow 0$ (which depend on $\omega$) such that for all
$k\geq 1$,

$\frac{1}{k}\left|\sum\limits_{s=\lfloor kb\rfloor+1}^{\lfloor
ka\rfloor}A_{1}(s)\right|\leq\lambda_{1}|a-b|+\beta_{k}^{1},$
$\frac{1}{k}\left|\sum\limits_{s=\lfloor kb\rfloor+1}^{\lfloor
ka\rfloor}S_{1}(s)+S_{2}(s)\right|\leq(\mu_{1}+\mu_{2})|a-b|+\beta_{k}^{2},$

and

$\frac{1}{k}\Big{|}Q_{1}(ka)-Q_{1}(kb)+Q_{2}(ka)-Q_{2}(kb)\Big{|}\leq\beta_{k}^{3},$

which imply

$\left|N^{(k)}_{1}(\omega,a)-N^{(k)}_{1}(\omega,b)\right|\leq(\lambda_{1}+\mu_{1}+\mu_{2})|a-b|+\left(\beta_{k}^{1}+\beta_{k}^{2}+\beta_{k}^{3}\right).$

Analogously we can show that

$\left|N^{(k)}_{2}(\omega,a)-N^{(k)}_{2}(\omega,b)\right|\leq(\lambda_{2}+\mu_{2}+\mu_{3})|a-b|+\left(\beta_{k}^{4}+\beta_{k}^{5}+\beta_{k}^{6}\right).$

The proof is completed by setting
$\beta_{k}=\beta_{k}^{1}+\beta_{k}^{2}+\beta_{k}^{3}+\beta_{k}^{4}+\beta_{k}^{5}+\beta_{k}^{6}$,
and $L=\lambda_{1}+\lambda_{2}+\mu_{1}+2\mu_{2}+\mu_{3}$. $\square$
∎

We are now ready to prove the existence of convergent subsequences of the
process of interest.

######  Proposition 2.

Fix $T>0$, $\omega\in\mathcal{C}$, and some ${\bf
n^{0}}\in\mathbb{R}_{+}^{2}$. Suppose (as in Lemma 9) that

$\left\|{\bf N}^{(k)}(\omega,0)-{\bf n^{0}}\right\|_{1}\leq B_{k},$

where $B_{k}\downarrow 0$. Then, every subsequence of $\left\\{{\bf
N}^{(k)}(\omega,\cdot)\right\\}_{k=1}^{\infty}$ contains a further subsequence
$\left\\{{\bf N}^{(k_{\ell})}(\omega,\cdot)\right\\}_{\ell=1}^{\infty}$ that
converges to a coordinate-wise Lipschitz continuous function ${\bf n}(\cdot)$
with ${\bf n}(0)={\bf n^{0}}$ and

$|n_{i}(a)-n_{i}(b)|\leq L|a-b|,\quad\quad\forall\,a,b\in[0,T],$

where $L$ does not depend on $T$, $\omega$, nor on ${\bf n}(\cdot)$.

###### Proof.

Proof: As in Lemma 9, let
$L=\lambda_{1}+\lambda_{2}+\mu_{1}+2\mu_{2}+\mu_{3}$. Note that, if the
trajectories were $L$-Lipschitz continuous, then the Arzelà-Ascoli would
immediately give us this result. However, since trajectories are only
approximately $L$-Lipschitz continuous (Lemma 9), a more involved argument is
required. This argument was introduced in [6] and further developed in [36]
(and it is therefore omitted), and involves doing a continuous linear
interpolation of the piece-wise constant to prove the “closeness” of
$E_{k}\big{(}B_{k},\beta_{k}\big{)}$ to the sequentially compact set $E_{c}$.
$\square$
∎

###  F.2 Derivatives of the limit points

In this subsection we will show that the limit points of the sequence of
sample paths (which we showed that they are Lipschitz continuous in
Proposition 2) have the same derivatives as a fluid solution (cf. Definition
1) for all regular points.

######  Proposition 3.

Fix $\omega\in\mathcal{C}$ and $T>0$. Let ${\bf n}(\cdot)$ be a limit point of
some subsequence of $\left\\{{\bf
N}^{(k)}(\omega,\cdot)\right\\}_{k=1}^{\infty}$. Then, ${\bf n}(\cdot)$ has
the same derivatives as a fluid solution (cf. Definition 1) for all regular
points.

###### Proof.

Proof: We fix some $\omega\in\mathcal{C}$ and for the rest of this proof we
suppress the dependence on $\omega$ in our notation. Let $\left\\{{\bf
N}^{(k_{\ell})}(\cdot)\right\\}_{\ell=1}^{\infty}$ be a subsequence such that

$\lim\limits_{\ell\to\infty}\sup\limits_{0\leq t\leq T}\left\|{\bf
N}^{(k_{\ell})}(t)-{\bf n}(t)\right\|_{1}=0,\qquad a.s.$

After possibly restricting, if necessary, to a further subsequence, we can
define Lipschitz continuous functions $a_{i}(\cdot)$ and $r_{i}(\cdot)$ as the
limits of the subsequences of cumulative arrivals and cumulative matching
processes $\big{\\{}A_{i}^{(k_{\ell})}(\cdot)\big{\\}}_{\ell=1}^{\infty}$ and
$\big{\\{}R_{i}^{(k_{\ell})}(\cdot)\big{\\}}_{\ell=1}^{\infty}$ respectively,
where

$R_{i}^{(k_{\ell})}(t)=\frac{1}{k_{\ell}}\sum\limits_{j=1}^{\lfloor
k_{\ell}t\rfloor}\sum\limits_{\ell=1}^{M_{1}(j)}Y_{\ell}^{(1)}(j).$

Because of the relation
$N_{i}^{(k)}(t)=N_{i}^{(k)}(0)+A_{i}^{(k)}(t)-R_{i}^{(k)}(t)$, it is enough to
prove the following relations, for almost all $t$:

$\displaystyle\frac{da_{i}(t)}{dt}=$
$\displaystyle\lambda_{i}\qquad\text{and}\qquad\frac{dr_{i}(t)}{dt}=R_{i}(n(t)).$

We will provide a proof only for the second one, as the first one is immediate
by the Functional Strong Law of Large Numbers.

Let us fix some time $t\in[0,T)$, which is a regular time for both
$r_{1}(\cdot)$ and $r_{2}(\cdot)$. Let $\epsilon>0$ be small enough so that
$t+\epsilon\leq T$ and so that it also satisfies a condition to be introduced
later. By construction, we have

$\displaystyle R^{(k_{\ell})}_{1}(t+\epsilon)-R^{(k_{\ell})}_{1}(t)$
$\displaystyle=\frac{1}{k_{\ell}}\sum\limits_{j=\lfloor
k_{\ell}t\rfloor+1}^{\lfloor
k_{\ell}(t+\epsilon)\rfloor}\sum\limits_{\ell=1}^{M_{1}(j)}Y_{\ell}^{(1)}(j),$
$\displaystyle R^{(k_{\ell})}_{2}(t+\epsilon)-R^{(k_{\ell})}_{2}(t)$
$\displaystyle=\frac{1}{k_{\ell}}\sum\limits_{j=\lfloor
k_{\ell}t\rfloor+1}^{\lfloor
k_{\ell}(t+\epsilon)\rfloor}\sum\limits_{\ell=1}^{M_{2}(j)}Y_{\ell}^{(2)}(j),$

where

$\displaystyle M_{1}(j)$
$\displaystyle=\min\Bigg{\\{}Q_{2}(j)-D_{2}(j)+S_{2}(j)-X(j)M_{2}(j),\,\,Q_{1}(j)-D_{1}(j)+S_{1}(j),$
$\displaystyle\qquad\qquad\qquad\quad\qquad\qquad\qquad\qquad\qquad\quad\left.\min\left\\{m_{1}:\sum\limits_{\ell=1}^{m_{1}}Y_{\ell}^{(1)}(j)\geq
N_{1}(j)+A_{1}(j)\right\\}\right\\}$ (27) $\displaystyle M_{2}(j)$
$\displaystyle=\min\Bigg{\\{}Q_{3}(j)-D_{3}(j)+S_{3}(j)-[1-X(j)]M_{1}(j),\,\,Q_{2}(j)-D_{2}(j)+S_{2}(j),$
$\displaystyle\qquad\qquad\qquad\quad\qquad\qquad\qquad\qquad\qquad\quad\left.\min\left\\{m_{2}:\sum\limits_{\ell=1}^{m_{2}}Y_{\ell}^{(2)}(j)\geq
N_{2}(j)+A_{2}(j)\right\\}\right\\}.$ (28)

By Lemma 9, there exists a sequence $\beta_{k_{\ell}}\downarrow 0$ and a
constant $L$ such that

$N_{i}^{(k_{\ell})}(u)\in\big{[}n_{i}(t)-\left(\epsilon
L+\beta_{k_{\ell}}\right),\ n_{i}(t)+\left(\epsilon
L+\beta_{k_{\ell}}\right)\big{)},\quad\forall\,u\in[t,t+\epsilon]$

Then, for all sufficiently large $\ell$, we have

$N_{i}^{(k_{\ell})}(u)\in\big{[}n_{i}(t)-2\epsilon L,\ n_{i}(t)+2\epsilon
L)\big{)},\quad\forall\,u\in[t,t+\epsilon]$ (29)

and

$N_{i}^{(k_{\ell})}(u)+\frac{1}{k_{\ell}}A_{i}(\lfloor
u\rfloor)\in\big{[}n_{i}(t)-2\epsilon L,\ n_{i}(t)+2\epsilon
L)\big{)},\quad\forall\,u\in[t,t+\epsilon].$

Case (a): $n_{1}(t)>n_{2}(t)>0$

For $\epsilon$ small enough, we have $n_{1}(t)-2\epsilon L>n_{2}(t)+2\epsilon