A tale of tails: Asymptotics and Non-asymptotics in Load Balancing

# 154


Queueing Systems are hard to study in general, and except in special cases, it is not possible to exactly characterize the stationary distribution of queue lengths. Therefore, they have been studied in various asymptotic regimes, such as many server, heavy traffic and large deviations. Each of these regimes provides a different perspective on the design and performance of the system. Recent work has focused on establishing prelimit results by characterizing the rate of convergence, which enable one to translate the theoretical asymptotic results into practice. In the same spirit, we focus on the prelimit tail bounds on the queue lengths. It turns out that obtaining good nonasymptotic tail bounds bridges the gap between the various asymptotic regimes. The talk presents join-the-shortest-queue load balancing as an illustrative example. We first present an overview of results from the literature in various asymptotic regimes including some of our own prior work. We then present the recent results on nonasymptotic tail bounds. All these results are obtained using the transform method.

Prof. Siva Theja Maguluri, Georgia Tech

Siva Theja Maguluri is Fouts Family Early Career Professor and Assistant Professor in the H. Milton Stewart School of Industrial and Systems Engineering at Georgia Tech. He obtained his Ph.D. and MS in ECE as well as MS in Applied Math from UIUC, and B.Tech in Electrical Engineering from IIT Madras. His research interests span the areas of Control, Optimization, Algorithms and Applied Probability and include Reinforcement Learning theory and Stochastic Networks. His research and teaching are recognized through several awards including the “Best Publication in Applied Probability” award, NSF CAREER award, second place award at INFORMS JFIG best paper competition, Student best paper award at IFIP Performance, “CTL/BP Junior Faculty Teaching Excellence Award,” and “Student Recognition of Excellence in Teaching: Class of 1934 CIOS Award.”