operating at full capacity, it processes packets more quickly on average than the adversary can add them.) The network is considered to be [*stable*]{} if the expected load remains bounded, i.e. if $\sup_n
\E(X_n) < \infty$. In this context, our Corollary \[cor:X\_0\] may be interpreted as saying that a queueing network in the presence of a stochastic adversary is guaranteed to be stable, provided it satisfies the load condition (C1), and also the moment condition (C2) for some $p>2$. On the other hand, if $p \le 2$ then there is no such guarantee.

We note that there has been some previous work on related questions. For example, Hastad et al. (1996) consider bounds on $\sup_n \E(X_n)$ for certain time-homogeneous [*Markovian*]{} systems which correspond to particular “backoff protocols” for resolving ethernet conflicts. Close to our work, Hajek (1982) investigates bounds on hitting times for general random sequences having bounded [*exponential*]{} moments, and derives corresponding bounds on exponential moments of the hitting times; his work may thus be seen, roughly, as the $p\to\infty$ limit of our bounds.

Finally, we note that while the notion of “stability” considered here (namely, that $\sup_n \E(X_n) < \infty$) is different from that of Markov chain stability 