A LIFO queue in heavy traffic

Abstract

This paper describes the heavy-traffic behavior of an M/G/1 last-in-first-out preemptive resume queue. An appropriate framework for the analysis is provided by measure-valued processes. In particular, the paper exploits the setting of recent works by Le Gall and Le Jan.Their finite-measure-valued exploration process corresponds to our RES-measure (residual services measure) process, that captures all the relevant information about the evolution of the queue, while their height process corresponds to the queue-length process. The heavy-traffic “diffusion” approximations for the RES-measure and the queue-length processes are derived under the usual second moment assumptions on the service distributions. The tightness of queue lengths argument uses estimates for the total size and height of large Galton–Watson trees.

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 — 23 citations exist upstream.

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