UC Berkeley

We study a service system in which, in each service period, the server performs the current set B of tasks as a batch, taking time s(B), where the function s(·) is subadditive. A natural definition of 'traffic intensity under congestion' in this setting is ρ := limt → ∞ t-1Es (all tasks arriving during time [0, t]). We show that ρ < 1 and a finite mean of individual service times are necessary and sufficient to imply stability of the system. A key observation is that the numbers of arrivals during successive service periods form a Markov chain {An}, enabling us to apply classical regenerative techniques and to express the stationary distribution of the process in terms of the stationary distribution of {An}.