Past Awards
- "The Fluid Limit of a Heavily Loaded Processor Sharing Queue" by Gromoll, Puha & Williams, The Annals of Applied Probability, 2002, Vol. 12, 797-859
- "Invariant States & Rates of Convergence for a Critical Fluid Model of a Processor Sharing Queue" by Puha & Williams, The Annals of Applied Probability, 2004, Vol. 14, 517-554
- "Diffusion Approximation for a Processor Sharing Queue in Heavy Traffic" by Gromoll, The Annals of Applied Probability, 2004, Vol. 14, 555-611.
The Award recognizes an outstanding contribution to the field of Applied Probability during the years 2003–2006.
Queues with a Processor Sharing (PS) discipline are classical models for an egalitarian allocation of a scarce resource among competing users. PS queues first emerged, in the 60’s, as an idealization of the round-robin protocol in time-sharing computer systems. They have since found ample applications and consequently become standard models of computer and communications networks. There is a large body of literature on PS queues. All of it, with only rare exceptions, imposes the stringent parametric assumptions of Poisson arrivals and/or exponential service requirements.
In a series of three papers, Gromoll, Puha and Williams develop fluid and diffusion approximations for a PS queue with renewal arrivals and iid service requirements. These deep and insightful approximations are derived via laws of large numbers (fluid) and central limit theorems (diffusion), all within the framework of measure valued processes. Such processes arise naturally from keeping track of the residual service times of all customers in the system at any given time which, in turn, enables the recovery of traditional performance measures such as queue length and workload.
The three papers provide a meticulous elegant treatment of the measure-valued processes associated with PS queues. They solve outstanding difficult problems, which advances the state of the art of Applied Probability. They have also provided a foundation for subsequent limit theorems and approximations of additional complex systems, from many-server parallel queues that model call centers to bandwidth sharing communications networks that model the Internet.
The APS Prize Committee:
J.G. “Jim” Dai
Peter Taylor
Avishai Mandelbaum, Chair