Abstract: Intelligent dispatching is crucial to obtaining low response times in large-scale systems. The bulk of "power-of-d" policies studied in the literature assume that the system is homogeneous, meaning that all servers have the same speed; meanwhile, real-world systems often exhibit server speed heterogeneity. We introduce a general framework for describing and analyzing heterogeneity-aware power-of-d policies. The key idea behind our framework is that dispatching policies can make use of server speed information at two decision points: when choosing which d servers to query, and when assigning a job to one of those servers. Our framework explicitly separates the dispatching policy into a querying rule and an assignment rule; we consider general families of both rule types. We analyze mean response time and formulate novel optimization problems for the joint optimization of querying and assignment. Our analysis allows us to quantify the response time benefits that can be achieved by making full use of server speed information. Based on joint work with Jazeem Abdul Jaleel, Sherwin Doroudi, Alexander Wickeham, and Michael Xu.
Bio: Kristy Gardner is an Assistant Professor in the Computer Science Department at Amherst College. Her work primarily focuses on designing and analyzing dispatching policies for large-scale systems. She received her M.S. and PhD in 2015 and 2017 respectively, both from Carnegie Mellon University, and her B.A. in 2012 from Amherst College.
Pizza will be served.