Publications

An in-progress version appeared as The RESET Technique for Multiserver-job Analysis, Isaac Grosof, Student Research Competition at SIGMETRICS 2023. Acknowledging Yige Hong, Mor Harchol-Balter, Alan Scheller-Wolf.

[paper] [arxiv] [SRC paper] [short paper] [talks]

Winner of the ACM SIGMETRICS 2023 Graduate Student Research Competition

Note: while correct, the results of the MARC section of this paper are not novel. See the MAMS technical report’s literature review for details. The RESET section of this paper is novel, in contrast.

Optimal Scheduling in the Multiserver-job Model under Heavy Traffic

Isaac Grosof, Ziv Scully, Mor Harchol-Balter, Alan Scheller-Wolf. ACM SIGMETRICS, June 2023.

[paper] [arxiv] [short paper] [slides] [talks]

WCFS: A new framework for analyzing multiserver systems

Isaac Grosof, Mor Harchol-Balter, Alan Scheller-Wolf. Queueing Systems, July 2022.

[paper] [arxiv] [video] [old version]

Towards the shortest DRAT proof of the Pigeonhole Principle

Isaac Grosof, Naifeng Zhang, Marijn Heule. Pragmatics of SAT, August 2022.

[paper] [arxiv]

Uniform Bounds for Scheduling with Job Size Estimates

Ziv Scully, Isaac Grosof, Michael Mitzenmacher. Innovations in Theoretical Computer Science, Jan. 2022.

[paper] [arxiv] [video] [talks]

Nudge: Stochastically Improving upon FCFS

Isaac Grosof, Kunhe Yang, Ziv Scully, Mor Harchol-Balter. ACM SIGMETRICS, June 2021.

[paper - edited] [arxiv] [short paper] [slides] [slides pdf] [talks]

Winner of the SIGMETRICS 2021 Best Paper Award

8/13/24: I’ve uploaded a lightly edited the version of the paper to fix some minor proof bugs, in the proofs of Theorem 4.1 and Lemma 5.3. Here is the original version, for posterity.

The Gittins Policy is Nearly Optimal in the M/G/k under Extremely General Conditions

Ziv Scully, Isaac Grosof, Mor Harchol-Balter. ACM SIGMETRICS, June 2021.

[paper] [short paper]

Winner of the INFORMS 2022 George Nicholson Award

Optimal Multiserver Scheduling with Unknown Job Sizes in Heavy Traffic

Ziv Scully, Isaac Grosof, Mor Harchol-Balter. IFIP Performance, Nov. 2020.

[paper] [arxiv] [MAMA paper] [short paper]

The CacheLib Caching Engine: Design and Experiences at Scale

Ben Berg, Daniel Berger, Sara McAllister, Isaac Grosof, Sathya Gunasekar, Jimmy Lu, Michael Uhlar, Jim Carrig, Nathan Beckmann, Mor Harchol-Balter, Greg Ganger. OSDI, Nov. 2020.

[paper] [canonical version]

Load Balancing Guardrails

Keeping Your Heavy Traffic on the Road to Low Response Times

Isaac Grosof, Ziv Scully, Mor Harchol-Balter. ACM SIGMETRICS, Jun. 2019.

Winner of the SIGMETRICS 2019 Best Student Paper Award

Invited paper at STOC 2021 Theory Fest

[paper] [arxiv] [short paper] [poster] [talks]

SRPT for Multiserver Systems

Isaac Grosof, Ziv Scully, Mor Harchol-Balter. IFIP Performance, Dec. 2018. Also in the journal: Performance Evaluation, Nov. 2018.

Winner of the Performance 2018 Best Student Paper Award

[paper] [arxiv] [MAMA paper] [short paper] [talks]

Computational Complexity of Motion Planning of a Robot through Simple Gadgets

Erik D. Demaine, Isaac Grosof, Jayson Lynch, and Mikhail Rudoy. Ninth International Conference on Fun with Algorithms, June 2018.

[paper] [arxiv] [blog post]

Push-Pull Block Puzzles are Hard

Erik D. Demaine, Isaac Grosof, Jayson Lynch. International Conference on Algorithms and Complexity, May 2017.

[paper] [arxiv] [blog post]

Short Papers

Bounds on M/G/k Scheduling Under Moderate Load

Isaac Grosof, Ziyuan Wang. Accepted to the MAMA workshop at SIGMETRICS 2024.

[paper] [talk]

Simple Policies for Multiresource Job Scheduling

Zhongrui Chen, Isaac Grosof, Benjamin Berg. Accepted to the MAMA workshop at SIGMETRICS 2024.

[paper]

New Stability Results for Multiserver-job Models via Product-form Saturated Systems

Isaac Grosof, Mor Harchol-Balter, Alan Scheller-Wolf. MAMA workshop at SIGMETRICS 2023.

[paper] [old full version] [old full arxiv] [talks]

The old version of the above paper was not accepted, with good reason. Much of the old paper was devoted to rederiving standard results on the saturated system, which we missed in our literature review. However, the product form result is still novel, and that’s the focus of the MAMA version.

ServerFilling: A better approach to packing multiserver jobs

Isaac Grosof, Mor Harchol-Balter. ApPLIED workshop at PODC 2023.

[paper]

Open Problem—M/G/k/SRPT Under Medium Load

Isaac Grosof. Stochastic Systems, arising out of INFORMS 2018. Sep. 2019.

[paper]

Thesis document

Optimal Scheduling in Multiserver Queues

Isaac Grosof. July 2023.

[thesis document] [short version] [talks] [thesis proposal]

Winner of the SIGMETRICS 2024 Doctoral Dissertation Award

One of two CMU nominees for the ACM Dissertation Award

Performance of NPG in Countable State-Space Average-Cost RL

Yashaswini Murthy, Isaac Grosof, Siva Theja Maguluri, R. Srikant.

[paper] [arxiv]

Convergence for Natural Policy Gradient on Infinite-State Average-Reward Markov Decision Processes

Isaac Grosof, Siva Theja Maguluri, R. Srikant.

[paper] [arxiv] [talks]

Papers which I’m not planning to submit

These are papers where I/we think the results are accurate, but not strong or novel enough to warrant peer-reviewed publication.

Analysis of Markovian Arrivals and Service with Applications to Intermittent Overload

Isaac Grosof, Yige Hong, Mor Harchol-Balter.

[paper] [old paper] [arxiv] [talk (tutorial)]

I do not stand by the novelty claims in the old paper and the tutorial. The new paper (technical report) has removed those claims and introduced a detailed literature review, which I stand by.

Incentive Compatible Queues Without Money

Isaac Grosof, Michael Mitzenmacher.

[paper] [arxiv]

Notes (short works not intended for publication)

Moments of Integrated Work in the M/G/1

Isaac Grosof

[paper]