A Tale of Two Traffics: Optimizing Tail Latency in the Light-Tailed M/G/k

We consider the problem of scheduling to minimize asymptotic tail latency in the M/G/ k queue with light-tailed job size distribution. This problem combines the challenges of scheduling for tail latency and scheduling in multiserver queues, but there is hope. In the simpler setting of the single-server M/G/1, the recently proposed ɣ-Boost policy is tail constant optimal, and it has excellent empirical tail latency. And for the simpler objective of mean latency, it is known that the optimal policy in the M/G/1, namely SRPT (shortest remaining processing time), is also excellent in the M/G/ k : it is provably optimal in heavy traffic and has state-of-the-art empirical performance in lighter traffic. One might therefore hope that ɣ -Boost is similarly effective in the M/G/ k , but our results paint a more complicated picture. In heavy traffic, we prove that ɣ -Boost is indeed tail constant optimal. We also prove an analogous result for scheduling with unknown sizes, where ɣ -Boost is replaced by its unknown-size counterpart. But in lighter traffic, we find empirically that ɣ -Boost can be even worse than FCFS (first-come, first-served). This is a significant shortcoming, as the boundary between ''lighter'' and ''heavy'' traffic occurs at higher load when the number of servers k is larger. To overcome this, we design a new variant of ɣ -Boost that outperforms the original by, counterintuitively, giving more priority to larger jobs. The new variant, which we prove is also heavy-traffic optimal, has state-of-the-art empirical tail latency at lighter loads, outperforming even a much more computationally intensive mixed-integer-programming heuristic.