Queueing with Redundant Requests: First Exact Analysis

Mor Harchol-Balter
Professor, Carnegie Mellon University, Computer Science Department
Given on: May 21th, 2015
Venue: Packard 101
Time: 4:15pm to 5:15pm


Recent computer systems research has proposed using redundant requests to reduce latency. The idea is to replicate a request so that it joins the queue at multiple servers, where the request is considered complete as soon as any one copy of the request completes.

The performance analysis of systems with redundant requests is very hard, and only approximations and bounds exist. We will present the first exact analysis of systems with redundancy. We allow for any number of classes of redundant requests, and number of classes of non-redundant requests, any degree of redundancy, and any number of heterogeneous servers. We derive the limiting distribution on the state of the system.

We seek to understand the benefit and pain caused by redundancy and to compare redundancy with other smart resource allocation schemes. Our analysis leads to some surprising results on the effectiveness of redundancy.

Based on joint work with: Kristen Gardner, Sam Zbarsky, Sherwin Doroudi, Alan Scheller-Wolf. To appear in SIGMETRICS 2015.


Mor Harchol-Balter is a Professor of Computer Science at Carnegie Mellon University. From 2008-2011, she served as the Associate Department Head for Computer Science. Mor received her doctorate from the Computer Science department at U.C. Berkeley in 1996. She is heavily involved in the ACM SIGMETRICS research community, where she served as Technical Program Chair for Sigmetrics 2007 and as General Chair for Sigmetrics 2013. Mor’s work focuses on the design, stochastic analysis, and implementation of new resource allocation policies (load balancing policies, power management policies, and scheduling policies) for distributed systems. She recently published a textbook, “Performance Analysis and Design of Computer Systems,” which illustrates how counter-intuitive such resource allocation policies can be. Mor is a recipient of the NSF Postdoctoral Fellowship in the Mathematical Sciences, the McCandless Chair, the NSF CAREER award, multiple best paper awards, and many teaching awards. She has graduated many PhD students, most of whom are now professors in top academic institutions.