IGIsaac Grosof

Isaac Grosof

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Isaac Grosof has a total of 16 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Graph-based product form

    by Céline Comte, Isaac Grosof


  • Open Access

    Multiserver-job response time under multilevel scaling

    by Isaac Grosof, Hayriye Ayhan

    We study the multiserver-job setting in the load-focused multilevel scaling limit, where system load approaches capacity much faster than the growth of the number of servers $n$ . We consider the “1 and $n$ ” system, where each job requires either one server or all $n$ . Within the multilevel scaling limit, we examine three regimes: load dominated by $n$ -server jobs, 1-server jobs, or balanced. In each regime, we characterize the asymptotic growth rate of the boundary of the stability region and the scaled mean queue length. We demonstrate that mean queue length peaks near balanced load via theory, numerics, and simulation.

  • Open Access

    Convergence of Natural Policy Gradient for a family of infinite-state queueing MDPs

    by Isaac Grosof, Siva Theja Maguluri, R. Srikant

    A wide variety of queueing systems can be naturally modeled as infinite-state Markov Decision Processes (MDPs). In the reinforcement learning (RL) context, a variety of algorithms have been developed to learn and optimize these MDPs. At the heart of many popular policy-gradient-based learning algorithms, such as natural actor-critic, TRPO, and PPO, lies the Natural Policy Gradient (NPG) policy optimization algorithm. Convergence results for these RL algorithms rest on convergence results for the NPG algorithm. However, all existing results on the convergence of the NPG algorithm are limited to finite-state settings. We study a general class of queueing MDPs and prove a $$O(1/\sqrt{T})$$ O ( 1 / T ) convergence rate for the NPG algorithm, if the NPG algorithm is initialized with the MaxWeight policy. This is the first convergence rate bound for the NPG algorithm for a general class of infinite-state average-reward MDPs. Moreover, our result applies to a beyond the queueing setting to any countably infinite MDP satisfying certain mild structural assumptions, given a sufficiently good initial policy. Key to our result are state-dependent bounds on the relative value function achieved by the iterate policies of the NPG algorithm.


  • Open Access

    Improving Multiresource Job Scheduling with Markovian Service Rate Policies

    by Zhongrui Chen, Isaac Grosof, Benjamin Berg

    Modern cloud computing workloads are composed of multiresource jobs that require a variety of computational resources in order to run, such as CPU cores, memory, disk space, or hardware accelerators. A server can run a set of multiresource jobs in parallel if the total resource demands of those jobs do not exceed the resource capacity of the server. Given a stream of arriving multiresource jobs, a scheduling policy must decide which jobs to run in parallel at every moment in time in order to minimize the mean response time across jobs --- the average time between when a job arrives to the system until it is completed. We develop and analyze a new class of policies for scheduling multiresource jobs called Markovian Service Rate (MSR) policies. An MSR policy precomputes several candidate schedules, sets of jobs that can run in parallel, and then switches between these candidate schedules randomly according to a continuous-time Markov chain. While prior scheduling policies are either computationally complex, analytically intractable, or result in high mean response time, we develop an analysis of MSR policies to prove that they are both computationally simple and can guarantee low mean response time. We also show that these policies perform well in practice using simulations based on traces from the Google Borg cluster scheduler. This abstract summarizes our full paper.

  • Open Access

    Improving Multiresource Job Scheduling with Markovian Service Rate Policies

    by Zhongrui Chen, Isaac Grosof, Benjamin Berg

    Modern cloud computing workloads are composed of multiresource jobs that require a variety of computational resources in order to run, such as CPU cores, memory, disk space, or hardware accelerators. A single cloud server can typically run many multiresource jobs in parallel, but only if the server has sufficient resources to satisfy the demands of every job. A scheduling policy must therefore select sets of multiresource jobs to run in parallel in order to minimize the mean response time across jobs --- the average time from when a job arrives to the system until it is completed. Unfortunately, achieving low response times by selecting sets of jobs that fully utilize the available server resources has proven to be a difficult problem. In this paper, we develop and analyze a new class of policies for scheduling multiresource jobs, called Markovian Service Rate (MSR) policies. While prior scheduling policies for multiresource jobs are either highly complex to analyze or hard to implement, our MSR policies are simple to implement and are amenable to response time analysis. We show that the class of MSR policies is throughput-optimal in that we can use an MSR policy to stabilize the system whenever it is possible to do so. We also derive bounds on the mean response time under an MSR algorithm that are tight up to an additive constant. These bounds can be applied to systems with different preemption behaviors, such as fully preemptive systems, non-preemptive systems, and systems that allow preemption with setup times. We show how our theoretical results can be used to select a good MSR policy as a function of the system arrival rates, job service requirements, the server's resource capacities, and the resource demands of the jobs.


  • Open Access

    Heavy-Traffic Optimal Size- and State-Aware Dispatching

    by Runhan Xie, Isaac Grosof, Ziv Scully

    We study the problem of dispatching jobs to multiple FCFS (First-Come, First-Served) queues. We consider the case where the dispatcher is size-aware, meaning it learns the size (i.e. service time) of each job as it arrives; and state-aware, meaning it always knows the amount of work (i.e. total remaining service time) at each queue. While size- and state-aware dispatching to FCFS queues has been extensively studied, little is known about optimal dispatching for the objective of minimizing mean delay. In this work, we propose the first size- and state-aware dispatching policy, called CARD (Controlled Asymmetry Reduces Delay), that provably minimizes mean delay in heavy traffic. This work summarizes our full paper.

  • Open Access

    Heavy-Traffic Optimal Size- and State-Aware Dispatching

    by Runhan Xie, Isaac Grosof, Ziv Scully

    We study the problem of dispatching jobs to multiple FCFS (First-Come, First-Served) queues. We consider the case where the dispatcher is size-aware, meaning it learns the size (i.e. service time) of each job as it arrives; and state-aware, meaning it always knows the amount of work (i.e. total remaining service time) at each queue. While size- and state-aware dispatching to FCFS queues has been extensively studied, little is known about optimal dispatching for the objective of minimizing mean delay. In this work, we propose the first size- and state-aware dispatching policy, called CARD (Controlled Asymmetry Reduces Delay), that provably minimizes mean delay in heavy traffic. This work summarizes our full paper.

  • Open Access

    Heavy-Traffic Optimal Size- and State-Aware Dispatching

    by Runhan Xie, Isaac Grosof, Ziv Scully

    Dispatching systems, where arriving jobs are immediately assigned to one of multiple queues, are ubiquitous in computer systems and service systems. A natural and practically relevant model is one in which each queue serves jobs in FCFS (First-Come First-Served) order. We consider the case where the dispatcher is size-aware, meaning it learns the size (i.e. service time) of each job as it arrives; and state-aware, meaning it always knows the amount of work (i.e. total remaining service time) at each queue. While size- and state-aware dispatching to FCFS queues has been extensively studied, little is known about optimal dispatching for the objective of minimizing mean delay. A major obstacle is that no nontrivial lower bound on mean delay is known, even in heavy traffic (i.e. the limit as load approaches capacity). This makes it difficult to prove that any given policy is optimal, or even heavy-traffic optimal. In this work, we propose the first size- and state-aware dispatching policy that provably minimizes mean delay in heavy traffic. Our policy, called CARD (Controlled Asymmetry Reduces Delay), keeps all but one of the queues short, then routes as few jobs as possible to the one long queue. We prove an upper bound on CARD's mean delay, and we prove the first nontrivial lower bound on the mean delay of any size- and state-aware dispatching policy. Both results apply to any number of servers. Our bounds match in heavy traffic, implying CARD's heavy-traffic optimality. In particular, CARD's heavy-traffic performance improves upon that of LWL (Least Work Left), SITA (Size Interval Task Assignment), and other policies from the literature whose heavy-traffic performance is known.


  • Open Access

    Optimal Scheduling in the Multiserver-job Model under Heavy Traffic

    by Isaac Grosof, Ziv Scully, Mor Harchol-Balter, Alan Scheller-Wolf

    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 on maximizing utilization, with almost nothing known about mean response time. Our goal in this paper is to minimize mean response time in a multiserver-job setting. Minimizing mean response time requires prioritizing small jobs while simultaneously maximizing utilization. Our question is how to achieve these joint objectives. We devise the ServerFilling-SRPT scheduling policy, which is the first policy to minimize mean response time in the multiserver-job model in the heavy traffic limit. In addition to proving this heavy-traffic result, we present empirical evidence that ServerFilling-SRPT outperforms all existing scheduling policies for all loads, with orders of magnitude improvements at high load. Because ServerFilling-SRPT requires knowing job sizes, we also define the ServerFilling-Gittins policy, which is optimal when sizes are unknown or partially known. For more detail, see the full paper https://doi.org/10.1145/3570612