PreprintCC BY 4.0arXiv
DynaSPLIT: Strong tail-optimal scheduling for the M/G/n with heavy-tailed job sizes
Abstract
We study the asymptotic response time tail in the M/G/n queue with heavy-tailed (regularly varying) job sizes. For this setting, strongly tail optimal policies are known only at lower load, where n-1 servers suffice for stability. At higher load, the tail optimal scheduling has been open. This paper presents DynaSPLIT, the first strongly tail optimal policy at high load. Together with prior work, this result shows that strong tail optimality is achievable across the entire stability region of the M/G/n with heavy-tailed job sizes.
Related
- Decentralized SGD under Heavy-Tailed Noise: Optimal Convergence Rates and the Role of Gradient Clipping
- Limit theory for a class of non-stationary linear processes with weakly dependent heavy-tailed innovations
- Tight Heavy-Tailed Complexity Bounds for Optimizing Polyak--Łojasiewicz Objectives
- Hypocoercivity of Tempered Bouncy Particle Samplers for Heavy-Tailed Targets
- Spectral aspects of random heavy-tailed tensors
BibTeX
@misc{li2026dynasplit,
title = {{DynaSPLIT: Strong tail-optimal scheduling for the M/G/n with heavy-tailed job sizes}},
author = {Zhouzi Li and Mor Harchol-Balter and Alan Scheller-Wolf},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.17329},
eprint = {2610.17329},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.17329},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - DynaSPLIT: Strong tail-optimal scheduling for the M/G/n with heavy-tailed job sizes
AU - Zhouzi Li
AU - Mor Harchol-Balter
AU - Alan Scheller-Wolf
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.17329
UR - https://arxiv.org/abs/2610.17329
AB - We study the asymptotic response time tail in the M/G/n queue with heavy-tailed (regularly varying) job sizes. For this setting, strongly tail optimal policies are known only at lower load, where n-1 servers suffice for stability. At higher load, the tail optimal scheduling has been open. This paper presents DynaSPLIT, the first strongly tail optimal policy at high load. Together with prior work, this result shows that strong tail optimality is achievable across the entire stability region of the M/G/n with heavy-tailed job sizes.
ER -