Power-law and exponential tails in a stochastic priority-based model queue

Abstract

We derive exact asymptotic results for a stochastic queueing model in which tasks are executed according to a continuous-valued priority. The distribution P(τ) of the waiting times τ of executed tasks for this model is shown to behave asymptotically as a power law, P(τ)∼ τ-3 2, when the average rates of task arrival λ and execution μ satisfy μ≤λ (as was earlier noted empirically). For μ>λ, P(τ)∼ τ-5 2 exp[-(μ-λ) 2 τ]. © 2008 The American Physical Society.