A LIFO QUEUE IN HEAVY TRAFFIC

Vlada Limic

This paper describes the heavy traffic behavior of a M/G/1 {\em 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 (1997). Their finite-measure-valued {\em exploration} process, corresponds to our {\em RES-measure} (residual services measure) process, that captures all the relevant information about the evolution of the queue, while their {\em height} process corresponds to the {\em 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.