2026/07/10 by Ziyuan Wang, Izzy Grosof · 1 voice
Computer Science · Mathematics · #cs.PF #math.PR
In large-scale computing systems, jobs often demand heterogeneous server allocations: large jobs that occupy a substantial fraction of the servers are of high importance and are thus latency-sensitive, while small jobs fill in the remaining capacity to maintain throughput. To model this dynamic, we introduce the half-batch multiserver-job (MSJ) framework, a queueing model in which large jobs arrive according to a Poisson process and require all servers simultaneously, while small jobs, each needing only one server, are always available. We prove that, in the half-batch MSJ model, the Pareto frontier for large-job mean response time and small-job throughput admits a simple and exact characterization. It is generated by a family of convoy policies, under which the system serves small jobs until k large jobs have arrived and then switches to serving large jobs, together with convex combinations of neighboring convoy policies. Our result is fully general and non-asymptotic, holding for every stable arrival rate λ, every number of servers n, and every large-job size distribution S.