Introduction
Modern data centers face the challenge of managing heterogeneous workloads consisting of both elastic and inelastic jobs. Elastic jobs can parallelize linearly across any number of available servers (e.g., distributed machine learning training), while inelastic jobs are sequential and restricted to a single server (e.g., simple database queries). The primary objective for cluster schedulers is to allocate $k$ servers to a continuous stream of these jobs to minimize the mean response time.
Problem Formulation
The system is modeled as a continuous-time Markov chain where jobs arrive according to Poisson processes with rates $\lambda_I$ and $\lambda_E$ for inelastic and elastic jobs, respectively. Job sizes are exponentially distributed with means $1/\mu_I$ and $1/\mu_E$, but these sizes are unknown to the scheduler at the time of arrival. The scheduler must decide how to distribute $k$ servers among the waiting jobs. Two primary policies are considered: Elastic-First (EF), which prioritizes parallelizable work, and Inelastic-First (IF), which prioritizes sequential work.
Methodology
The authors analyze the system using a 2D-infinite Markov chain, where the state $(i, j)$ represents the number of inelastic and elastic jobs in the system.
To overcome the computational difficulty of solving a 2D-infinite chain, a novel technique called Busy Period Transitions was employed. By approximating the time spent processing elastic jobs as an M/M/1 busy period and replacing it with a Coxian distribution, the authors collapsed the complex 2D chain into a solvable 1D-infinite chain, allowing for exact analysis via Matrix-Analytic methods.
The Inelastic-First (IF) policy gives preemptive priority to inelastic jobs. Under IF, if there are $i$ inelastic jobs, they occupy $\min(i, k)$ servers. Any remaining $k - \min(i, k)$ servers are then allocated to the elastic jobs. This behavior is captured in the system's sample path over time.
Key Insights and Results
The core contribution of this work is the proof of optimality for the IF policy. Using a sample path argument and stochastic dominance, the authors demonstrate that IF minimizes the remaining work in the system compared to any other non-idling, first-come-first-serve policy, provided that elastic jobs are larger on average than inelastic jobs ($\mu_I \ge \mu_E$).
This result is somewhat counterintuitive, as one might expect prioritizing highly parallelizable jobs to be more efficient. However, prioritizing inelastic jobs ensures that all servers remain saturated for longer periods, maximizing overall throughput. This condition ($\mu_I \ge \mu_E$) aligns with real-world data center workloads where distributed training tasks (elastic) are typically much larger than individual inference requests (inelastic).
Conversely, the study shows that if elastic jobs are smaller on average ($\mu_I < \mu_E$), the Elastic-First (EF) policy can outperform IF. The performance gap between these policies widens significantly as the system load increases. The analytical model developed was highly accurate, matching simulation results within a 1% error margin.
Conclusion and Future Work
This research provides a rigorous mathematical foundation for scheduling mixed workloads in data centers. While the IF policy is optimal for the most common scenarios, the model's assumptions—such as perfect linear speedup and exponential job size distributions—present opportunities for future refinement. Future work could explore optimal policies for regimes where elastic jobs are smaller or investigate the impact of bounded elasticity and heavy-tailed job size distributions.
Summary updated