Strongly Tail-Optimal Scheduling in the Light-Tailed M/G/1

George Yu, Ziv Scully

Abstract: We study the problem of scheduling jobs in a queueing system, specifically an M/G/1 with light-tailed job sizes, to asymptotically optimize the response time tail. This means scheduling to make $\mathbf{P}[T > t]$, the chance a job's response time exceeds $t$, decay as quickly as possible in the $t \to \infty$ limit. For some time, the best known policy was First-Come First-Served (FCFS), which has an asymptotically exponential tail: $\mathbf{P}[T > t] \sim C e^{-\gamma t}$. FCFS achieves the optimal decay rate $\gamma$, but its tail constant $C$ is suboptimal. Only recently have policies that improve upon FCFS's tail constant been discovered. But it is unknown what the optimal tail constant is, let alone what policy might achieve it. In this paper, we derive a closed-form expression for the optimal tail constant $C$, and we introduce $\gamma$-Boost, a new policy that achieves this optimal tail constant. Roughly speaking, $\gamma$-Boost operates similarly to FCFS, but it pretends that small jobs arrive earlier than their true arrival times. This significantly reduces the response time of small jobs without unduly delaying large jobs, improving upon FCFS's tail constant by up to 50% with only moderate job size variability, with even larger improvements for higher variability. While these results are for systems with full job size information, we also introduce and analyze a version of $\gamma$-Boost that works in settings with partial job size information, showing it too achieves significant gains over FCFS. Finally, we show via simulation that $\gamma$-Boost has excellent practical performance.

Introduction

In high-performance computing and modern web services, "tail latency" is often the most critical performance metric. While average response times are important, Service Level Objectives (SLOs) typically focus on the 99th or 99.9th percentile of requests. In these systems, a single delayed request can bottleneck an entire distributed operation.

This research, recently published in Proceedings of the ACM on Measurement and Analysis of Computing Systems (SIGMETRICS), addresses a long-standing open problem in queueing theory: how to schedule jobs in an M/G/1 queue (a single server with Poisson arrivals and general job sizes) to minimize the probability of extreme delays. Specifically, the study focuses on "light-tailed" job size distributions, such as the Exponential distribution, where the likelihood of encountering a massive job is low.

The Limits of FCFS

For decades, First-Come First-Served (FCFS) was the gold standard for light-tailed systems. It was mathematically proven that FCFS achieves the optimal decay rate $\gamma$—meaning the probability of a long wait drops off exponentially at the fastest possible rate. However, the tail constant $C$ (the multiplier in front of that exponential decay) remained a point of contention. While newer policies like "Nudge" showed that FCFS's constant could be improved, the absolute theoretical limit for this constant—and the policy required to reach it—remained unknown.

The $\gamma$-Boost Policy

The authors introduce a novel family of scheduling policies called Boost. The intuition behind Boost is to maintain the fairness of FCFS while providing a slight advantage to smaller jobs to prevent them from being stuck behind larger ones.

The policy operates by calculating a "boosted arrival time" for each job $i$ based on its true arrival time $a_i$ and its size $s_i$. The server always prioritizes the job with the earliest boosted arrival time:

$$a_i - b(s_i)$$

Through rigorous mathematical derivation, the authors identified the specific boost function $b_\gamma(s)$ that achieves "strong tail optimality":

$$b_\gamma(s) = \frac{1}{\gamma} \log \frac{1}{1 - \exp(-\gamma s)}$$

where $\gamma$ is the system's asymptotic decay rate. This function ensures that small jobs are prioritized just enough to exit the system quickly, but not so much that they starve larger jobs—a common failure mode of policies like Shortest Remaining Processing Time (SRPT) in light-tailed environments.

Theoretical and Practical Insights

The "Cheating" Lower Bound

To prove that $\gamma$-Boost is truly optimal, the authors constructed a "cheating" lower bound. They modeled a hypothetical server with perfect foresight—one that could see all future arrivals within a busy period. They then demonstrated that the "honest" $\gamma$-Boost policy, which only knows about jobs that have already arrived, matches the performance of this omniscient server as response time $t$ approaches infinity.

Negative Discounting

A surprising theoretical finding is the connection between tail optimization and classic scheduling theory. The authors discovered that minimizing the tail constant is mathematically equivalent to a scheduling problem using a negative discount rate. This provides a new lens through which to view tail latency optimization.

Performance Gains

Because this is a theoretical breakthrough, the authors validated their findings using extensive simulations across various job-size distributions, including Uniform, Exponential, Hyperexponential, and Bounded Lomax. The results were significant:

  • Efficiency: $\gamma$-Boost improved the tail constant by 30% to 50% over FCFS for standard distributions.
  • Variability: In systems with high job-size variability (e.g., Hyperexponential), the gains were even more pronounced.
  • Stochastic Dominance: Beyond the asymptotic limit, $\gamma$-Boost was shown to be "stochastically better" than FCFS across the entire distribution of response times.

Flexibility and Future Work

One of the most practical aspects of $\gamma$-Boost is its robustness. The policy remains effective even if the scheduler only has partial information (e.g., knowing a job's type rather than its exact size) or if the estimate of the decay rate $\gamma$ is slightly inaccurate.

While the current proofs are centered on the single-server M/G/1 model, the success of $\gamma$-Boost opens several avenues for future research. Extending these principles to multi-server (M/G/k) environments and exploring hardware implementations—such as mapping boosted arrival times to Push-In First-Out (PIFO) queues in network switches—are the next steps in bringing strong tail optimality to real-world infrastructure.

Summary updated

Abstract

We study the problem of scheduling jobs in a queueing system, specifically an M/G/1 with light-tailed job sizes, to asymptotically optimize the response time tail. This means scheduling to make $\mathbf{P}[T > t]$, the chance a job's response time exceeds $t$, decay as quickly as possible in the $t \to \infty$ limit. For some time, the best known policy was First-Come First-Served (FCFS), which has an asymptotically exponential tail: $\mathbf{P}[T > t] \sim C e^{-γt}$. FCFS achieves the optimal *decay rate* $γ$, but its *tail constant* $C$ is suboptimal. Only recently have policies that improve upon FCFS's tail constant been discovered. But it is unknown what the optimal tail constant is, let alone what policy might achieve it. In this paper, we derive a closed-form expression for the optimal tail constant $C$, and we introduce *$γ$-Boost*, a new policy that achieves this optimal tail constant. Roughly speaking, $γ$-Boost operates similarly to FCFS, but it pretends that small jobs arrive earlier than their true arrival times. This significantly reduces the response time of small jobs without unduly delaying large jobs, improving upon FCFS's tail constant by up to 50% with only moderate job size variability, with even larger improvements for higher variability. While these results are for systems with full job size information, we also introduce and analyze a version of $γ$-Boost that works in settings with partial job size information, showing it too achieves significant gains over FCFS. Finally, we show via simulation that $γ$-Boost has excellent practical performance.
BibTeX
@article{yu2024strongly,
  author = {George Yu and Ziv Scully},
  title = {{Strongly Tail-Optimal Scheduling in the Light-Tailed M/G/1}},
  journal = {Proc. ACM Meas. Anal. Comput. Syst.},
  year = {2024},
  doi = {10.1145/3656011},
}
Figure