Abstract

We present a survey of the main ergodic theory techniques which are used in the study of iterates of monotone and homogeneous stochastic operators. It is shown that ergodic theorems on discrete event networks (queueing networks and/or Petri nets) are a generalization of these stochastic operator theorems. Kingman's subadditive ergodic theorem is the key tool for deriving what we call first order ergodic results. We also show how to use backward constructions (also called Loynes schemes in network theory) in order to obtain second order ergodic results. We present a review of systems within this framework, concentrating on two models, precedence constraint networks and Jackson type networks.

Introduction Many systems appearing in manufacturing, communication or computer science accept a description in terms of discrete event systems. A usual characteristic of these systems is the existence of some sources of randomness affecting their behaviour. Hence a natural framework to study them is the one of stochastic discrete event systems.

In this survey paper, we are concerned with two different types of models. First, we consider the study of the iterates Tn o Tn− 1 o … o T0, where Ti: ℝk × Ω → ℝk is a random monotone and homogeneous operator. Second, we introduce and study stochastic discrete event networks entering the so-called monotone-separable framework. A subclass of interest is that of stochastic open discrete event networks.

It will appear that these models, although they have been studied quite independently in past years, have a lot of common points. They share the same kind of assumptions and properties: monotonicity, homogeneity and non-expansiveness.