Position: Ph.D. Candidate

Current Institution: Carnegie Mellon University

Analyzing Response Time in Systems with Redundant Requests

Reducing latency is a primary concern in computer systems. As cloud computing and resource sharing become more prevalent, the problem of how to reduce latency becomes more challenging because there is a high degree of variability in server speeds. Recent computer systems research has shown that the same job can take 12x or even 27x longer to run on one machine than another, due to varying background load, garbage collection, network contention, and other factors. This server variability is transient and unpredictable, making it hard to know how long a job will take to run on any given server, and therefore how best to dispatch and schedule jobs.

An increasingly popular strategy for combating server variability is redundancy. The idea is to create multiple copies of the same job, dispatch these copies to different servers, and wait for the first copy to complete service. A great deal of empirical computer systems research has demonstrated the benefits of redundancy: using redundancy can yield up to a 50% reduction in mean response time. As redundancy gains prominence in systems, in recent years the theoretical community has begun attempting to analyze performance in systems with redundancy. Unfortunately, most of this work provides only bounds and approximations for performance, and most makes simplifying assumptions for mathematical tractability that lead to unrealistically optimistic results.

The two major foci of my work are (1) to derive the first exact analysis of response time in systems with redundancy, and (2) to develop a more realistic model of redundancy and to design and analyze dispatching and scheduling policies that yield good performance within this model. We show that even in a realistic setting in which running multiple copies of the same job adds load to the system, it is possible to design redundancy policies that provably improve performance.

Kristy is a PhD candidate in the Computer Science Department at Carnegie Mellon University, where she works with Mor Harchol-Balter. Her research interests are in queueing theory and performance modeling of computer systems. Her current work focuses on analyzing performance in systems with redundant requests, in which jobs create multiple copies of themselves but require only one copy to complete service. Kristy received an NSF Graduate Research Fellowship in 2012 and a Google Anita Borg Memorial Scholarship in 2016. She obtained her B.A. in Computer Science from Amherst College in 2012.