text:
\section{Proofs}

\subsection{Proof of Lemma~\ref{lem:invertible}}

\begin{qlemma}{\ref{lem:invertible}}
 \stmtleminvertible
\end{qlemma}

\begin{proof}
By the traffic equation $\boldsymbol{\lambda} = \boldsymbol{\alpha} + \boldsymbol{\lambda} A$ we have $\boldsymbol{\lambda} A \le \boldsymbol{\lambda}$, with $\boldsymbol{\lambda} > \boldsymbol{0}$.
By~\cite[Theorem~2.1.11]{book:BermanP} this implies that the spectral radius of~$A$ is at most~$1$
 (where the spectral radius is the largest absolute value of the eigenvalues of~$A$).

To show the statement of the lemma, it now suffices to show that $I-A$ is invertible.
Consider the (monotone) function $\boldsymbol{f} : \mathbb{R}_{\ge 0}^n \to \mathbb{R}_{\ge 0}^n$ with $\boldsymbol{f}(\boldsymbol{x}) := \boldsymbol{\alpha} + \boldsymbol{x} A$.
By the traffic equation, $\boldsymbol{\lambda}$ is a fixed point of~$\boldsymbol{f}$.
Assume for a contradiction that $I-A$ is singular, i.e., there is $\boldsymbol{y} \in \mathbb{R}^n$ with $\boldsymbol{y} \ne \boldsymbol{0}$ and $\boldsymbol{y} A = \boldsymbol{y}$.
Then $\boldsymbol{\lambda} + r \boldsymbol{y}$ is a fixed point for all $r \in \mathbb{R}$.
Choose $r$ so that $\boldsymbol{z} := \boldsymbol{\lambda} + r \boldsymbol{y} \in \mathbb{R}_{\ge 0}^n$, but $\boldsymbol{z}_i = 0$ for some $i \in \{1, \ldots, n\}$.
By the monotonicity of~$\boldsymbol{f}$, all points $\boldsymbol{u} \in \{ \boldsymbol{0}, \boldsymbol{f}(\boldsymbol{0}), \boldsymbol{f}(\boldsymbol{f}(\boldsymbol{0})), \ldots\}$
 satisfy $\boldsymbol{0} \le \boldsymbol{u} \le \boldsymbol{z} = \boldsymbol{f}(\boldsymbol{z})$.
It follows that $\boldsymbol{u}_i = 0$ for all~$\boldsymbol{u}$.
This contradicts the fact that queue~$i$ is ``reachable''
 (recall that ``queue~$i$ is reachable'' means there is $j \in \mathbb{N}$ with $(\boldsymbol{\alpha} A^j)_i \ne 0$).
\end{proof}

\subsection{Proof of Proposition~\ref{prop:traffic-erg}}
In this section we complete the proof of

\begin{qproposition}{\ref{prop:traffic-erg}}
 \stmtproptrafficerg
\end{qproposition}

Recall from Lemma~\ref{lem:invertible} that the matrix series $A^* := \sum_{i=0}^\infty A^i$ converges (``exists'') in~$\mathbb{R}_{\ge 0}^{n \times n}$ and equals $(I-A)^{-1}$.
Observe that for any vector $\boldsymbol{v}^T = A^* \boldsymbol{w}^T$ with $\boldsymbol{w} \in \mathbb{R}^n$, we have $\boldsymbol{v}^T = A \boldsymbol{v}^T + \boldsymbol{w}^T$.
We prove Lemma~\ref{lem:good-max}:

\begin{qlemma}{\ref{lem:good-max}}
 If $\boldsymbol{0} \ne \boldsymbol{x} \in \mathbb{R}_{\ge 0}^n$ and $\boldsymbol{x}_i = 0$, then $\boldsymbol{x} \qsT{i} < V(\boldsymbol{x})$.
\end{qlemma}
\begin{proof}
For the proof we use the following notation:
For a matrix~$M$ we denote by $M_{i..j}$ the matrix obtained by restricting~$M$ to its rows indexed by $i, \ldots, j$.
Similarly, we denote by $M_{i..j,k..\ell}$ the matrix~$M$ restricted to the corresponding rows and columns.

Let $Q \in \mathbb{R}_{\ge 0}^{n \times n}$ denote the matrix whose columns are $\qsT{1}, \ldots, \qsT{n}$.
Note that $\boldsymbol{1} Q = \boldsymbol{1}$.
We have $Q = A^* D$ where $D \in \mathbb{R}_{\ge 0}^{n \times n}$ is the diagonal matrix with $1/D_{ii} = ( \boldsymbol{1} A^* )_i$.
Further, we define the matrix $P \in \{-1,0,1\}^{n \times (n-1)}$ with
 \[
  P := \begin{pmatrix}
        -1 \ & \ -1 \ & \ -1 \ & \cdots & \ -1 \ & \ -1 \\
        1  &  0 &  0 & \cdots & 0  &  0 \\
        0  &  1 &  0 & \cdots & 0  &  0 \\
           &    &    & \ddots  \\
        0  & 0  &  0 & \cdots & 0  & 1
       \end{pmatrix} \;.
 \]

W.l.o.g.\ let $\boldsymbol{x}_1 = 0$.
With the notation above and writing $\bar\boldsymbol{x} := (x_2, \ldots, x_n) \in \mathbb{R}_{\ge 0}^{n-1}$,
 the lemma states that
\begin{equation} \label{eq:max-inequality}
 \text{there is no } \bar\boldsymbol{x} \in \mathbb{R}_{\ge 0}^{n-1} \text{ with } \bar\boldsymbol{x} \ne \boldsymbol{0} \text{ and } \bar\boldsymbol{x} Q_{2..n} P \le \boldsymbol{0} \,.
