36 citations · 122 across the 30 of their papers we have counts for
26 papers · 1 filter
DynaSPLIT: Strong tail-optimal scheduling for the M/G/n with heavy-tailed job sizes
Zhouzi Li, Mor Harchol-Balter, Alan Scheller-Wolf
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 lo…
SPLIT: SymPathy for Large jobs Improves Tail latency
Zhouzi Li, Mor Harchol-Balter, Alan Scheller-Wolf
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.…
LookAhead: The Optimal Non-decreasing Index Policy for a Time-Varying Holding Cost problem
Keerthana Gurushankar, Zhouzi Li, Mor Harchol-Balter +1
In practice, the cost of delaying a job can grow as the job waits. Such behavior is modeled by the Time-Varying Holding Cost (TVHC) problem, where each job's instantaneous holding…
An Upper Bound on the M/M/k Queue With Deterministic Setup Times
Jalani Williams, Weina Wang, Mor Harchol-Balter
In many systems, servers do not turn on instantly; instead, a setup time must pass before a server can begin work. These "setup times" can wreak havoc on a system's queueing; this…
Improving Upon the generalized c-mu rule: a Whittle approach
Zhouzi Li, Keerthana Gurushankar, Mor Harchol-Balter +1
Scheduling a stream of jobs whose holding cost changes over time is a classic and practical problem. Specifically, each job is associated with a holding cost (penalty), where a job…
Analysis of Markovian Arrivals and Service with Applications to Intermittent Overload
Isaac Grosof, Yige Hong, Mor Harchol-Balter
In many important real-world queueing settings, arrival and service rates fluctuate over time. We consider the MAMS system, where the arrival and service rates each vary according…
Can Increasing the Hit Ratio Hurt Cache Throughput? (Long Version)
Ziyue Qiu, Juncheng Yang, Mor Harchol-Balter
Software caches are an intrinsic component of almost every computer system. Consequently, caching algorithms, particularly eviction policies, are the topic of many papers. Almost a…
Asymptotically Optimal Scheduling of Multiple Parallelizable Job Classes
Benjamin Berg, Benjamin Moseley, Weina Wang +1
Modern computing workloads are often composed of parallelizable jobs. A parallelizable job can be completed more quickly when run on additional servers. However, each job can only…
The RESET and MARC Techniques, with Application to Multiserver-Job Analysis
Isaac Grosof, Yige Hong, Mor Harchol-Balter +1
Multiserver-job (MSJ) systems, where jobs need to run concurrently across many servers, are increasingly common in practice. The default service ordering in many settings is First-…
Optimal Scheduling in the Multiserver-job Model under Heavy Traffic
Isaac Grosof, Ziv Scully, Mor Harchol-Balter +1
Multiserver-job systems, where jobs require concurrent service at many servers, occur widely in practice. Essentially all of the theoretical work on multiserver-job systems focuses…
How to Schedule Near-Optimally under Real-World Constraints
Ziv Scully, Mor Harchol-Balter
Scheduling is a critical part of practical computer systems, and scheduling has also been extensively studied from a theoretical perspective. Unfortunately, there is a gap between…
WCFS: A new framework for analyzing multiserver systems
Isaac Grosof, Mor Harchol-Balter, Alan Scheller-Wolf
Multiserver queueing systems are found at the core of a wide variety of practical systems. Many important multiserver models have a previously-unexplained similarity: identical mea…
Nudge: Stochastically Improving upon FCFS
Isaac Grosof, Kunhe Yang, Ziv Scully +1
The First-Come First-Served (FCFS) scheduling policy is the most popular scheduling algorithm used in practice. Furthermore, its usage is theoretically validated: for light-tailed…
Zero Queueing for Multi-Server Jobs
Weina Wang, Qiaomin Xie, Mor Harchol-Balter
Cloud computing today is dominated by multi-server jobs. These are jobs that request multiple servers simultaneously and hold onto all of these servers for the duration of the job.…
Stability for Two-class Multiserver-job Systems
Isaac Grosof, Mor Harchol-Balter, Alan Scheller-Wolf
Multiserver-job systems, where jobs require concurrent service at many servers, occur widely in practice. Much is known in the dropping setting, where jobs are immediately discarde…
Optimal Resource Allocation for Elastic and Inelastic Jobs
Benjamin Berg, Mor Harchol-Balter, Benjamin Moseley +2
Modern data centers are tasked with processing heterogeneous workloads consisting of various classes of jobs. These classes differ in their arrival rates, size distributions, and j…
Optimal Multiserver Scheduling with Unknown Job Sizes in Heavy Traffic
Ziv Scully, Isaac Grosof, Mor Harchol-Balter
We consider scheduling to minimize mean response time of the M/G/k queue with unknown job sizes. In the single-server case, the optimal policy is the Gittins policy, but it is not…
Simple Near-Optimal Scheduling for the M/G/1
Ziv Scully, Mor Harchol-Balter, Alan Scheller-Wolf
We consider the problem of preemptively scheduling jobs to minimize mean response time of an M/G/1 queue. When we know each job's size, the shortest remaining processing time (SRPT…
Load Balancing Guardrails: Keeping Your Heavy Traffic on the Road to Low Response Times
Isaac Grosof, Ziv Scully, Mor Harchol-Balter
Load balancing systems, comprising a central dispatcher and a scheduling policy at each server, are widely used in practice, and their response time has been extensively studied in…
heSRPT: Optimal Parallel Scheduling of Jobs With Known Sizes
Benjamin Berg, Rein Vesilo, Mor Harchol-Balter
When parallelizing a set of jobs across many servers, one must balance a trade-off between granting priority to short jobs and maintaining the overall efficiency of the system. Whe…
SRPT for Multiserver Systems
Isaac Grosof, Ziv Scully, Mor Harchol-Balter
The Shortest Remaining Processing Time (SRPT) scheduling policy and its variants have been extensively studied in both theoretical and practical settings. While beautiful results a…
Optimal Scheduling and Exact Response Time Analysis for Multistage Jobs
Ziv Scully, Mor Harchol-Balter, Alan Scheller-Wolf
Scheduling to minimize mean response time in an M/G/1 queue is a classic problem. The problem is usually addressed in one of two scenarios. In the perfect-information scenario, the…
SOAP: One Clean Analysis of All Age-Based Scheduling Policies
Ziv Scully, Mor Harchol-Balter, Alan Scheller-Wolf
We consider an extremely broad class of M/G/1 scheduling policies called SOAP: Schedule Ordered by Age-based Priority. The SOAP policies include almost all scheduling policies in t…
Practical Bounds on Optimal Caching with Variable Object Sizes
Daniel S. Berger, Nathan Beckmann, Mor Harchol-Balter
Many recent caching systems aim to improve miss ratios, but there is no good sense among practitioners of how much further miss ratios can be improved. In other words, should the s…