Theory Seminar
October 2, 2026 1:00PM—2:00PM
Location:
In Person
-
Reddy Conference Room, Gates Hillman 4405
Speaker:
MOR HARCHOL-BALTER,
Bruce J. Nelson Professor of Computer Science Department of Computer Science, Carnegie Mellon University
https://www.cs.cmu.edu/~harchol/
Scheduling is the primary tool we have for improving system performance without purchasing additional resources. By simply changing the order in which we run jobs, we can dramatically improve response time (both mean response time and the tail of response time). Scheduling is particularly effective in the case of heavy-tailed job size distributions, which are omnipresent and can result in very high response times. In this talk we focus on the heavy-tailed job size setting.
We will start by reviewing optimal scheduling for the single-server queue (the M/G/1), both for the mean and asymptotic tail of response time. This is well understood. We then turn to multi-server systems (the M/G/n), where almost nothing is understood on optimal scheduling. We present our new results on the first scheduling algorithms for the M/G/n which are asymptotically strongly tail optimal.
We finish by discussing newer job models, like the multi-server job model, which is representative of today’s datacenter jobs. Here we present some recent algorithms for optimal scheduling under heavy traffic.
Throughout, our emphasis will be on intuition and lessons learned.
Joint work with primarily Zhouzi Li and Alan Scheller-Wolf.
⇢ This talk is meant as a practice talk for the Markov Lecture keynote which I'm giving next month at INFORMS APS
For More Information:
korinna@cmu.edu