\end{equation}
We use Farkas' lemma for the proof:
\begin{lemma}[Farkas' lemma]
 Let $M \in \mathbb{R}^{m \times n}$ and $\boldsymbol{b} \in \mathbb{R}^m$.
 Then exactly one of the following is true:
 \begin{itemize}
   \item[1.]
    There exists $\boldsymbol{x} \in \mathbb{R}^m$ with $\boldsymbol{x} M \le \boldsymbol{0}$ and $\boldsymbol{x} \boldsymbol{b}^T > 0$.
   \item[2.]
    There exists $\boldsymbol{y} \in \mathbb{R}^n$ with $M \boldsymbol{y}^T = \boldsymbol{b}^T$ and $\boldsymbol{y} \ge \boldsymbol{0}$.
 \end{itemize}
\end{lemma}
Using Farkas' lemma we prove~\eqref{eq:max-inequality} by exhibiting $\boldsymbol{b} > \boldsymbol{0}$ and $\boldsymbol{y} \ge \boldsymbol{0}$ such that $Q_{2..n} P \boldsymbol{y}^T = \boldsymbol{b}^T$.
We choose
\[
 \boldsymbol{b}^T := (A_{2..n,2..n})^* \boldsymbol{1}^T \ge \boldsymbol{1}^T > \boldsymbol{0}^T \,.
\]
We have $\boldsymbol{1} Q = \boldsymbol{1}$, which implies $\boldsymbol{1} Q^{-1} = \boldsymbol{1} Q Q^{-1} = \boldsymbol{1}$,
 hence $P (Q^{-1})_{2..n} = Q^{-1} - E$ where $E \in \{0,1\}^{n \times n}$ denotes the matrix with $\boldsymbol{1}$ in the first row and $\boldsymbol{0}$ in the other rows.
It follows
\begin{equation} \label{eq:PQP=QP}
 P (Q^{-1})_{2..n} P = Q^{-1} P \,.
\end{equation}
Setting
 \[
  \boldsymbol{y}^T := (Q^{-1})_{2..n} P \boldsymbol{b}^T
 \]
we therefore have
 \[
  Q_{2..n} P \boldsymbol{y}^T = Q_{2..n} P (Q^{-1})_{2..n} P \boldsymbol{b}^T \mathop{=}^{\eqref{eq:PQP=QP}} Q_{2..n}  Q^{-1} P \boldsymbol{b}^T = P_{2..n} \boldsymbol{b}^T = \boldsymbol{b}^T \,,
 \]
 as desired.
It remains to prove $\boldsymbol{y} \ge \boldsymbol{0}$.
As $Q = A^* D$, we have $Q^{-1} = D^{-1} (I-A)$ with $D^{-1}$ nonnegative, so it suffices to prove that $(I-A)_{2..n} P \boldsymbol{b}^T \ge \boldsymbol{0}^T$.
Indeed we have
 \[
  (I-A)_{2..n} P \boldsymbol{b}^T \ = \ (I - A_{2..n} P) \boldsymbol{b}^T \ = \ \boldsymbol{b}^T - A_{2..n} P \boldsymbol{b}^T \ \ge \ \boldsymbol{b}^T - A_{2..n,2..n} \boldsymbol{b}^T \ = \ \boldsymbol{1}^T \,,
 \]
 where the inequality holds as $\boldsymbol{b}^T$ and the first column of~$A_{2..n}$ are nonnegative and the first row of~$P$ is negative.

\end{proof}

\noindent Recall the following lemma:

\begin{qlemma}{\ref{lem:piecewise-neg-drift}}
 \stmtlempiecewisenegdrift
\end{qlemma}

\medskip
Proposition~\ref{prop:traffic-erg} follows from Lemma~\ref{lem:piecewise-neg-drift}
 using exactly the reasoning from theorem~1 and lemma~5 of~\cite{DownMeyn97piecewise}.

\section{Conclusions} \label{sec:conclusions}
We have suggested and studied controlled branching networks,
 a queueing model which extends Jackson networks
  by nondeterministic and branching features as required to model parallel systems.
Although much of the classical theory (such as product-form stationary distributions) no longer holds for controlled branching networks,
 we have shown that the traffic equations can be generalized.
This enabled us to construct a suitable Lyapunov function
 which we have used to establish strong stability properties.
We have shown for the controlled model that static randomized schedulers are sufficient to achieve those strong stability properties.
Linear programming can be used to efficiently compute such a scheduler, which at the same time minimizes the maximal queue utilization.

Future work should include the investigation of more performance measures, e.g., the long-time average queue size.
Can non-static schedulers help to minimize it?
\subsection{Controlled branching networks} \label{sec:contr}
In this subsection we generalize the traffic equations~(\ref{eq:traffic}) to deal with an arbitrary controlled branching network $\mathcal{N}$.
To obtain a distribution on actions for a static randomized ergodic scheduler,
we assign variables to actions instead of queues, i.e., for every action $\xi$ of the network we introduce a variable $\lambda_{\xi}$ capturing the {\em rate of firing the action $\xi$}.
Denote by $\bar{\Sigma}$ the set $\bigcup_{i=1}^n \Sigma_i$.
Given $\zeta\in \bar{\Sigma}$ and $j\in \{1,\ldots,n\}$, we denote by $A_{\zeta j}$ the average number of jobs added to the queue $j$ when the action $\zeta$ fires,
 i.e., for $\zeta\in \Sigma_i$ we set
\[
A_{\zeta j} := \sum_{\boldsymbol{r}\in R_i(\zeta)} \mathit{Prob}_i(\zeta)(\boldsymbol{r}) \cdot \boldsymbol{r}_j\,.
\]
 %
We generalize~\eqref{eq:traffic} to the \emph{traffic LP} presented in Figure~\ref{fig:LP-delta},
 where the variable~$\delta$ is intended to bound, for all~$j$, the probability that queue~$j$ is busy.
\begin{figure}[ht]
\begin{center}
\[
\min\, \delta \ \text{subject to}
\]
\begin{align*}
\sum_{\xi\in \Sigma_j} \lambda_{\xi} \quad & = \quad \boldsymbol{\alpha}_j+\sum_{i=1}^n \sum_{\zeta\in \Sigma_i} \lambda_{\zeta}\cdot A_{\zeta j} & j\in \{1,\ldots,n\} \\
\delta \quad & \geq \quad \frac{\sum_{\xi\in \Sigma_j} \lambda_{\xi}}{\mu_j} & \quad  \quad j\in \{1,\ldots,n\} \\
\lambda_{\xi} \quad & \geq \quad 0 & \xi\in \bar{\Sigma}
\end{align*}

\end{center}
\caption{The traffic LP.}
\label{fig:LP-delta}
\end{figure}

We prove the following
\begin{proposition}\label{prop:traffic-LP}\
\begin{enumerate}
\item
    If there exists an arbitrary ergodic scheduler for~$\mathcal{N}$, then the traffic LP can be solved with $\min \delta<1$.
   \item If the traffic LP is solved with $\min \delta<1$, one can compute in polynomial time a static randomized ergodic scheduler $\Theta_s$ for~$\mathcal{N}$. Moreover, denoting by $\rho_i$ the {\em utilization} $\lim_{t \to \infty} \Pr(\boldsymbol{x}_i(t) \ne 0)$
   of the queue $i$, the scheduler $\Theta_s$ minimizes
     $\max_i \rho_i$ among all memoryless ergodic schedulers.
\end{enumerate}
Hence one can decide in polynomial time whether an arbitrary ergodic scheduler exists;
 if yes, one can compute in polynomial time a static randomized ergodic scheduler.
\end{proposition}
Let us first concentrate on part~1. Let $\Theta$ be an ergodic scheduler.
Roughly speaking, we prove that a feasible solution of the traffic LP can be constructed using (limit) frequencies of firing individual actions in $\mathcal{N}_{\Theta}$.
Formally, given a run $\omega$ of $\mathcal{N}_{\Theta}$, $t\in \mathbb{R}_{\ge 0}$ and $\xi\in \bar{\Sigma}$, we denote by $O^{\leq t}_{\xi}(\omega)$ the number of times the action $\xi$ is fired up to time $t$ on $\omega$.
For memoryless $\Theta$ we have the following result.
\newcommand{\stmtpropergtraffic}{
Assume that $\Theta$ is a {\em memoryless} ergodic scheduler.
For every $\xi\in \bar{\Sigma}$ there is a constant $O_{\xi}$ such that for almost all runs $\omega$ of $\mathcal{N}_{\Theta}$ the limit \[\lim_{t\rightarrow{} \infty} \frac{O^{\leq t}_{\xi}(\omega)}{t}\]
exists and is equal to $O_{\xi}$. There is $\bar{\delta}<1$ such that $\left(\bar{\delta},O_{\xi}\mid \xi\in \bar{\Sigma}\right)$ solves the traffic LP.
Moreover, for every $i\in \{1,\ldots,n\}$ the utilization $\rho_i$ of the queue $i$ in $\mathcal{N}_{\Theta}$ is equal to $\frac{\sum_{\xi\in \Sigma_i} O_{\xi}}{\mu_i}$.
}
\begin{lemma}\label{prop:erg-traffic}
\stmtpropergtraffic
\end{lemma}
We prove Lemma~\ref{prop:erg-traffic} \ifthenelse{\equal{\techRep}{true}}{in Appendix~\ref{app:contr}}{in~\cite{BK12:stacs-report}}.
If there exists an arbitrary (i.e.\ possibly history-dependent) ergodic scheduler,
 then by~Theorem~7.3.8 of \cite{book:Puterman} there exists also a memoryless (and deterministic) ergodic scheduler.%
\footnote{To be formally correct, we apply Theorem~7.3.8 of \cite{book:Puterman} to the {\em embedded} discrete time MDP and obtain a scheduler which returns to the state $\boldsymbol{0}$ in finitely many steps (on average). As there are only finitely many rates in our system, this means that also the expected return time to $\boldsymbol{0}$ is finite.}
This fact, combined with Lemma~\ref{prop:erg-traffic}, implies part~1.\ of Proposition~\ref{prop:traffic-LP}.

Now let us concentrate on part 2.\ of Proposition~\ref{prop:traffic-LP}.
\begin{lemma}\label{lem:LP-sched}
Any feasible solution $\left(\bar{\delta},\bar{\lambda}_{\xi}\mid \xi\in \bar{\Sigma}\right)$ of the traffic LP with $\bar{\delta}<1$ {\em induces} a static randomized ergodic scheduler whose utilization of any queue $i$ is equal to $\frac{\sum_{\xi\in \Sigma_i} \bar{\lambda}_{\xi}}{\mu_i}$.
\end{lemma}
\begin{proof}
We construct a static randomized scheduler $\Theta$ which chooses an action $\xi\in \Sigma_i$ for the queue $i$ with probability
\begin{equation}\label{eq:prob_act}
P_{\xi}=\frac{\bar{\lambda}_{\xi}}{\sum_{\zeta\in \Sigma_i} \bar{\lambda}_{\zeta}}\quad , \quad \sum_{\zeta\in \Sigma_i} \bar{\lambda}_{\zeta}>0\,.
\end{equation}
Otherwise, if $\sum_{\zeta\in \Sigma_i} \bar{\lambda}_{\zeta}=0$, we may control the queue $i$ arbitrarily because no jobs ever come to the queue.  We further assume (w.l.o.g.) that such queues have been removed from the network, i.e., that $P_{\xi}$ is defined using~(\ref{eq:prob_act}) for all $\xi\in \bar{\Sigma}$.
Note that $\sum_{\xi\in \Sigma_i} P_{\xi}=1$ for every $i\in \{1,\ldots,n\}$.

Fixing the scheduler $\Theta$ we obtain a purely stochastic branching network whose traffic equations are deficiently solvable.
Formally, we define a new purely stochastic branching network $\mathcal{N}'$ with $n$ queues with
 the same arrival rate, the same arrival production function and the same queue rates as~$\mathcal{N}$.
Further, $\mathcal{N}'$ has
 $R'_i=\bigcup_{\xi\in \Sigma_i} R_i(\xi)$ and the following production functions $\mathit{Prob}'_i$ associated to queues:
\[
\mathit{Prob}'_i(\boldsymbol{r})=\sum_{\xi\in \Sigma_i} P_{\xi}\cdot \mathit{Prob}_i(\xi)(\boldsymbol{r})\quad , \quad\boldsymbol{r}\in R'_i
\]
(Here we formally assume $\mathit{Prob}_i(\xi)(\boldsymbol{r})=0$ for $\boldsymbol{r}\not\in R_{\xi}$.)
The traffic equations~\eqref{eq:traffic_unc} for $\mathcal{N}'$ have the following form:
\begin{equation}\label{eq:traffic-derived}
\lambda_{j} \quad = \quad \alpha_j+\sum_{i=1}^n\lambda_{i}\cdot A'_{i j}
\quad , \quad j \in \{1, \ldots, n\}
\end{equation}
with
\begin{align*}
A'_{i j} := \sum_{\boldsymbol{r}\in R'_i} & \mathit{Prob}'_i(\boldsymbol{r})\cdot \boldsymbol{r}_j=
\sum_{\xi\in \Sigma_i}P_{\xi}  \sum_{\boldsymbol{r}\in R'_i} \mathit{Prob}_i(\xi)(\boldsymbol{r})\cdot \boldsymbol{r}_j= \\
& =\sum_{\xi\in \Sigma_i} \frac{\bar{\lambda}_{\xi}}{\sum_{\zeta\in \Sigma_i} \bar{\lambda}_{\zeta}}\sum_{\boldsymbol{r}\in R'_i} \mathit{Prob}_i(\xi)(\boldsymbol{r})\cdot \boldsymbol{r}_j =
\sum_{\xi\in \Sigma_i} \frac{\bar{\lambda}_{\xi}}{\sum_{\zeta\in \Sigma_i} \bar{\lambda}_{\zeta}}\cdot A_{\xi j}\,.
\end{align*}
Setting $\lambda_i := \sum_{\xi\in \Sigma_i} \bar{\lambda}_{\xi}$ for every $i\in \{1,\ldots,n\}$,
 we obtain $\lambda_i A'_{i j} = \sum_{\xi\in \Sigma_i} \bar{\lambda}_{\xi} A_{\xi j}$.
If we put this equality into the first equation of the traffic LP, we see that $(\lambda_1, \ldots, \lambda_n)$ solves~\eqref{eq:traffic-derived}. Also, $\lambda_j<\mu_j$ for all $j \in \{1, \ldots, n\}$.
Proposition~\ref{prop:traffic-erg} then implies that the scheduler $\Theta$ is ergodic.

Finally, let us concentrate on the utilization. Note that the utilization of any queue $i$ is the same in $\mathcal{N}'$ as in
$\mathcal{N}_{\Theta}$, so it suffices to concentrate on $\mathcal{N}'$.
Observe that the matrix $I-A'$ is invertible by Lemma~\ref{lem:invertible}.
This means that
$(\lambda_1, \ldots, \lambda_n)$ is, in fact, the {\em unique} solution of~\eqref{eq:traffic-derived}.
Then however, by Lemma~\ref{prop:erg-traffic}, the utilization $\rho_i$ of queue~$i$ in $\mathcal{N}'$ (and thus also in $\mathcal{N}_{\Theta}$) is equal to
$\frac{\lambda_i}{\mu_i}=\frac{\sum_{\xi\in \Sigma_i}\bar{\lambda}_{\xi}}{\mu_i}$.
\end{proof}
To complete the proof of Proposition~\ref{prop:traffic-LP}, we consider the problem of minimizing the maximal utilization $\max_i \rho_i$.
Let $\Theta_s$ be a static randomized ergodic scheduler induced by a solution of the traffic LP in the sense of Lemma~\ref{lem:LP-sched}
 (here we consider a solution which minimizes $\delta$).
Observe that the scheduler $\Theta_s$ minimizes $\max_i \rho_i$ among all schedulers induced by solutions of the traffic LP.
However, by Lemmas \ref{prop:erg-traffic}~and~\ref{lem:LP-sched}, for every memoryless scheduler $\Theta$
 there exists a static randomized scheduler induced by a solution of the traffic LP which has the same utilization of each queue as $\Theta$.
Thus $\Theta_s$ minimizes $\max_i \rho_i$ among all memoryless ergodic schedulers.

\section{Introduction} \label{sec:intro}
Queueing theory plays a central role in the performance analysis of computer systems.
In particular, \emph{queueing networks} are gaining attraction as models of parallel systems.
A queueing network is a set of processing units (called \emph{servers}), each of which performs tasks (called \emph{jobs}) of a certain type.
Each server has its own queue of jobs waiting to be processed.
The successful completion of a job may trigger one (or more) new jobs (of possibly different type) that need to be processed as well.
In addition to this ``internal'' job creation, so-called \emph{open} queueing networks allow for new jobs to arrive ``externally'', i.e., from outside.

Queueing networks are a popular model for both hardware and software systems because of their simplicity and generality.
On the hardware side, queueing networks can, e.g., be used for modeling multi-core processors, see e.g.~\cite{Zisgen08}
 and the references in~\cite{DengPurvis11}.
One advantage of queueing-based analyses is their scalability with growing parallelism; e.g., it is said in~\cite{Madan11}:
``Cycle-accurate full-system performance simulators do not scale well beyond a few tens of processor cores at best.
As such, analytical models based on the theory of queueing systems, are a logical choice for developing a basic understanding
 of the fundamental tradeoffs in future, large-scale multi-core systems.''
On the software side, queueing networks are used for modeling message passing.
It is said in~\cite{LaTorre08}:
``Two natural classes of systems can be modeled using such a framework:
asynchronous programs on a multi-core computer and distributed programs communicating on a network.''
Of course, the realm of queueing networks stretches far beyond computer science, see \cite{Bolch,book:Daigle10}.

The simplest queueing networks are so-called \emph{Jackson networks}~\cite{Jackson57}:
Given two servers $i, j \in \{1, \ldots, n\}$, there is a ``rule'' of the form $i \btran{p_{ij}} j$ which specifies the probability $p_{ij}$
 that the completion of an $i$-job results in the creation of a $j$-job.
There are also rules $i \btran{p_{i0}} \varepsilon$ where $p_{i0} = 1 - \sum_{j} p_{ij}$ specifies the probability that no new job is created.
Each server~$i$ has a \emph{rate}~$\mu_i$ with which an $i$-job is processed if there is one.
In addition, there is a rate~$\alpha_i$ with which $i$-jobs arrive from outside the network.
The processing times and the external arrivals are exponentially distributed,
 so that a Jackson network describes a \emph{continuous-time Markov chain (CTMC)}.
It was shown in Jackson's paper~\cite{Jackson57} that
 if the rate $\lambda_i$ of internal \emph{and} external arrivals at server~$i$ is less than~$\mu_i$ for all~$i$,
  then the network is \emph{stable}, i.e., the average queue length is finite and almost surely all queues are empty infinitely often.
Moreover, Jackson networks allow a \emph{product form}, i.e., the steady-state distribution of the queue lengths can be expressed
 as a product of functions $\pi_i(k)$, where $\pi_i(k)$ is the steady-state probability that queue~$i$ has length~$k$.

\begin{example}[network processor] \label{ex:network-processor}
 In~\cite{AhmadiWong07}, Jackson networks are used to model network processors,
  i.e., chips that are specifically targeted at networking applications---think of a router.
 We describe the model from~\cite{AhmadiWong07} (sections 4.1 and~4.2, slightly adapted).
 Before packets are processed in the ``master processor''~$M$, they pass through the ``data plane''~$D$,
  from which a fraction~$q$ of packets needs to be processed first in the ``control plane''~$C$:
 \[
  D \btran{1-q} M \qquad D \btran{q} C \qquad C \btran{1} M \qquad M \btran{1} \varepsilon
 \]
 An ``arrival manager''~$A$ sends some packets (fraction~$d_0$) directly to~$D$,
  but others (fractions~$d_1,\ldots,d_n$ with $d_0 + d_1 + \cdots + d_n=1$) are sent to ``slave processors'' $S_1, \ldots, S_n$ to assist the master.
 Some packets (fraction~$b$) still need the attention of the master after having been processed by a slave:
 \begin{equation}
  A \btran{d_0} D \qquad A \btran{d_i} S_i \qquad S_i \btran{b} D \qquad S_i \btran{1-b} \varepsilon \quad , \quad i \in \{1, \ldots, n\}. \tag*{}
 \end{equation}
\end{example}

Jackson networks and their extensions have been thoroughly studied, but they are restricted in their modelling capabilities,
 as (i) the completion of a job may trigger at most one job,
 and (ii) there is no nondeterminism that would allow to control the output probabilities of a server.
Considering~(i), it seems unnatural to assume that a distributed program communicating on a network
 produces at most one message at the end of its computation.
Considering~(ii), the ``arrival manager''~$A$ in Example~\ref{ex:network-processor}
 may want to flexibly pass incoming packets to the master or one of the slaves, possibly depending on the current load.
These restrictions have not been fully addressed, not even in isolation.
In this paper we introduce \emph{controlled branching queueing networks}, which are Jackson-like networks but allow for
 both nondeterminism (``controlled'') and the creation of more than one job (``branching'').

Both extensions directly raise computational issues.
We show in Example~\ref{ex:no-product-form} on page~\pageref{ex:no-product-form} that even purely stochastic branching networks do not allow a product form,
 which illustrates the mathematical challenge%
\footnote{It is noted in~\cite{HarrisonWilliams92} that ``[\ldots] virtually all of the models that have been successfully analyzed
 in classical queueing network theory are models having a so-called product form stationary distribution.''}
 of this extension
  and poses the question for an effective criterion that allows to determine whether the network is stable,
 i.e., returns to the empty state infinitely often.
Moreover, due to the nondeterminism, we now deal with \emph{continuous-time Markov decision processes (CTMDPs)}.
Our main theorem (Theorem~\ref{thm:main-charact}) states that if there exists any scheduler
 resolving the nondeterminism in such a way that the controlled branching network is stable,
 then there exists a \emph{randomized static} scheduler that achieves stability as well,
 where by ``randomized static'' we mean that the decisions may be randomized but not dependent on the current state (such as the load) of the system.
Moreover, the existence of such a stabilizing scheduler and the scheduler itself can be determined in polynomial time,
 and, finally, the randomized static scheduler is stabilizing in a very strong sense, in particular, all moments of the queue sizes are finite.

\emph{Related work.}
We use nondeterminism to describe systems whose behaviour is not completely specified.
A system \emph{designer} can then resolve the nondeterminism to achieve certain goals, in our case stability.
Although nondeterminism is a very well established modelling feature of probabilistic systems (see e.g.~\cite{Kwiat11}),
 the literature on automatic design of stabilizing controllers for queueing networks is sparse.
\emph{Flow-controlled} networks \cite{Stidham85,Massey91} allow to control only the external arrival stream or the service rates
 (see also \cite{Azaron03} and the references therein).
The authors of~\cite{Kumar96,Glazebrook99} consider queueing networks with fewer servers than job types,
 so that the controller needs to assign servers to queues.
As in~\cite{Kumar96,Glazebrook99}, we also use linear programming to design a controller,
 but our aim is different:
 we allow the controller to influence the production of the individual queues,
 and we study the complexity of designing stabilizing controllers and the nature of such controllers.
There has been a substantial amount of work in the last years analyzing probabilistic systems with ``branching features'',
 most prominently on \emph{recursive Markov chains} \cite{EYstacs05Extended,EtessamiWY08} and \emph{probabilistic pushdown systems} \cite{EKM04,BKKV:ICALP11}.
While these models allow for a probabilistic splitting of tasks by pushing new procedures on a stack,
 the produced tasks are processed in a strictly sequential manner, whereas the queues in a queueing network process jobs in parallel and in continuous time.
Recently, \emph{probabilistic split-join systems} were introduced~\cite{KW11:TACAS}, which allow for branching but not for external arrivals,
 and assume unlimited parallelism.
In~\cite[chapter~8]{KitaevRykov95} a queueing model with multiple classes of tasks and ``feedback'' is discussed,
 which is similar to our branching except that there is only one server, hence there is no parallelism.
Algorithmic theory of queueing systems has also attracted some attention in the past.
In particular, for \emph{closed} (i.e., without external arrivals) queueing systems,
 \cite{Papadimitriou94thecomplexity} shows EXP-completeness of minimizing a weighted throughput of the queues.

\section{Preliminaries} \label{sec:prel}

\emph{Numbers.}
We use $\mathbb{Z}, \mathbb{Q}, \mathbb{R}$ for the sets of integer, rational, real numbers, respectively, and $\mathbb{N}, \mathbb{Q}_{\ge 0}, \mathbb{R}_{\ge 0}$ for their respective subsets of nonnegative numbers.

\smallskip\noindent
\emph{Vectors and Matrices.}
Let $n \ge 1$.
We use boldface letters for denoting vectors $\boldsymbol{x} = (\boldsymbol{x}_1, \ldots, \boldsymbol{x}_n) \in \mathbb{R}^n$.
Vectors are row vectors per default, and we use superscript $^T$ for transpose, so that $\boldsymbol{x}^T$ denotes a column vector.
If the dimension $n$ is clear from the context, we write $\boldsymbol{0} := (0, \ldots, 0)$, $\boldsymbol{1} := (1, \ldots, 1)$, and
 $\es{i} = (0, \ldots, 0, 1, 0, \ldots, 0)$ for the vector with the $1$ at the $i$th component ($1 \le i \le n$).
It is convenient to define $\es{0} := \boldsymbol{0}$.
For two vectors $\boldsymbol{x}, \boldsymbol{y} \in \mathbb{R}^n$ we write $\boldsymbol{x} \sim \boldsymbol{y}$ with $\mathord{\sim} \in \{\mathord{=},\mathord{<},\mathord{\le},\mathord{>},\mathord{\ge}\}$
 if the respective relation holds componentwise.
For a vector $\boldsymbol{x} \in \mathbb{R}^n$ we denote its \emph{1-norm} by~$\norm{\boldsymbol{x}} := \sum_{i=1}^n |\boldsymbol{x}_i|$.
When $\boldsymbol{x} \in \mathbb{N}^n$ is a vector of queue sizes, we refer to~$\norm{\boldsymbol{x}}$ as the \emph{total queue size}.
For a matrix $A \in \mathbb{R}^{n \times n}$, we write $A_i$ for its $i$th row, i.e., $A_i = (A_{i 1}, \ldots, A_{i n})$.

\smallskip\noindent
\emph{CTMDP.} A {\em continuous-time Markov decision process (CTMDP)} consists of an at most countable set $S$ of states,
 an initial state~$s_1 \in S$,
 a~set of actions $\Sigma$~\footnote{Usually, each state has its own set of available actions.
 As this feature is not needed for queueing networks, we stick to the simpler version in which all actions are always available.},
 and a transition rate $q(s,\sigma,s')\geq 0$ for each pair of states $s,s'\in S$ and each action $\sigma\in \Sigma$ (here
 $q(s,\sigma,s')=0$ means that the transition from $s$ to $s'$ never occurs).
We define a {\em continuous-time Markov chain (CTMC)} to be a CTMDP whose set of actions $\Sigma$ is a singleton
 (we usually do not write the only action explicitly, so the transition rates of a CTMC are denoted by $q(s,s')$, etc.).

Intuitively, a run of a CTMDP starts in~$s_1$
 and then evolves in so-called epochs.
Assume that (after the previous epoch) the system is in a state $s$.
The next epoch consists of the following phases: First, a scheduler chooses an action $\sigma\in \Sigma$ to be executed.
Second, a waiting time for transition to each state $s'\in S$ is chosen according to the exponential distribution with the rate $q(s,\sigma,s')$
 (here we assume that if $q(s,\sigma,s')=0$, then the waiting time is~$\infty$).
The transitions compete in a way such that the one with the least waiting time is executed and the state of the CTMDP is chosen accordingly
 (the other transitions are subsequently discarded).

Formally, a~{\em run} is
an infinite sequence $s_1,\sigma_1,t_1,s_2,\sigma_2,t_2,\ldots\in (S\times \Sigma\times \mathbb{R}_{\ge 0})^{\omega}$. We denote by $\mathit{Run}$ the set of all runs.
A {\em scheduler} is a function $\Theta$ which assigns to every finite path $s_1,\sigma_1,t_1,s_2,\sigma_2,t_2,\ldots s_{n}\in (S \times \Sigma\times \mathbb{R}_{\ge 0})^*\times S$
 a probability distribution~$\Theta(w)$ on actions (i.e. $\Theta(w):\Sigma\rightarrow [0,1]$ satisfies $\sum_{\sigma\in \Sigma} \Theta(w)(\sigma)=1$).
For technical reasons, we have to restrict ourselves to measurable schedulers (for details see~e.g.~\cite{NSK:CTMDP-delayed}).

We work with a measurable space of runs $(\mathit{Run},\mathcal{F})$ where $\mathcal{F}$ is the smallest $\sigma$-algebra generated
by basic cylinders (i.e. sets of runs with common finite prefix) in a standard way.
Every
scheduler $\Theta$ induces a unique probability measure $\Pr_{\Theta}$ on $\mathcal{F}$ determined by the probabilities of the basic cylinders.
For detailed definitions see~\cite{NSK:CTMDP-delayed}.
Then each scheduler $\Theta$ {\em induces} a stochastic process $\left(x(t)\mid t\in \mathbb{R}_{\ge 0}\right)$ on the probability space $(\mathit{Run},\mathcal{F},\Pr_{\Theta})$ where $x(t)$ is the current state of the run in time $t$, i.e.,
each $x(t)$ is a random variable defined by
\[
x(t)(s_1,\sigma_1,t_1,s_2,\sigma_2,t_2,\ldots)=s_i \quad , \quad \sum_{j=1}^{i-1} t_i\leq t \text{ and } \sum_{j=1}^{i} t_i\geq t\,.
\]
A scheduler $\Theta$ is {\em memoryless} if for every path $w=s_1,\sigma_1,t_1,s_2,\sigma_2,t_2,\ldots s_{n+1}\in (S \times \Sigma\times \mathbb{R}_{\ge 0})^*\times S$ we have that $\Theta(w)=\Theta(s_{n+1})$.

\smallskip\noindent
\emph{Networks.}
Define $\Prod{n,K} := \{\boldsymbol{r} \in \mathbb{N}^n \mid \boldsymbol{r}_1 + \cdots + \boldsymbol{r}_n \le K\}$.
A \emph{production function} for $(n,K)$ is a function $\mathit{Prob}: R \to \mathbb{Q} \cap (0,1]$ with $R \subseteq \Prod{n,K}$
 such that $\sum_{\boldsymbol{r} \in R} \mathit{Prob}(\boldsymbol{r}) = 1$.
A \emph{controlled branching network} \emph{with $n$ queues and branching factor~$K$}
 consists of an arrival rate $\mu_0 \in \mathbb{Q} \cap (0,\infty)$,
 queue rates $\mu_i \in \mathbb{Q} \cap (0,\infty)$ for $i \in \{1, \ldots, n\}$,
 an arrival production function $\mathit{Prob}_0: R_0 \to \mathbb{Q} \cap (0,1]$ for $(n,K)$,
 and finite action sets $\Sigma_1, \ldots, \Sigma_n$ as follows.
An action $\sigma_i \in \Sigma_i$ assigns to queue~$i$ a production function $\mathit{Prob}_i(\sigma_i): R_i(\sigma_i) \to \mathbb{Q} \cap (0,1]$ for $(n,K)$.
Define $\Sigma := \Sigma_1 \times \cdots \times \Sigma_n$.
If $\sigma = (\sigma_1, \ldots, \sigma_n) \in \Sigma$,
 we write $R_i(\sigma)$, $\mathit{Prob}_i(\sigma)$ and $R_0(\sigma)$, $\mathit{Prob}_0(\sigma)$
  to mean $R_i(\sigma_i)$, $\mathit{Prob}_i(\sigma_i)$ and $R_0$, $\mathit{Prob}_0$.
Observe that the rates~$\mu_i$ do not depend on actions.
This simplification is without loss of generality.%
\footnote{To show that this assumption is w.l.o.g.\ one can employ the standard ``uniformization'' trick.
More precisely, assume that the actions of a queue~$i$ have different rates.
Define $\mu_i$ to be the maximum of all rates of~$\Sigma_i$ and compensate by ``adding self-loops'', i.e.,
 make the actions of~$\Sigma_i$ generate a new job for queue~$i$ with a suitable probability.
This effectively substitutes a transition with longer delay by possibly several transitions with delay~$\mu_i$.
As static schedulers can be easily translated between the original and the transformed system, our results remain valid.}
We assume a nonzero arrival stream, i.e., there is $\boldsymbol{r} \in R_0$ with $\boldsymbol{r} \ne \boldsymbol{0}$.
We define the \emph{size} of a controlled network by
 $n + K + \left(\sum_{i=0}^n |\mu_i|\right) + |R_0| + |\mathit{Prob}_0| + \sum_{i=1}^n \sum_{\sigma_i \in \Sigma_i}  |R_i(\sigma_i)| + |\mathit{Prob}_i(\sigma_i)|$,
 where $|\mu_i|$ etc.\ means the description size assuming the rationals are represented as fractions of integers in binary.
A controlled branching network induces a CTMDP
 with state space~$\mathbb{N}^n$ (the queue sizes), initial state~$\boldsymbol{0}$, action set~$\Sigma$, and transition rates
 \[
  q(\boldsymbol{x},\sigma,\boldsymbol{y}) = \sum_{i\in \{0,1,\ldots,n\}: i=0 \lor \boldsymbol{x}_i \ne 0} \ \sum_{\boldsymbol{r} \in R_i(\sigma) : \boldsymbol{y} = \boldsymbol{x} - \es{i} + \boldsymbol{r}} \mu_i \mathit{Prob}_i(\sigma)(\boldsymbol{r})
   \qquad \text{for $\boldsymbol{x},\boldsymbol{y} \in \mathbb{N}^n$, $\sigma \in \Sigma$.}
 \]
Interpreting this definition, there is a ``race'' between external arrivals (rate~$\mu_0$) and the nonempty queues (rates~$\mu_i$);
 if the external arrivals win, new jobs are added according to~$\mathit{Prob}_0(\sigma)$;
 if queue~$i$ wins, one $i$-job is removed and new jobs are added according to~$\mathit{Prob}_i(\sigma)$.

An \emph{purely stochastic branching network} is a controlled branching network with $\Sigma = \{\sigma\}$,
 i.e., with a unique action for each queue.
Hence, the induced CTMDP is a CTMC.
In the purely stochastic case we write only $R_i$ for $R_i(\sigma)$ etc.
If $\mathit{Prob}_i(\boldsymbol{r}) = p$ in the purely stochastic case, we use in examples the notation $i \btran{p} \boldsymbol{r}$,
 where we often write $\boldsymbol{r} \in \Prod{n,K}$ as a multiset without curly brackets.
For instance, if $n=2$, we write $1 \btran{p} 1,2$ and $1 \btran{p} 2,2$ and $1 \btran{p} \varepsilon$
 to mean $\mathit{Prob}_1(\boldsymbol{r}) = p$ with $\boldsymbol{r} = (1,1)$ and $\boldsymbol{r} = (0,2)$ and $\boldsymbol{r} = (0,0)$, respectively.

Fixing a controlled network~$\mathcal{N}$ and a scheduler $\Theta$ for the CTMDP induced by~$\mathcal{N}$, we obtain a stochastic process
$\mathcal{N}_{\Theta}=(\boldsymbol{x}(t) \mid t\in \mathbb{R}_{\ge 0})$, where $\boldsymbol{x}(0)=\boldsymbol{0}\in \mathbb{N}^n$, which evolves according to the dynamics of~$\mathcal{N}$ and the scheduler $\Theta$.
In the purely stochastic case we drop the subscript~$\Theta$, and so we identify a network~$\mathcal{N}$ with its induced stochastic process.

\begin{example}[no product form] \label{ex:no-product-form}
 Consider the purely stochastic branching network with $0 \btran{1} 1,2$ and $1 \btran{1} \varepsilon$ and $2 \btran{1} \varepsilon$.
 If its stationary distribution~$\pi$ (for a definition of stationary distribution see before Theorem~\ref{thm:main-charact})
 had product from, the queues would be ``independent in steady-state'', i.e.,
  $\pi(\boldsymbol{x}_2 \ge 1 \mid \boldsymbol{x}_1 \ge 1) = \pi(\boldsymbol{x}_2 \ge 1)$, where by~$\boldsymbol{x}$ we mean $\boldsymbol{x}(t)$ in steady state.
 However, if $\mu_0$ is much smaller than $\mu_1=\mu_2$, then we have $\pi(\boldsymbol{x}_2 \ge 1 \mid \boldsymbol{x}_1 \ge 1) > \pi(\boldsymbol{x}_2 \ge 1)$,
  intuitively because $\boldsymbol{x}_1 \ge 1$ probably means that there was an arrival recently, so that $\boldsymbol{x}_2 \ge 1$ is more likely than usual.
 More concretely, let $\mu_0 = 1$ and $\mu_1 = \mu_2 = 3$
  and consider the 2-state Markov chain obtained by assuming that each arrival leads to the state $(1,1)$ and each completion of any job leads
  to the state $(0,0)$.
 By computing the stationary distribution $\pi'$ of this 2-state Markov chain in the standard way,
  we obtain $\pi'((0,0)) = 6/7$ and $\pi'((1,1)) = 1/7$.
 Since this 2-state Markov chain ``underapproximates'' the CTMC induced by the network,
  we have $\pi(\boldsymbol{x}_1 \ge 1 \ \land \ \boldsymbol{x}_2 \ge 1) \ge 1/7$.
 On the other hand, by considering the two queues separately, the standard formula for the M/M/1 queue gives
  $\pi(\boldsymbol{x}_1 \ge 1) = \pi(\boldsymbol{x}_2 \ge 1) = 1/3$.
 Product form would imply $\pi(\boldsymbol{x}_1 \ge 1 \ \land \ \boldsymbol{x}_2 \ge 1) = \pi(\boldsymbol{x}_1 \ge 1) \cdot \pi(\boldsymbol{x}_2 \ge 1) = 1/9$,
  contradicting the inequality above.
\end{example}

\section{Results} \label{sec:results}
We focus on the stability of purely stochastic and controlled branching networks.
Our notion of stability requires that the network is completely empty infinitely many times.
Given a stochastic process $(\boldsymbol{x}(t) \mid t\in \mathbb{R}_{\ge 0})$,
 we say that the process is \emph{ergodic} if the expected return time to $\boldsymbol{0}$ is finite.
More formally, define a random variable $R$ by
\[
R\quad :=\quad \inf_{t>0}\, \left\{t\mid \boldsymbol{x}(t)=\boldsymbol{0}, \exists t'<t:\boldsymbol{x}(t')\not = \boldsymbol{0}\right\} \,.
\]
Then the process is ergodic iff $\Ex{R}<\infty$.
In the controlled case, we say that a scheduler~$\Theta$ for~$\mathcal{N}$ is \emph{ergodic for~$\mathcal{N}$} if $\mathcal{N}_\Theta$ is ergodic.
In the following we use stability and ergodicity interchangeably.
A scheduler $\Theta$ is {\em static} if it always chooses the same fixed distribution on actions.
Note that static schedulers are memoryless.
If in a stochastic process $(\boldsymbol{x}(t) \mid t\in \mathbb{R}_{\ge 0})$ the limit $\pi(\boldsymbol{x}) := \lim_{t \to \infty} \Pr(\boldsymbol{x}(t) = \boldsymbol{x})$ exists for all $\boldsymbol{x} \in \mathbb{N}^n$ and $\sum_{\boldsymbol{x}\in \mathbb{N}^n} \pi(\boldsymbol{x})=1$,
 then $\pi: \mathbb{R}_{\ge 0} \to [0,1]$ is called the \emph{stationary distribution}.
\begin{theorem}\label{thm:main-charact}
Let $\mathcal{N}$ be a controlled branching network.
It is decidable in polynomial time whether there exists an (arbitrary) ergodic scheduler for~$\mathcal{N}$.
If it exists, one can compute, in polynomial time, a {\em static randomized} ergodic scheduler for~$\mathcal{N}$
with stationary distribution~$\pi$ such that there exists an exponential moment of the total number of waiting jobs,
 i.e., there is $\delta > 0$ such that
 $\sum_{\boldsymbol{x} \in \mathbb{N}^n} \exp(\delta \norm{\boldsymbol{x}}) \pi(\boldsymbol{x})$ exists.
\end{theorem}

To prove Theorem~\ref{thm:main-charact} we generalize the concept of {\em traffic equations} (see~e.g.~\cite{book:Chen01}) from the theory of Jackson networks.
Intuitively, the traffic equations express the fact that the inflow of jobs to a given queue must be equal to the outflow.

Remarkably, the traffic equations
 characterize the stability of the Jackson network.
More precisely, a Jackson network is stable
 if and only if
 there is a solution of the traffic equations whose components are strictly smaller than the rates of the corresponding queues (we call such a solution {\em deficient}).

We show how to extend the traffic equations so that they characterize the stability of controlled branching networks.
For a smooth presentation, we start with {\em purely stochastic} branching networks and add control later on.
Hence, the overall plan of the proof of Theorem~\ref{thm:main-charact} is as follows:
Set up traffic equations for purely stochastic branching networks and show that if there is a deficient solution of these equations, then the network is stable.
This result, presented in Section~\ref{sec:uncontr} (Proposition~\ref{prop:traffic-erg}), is of independent interest and
 requires the construction of a suitable \emph{Lyapunov function}.
Then, in Section~\ref{sec:contr}, we generalize the traffic equations to controlled branching networks and show that any ergodic scheduler determines a deficient solution
 (Proposition~\ref{prop:traffic-LP}).
This solution naturally induces a static scheduler, which, when fixed, determines an purely stochastic network with deficiently solvable traffic equations.
Propositions \ref{prop:traffic-erg} and~\ref{prop:traffic-LP} imply Theorem~\ref{thm:main-charact} and provide some additional results.

\subsection{Purely stochastic branching networks} \label{sec:uncontr}
Assume that $\mathcal{N}$ is purely stochastic, i.e., there is a single action for each queue.
In such a case the CTMDP induced by the network is in fact a CTMC.
We associate the following quantities to a network, which will turn out to be crucial for its performance.
Let $\boldsymbol{\mu} := (\mu_1, \ldots, \mu_n)$.
Let $\boldsymbol{\alpha} \in \mathbb{R}_{\ge 0}^n$ be the vector with $\boldsymbol{\alpha}_i := \mu_0 \sum_{\boldsymbol{r} \in R_0} \mathit{Prob}_0(\boldsymbol{r}) \boldsymbol{r}_i$;
 i.e., $\boldsymbol{\alpha}_i$ indicates the expected number of external arrivals at queue~$i$ per time unit.
Note that $\boldsymbol{\alpha} \ne \boldsymbol{0}$, as we assume a nonzero arrival stream.
Let $A \in \mathbb{R}_{\ge 0}^{n \times n}$ be the matrix with $A_{i j} := \sum_{\boldsymbol{r} \in R_i} \mathit{Prob}_i(\boldsymbol{r}) \boldsymbol{r}_j$;
 i.e., $A_{i j}$ indicates the expected production of $j$-jobs when queue~$i$ fires.
W.l.o.g.\ we assume that all queues are ``reachable'', i.e., for all queues~$i$ there is $j \in \mathbb{N}$ with $(\boldsymbol{\alpha} A^j)_i \ne 0$.
 We define a set of \emph{traffic equations}
\begin{equation}\label{eq:traffic_unc}
\lambda_{j} \quad = \quad \alpha_j+\sum_{i=1}^n\lambda_{i}\cdot A_{i j}
 \quad , \quad j \in \{1, \ldots, n\},
\end{equation}
in matrix form:
\begin{equation}
  \boldsymbol{\lambda} = \boldsymbol{\alpha} + \boldsymbol{\lambda} A\,. \label{eq:traffic}
 \end{equation}

We prove the following proposition.
\newcommand{\stmtproptrafficerg}{
Assume that
 $\boldsymbol{\lambda} \in \mathbb{R}_{\ge 0}^n$
solves the traffic equations~\eqref{eq:traffic} and satisfies $\boldsymbol{\lambda}<\boldsymbol{\mu}$.
Then the following conclusions hold:
\begin{enumerate}
 \item
  The process~$\mathcal{N}$ is ergodic, i.e., the expected return time to~$\boldsymbol{0}$ is finite.
 \item
  There exists a stationary distribution~$\pi$ such that there exists an exponential moment of the total queue size,
   i.e., there is $\delta > 0$ such that $\sum_{\boldsymbol{x} \in \mathbb{N}^n} \exp(\delta \norm{\boldsymbol{x}}) \pi(\boldsymbol{x})$ exists.
\end{enumerate}
}
\begin{proposition}\label{prop:traffic-erg}
 \stmtproptrafficerg
\end{proposition}
The key step to the proof of Proposition~\ref{prop:traffic-erg} is to construct a so-called \emph{Lyapunov function}
 with respect to which the process~$\mathcal{N}$ exhibits a ``negative drift''.
This is in fact a classical technique for showing the stability of queueing systems \cite{MeynTweedie93};
 the difficulty lies in finding a suitable Lyapunov function.
The ``drift'' of~$\mathcal{N}$ is given by the \emph{mean velocity vector} $\boldsymbol{\Delta}(\boldsymbol{x}) \in \mathbb{R}_{\ge 0}^n$ of~$\mathcal{N}$,
 defined by $\boldsymbol{\Delta}(\boldsymbol{x}) := \lim_{h\to 0^+} \Ex{\boldsymbol{x}(t+h) - \boldsymbol{x}(t) \mid \boldsymbol{x}(t) = \boldsymbol{x}}/h$.
The limit exists, is independent of~$t$, and we have
\begin{equation}
 \boldsymbol{\Delta}(\boldsymbol{x}) = \boldsymbol{\alpha} + \sum_{i: \boldsymbol{x}_i \ne 0} \mu_i (-{\es{i}} + A_i) \,. \label{eq:mean-velocity-main}
\end{equation}
The following lemma is implicitly proved in~\cite[theorem~1]{DownMeyn97piecewise}.
\begin{lemma}\label{lem:thm1-piecewise}
 Suppose that a function $\widetilde{V} : \mathbb{R}_{\ge 0}^n \to \mathbb{R}_{\ge 0}$ is two times continuously differentiable, $\widetilde{V}(\boldsymbol{x}) = 0$ implies $\boldsymbol{x} = \boldsymbol{0}$,
  and that there is $\gamma > 0$ such that we have
  \[
   \boldsymbol{\Delta}(\boldsymbol{x}) \big(\widetilde{V}'(\boldsymbol{x})\big)^T \le -\gamma \qquad \text{ for all $\boldsymbol{x} \ne \boldsymbol{0}$, }
  \]
  where $\widetilde{V}'(\boldsymbol{x})$ denotes the gradient of~$\widetilde{V}$ at~$\boldsymbol{x}$.
 Then the conclusions of Proposition~\ref{prop:traffic-erg} holds.
\end{lemma}
Following~\cite{DownMeyn97piecewise}, we construct the Lyapunov function~$\widetilde{V}$ in two stages:
 we first define a suitable \emph{piecewise linear} function~$V: \mathbb{N}^n \to \mathbb{R}_{\ge 0}$;
  then $V$ is \emph{smoothed} to obtain~$\widetilde{V}$.
For the definition of~$V$ we need the following lemma.
\newcommand{\stmtleminvertible}{
 The matrix series $A^* := \sum_{i=0}^\infty A^i$ converges (``exists'') in~$\mathbb{R}_{\ge 0}^{n \times n}$ and is equal to $(I-A)^{-1}$.
}
\begin{lemma} \label{lem:invertible}
 \stmtleminvertible
\end{lemma}
Define vectors $\qs{1}, \ldots, \qs{n} \in \mathbb{R}_{\ge 0}^n$ by setting $\qsT{i} := \asT{i} / \norm{\as{i}}$,
 where $\asT{i}$ is the $i$th column of~$A^*$.
Observe that we have $\boldsymbol{1} \qsT{i} = 1$ for all~$i$.
Define the function $V : \mathbb{R}_{\ge 0}^{n} \to \mathbb{R}_{\ge 0}$ by $V(\boldsymbol{x}) := \max_i \{\boldsymbol{x} \qsT{i}\}$.
We will use the following property of~$V$:
\begin{lemma} \label{lem:good-max}
 If $\boldsymbol{0} \ne \boldsymbol{x} \in \mathbb{R}_{\ge 0}^n$ and $\boldsymbol{x}_i = 0$, then $\boldsymbol{x} \qsT{i} < V(\boldsymbol{x})$.
\end{lemma}
Lemma~\ref{lem:good-max} is not obvious; \ifthenelse{\equal{\techRep}{true}}{in the appendix}{in~\cite{BK12:stacs-report}} we use Farkas' lemma for the proof.
The following lemma describes the crucial ``negative drift'' property of~$V$:
\newcommand{\stmtlempiecewisenegdrift}{
 There is $\gamma > 0$ such that we have
  \[
   \boldsymbol{\Delta}(\boldsymbol{x}) \big(V'(\boldsymbol{x})\big)^T \le -\gamma \qquad \text{ for all $\boldsymbol{x} \ne \boldsymbol{0}$ }
  \]
  and all subgradient vectors $V'(\boldsymbol{x})$ of~$V$ at~$\boldsymbol{x}$.
 More precisely, one can choose
  \[ \gamma := \min_i (\mu_i - \boldsymbol{\lambda}_i) / \norm{\as{i}} \,,
  \]
  where $\asT{i}$ is the $i$th column of~$A^*$.
}
\begin{lemma} \label{lem:piecewise-neg-drift}
 \stmtlempiecewisenegdrift
\end{lemma}
\begin{example}
 Consider the network with
 \[
   0 \btran{1} 1
    \qquad \begin{array}{l} 1 \btran{1/5} 2,2 \\ 1 \btran{4/5} \varepsilon \end{array}
    \qquad \begin{array}{l} 2 \btran{1/6} 1,2 \\ 2 \btran{5/6} \varepsilon \end{array}\,,
 \]
 arrival rate $\mu_0 = 7/30$, and $\boldsymbol{\mu} = (5/12, 7/20)$, so that $\mu_0 + \mu_1 + \mu_2 = 1$.
 Let us write $[0] := \boldsymbol{\alpha} = \mu_0 (1,0)$, \ $[1] := \mu_1 (-\es{1} + A_1)$, \ $[2] := \mu_2 (-\es{2} + A_2)$, \
  $[01] := [0] + [1]$, \ $[02] := [0] + [2]$, \ $[012] := [0] + [1] + [2]$.
 These vectors are shown in Figure~\ref{fig:piecewise-neg-drift}~(a).

 The mean velocity vector $\boldsymbol{\Delta}(\boldsymbol{x})$ is one of the vectors $[0], [01], [02], [012]$,
  depending on which components of~$\boldsymbol{x}$ are nonzero.
 The vector field in Figure~\ref{fig:piecewise-neg-drift}~(b) shows the corresponding vectors for several $\boldsymbol{x} \in \mathbb{N}^2$.
 The connected line segments indicate points $\boldsymbol{x}$ with the same value of
  $V(\boldsymbol{x}) = \max \{\boldsymbol{x} \qsT{1}, \boldsymbol{x} \qsT{2}\} = \max \{ \frac56 \boldsymbol{x}_1 + \frac16 \boldsymbol{x}_2, \frac27 \boldsymbol{x}_1 + \frac57 \boldsymbol{x}_2 \}$
   (values $0.5, 1, 1.5, \ldots$).
 It can be seen from the figure that the drift is negative with respect to the gradient of~$V$, if $\boldsymbol{x} \ne \boldsymbol{0}$.
\tikzset{>=latex',
 axis/.style={->},
 elem/.style={->,thick},
 drift/.style={->,ultra thick},
}
\begin{figure}
\begin{tabular}{cc}
\begin{tikzpicture}[scale=10]

 \draw[axis] (-0.25,0) -- (0.35,0);
 \draw[axis] (0,-0.31) -- (0,0.25);
 \draw (0.2,-0.01) -- (0.2,+0.01);
 \draw (-0.01,0.2) -- (+0.01,0.2);
 \node             at (0.2,-0.03) {$0.2$};
 \node             at (0.35,-0.03) {$\boldsymbol{x}_1$};
 \node             at (-0.04,0.2) {$0.2$};
 \node             at (-0.03,0.25) {$\boldsymbol{x}_2$};
 \draw[elem] (7/30,0) -- (-11/60,1/6);
 \draw[elem] (-11/60,1/6) -- (-1/8,-1/8);
 \draw[elem] (7/30,0) -- (7/24,-7/24);
 \draw[elem] (7/24,-7/24) -- (-1/8,-1/8);
 \draw[drift] (0,0) -- (7/30,0);
 \draw[drift] (0,0) -- (-11/60,1/6);
 \draw[drift] (0,0) -- (7/24,-7/24);
 \draw[drift] (0,0) -- (-1/8,-1/8);
 \node at (0.12,-0.03) {$[0]$};
 \node at (0.06,0.1) {$[1]$};
 \node at (0.06,-0.23) {$[1]$};
 \node at (0.29,-0.12) {$[2]$};
 \node at (-0.19,0.06) {$[2]$};
 \node at (-0.1,0.05) {$[01]$};
 \node at (0.17,-0.12) {$[02]$};
 \node at (-0.04,-0.09) {$[012]$};
\end{tikzpicture}
&
\begin{tikzpicture}[scale=1.8]
 \draw[axis] (0,0) -- (3.5,0);
 \draw[axis] (0,0) -- (0,3.5);
 \node at (3.42,-0.2) {$\boldsymbol{x}_1$};
 \node at (-0.17,3.42) {$\boldsymbol{x}_2$};
 \draw[step=1,gray] (0,0) grid (3.2,3.2);
 \draw (1,-0.07) -- (1,0.07);
 \draw (2,-0.07) -- (2,0.07);
 \draw (3,-0.07) -- (3,0.07);
 \draw (-0.07,1) -- (0.07,1);
 \draw (-0.07,2) -- (0.07,2);
 \draw (-0.07,3) -- (0.07,3);
 \node at (1,-0.2) {$1$};
 \node at (2,-0.2) {$2$};
 \node at (3,-0.2) {$3$};
 \node at (-0.2,1) {$1$};
 \node at (-0.2,2) {$2$};
 \node at (-0.2,3) {$3$};
 \draw[drift] (0,0) -- (7/30,0);
 \draw[drift] (1,0) -- (1-11/60,1/6);
 \draw[drift] (2,0) -- (2-11/60,1/6);
 \draw[drift] (3,0) -- (3-11/60,1/6);
 \draw[drift] (0,1) -- (7/24,1-7/24);
 \draw[drift] (0,2) -- (7/24,2-7/24);
 \draw[drift] (0,3) -- (7/24,3-7/24);
 \draw[drift] (1,1) -- (1-1/8,1-1/8);
 \draw[drift] (2,1) -- (2-1/8,1-1/8);
 \draw[drift] (3,1) -- (3-1/8,1-1/8);
 \draw[drift] (1,2) -- (1-1/8,2-1/8);
 \draw[drift] (2,2) -- (2-1/8,2-1/8);
 \draw[drift] (3,2) -- (3-1/8,2-1/8);
 \draw[drift] (1,3) -- (1-1/8,3-1/8);
 \draw[drift] (2,3) -- (2-1/8,3-1/8);
 \draw[drift] (3,3) -- (3-1/8,3-1/8);
 \clip (0,0) rectangle (3.2,3.2);
 \draw (1*0.6,0) -- (1*0.5,1*0.5) -- (0,1*0.7);
 \draw (2*0.6,0) -- (2*0.5,2*0.5) -- (0,2*0.7);
 \draw (3*0.6,0) -- (3*0.5,3*0.5) -- (0,3*0.7);
 \draw (4*0.6,0) -- (4*0.5,4*0.5) -- (0,4*0.7);
 \draw (5*0.6,0) -- (5*0.5,5*0.5) -- (0,5*0.7);
 \draw (6*0.6,0) -- (6*0.5,6*0.5) -- (0,6*0.7);
 \node at (0.14,0.14) {$[0]$};
 \node at (0.7,0.14) {$[01]$};
 \node at (0.4,0.8) {$[02]$};
 \node[inner sep=0mm] at (0.72,0.9) {$[012]$};
\end{tikzpicture}
\\
(a)
&
(b)
\end{tabular}
\caption{Illustration of negative drift.}
\label{fig:piecewise-neg-drift}
\end{figure}
\end{example}
\begin{proof}[Proof of Lemma~\ref{lem:piecewise-neg-drift}]
 Let $\boldsymbol{x} \ne \boldsymbol{0}$.
 We need to show $\boldsymbol{\Delta}(\boldsymbol{x}) \qsT{i} \le -\gamma$ for all $i$ with $\boldsymbol{x} \qsT{i} = V(\boldsymbol{x})$.
 W.l.o.g.\ we assume that $\boldsymbol{x} \qsT{1} = V(\boldsymbol{x})$ and show only $\boldsymbol{\Delta}(\boldsymbol{x}) \qsT{1} \le -\gamma$.
 By Lemma~\ref{lem:good-max} we have $\boldsymbol{x}_1 \ne 0$.
 It follows from the property $(I-A) A^* = I$ and the definition of~$\qs{1}$ that we have
  \begin{equation} \label{eq:q1-cancellations-main}
   (-{\es{1}} + A_1) \qsT{1} = -1/\norm{\as{1}} \qquad \text{and} \qquad (-\es{i} + A_i) \qsT{1} = 0 \quad \text{ for $2 \le i \le n$.}
  \end{equation}
 Hence we have:
 \begin{align*}
  \boldsymbol{\Delta}(\boldsymbol{x}) \qsT{1} & = \left( \boldsymbol{\alpha} + \sum_{i: \boldsymbol{x}_i \ne 0} \mu_i (-{\es{i}} + A_i) \right) \qsT{1}  && \text{by~\eqref{eq:mean-velocity-main}} \\
                        & = \boldsymbol{\alpha} \qsT{1} - \mu_1 / \norm{\as{1}} && \text{by~\eqref{eq:q1-cancellations-main} and $\boldsymbol{x}_1 \ne 0$} \\
                        & \le -\gamma + \boldsymbol{\alpha} \qsT{1} - \boldsymbol{\lambda}_1 / \norm{\as{1}} && \text{by the definition of~$\gamma$} \\
                        & = -\gamma + \left( \boldsymbol{\alpha} + \sum_{i=1}^n \boldsymbol{\lambda}_i (-{\es{i}} + A_i) \right) \qsT{1}
                                  && \text{by~\eqref{eq:q1-cancellations-main}} \\
                        & = -\gamma + \left( \boldsymbol{\alpha} + \boldsymbol{\lambda} (-I+A) \right) \qsT{1} \\
                        & = -\gamma + \boldsymbol{0} \qsT{1} = -\gamma && \text{by the traffic equation.}
 \end{align*}
\end{proof}
Using integration, one can obtain a two times continuously differentiable function~$\widetilde{V}$ satisfying the conditions in Lemma~\ref{lem:thm1-piecewise}:
the function~$V$ is smoothed by defining $\widetilde{V}(\boldsymbol{x})$, for all~$\boldsymbol{x}$, as an ``average'' of the values~$V(\boldsymbol{y})$
  where $\boldsymbol{y}$ belongs to a small ball around~$\boldsymbol{x}$;
 see the appendix of~\cite{DownMeyn97piecewise} for the formal details.
This concludes the proof of Proposition~\ref{prop:traffic-erg}.

\section{Proofs of Section~\ref{sec:contr}}
\subsection{Proof of Lemma~\ref{prop:erg-traffic}} \label{app:contr}

\begin{qlemma}{\ref{prop:erg-traffic}}
\stmtpropergtraffic
\end{qlemma}
\medskip

We divide our proof of Lemma~\ref{prop:erg-traffic} into four claims.
\begin{claim}\label{lem:ex-freq}
For every $\xi\in \bar{\Sigma}$ there is a constant $O_{\xi}$ such that for almost all runs $\omega$ of $\mathcal{N}_{\Theta}$ the limit
\[
\lim_{t\rightarrow{} \infty} \frac{O^{\leq t}_{\xi}(\omega)}{t}
\]
exists and is equal to $O_{\xi}$.
\end{claim}
\begin{proof}
Given an action $\xi\in \bar{\Sigma}$ and $i\geq 1$, denote by $M^{\xi}_i$ a random variable giving the number of times the action $\xi$ is fired between the $i$-th and $i+1$-st visit to $\boldsymbol{0}$ (note that the network starts with all empty queues so the first visit happens at time $0$). Observe that all $M^{\xi}_i$
are identically distributed.
Also, as the expected return time to $\boldsymbol{0}$ is finite and there are only finitely many distinct rates (i.e. the expected time between two state transitions is bounded from below by a positive constant), the expectation $\Ex{M^{\xi}_1}$ is finite. By the strong law of large numbers (see~e.g.~\cite{Billingsley:book}), there is a constant $M^{\xi}$ such that for almost all runs $\omega$ the limit $\lim_{n\rightarrow \infty} \frac{\sum_{i=1}^n M^{\xi}_i(\omega)}{n}$ exists and is equal to $M^{\xi}$.
For $i\geq 1$ we define $R_i$ to be a random variable giving the total time between the $i$-th and $i+1$-st visits to $\boldsymbol{0}$.
Note that $R_1$ is precisely the variable $R$ giving the return time to $\boldsymbol{0}$.
 By the strong law of large numbers, for almost all runs $\omega$ the limit $\lim_{n\rightarrow \infty} \frac{\sum_{i=1}^n R_i(\omega)}{n}$ exists and is equal to $\Ex{R_1}=\Ex{R}<\infty$.

Now note that for $t\geq 0$ and $n\geq 1$ satisfying $\sum_{i=1}^{n-1} R_i(\omega)\leq t\leq \sum_{i=1}^n R_i(\omega)$ (here for $n=1$ we assume $\sum_{i=1}^{n-1} R_i(\omega)=0$) we have
\begin{equation}\label{eq:three}
\frac{\sum_{i=1}^{n-1} M^{\xi}_i(\omega)}{\sum_{i=1}^n R_i(\omega)}\quad \leq \quad\frac{O^{\leq t}_{\xi}(\omega)}{t}\quad
\leq \quad\frac{\sum_{i=1}^{n} M^{\xi}_i(\omega)}{\sum_{i=1}^n R_i(\omega)}
\end{equation}
The limit of the rightmost term of (\ref{eq:three}) exists:
\[
\frac{M^{\xi}}{\Ex{R}}\quad = \quad\lim_{n\rightarrow \infty} \frac{\sum_{i=1}^n M^{\xi}_i(\omega)}{n}\cdot \lim_{n\rightarrow \infty}\frac{n}{\sum_{i=1}^n R_i(\omega)}\quad = \quad \lim_{n\rightarrow \infty} \frac{\sum_{i=1}^n M^{\xi}_i(\omega)}{\sum_{i=1}^n R_i(\omega)}
\]
Similarly, the limit of the left most term of (\ref{eq:three}) exists:
\[
\frac{M^{\xi}}{\Ex{R}}\quad = \quad \left(\lim_{n\rightarrow \infty} \frac{\sum_{i=1}^{n-1} M^{\xi}_i(\omega)}{n-1}\cdot\lim_{n\rightarrow \infty} \frac{ n-1}{n}\right)\cdot \lim_{n\rightarrow \infty}\frac{n}{\sum_{i=1}^n R_i(\omega)}\quad = \quad \lim_{n\rightarrow \infty} \frac{\sum_{i=1}^n M^{\xi}_i(\omega)}{\sum_{i=1}^n R_i(\omega)}
\]
Thus by basic properties of limits, the limit
$\lim_{t\rightarrow \infty} \frac{O^{\leq t}_{\xi}(\omega)}{t}$ exists
and is equal to $\frac{M^{\xi}}{\Ex{R}}$.
\end{proof}
The following two claims show that the frequencies indeed solve the traffic LP with $\delta<1$.
\begin{claim}
For every $j\in \{1,\ldots,n\}$ we have
\begin{equation}\label{eq:flow}
\sum_{\xi\in \Sigma_j} O_{\xi} = \sum_{i=0}^n \sum_{\zeta\in \Sigma_i} O_{\zeta}\cdot A_{\zeta j}
\end{equation}
Here we assume (in order to simplify notation) that the external source is a (symbolic) queue $0$, with action set $\Sigma=\{\iota\}$ where $\iota$ has rate $\mu_0$ and a production function $\mathit{Prob}_0$ (thus $O_{\iota}\cdot A_{\iota j}=\boldsymbol{\alpha}_j$).
\end{claim}
\begin{proof}
Denote by $O^{\leq t}_{\zeta\rightarrow j}(\omega)$ the number of jobs produced for queue $j$ by firing the action $\zeta$. The crucial observation is that for almost all runs $\omega$ we have
\[
\lim_{t\rightarrow \infty} \frac{\sum_{\xi\in \Sigma_j} O^{\leq t}_{\xi}(\omega)}{t}\quad = \quad \lim_{t\rightarrow \infty}\frac{\sum_{i=0}^n \sum_{\zeta\in \Sigma_i} O^{\leq t}_{\zeta\rightarrow j}(\omega)}{t}
\]
Indeed, $\sum_{\xi\in \Sigma_j} O^{\leq t}_{\xi}(\omega)\leq \sum_{i=0}^n \sum_{\zeta\in \Sigma_i} O^{\leq t}_{\zeta\rightarrow j}(\omega)$ for all $t$ and $\omega$ because $\sum_{i=0}^n \sum_{\zeta\in \Sigma_i} O^{\leq t}_{\zeta\rightarrow j}(\omega)$ is precisely the number of jobs that enter the queue $j$ up to time $t$. On the other hand, $\sum_{i=0}^n \sum_{\zeta\in \Sigma_i} O^{\leq t}_{\zeta\rightarrow j}(\omega)\leq \sum_{\xi\in \Sigma_j} O^{\leq t}_{\xi}(\omega)$ for infinitely many $t$ and almost all $\omega$ because (almost surely) queue $j$ becomes empty infinitely many times.

We obtain that
\begin{eqnarray*}
\sum_{\xi\in \Sigma_j} O_{\xi} & = & \sum_{\xi\in \Sigma_j} \lim_{t\rightarrow{} \infty} \frac{O^{\leq t}_{\xi}(\omega)}{t} \\
 & = & \lim_{t\rightarrow{} \infty} \frac{\sum_{\xi\in \Sigma_j} O^{\leq t}_{\xi}(\omega)}{t} \\

 & = & \lim_{t\rightarrow{} \infty} \frac{\sum_{i=0}^n \sum_{\zeta\in \Sigma_i} O^{\leq t}_{\zeta\rightarrow j}(\omega)}{t} \\
 & = & \sum_{i=0}^n \sum_{\zeta\in \Sigma_i}\lim_{t\rightarrow{} \infty} \frac{O^{\leq t}_{\zeta\rightarrow j}(\omega)}{t} \\
 & = & \sum_{i=0}^n \sum_{\zeta\in \Sigma_i}
 \lim_{t\rightarrow{} \infty} \frac{O^{\leq t}_{\zeta}(\omega)}{t}\cdot
 \lim_{t\rightarrow{} \infty}  \frac{O^{\leq t}_{\zeta\rightarrow j}(\omega)}{O^{\leq t}_{\zeta}(\omega)}  \\
 & = & \sum_{i=0}^n \sum_{\zeta\in \Sigma_i} O_{\zeta}\cdot A_{\zeta j}
\end{eqnarray*}
Here the last equality follows from Claim~1 and the fact that
$\lim_{t\rightarrow{} \infty}  \frac{O^{\leq t}_{\zeta\rightarrow j}(\omega)}{O^{\leq t}_{\zeta}(\omega)}$ is
the average number of jobs for queue $j$ produced by firing $\zeta$, i.e., $A_{\zeta j}$.
\end{proof}
\begin{claim}
For every $i\in \{1,\ldots,n\}$ we have
\begin{equation}\label{eq:cap}
\frac{\sum_{\xi\in \Sigma_i} O_{\xi}}{\mu_{i}}<1
\end{equation}
\end{claim}
\begin{proof}
Intuitively, we show that $\frac{\sum_{\xi\in \Sigma_i} O_{\xi}}{\mu_{i}}+\pi(\boldsymbol{0})$ is equal to the proportion of time in which either the queue $i$ operates a job or all queues are empty. As this proportion is at most $1$ and $\pi(\boldsymbol{0})>0$, we obtain the desired result.

Formally, denote by $T_n$ the total amount of time in which the first $n$ jobs are processed by queue $i$ (by this we mean the total time from the beginning of the computation needed to finish $n$ jobs using the ``machine'' operating queue $i$). Denote by $N_j$ the total time it takes to process the $j$-th job from queue $i$ (by this we mean the time the ``machine'' actively spends by processing the job).

Observe that for almost all runs $\omega$ we have that $\lim_{n\rightarrow \infty}
\frac{\sum_{j=1}^{n} N_j(\omega)}{n}$ is the average processing time of the queue $i$ which is $\frac{1}{\mu_i}$, and that
$\frac{n}{T_n(\omega)}$ is equal to
\[
\frac{\sum_{\xi\in \Sigma_i} O^{\leq T_n(\omega)}_{\xi}}{T_n(\omega)}
\]
which means that by Claim~1,
\[
\lim_{n\rightarrow \infty}\frac{n}{T_n(\omega)}\quad =\quad
\lim_{n\rightarrow \infty} \frac{\sum_{\xi\in \Sigma_i} O^{\leq T_n(\omega)}_{\xi}}{T_n(\omega)}\quad = \quad \sum_{\xi\in \Sigma_i} O_{\xi}
\]
Thus
\begin{equation}\label{eq:util}
\lim_{n\rightarrow \infty}
\frac{\sum_{j=1}^{n} N_j(\omega)}{T_n(\omega)}\quad = \quad \lim_{n\rightarrow \infty}
\frac{\sum_{j=1}^{n} N_j(\omega)}{n}\cdot \lim_{n\rightarrow \infty}\frac{n}{T_n(\omega)}\quad = \quad
\frac{\sum_{\xi\in \Sigma_i} O_{\xi}}{\mu_i}
\end{equation}
Denote by $E_n$ the total amount of time the network spends in state $\boldsymbol{0}$ before queue~$i$ finishes $n$ jobs (by this we mean the sum of all time intervals up to time $T_n$ in which all queues are simultaneously idle before $n$ jobs are finished by the ``machine'' operating queue $i$).
Intuitively, $\lim_{n\rightarrow \infty} \frac{E_n(\omega)}{T_n(\omega)}$ is equal to the proportion of time spent in $\boldsymbol{0}$ which is equal to $\pi(\boldsymbol{0})>0$. More precisely, by the Ergodic Theorem, see~Theorem 3.8.1~of~\cite{No98}, for almost all runs $\omega$ we have
\begin{equation}\label{eq:invzero}
0\quad <\quad \pi(\boldsymbol{0})\quad = \quad \lim_{t\rightarrow \infty} \frac{1}{t} \int_0^t I[\boldsymbol{x}(\omega)=\boldsymbol{0}](s) ds\quad = \quad
\lim_{n\rightarrow \infty} \frac{E_n(\omega)}{T_n(\omega)}
\end{equation}
Finally, by (\ref{eq:util}) and (\ref{eq:invzero}),
{
\begin{align*}\label{eq:proportion}
\frac{\sum_{\xi\in \Sigma_i} O_{\xi}}{\mu_i}\ & < \
\frac{\sum_{\xi\in \Sigma_i} O_{\xi}}{\mu_i}+\pi(\boldsymbol{0})\ =\ \\ &
 \frac{\sum_{j=1}^{n} N_j(\omega)}{n}\cdot \lim_{n\rightarrow \infty}\frac{n}{T_n(\omega)}+
\lim_{n\rightarrow \infty}\frac{E_n(\omega)}{T_n(\omega)}
\ = \
\lim_{n\rightarrow \infty}
\frac{\sum_{j=1}^{n} N_j(\omega)+E_n(\omega)}{T_n(\omega)}
\ \leq \ 1
\end{align*}
}
\end{proof}
\begin{claim}
For every $i\in \{1,\ldots,n\}$, $\rho_i=\frac{\sum_{\xi\in \Sigma_i} O_{\xi}}{\mu_i}$.
\end{claim}
\begin{proof}
By the Ergodic Theorem, see~Theorem 3.8.1~of~\cite{No98}, and by~(\ref{eq:util}), for almost all runs $\omega$ we have
\begin{align*}
\rho_i\quad = \quad \lim_{t \to \infty} & \Pr(\boldsymbol{x}_i(t) \ne 0)\quad  = \quad \sum_{\boldsymbol{x}\in \mathbb{N}^n:\boldsymbol{x}_i\not =0}  \pi(\boldsymbol{x})\quad \\ & = \quad
\lim_{t\rightarrow \infty}  \frac{1}{t} \int_0^t I[\boldsymbol{x}_i(\omega)\not = 0](s) ds
\quad  = \quad \lim_{n\rightarrow \infty}
\frac{\sum_{j=1}^{n} N_j(\omega)}{T_n(\omega)}\quad =\quad\frac{\sum_{\xi\in \Sigma_i} O_{\xi}}{\mu_i}
\end{align*}
\end{proof}

\noindent This finishes a proof of Lemma~\ref{prop:erg-traffic}.

redpajama_set_name: RedPajamaArXiv


From time to time, participants in the college's study abroad to Nishinomiya, Japan, led by Tom Salsbury, will be giving updates on their experiences. This one was written by preservice teacher Gracie Lee, and received no editing from the college.
And we are off to another adventure in Japan! Today's journey would begin a little later as we all decided that some much needed sleep would be necessary.
After waking up, showering, and eating breakfast, we were off to see the Himeji Castle. Boy was it a sight to see. It was so beautiful and well designed. Steep stairs and low doorway entries accompanied the castle. After taking lots of pictures and enjoying the view, it was time for lunch. We decided to eat together for another group meal. It was delicious! I had curry for the third day in a row and it was magnificent! After eating lunch, the group decided to split up. Some of us went to the zoo, while others went on adventures of their own. To wrap up the day at the castle, a couple of us decided to take a walk through the Nishi-Oyashiki-Ato Garden. The garden was huge! There were at least 12 different types of gardens at the Nishi-Oyashiki-Ato Garden. Lots of fish, flowers, and trees made for a wonderful afternoon. After the garden, it was time to catch the train and head back to the Hostel.
It sure was a great Saturday in Japan! The weather was perfect, not too hot and not too cold. It's sad to think that our adventure is coming to an end, but we all have made the best of our journey in Japan.


YEREVAN. – The American dollar's (USD) exchange rate against the Armenian dram (AMD) comprised AMD 483.80/$1 in Armenia on Friday; this is up by AMD 0.32 from Thursday, informed the press service of the Central Bank of Armenia.
The exchange rate for one euro was AMD 554.58 (down by AMD 2.58), that of one British pound totaled AMD 630.39 (down by AMD 4.23), and the rate of one Russian ruble made up AMD 7.37 (down by AMD 0.01) in the country.
In addition, one gram of silver, gold and platinum amounted to AMD 227.72, AMD 19,104.65 and AMD 13,026.07, respectively.


Well Done to everyone today brilliant job time keepers, marshals, signs and racers that all took part.
Poole Wheelers celebrated 2018 with its annual dinner and prize presentation at Salterns Hotel on 24th November with lots of members and guests attending.
Next year Poole Wheelers will be supporting the local charity, AboutFace, which provides support for patients who have been diagnosed or living with head and neck cancer. Fellow wheeler, Robin Darch, already organised a ride in support on 17th November in aid of this and the club will continue to support in the coming year.
Thanks to Les Pick for being master of ceremony and to Ellie Rendell for handing out the trophies. Photographs courtesy of John Pick.
Isabel Sharp won the 10-mile National Youth Championship at the RTTC finals staged in Norfolk on Saturday 8th September! Not content with just being National Champion, Isabel also clocked a new the GHS Championship Record… This is an extraordinary achievement from a rider who is still only 13!
Poole Wheelers also took home the team price with Tom, Jamie and Isabel, who all also won their respective age groups. Their combined winning time of 1:01:52 was also a new GHS Championship Record. That's a lot of winning!
This caps off an extraordinary summer for our youth riders, who have been competing in a range of races in the UK and abroad. Jamie even won the Kids-Tour Berlin 2018, a four stage race, as part of the international Cannibal Team. After a fantastic performance in individual and Team time trials, a road race and a criterium race, Jamie won the Yellow Jersey and Cannibal Team won the Team Classification!
Congratulations from everyone in Poole Wheelers to all our youth riders!
It's been a busy 2017 for the youth riders of the club on the track and road.
It all started back in January with the National Icebreakers in Newport. We had many riders competing across the 3 weekends gaining some awesome results showing off the club colours. These riders were Oliver P, Digby, Jamie, Charlotte, Tom and Lucy.
The National Youth Circuit Series got under way at Hog Hill. This series carried on throughout the summer months with some riders travelling across the country from London to the Isle of Man, Morecambe and Lancaster, Hillingdon, Stirling and finally Scarborough. Some really tough racing for our riders, gaining huge amounts of experience with Lucy finishing 4th overall against the country's best U16 Girls.
We also had Tom and Jamie travel down to Devon for some regional youth racing both achieving highly each event and doing the club very proud!
Easter brought around a few big races for the youth riders with Lucy competing in the Youth Tour of Scotland for the South and then many racing at the Castle Combe Easter Classic. In fact, we had a rider in nearly every age category!
April also brought the first of the regional youth omniums in Portsmouth, followed by Brighton and of course Poole Wheelers very own event at Bournemouth Velodrome. Our event was incredibly well organised by Simon and Michelle Pettifer which made for the most enjoyable omnium yet! Thanks again to all the sponsors too!
Our riders competing in these included Jamie, Charlie P, Oliver P, Digby, Patrick, Thom-Eidar, Charlotte, Tom, Lucy, Dan, Oliver G, Oliver T, Evie, Ben and Charlie A. For some of our riders it was their first ever race and they sure did everyone proud!
Not only was the team spirit high, but the talent was clearly recognised with Jamie, Oliver G, Evie, Lucy, Oliver P and Charlie P all gaining podium spots across the three rounds.
Jamie and Lucy earned enough points to qualify for the National Omnium Final at Herne Hill. Both showed the PW colours with strength and determination among the country's best riders.
Throughout the summer we had a number of leagues that our youth riders were attending such as Odd Down, Goodwood, Thruxton, Portsmouth circuits and the Winchester Park and Rides.
Winchester Criterium included the Southern Regional Road Championships again this year with storming rides from the youngsters including a podium finish from Oliver G, and a top 5 from Charlie P and Jamie along with all our youths giving it 100%.
The summer was a big one for our riders. Lucy and Jamie both competed in the London Prudential Youth Grand Prix at the Olympic Park for the South Team. First time in a team for Jamie and both performing to their best as always.
Tour of Assen for Tom, Jamie, Oliver G, Ben, Oliver P and Charlie P gave some great experience in Holland and some of the toughest racing yet! There's a great article written by Jamie on our website.
At the same time as Assen, Lucy was racing in the National Youth Track Championships in Newport, a long draining week but plenty of experience gained each day. As we came to the end of the long season we had the UK School Games finals for Lucy and the rest of Team South. She and the other girls raced brilliantly gaining 3rd overall after the short crit races and 3rd by a fraction of a second in a gruelling team time trial. Lucy herself gained 2nd in the sprints day and 8th in her final youth road race.
Our final track race for the youth was for Tom and Lucy in the Inter-Regional Track Championships up in Glasgow. Both doing their bit for the team in a tough weekend of racing.
Many of the youth riders have taken part in time trials too over the summer and there are details of those on our Time Trial page. Three riders – Tom, Jamie and Izzy – recently won their categories at the National Closed Circuit competition. So watch this space for further wins.
What a year it has been for all our youth riders with ups and downs for everyone. It's all learning and amazing experience, and a big thank you to all the organisers and volunteers at all the events across the country.
And not forgetting Graham our coach and the parents for the constant support and encouragement throughout the season. Thank you!
Graham on his track bike at Bournemouth joining in our fun!
Not content with holding all three club TT records over 10, 25 and 50 miles, Sam Wadsley decided to knock another 22 seconds off his 10 mile record to an astonishing 19:00 at the Paceline RT 10 on the P881r Griggs Green course. After the ride he thanked Greg Parker Cycle Coaching for all his help this season.
Sam's efforts have not gone unnoticed and it was announced earlier today that he has joined Primera-TeamJobs Senior team for the 2018 season! Primera announced "it is pleasure to have such a talented young rider on the team", and that he is "looking forward to being part of a close-knit team and would love to achieve a top 10 in a national TT event". Sam will remain in contact with Poole Wheelers as a second claim member of course, and will be joined in the Primera ranks by another Poole Wheelers second claim, Martin Rowland, who in 2017 teamed up with Ryan Weston as UK-Biking – Bournemouth Cycleworks – Trek Cycling Team sponsored riders.
Sam has been on a tremendous journey in Poole Wheelers since his first TT on 17th April 2013. Legend has it the young chap turned up to one of our club TTs pleading to have a go. Craig Weston did a 2-up with him to clock in a 27:43 and fondly recalled: "I even said stay on my wheel for 9 miles and with a mile to go ride past me and give everything you have, you lasted about 20 yards before blowing up." His talent was obvious though, as he finished the season with a PB of 22:47 and joint winner of our Third Division. He won our First Division in 2014, and has won the Premier Division for the past three seasons (2015, 2016, 2017 – last one unofficial / unconfirmed). In 2015 he also won the club's Rothwell league, and he of course picked up most of the junior trophies on the way. He will be missed by everyone in the club, though fortunately it means someone else will get the chance to feel what its like to lift any number of the club trophies Sam has dominated in the last few years.
Best of luck from everyone in the club! You are a giant among men.
You can view Sam's record 10 ride on Strava, and our club records on the PW results website.
Featured photo is from one of Sam's previous 25 mile club record rides.
Sam Wadsley continued his magnificent season yesterday by setting a new Poole Wheeler's club record for a 10 mile time trial, to go with his 25 mile and 50 mile club records set earlier in the season.
The new club record is a blisteringly fast 19:22 set on 27th August at the Team Swift Charity Event on the V718/10 course. This is a six second improvement upon the previous club record (19:28) set by late Gary Dighton on our own P415/10 course on 14th July 2013. Sam's previous PB on a 10 was 19:48 set on the P881R/10 course 14th June earlier this year.
Earlier today Sam Wadsley improved his 25 mile TT club record, with a new PB of 49:12! The new club record was achieved on 20th August at the "www.realteam.co.uk (Men)(Chq To M Heritage-Owen)" race, again on the R25/3H course. Full results will be published on the CTT website in due course.
This is of course a new personal best for Sam and an impressive 12 second improvement on his previous club record on the distance set at the RTTC National Championship on 6th August.
Check out his record breaking ride on Strava.
Congratulations, Sam, and keep them coming!
Sam Wadsley set a new Poole Wheelers club record for a 25 mile TT at the RTTC National Championship on 6th August on the R25/3H course. His time of 49:31 means he is the first Poole Wheelers to have recorded a sub-50 25 mile TT (full club stats on our results page). Check out Sam's record breaking ride on Strava.
The club record gave Sam a 40th place overall. Fellow Poole Wheeler, Steven Pink, came in 96th place with a time of 52:49.
You can read the full race report and access detailed results on the CTT website.


9 out of 10 based on 602 ratings. 2,799 user reviews.
THIS IS COMPLETE AUDI S4 2001 REPAIR AND SERVICE MANUAL . Fixing problems in your vehicle is a do-it-approach with the Auto Repair Manuals as they contain comprehensive instructions and procedures on how to fix the problems in your ride. Also customer support over the email , and help to fix your car right the first time !!!!! 20 years experience in auto repair and body work.
Audi S4. The Audi S4, whose production first started in the year 1991, is a high performance variant to the Audi A4 compact executive car model. Originally produced only till 1994, the S4 was a performance-oriented version of the manufacturer's 100 saloon/sedan.
2001 AUDI S4 Service and Repair Manual. $26. VIEW DETAILS. 2002 Audi S4 Service & Repair Manual Software. $24. VIEW DETAILS. 2002 AUDI S4 Service and Repair Manual. $26. VIEW DETAILS. 2003 - 2006 AUDI S4 Parts LIST CATALOG. $16. VIEW DETAILS. 2003 AUDI S4 Service and Repair Manual. $26.
wwwsgeek››Audi Repair Manual›S4 PartsEvery Audi S4 Repair Manual is specifically focused on the car it was produced for, organized by the year, make, and model. The Audi S4 Repair Manual is a helpful manual that includes detailed directions on how to repair a car or truck. An Audi S4 Repair Manual is as important as a set of good tools for working on a car.


text:
Macaws are here: great books by post for 12 to 14-year-olds
We're delighted to have launched a new reading level for 12 to 14-year-olds. It looks and feels a bit different to our existing subscriptions but our focus on sending the very best books and encouraging a love of reading remains.
We know from personal experience that it's hard to find books that feel grown-up enough for our 12-year-olds but don't venture too far into the edgier realms of relationships, peer pressure and angst found in many young adult books.
Research shows that the quality and quantity of reading children do drops significantly as they progress through secondary school, so finding the right books to keep them engaged and enthusiastic feels more important than ever.
A NEW SUBSCRIPTION EXPERIENCE FOR 12 to 14-YEAR-OLDS
We're excited to curate a selection of brilliant, varied and unusual books for our Macaw subscribers to explore. We carefully consider every book we choose and only ever send titles we'd happily share with our own kids.
Reflecting their growing independence, Macaws have the option to choose between two books each month, charting their own course through our recommendations. You can also keep the element of surprise if you prefer or even upgrade to receive both books each month.
Each book is accompanied by book club-style questions, activity ideas and further reading recommendations.
I love it - how can we sign up?
Our Macaw subscription is now live. Sign up today and receive your first book next month!
SET UP YOUR MACAW SUBSCRIPTION
We've had a think about questions you might have and answered them below. But if you need any more information, please feel free to contact us.
Who is this subscription for?
This is an ideal book subscription for 12 to 14-year-olds who are in the early years of secondary school. We pick books that can be enjoyed equally by both girls and boys.
Enthusiastic readers will enjoy the variety of titles we send and we hope will discover new favourite authors and genres.
For more reluctant readers the subscription is a great way to keep them engaged with books – whether they read them independently or you share one great book together each month.
How is it different from Cockatoos?
The books our Macaws receive wouldn't be suitable for Cockatoos, the youngest of whom are only 8 years old. The books are meatier and touch on more complex moral, social and emotional issues.
Macaws also have the option to choose between two different books each month, charting their own course through our recommendations. Subscribers that have their own email address can manage their selections independently and we encourage them to submit their reviews, comments and questions.
What sort of books do you send?
We pick books that we feel sit comfortably between the middle grade (usually aimed at 8 to 12-year-olds) and young adult categories. They are challenging and thought-provoking with more complex themes than most middle grade novels but without focusing too much on the teenage angst and romantic struggles common in YA books.
As ever, we focus on presenting a wide variety of books covering many genres and introducing subscribers to authors and stories they may not otherwise have tried. We've developed great relationships with publishers over the past 3 years and work with them directly to discover the perfect books for this age group.
Why have you developed this?
We know that 12 to 14 years old can be a tricky age for many reasons, but when it comes to reading we've identified a specific problem. At this age, many kids are feeling a bit too old for classic middle grade novels (which we'd send our Cockatoos) but aren't ready for all that Young Adult (YA) novels have to offer, particularly the focus on relationships and teenage angst.
When they can't find the right books, it's all to easy to return to primary school favourites or stop reading all together. But even reading for just 15 minutes a day can make a huge difference, so finding great, age-appropriate books is crucial.
As our own children enter this age group, we've discovered that even with our knowledge of the publishing landscape it's hard to find those goldilocks books that aren't too young, aren't too old, but are just right!
So, we've set out to help other parents in the same boat by carefully curating book selections for this age group that will keep kids excited and engaged in reading for the sheer fun of it.

redpajama_set_name: RedPajamaCommonCrawl


text:
Q: How to stop UIScrollView when fingers are lifted (Swift 4) How do I stop a scrollView when the user lifts their fingers instead of just bouncing back to the top?
var displayData = UITextView()

func displayTallTable() {

    displayData.text = outputString

    // getFrameBounds (x, y, width, height)
    displayData.frame = CGRect(x: x, y: y, width: w, height: h)

    self.addSubview(scrollView)
    scrollView.addSubview(displayData)

    let g = self.safeAreaLayoutGuide

    scrollView.leadingAnchor.constraint(equalTo: g.leadingAnchor).isActive = true
    scrollView.trailingAnchor.constraint(equalTo: g.trailingAnchor).isActive = true
    scrollView.topAnchor.constraint(equalTo: g.topAnchor).isActive = true
    scrollView.bottomAnchor.constraint(equalTo: g.bottomAnchor).isActive = true
}

I can drag the view up but when I lift my fingers, it just bounces back to the top.
So, I added UIScrollViewDelegate to the class:
class TallView: UIView, UIScrollViewDelegate { ... }
and have tried the following, none of which is called:
func scrollViewWillBeginDecelerating(_ scrollView: UIScrollView) {
    debugPrint("scrollViewWillBeginDecelerating")
}
func scrollViewDidScroll(_ scrollView: UIScrollView) {
    debugPrint("scrollViewDidScroll")
}
func scrollViewWillBeginDragging(_ scrollView: UIScrollView) {
    debugPrint("scrollViewWillBeginDragging")
}
func scrollViewWillEndDragging(_ scrollView: UIScrollView, withVelocity velocity: CGPoint, targetContentOffset: UnsafeMutablePointer<CGPoint>) {
    debugPrint("scrollViewWillEndDragging")
}
func scrollViewDidChangeAdjustedContentInset(_ scrollView: UIScrollView) {
    debugPrint("scrollViewDidChangeAdjustedContentInset")
}

It seems that :
func killScroll() {
    self.scrollView.isScrollEnabled = false;
    self.scrollView.isScrollEnabled = true;
}

(from: How can I programmatically force-stop scrolling in a UIScrollView?) should do the trick, but I don't know what should be calling it.
What am I missing?

A: If I understand you correctly, you may want this this effect:
func scrollViewDidScroll(_ scrollView: UIScrollView) {
        if !scrollView.isTracking {
            let contentOffset = scrollView.contentOffset
            // if you want to locate to the top, you could set: let contentOffset = CGPoint.zero
            scrollView.setContentOffset(contentOffset, animated: false)
        }
    }
}

redpajama_set_name: RedPajamaStackExchange


The whole cooking process is completely automated machine controlled by a microcomputer. This cooker is most appropriate for cooking small amount of rice. The microcomputer carefully controls each cooking step to provide ideal conditions and even cooking. This is a cabinet design for small business ans those with limited installation space.
-Radial burner, cooks rice evenly.
-The cooking adjustment function, caters to different rice menus.
-A diversified range of cooking modes: plain rice, porridge, musenmai(rinse-free rice) and etc.
-Self-diagnotic function detects flameout, accidental fire, power out gas, empty cooking, etc and automatically shuts off the gas and gives out alarm light and buzz.
-The machine is rated Grade A by fire protection testing of gas appliances.
-(Carbon heaters) enhance thermal efficiency by almost 30%. It can cook a variesty of rice products from white rice to rinse-free rice and even pilaf.


Our work for Glass Aircraft Model , Glass Car Model , Aircraft Model Gift , You may obtain the lowest price tag here. Also you may get high quality products and exceptional provider here! Please do not hesitate to call us!
"It really is our obligation to satisfy your requirements and efficiently serve you. Your fulfillment is our greatest reward. We're hunting forward to your check out for joint development for Glass Aircraft Model , Glass Car Model , Aircraft Model Gift , Customer's satisfaction is always our quest creating value for customers is always our duty a long term mutual-beneficial business relationship is what we've been doing for. We are an absolutely reliable partner for yourself in China. Of course other services like consulting can be offered too.


Display a login screen and allow the user to enter a user name and the corresponding password. The password will be obscured using asterisks.
The provided user name and password will be stored in the username and password configuration settings.


You are warmly welcome to the Faculty of Social and Management Sciences (FSMS). The Faculty came into being at the inception of the University in 1982, and it exists to facilitate the education, training and production of Social Scientists, Managers of industry, Geographers, Political Scientists, Sociologists, Psychologists, Economists as well as those who may want to be employers of labour in future. The Faculty is also interested in manpower development with the sole aim of addressing the emerging global challenges in all facets of human endeavour. Therefore, its programmes are designed to impart theoretical and practical knowledge of the kind that will encourage self-reliance in private individuals as well as in those who may want to operate in the public sector.
The Faculty houses eight Departments which are: Accounting, Banking & Finance, Business Administration, Economics, Geography and Planning Sciences, Political Science and Public Administration, Pure and Applied Psychology and Sociology. Mass Communication Department will soon move from the Faculty of Arts to the Faculty of Social and Management Sciences. With this new development, the number of Departments in the Faculty is set to increase to nine. The Faculty offers both undergraduate and postgraduate programmes. Undergraduate programmes leading to the award of B.Sc. (Hons) are offered in all the Departments in the Faculty. Postgraduate programmes leading to the award of the M.Sc. and Ph.D are also offered in all the Departments with the exception of departments of Accounting and Business Administration.
Each Department has its own handbook containing general information on such things as admission requirements, registration procedures, regulations governing the administration and conduct of examinations, regulations governing the award of degrees (undergraduates and postgraduates) as well as graduation requirements. The Faculty also has its own handbook that introduces students to the Faculty. In order to produce quality industrial managers for our society, the Faculty in collaboration with the SIWES unit of the university has established a tradition of compulsory internship programme deeply enmeshed in its academic programmes for her students to be self reliant and relevant in the global market place.
Please feel free to contact us for any information you require about our programmes in the Faculty.


text:
The 2019–20 season was Al-Shorta's 46th season in the Iraqi Premier League, having featured in all 45 previous editions of the competition. Al-Shorta participated in five competitions: the Iraqi Premier League (as defending champions), the Iraq FA Cup, the Iraqi Super Cup, the AFC Champions League and the Arab Club Champions Cup.

Al-Shorta won the Iraqi Super Cup for the first time in their history, beating Al-Zawraa on penalties after a 1–1 draw. They also reached the quarter-finals of the Arab Club Champions Cup, their best performance at the tournament since they were crowned champions in the 1981–82 season. Al-Shorta only played a total of six League matches and one FA Cup match in the season as both competitions were postponed for several months due to the 2019–2020 Iraqi protests and later cancelled due to the COVID-19 pandemic. The pandemic also led to their remaining four AFC Champions League group stage matches being postponed to the 2020–21 campaign.

Squad
Numbers in parenthesis denote appearances as substitute.

Personnel

Technical staff

Management

Kit
Supplier: Givova

Transfers

In

Out

Competitions

Iraqi Super Cup

Iraqi Premier League

Original season

Restarted season

Iraq FA Cup

AFC Champions League

Al-Shorta played two 2020 AFC Champions League matches in the 2019–20 season before their remaining matches in the competition were postponed to the following campaign due to the COVID-19 pandemic.

Group stage

Arab Club Champions Cup

Round of 32

Round of 16

Quarter-finals

References

External links
Al-Shorta website
Al-Shorta TV
Team info at goalzz.com

Al-Shorta SC seasons

redpajama_set_name: RedPajamaWikipedia


Giraffe - Windows Mobile App Catalog is closed at January 8, 2019, 23:00(JST).
copyright © 2019 妻がライバル all rights reserved.
©BANDAI NAMCO Arts Inc. All Rights Reserved.
Copyright © 2018 声優プロダクション Ability Soul Pro. All rights reserved.
2018/03/09 18:54:30 F1 Mods - MMG, FSONE, Formula Series One, Mak Modding Group, rFactor, Racing, F1, Video Games, Mod, Simulation, Gaming, Tickets.
As FSONE formula one 2008 mod is near to be released, we take a look at almost all of the teams tv cam shots from Codex. I believe the rest is on it's way. Keep your eyes open for this mod's soon release in both single player and server edition modes.