Past Awards
The award recognizes seminal research contributions that Marty Reiman and Ruth Williams have made, over the past several decades, to the theory and applications of “stochastic networks/systems” and their “heavy traffic approximations.” These profound contributions have been and have further led to breakthroughs in stochastic operations research in general, and queueing theory in particular. Their analysis of complex stochastic networks under conditions of heavy traffic, has not only led to the discovery and rigorous articulations of properties of the networks, and penetrating insights into the operational laws of real-world systems they model, but also led to deep theoretical developments in the study of reflected diffusions.
Starting with his Ph.D. thesis, Marty Reiman has had a lasting impact on the heavy traffic analysis of queueing systems. In it, he identified and characterized the diffusion limit of a generalized Jackson queueing network in heavy traffic. Specifically, this limit is a reflected Brownian motion (RBM) in the non-negative orthant, namely a multi-dimensional Brownian motion restricted to the non-negative orthant by oblique reflection at the orthant’s boundary. In companion and subsequent works, Reiman enunciated two heavy-traffic principles that rank among the most important and elegant contributions of heavy traffic theory: the snapshot principle, which relates waiting- and sojourn-times processes to queue-lengths, and the phenomenon of state-space collapse, that is, dimensionality reduction in the effective descriptions of the evolution of a stochastic system in heavy traffic.
Reiman’s research is characterized by deep intuition and penetrating understanding of the physical and mathematical laws that govern the systems that he studies. These virtues are clearly manifested in the following illustrative examples: the averaging principle for polling systems, jointly with Coffman and Puhalskii; the interpolation approximation, with Simon, that combines their light-traffic and the familiar heavy-traffic viewpoints; the study, motivated by call centers, of operational regimes (efficiency-driven, quality-driven and their balancing QED, namely, quality-and-efficiency driven) in many-server queueing models with abandoning customers (with Garnett and Mandelbaum); asymptotically optimal staffing of many-server queues (with Borst and Mandelbaum), e.g., square-root staffing in the Halfin-Whitt (QED) regime; the analysis in the latter regime, with Puhalskii, of the multiclass queue with phase-type service-times and static-priorities; the constant-order policy in lost-sales inventory systems with long lead times; and, jointly with Wang, his analysis of certainty equivalent control for network revenue management.
In Reiman’s work, one sees real inventiveness combined with strong mathematical and expository skills, supported by a solid command of several distinct application domains. His research has influenced and inspired work by the very best people in stochastic OR, including several previous winners of the von Neumann Theory Prize.
Ruth Williams has also had a deep and lasting impact on the study of heavy traffic analysis. This started with her PhD thesis and further work on RBM in a wedge, establishing semimartingale, local time, excursion and recurrence properties. It continued with her establishing a multidimensional generalization that identified necessary and sufficient conditions for weak existence and uniqueness in law of RBMs in the nonnegative orthant, which provides an alternative to the pathwise theory of Harrison and Reiman; and it culminated in the development of invariance principles (analogous to the Donsker-Varadhan invariance principle for the classical (unreflected) Brownian motion). This enabled the identification and verification of diffusion approximations, for multiclass queueing networks under certain state-space collapse conditions.
The above research provided the foundations for subsequent significant research, by Williams and others. One example is queues operating under a processor-sharing service discipline. Jointly, first with Gromoll and Puha and later with Puha and Stolyar, Williams described the evolution of such systems by a measure-valued process that keeps track of the residual service times of all jobs. Another example is asymptotically optimal control of parallel-server systems in heavy-traffic, first under complete resource pooling (with Bell) and recently under partial pooling (with Pesic); further examples include applications, with Kelly, to the analysis of a controlled motorway in heavy traffic; and, with Kang, Lee and Kelly and later with Gromoll, to bandwidth sharing networks that model congestion of data on the internet. For the latter, Williams established fluid limits and subsequently discovered that networks with proportional fairness admit a product-form (and hence tractable) stationary distribution in heavy traffic.
Williams’ research is characterized by its mathematical depth and elegance. She has greatly influenced researchers in operations research, stochastic processes and mathematics, doing so through survey lectures and articles that are exemplary in clarity and insight. Her expositions have introduced the field to researchers and described challenging open problems and directions, which have spurred further research.
In summary, Reiman and Williams have carried out pioneering research over the past several decades. This has led to fundamental breakthroughs in stochastic operations research in general, and queueing theory in particular, with a focus on stochastic networks and their behavior under heavy-traffic conditions. Their research, in which they have both influenced and built upon each other’s work, has had a lasting theoretical and practical impact that stands the test of time.
- "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