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

George Yu, Ziv Scully

This paper, recently published in Proceedings of the ACM on Measurement and Analysis of Computing Systems (SIGMETRICS), solves a long-standing open problem in queueing theory. It introduces a new scheduling policy that achieves the theoretical limit for "tail latency"—the probability that a job takes an exceptionally long time to complete—in common computing systems.

TL;DR

Researchers have developed $\gamma$-Boost, a scheduling policy that achieves "strong tail optimality" in M/G/1 queues with light-tailed job sizes. By subtly "boosting" the priority of smaller jobs based on a specific mathematical function, the policy reduces extreme response times by up to 50% compared to standard First-Come First-Served (FCFS) scheduling.

What Problem Does This Paper Address?

In high-performance computing and web services, "tail latency" is a critical metric. It’s not enough for the average response time to be fast; providers often have Service Level Objectives (SLOs) requiring that 99% or 99.9% of requests finish within a certain window.

The authors focus on the M/G/1 queue—a system with one server, random arrivals (Poisson), and a general distribution of job sizes. Specifically, they look at light-tailed distributions (like the Exponential distribution), where the probability of a massive job is very low.

For decades, First-Come First-Served (FCFS) was considered the benchmark for these systems. It was known that FCFS achieves the optimal decay rate (how fast the probability of a long wait drops off), but it was suspected that the tail constant (the multiplier in front of that decay) could be improved. While newer policies like "Nudge" showed progress, no one knew what the absolute best possible tail constant was, or how to reach it.

Methods

The authors introduce a family of policies called Boost. The core idea is simple: the scheduler operates like FCFS but "pretends" that smaller jobs arrived earlier than they actually did.

  1. Boosted Arrival Times: Each job $i$ has an arrival time $a_i$ and a size $s_i$. The scheduler calculates a "boosted arrival time": $a_i - b(s_i)$, where $b(s)$ is a boost function.
  2. Priority: The server always works on the job with the earliest boosted arrival time.
  3. The Optimal Function: Through rigorous proof, the authors derive the specific boost function that achieves optimality: $$b_\gamma(s) = \frac{1}{\gamma} \log \frac{1}{1 - \exp(-\gamma s)}$$ where $\gamma$ is the system's asymptotic decay rate.

To prove this is the best possible approach, the authors used a "cheating" lower bound. They imagined a hypothetical server that could see into the future to serve jobs within the current busy period. They then proved that their "honest" $\gamma$-Boost policy matches the performance of this "cheating" server as the response time $t$ goes to infinity.

Datasets

As a theoretical paper, the authors do not use real-world datasets. Instead, they evaluate $\gamma$-Boost using extensive simulations across several standard job-size distributions:

  • Uniform
  • Exponential
  • Hyperexponential (representing higher variability)
  • Bounded Lomax

These simulations involved up to 50 million arrivals per run to ensure statistical significance in the "tail" (the rare, long-running events).

Key Insights and Ideas

  • The Tension of Priority: In heavy-tailed systems (where giant jobs are common), policies like Shortest Remaining Processing Time (SRPT) are great. But in light-tailed systems, SRPT is actually terrible for the tail because a stream of tiny new arrivals can "starve" a large job indefinitely. $\gamma$-Boost finds the "Goldilocks" zone—prioritizing small jobs enough to get them out of the way, but not so much that they delay large jobs beyond the optimal limit.
  • Negative Discounting: The authors draw a fascinating parallel between tail optimization and classic "weighted discounted completion time" problems in scheduling. Surprisingly, they found that minimizing the tail constant is mathematically analogous to a scheduling problem with a negative discount rate.
  • Information Flexibility: $\gamma$-Boost works even if the scheduler doesn't know the exact job size. If jobs are simply labeled (e.g., "Type A" vs "Type B"), the policy can use the expected size to calculate the boost and still outperform FCFS.

Key Results

  • Strong Tail Optimality: The paper provides the first closed-form expression for the optimal tail constant and proves that $\gamma$-Boost achieves it.
  • Significant Speedups: In simulations, $\gamma$-Boost improved the tail constant by 30% to 50% over FCFS for common distributions. In cases with high job-size variability (Hyperexponential), the gains were even larger.
  • Stochastic Improvement: Beyond just the "limit" at infinity, $\gamma$-Boost was shown to improve the response time distribution across the board—it is "stochastically better" than FCFS.
  • Robustness: The policy remains effective even if the estimate of the decay rate ($\gamma$) is slightly off or if job sizes are estimated with noise.

Limitations and Future Work

  • Single Server Focus: The proofs are currently limited to the M/G/1 (single server) model. Extending this to multi-server (M/G/k) environments is a logical next step.
  • Poisson Arrivals: The model assumes arrivals follow a Poisson process. Real-world traffic can be burstier, and it remains to be seen how "Strongly Tail-Optimal" scheduling holds up under non-Poisson conditions.
  • Hardware Implementation: While the algorithm is simple, implementing "boosted arrival times" in high-speed network hardware (like switches) requires mapping the policy to abstractions like PIFO (Push-In First-Out) queues, which the authors suggest as a promising area for systems researchers.

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},
}

Loading related content...

Figure