SPLIT: SymPathy for Large jobs Improves Tail latency
Abstract
We study the asymptotic response time tail in the M/G/n multi-server queue with heavy-tailed (regularly varying) job sizes, a setting representative of modern computing workloads. For single-server systems, tail optimization is well understood: under heavy-tailed job sizes, policies such as SRPT that strictly prioritize short jobs are strongly tail optimal, and giving any priority to large jobs is harmful. For multi-server systems, the question has been almost entirely open. This paper gives the first strongly tail-optimal scheduling policies for the M/G/n queue with heavy-tailed job sizes. Our central finding is that the multi-server case is intrinsically different from the single-server case: giving a small amount of ``sympathy'' to large jobs is essential for strong tail optimality. We establish strong (or arbitrarily close to strong) tail optimality across the full stability region, both with and without knowledge of job sizes.
Related
- Projected Primal–Dual Gradient Preference Optimization Under Category-Wise Split-Conformal Safety Constraints for Large Language Model Post-Training
- Care Jobs in France: Sectors, Occupations, and Legal Categories of Employers
- Momentum in large-batch training: Polyak enlarges the critical batch size, Nesterov improves data efficiency
- How Much Does Submitting a Burst of Jobs Impact Waiting Time? An Analysis of the Jean Zay Workload Trace
- A QPTAS for Stochastic Scheduling of Bernoulli Jobs
BibTeX
@misc{li2026split,
title = {{SPLIT: SymPathy for Large jobs Improves Tail latency}},
author = {Zhouzi Li and Mor Harchol-Balter and Alan Scheller-Wolf},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.13749},
eprint = {2605.13749},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.13749},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - SPLIT: SymPathy for Large jobs Improves Tail latency
AU - Zhouzi Li
AU - Mor Harchol-Balter
AU - Alan Scheller-Wolf
PY - 2026
DA - 2026/10/18
PB - arXiv
DO - 10.48550/arxiv.2605.13749
UR - https://arxiv.org/abs/2605.13749
AB - We study the asymptotic response time tail in the M/G/n multi-server queue with heavy-tailed (regularly varying) job sizes, a setting representative of modern computing workloads. For single-server systems, tail optimization is well understood: under heavy-tailed job sizes, policies such as SRPT that strictly prioritize short jobs are strongly tail optimal, and giving any priority to large jobs is harmful. For multi-server systems, the question has been almost entirely open. This paper gives the first strongly tail-optimal scheduling policies for the M/G/n queue with heavy-tailed job sizes. Our central finding is that the multi-server case is intrinsically different from the single-server case: giving a small amount of ``sympathy'' to large jobs is essential for strong tail optimality. We establish strong (or arbitrarily close to strong) tail optimality across the full stability region, both with and without knowledge of job sizes.
ER -