SPLIT: SymPathy for Large jobs Improves Tail latency

Zhouzi Li, Mor Harchol-Balter, Alan Scheller-Wolf · 2026

Read SPLIT: SymPathy for Large jobs Improves Tail latency by Zhouzi Li, Mor Harchol-Balter, Alan Scheller-Wolf (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-13749.txt.

Introduction

Zhouzi Li, Mor Harchol-Balter and Alan Scheller-Wolf study response time tails in the M/G/n multi-server queue under heavy-tailed job sizes. Under heavy-tailed sizes, SRPT-style short-job priority is strongly tail optimal, and any priority to large jobs harms the tail. The authors give the first strongly tail-optimal scheduling rules for the M/G/n queue under heavy-tailed sizes. They show a little sympathy to large jobs is essential to strong tail optimality over the full stability region.

Catalog record

CREATORZhouzi Li, Mor Harchol-Balter, Alan Scheller-Wolf
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE89100
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.13749

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

SPLIT: SymPathy for Large jobs Improves Tail latency Zhouzi Li, Mor Harchol-Balter, Alan Scheller-Wolf Abstract . We study the asymptotic response time tail in the M/G/ n 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 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. 1. Introduction Optimal scheduling has been an important topic in the performance modeling community for many decades. In the simplest setting, where there is just a single server and the goal is to minimize mean response time, the optimal scheduling policy is well understood: at all times, preemptively serve the job with the Shortest Remaining Processing Time (SRPT) ( 32 ) . The intuition is that a single large job occupying the server forces many smaller jobs to wait, inflating the response time of all of them; SRPT avoids this by always preempting in favor of shorter jobs. This intuition is so fundamental that prioritizing short jobs has become almost synonymous with optimal scheduling. However, in addition to optimizing the mean response time, another important question is that of optimal tail scheduling . In many modern computing systems, the tail of the response time distribution matters at least as much as the mean: Metrics such as the 99th or 99.9th percentile of response time, often codified as service-level objectives (SLOs), directly govern user experience. This paper develops the first tail optimal scheduling policies for multiserver systems with heavy-tailed job sizes. We formally define tail optimality in Section 1.1 , briefly survey existing tail optimization results in Section 1.2 , and explain why the multi-server case remains open in Section 1.3 . We then present the main intuition behind our approach in Section 1.4 . 1.1. Definition of tail optimality A common theoretical formalization of tail optimization studies the asymptotic decay of \mathrm{\mathbb{P}}\left[T>t\right] as t\to\infty ( 38 ; 11 ; 28 ; 40 ; 39 ; 23 ) . As argued in ( 40 ) , there are several reasons to focus on this asymptotic regime: (i) optimizing \mathrm{\mathbb{P}}\left[T>t\right] for any single value of t is seldom the sole design objective; rather, one hopes to achieve low \mathrm{\mathbb{P}}\left[T>t\right] across a range of t ; (ii) practical SLOs relate to high-quantile response times, which correspond to large values of t ; and (iii) optimizing \mathrm{\mathbb{P}}\left[T>t\right] for fixed finite t appears to be theoretically intractable, whereas the asymptotic t\to\infty limit has seen promising recent progress. To make the notion of optimality precise, we say a scheduling policy \pi is weakly tail optimal if there exists a constant c\geq 1 such that \sup_{\pi^{\prime}}\limsup_{t\to\infty}\frac{\mathrm{\mathbb{P}}\left[T^{\pi}>t\right]}{\mathrm{\mathbb{P}}\left[T^{\pi^{\prime}}>t\right]}=c, and strongly tail optimal if additionally c=1 . Intuitively, a weakly optimal policy has the correct tail decay rate, while a strongly optimal policy matches the best achievable tail up to a (1+o(1)) factor. 1.2. Brief summary of tail optimization results For single-server systems, tail optimization is by now well understood, though the answer depends critically on whether the job size distribution is heavy-tailed or light-tailed. As shown by ( 38 ) , no single policy can be weakly tail optimal for both heavy-tailed and light-tailed distributions simultaneously; the two settings require fundamentally different scheduling strategies. Heavy-tailed (regularly varying) job size distributions are particularly important because they are widely observed in real-world computer workloads, including web file sizes ( 13 ) , Unix process lifetimes ( 20 ) , and modern cloud and datacenter job sizes ( 35 ) . Under heavy-tailed job sizes, a number of policies, including SRPT, Processor Sharing, Foreground-Background (FB), and SMART, have been shown to be strongly tail optimal ( 28 ; 8 ; 19 ; 11 ) . Together with the lower bound in ( 38 ) , these results completely characterize single-server tail optimality under heavy tails. Under light-tailed job sizes, the story is different: SRPT has the worst tail decay rate, while FCFS is weakly but not strongly tail optimal ( 11 ; 17 ) ; the strongly optimal policy Boost was proposed recently in ( 40 ) . We defer a more detailed discussion to Section 2 . Table 1 summarizes the state of affairs for single-server systems. Table 1 . Response time tail optimality results for single-server (M/G/1) systems. Light-tailed Sizes Heavy-tailed Sizes Weakly optimal FCFS ( 11 ) , Nudge ( 17 ) Strongly optimal (known sizes) Boost ( 40 ) SRPT ( 28 ) , SMART ( 28 ) Strongly optimal (unknown sizes) Gittins ( 23 ) PS ( 8 ; 19 ) , FB ( 28 ) 1.3. Tail optimality is open for multi-server systems The multi-server setting, by contrast, remains almost entirely open. The only prior result on tail-optimal scheduling in the M/G/ n is due to ( 39 ) , which studies light-tailed job sizes and shows that Boost is strongly tail optimal in the heavy-traffic regime; however, the performance of Boost degrades substantially outside of heavy traffic. To the best of our knowledge, no existing policy has been proved to be strongly – or even weakly – tail optimal for multi-server systems with heavy-tailed job sizes, which, as discussed above, is the setting most representative of real-world systems and workloads. This paper is the first to fill this gap. Table 2 summarizes the known results for multi-server systems, including the contributions of this paper. We study tail-optimal scheduling in the M/G/ n with heavy-tailed (regularly varying) job sizes. Our central finding is that optimal scheduling for multi-server systems is intrinsically different from optimal scheduling for single-server systems. On the one hand, we prove that SRPT- n (where the n servers at all times serve the n jobs with the shortest remaining processing time) is still weakly tail optimal (Theorem A.1 ). On the other hand, to achieve strong tail optimality, we find that one must give some “sympathy” (priority) to large jobs, a strategy that would be harmful in a single-server system. In the rest of the introduction, we describe our new policies and provide intuition for why giving priority to large jobs is beneficial in multi-server systems. Table 2 . Tail optimality results for multi-server (M/G/ n ) systems. ∗ In the case when system load \rho<\frac{n-1}{n} . † Arbitrarily close to strongly optimal. Light-tailed Sizes Heavy-tailed Sizes Weakly optimal SRPT- n [ This paper ] Strongly optimal Boost ( 39 ) (heavy traffic only) SPLIT ∗ [ This paper ] (known sizes) \mbox{Thresh-SPLIT}(d)^{\dagger} [ This paper ] Strongly optimal \mbox{TAGS-SPLIT}(d)^{\dagger} [ This paper ] (unknown sizes) 1.4. Intuition behind our approach SPLIT To understand why multi-server systems require a different approach, it is helpful

Read the complete text