Computer Science Thesis Proposal
Speaker
ISAAC GROSOF
Ph.D. Student
Computer Science Department
Carnegie Mellon University
When
-
Where
In Person
Description
In modern computer systems, multiserver queues are increasingly the norm, across databases, web servers, switches, and caches. Likewise, tail performance, such as the 99th percentile of response time (latency), is increasingly important. Unfortunately, the theory of scheduling is lagging behind, only able to characterize optimal scheduling policies in simpler single-server systems such as the M/G/1, and for simpler metrics such as mean response time.
In this thesis proposal, I prove the first optimality results for scheduling in multiserver systems, in both standard models such as the M/G/k, as well as more complex concurrent-service models. On the way to such optimality results, I also prove the first bounds on mean response time for nontrivial scheduling policies in a variety of important multiserver models.
I also prove optimality results on scheduling for the tail of response time. In particular, I provide the first counterexample to disprove an important conjecture, the "FCFS strong optimality" conjecture, with my new scheduling policy, Nudge.
Thesis Committee:
Mor Harchol-Balter (Chair)
Alan Scheller-Wolf
Weina Wang
Anupam Gupta
Michael Mitzenmacher (Harvard University)
Additional Information