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(\ensuremath{\tau})$ of the waiting times $\ensuremath{\tau}$ of executed tasks for this model is shown to behave asymptotically as a power law, $P(\ensuremath{\tau})\ensuremath{\sim}{\ensuremath{\tau}}^{\ensuremath{-}3∕2}$, when the average rates of task arrival $\ensuremath{\lambda}$ and execution $\ensuremath{\mu}$ satisfy $\ensuremath{\mu}\ensuremath{\le}\ensuremath{\lambda}$ (as was earlier noted empirically). For $\ensuremath{\mu}>\ensuremath{\lambda}$, $P(\ensuremath{\tau})\ensuremath{\sim}{\ensuremath{\tau}}^{\ensuremath{-}5∕2}\phantom{\rule{0.2em}{0ex}}\mathrm{exp}[\ensuremath{-}(\sqrt{\ensuremath{\mu}}\ensuremath{-}\sqrt{\ensuremath{\lambda}}{)}^{2}\ensuremath{\tau}]$.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 36 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.