{"id":"522e0be8-e573-496a-9a2a-ecfe9b0386cf","arxiv_id":"2412.08915","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A new class of Markov-chain-driven scheduling policies for multiresource jobs is throughput-optimal and admits additively tight mean response time bounds under preemptive, non-preemptive, and setup-time preemption models.","lead":"This paper introduces Markovian Service Rate (MSR) policies, a simple class of schedulers for multiresource cloud jobs that switch between candidate job packings using a Markov chain. If correct, MSR policies stabilize any stabilizable workload and come with response-time bounds that are tight up to an additive constant, while running in constant time per scheduling decision.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"nMSR modulating process depends on queue lengths, so the decoupling used in Theorem 6 and the additive-tight response-time bounds do not hold for non-preemptive systems.","rationale":"The reader's weakest assumption (exponential service requirements) is real and acknowledged in the paper, with a phase-type extension sketch. My concern is more directly load-bearing: the nMSR modulating process is not independent of queue lengths, which is exactly the property that makes the decoupling argument in Section 6 work. Without independence, Theorem 6's coupling proof cannot be completed, so the claimed additive-tight response-time bounds for non-preemptive systems are unproven. The same issue threatens the nMSR throughput-optimality proof, since switching routes can stall on empty queues. This does not invalidate the pMSR results (nor sMSR, whose switching transitions run at setup rates independent of queue state), but it substantially narrows the paper's headline claim that the bounds apply to non-preemptive systems. The paper can likely be repaired by either extending the coupling argument to handle state-dependent transitions or by explicitly restricting the response-time guarantees to pMSR/sMSR and adjusting the abstract and Section 6 accordingly. Therefore a conditional verdict, with this issue as a required revision, is appropriate. I partially agree with the reader: we both flag the independence assumption, but the reader's framing centers exponential service while the deeper problem is that nMSR violates the independence assumption even under exponential service.","tokens_in":35477,"tokens_out":10053,"duration_ms":98066,"concrete_test":"Simulate the nMSR policy from Figure 6b with the Section 7 example at low load (rho = 0.1), where the type-1 queue is empty a significant fraction of time. Compare the measured mean type-1 queue length E[Q_1] against the upper bound from Theorem 8 (computed using the claimed MSR-1 comparison). If E[Q_1] exceeds the upper bound, the Theorem 6 coupling fails for nMSR; if it remains within the bound, the decoupling may still hold empirically and the concern would be weakened.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper's central response-time analysis (Theorems 6 and 8) assumes the MSR modulating process is independent of queue lengths (Section 6.1: \"the number of jobs allowed in service at time t evolves according to the CTMC {u_i(t)}, which is assumed to be independent of the overall state of the system\"). This holds for pMSR and sMSR, whose transition rates are exogenous or setup-rate driven. It fails for nMSR: Section 5.1 restricts nMSR so that decreasing the number of scheduled jobs of a type occurs only at job completions, and the transition rates are at most mu_i * u_i(t). In the explicit example (Appendix F, Figure 6b), the transition from switching state t_{1,4,0} to t_{0,4,0} is labeled mu_1, meaning it occurs only when a type-1 job completes. Thus the modulating process is coupled to queue lengths. Theorem 6's coupling proof requires the two modulating processes to remain in corresponding states; when the MSR-1 queue is empty while the MSR system has a type-1 job, a completion in the MSR system can trigger an nMSR state transition that has no counterpart in the MSR-1 system, so the processes diverge. The induction in the proof does not account for this. Consequently, the claimed additive-tight bounds on mean response time for non-preemptive systems (abstract, Section 6) are unsupported. A related threat applies to Theorem 4's throughput-optimality proof: if a needed completion cannot occur because a queue is empty, an nMSR modulating process can be stuck in a switching state, making the renewal-reward argument's expected switching duration infinite.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces Markovian Service Rate (MSR) policies for scheduling multiresource jobs: a finite-state CTMC selects among a small set of candidate schedules, with the CTMC designed offline from arrival rates, service rates, and resource demands. The main claims are that the MSR class is throughput-optimal under preemptive, non-preemptive, and setup-time preemption models (Theorems 2, 4, and 5); that the mean queue length of an MSR policy is within an additive constant of a corresponding Markov-modulated M/M/1 system (Theorems 6 and 8); that an MIQCP formulation (equation (7)) can select policies that are constant-competitive with MaxWeight in heavy traffic (Theorem 10); and that the resulting policies perform well on a Google Borg trace. The paper provides appendices for most proofs, a public code repository, and a detailed example system.","tokens_in":35773,"tokens_out":15274,"duration_ms":165584,"significance":"If the claims hold, this is a substantial step: it offers a class of low-complexity, offline-designed scheduling policies with throughput optimality and explicit response-time bounds for multiresource jobs, which prior work largely lacked. The pMSR and sMSR results, the use of relative completions from prior work, the closed-form bounds, and the reproducible Borg-trace evaluation are genuine strengths. The main concern is that the non-preemptive (nMSR) analysis relies on an independence assumption contradicted by the definition of nMSR, and the MIQCP in equation (7) has a units inconsistency; these issues are load-bearing for the paper's broadest claims and require repair.","major_comments":[{"comment":"The decoupling argument assumes that the modulating process {u_i(t)} is independent of the queue-length state; Section 6.1 states this explicitly (\"assumed to be independent of the overall state of the system\"), and it is true for pMSR and sMSR policies, whose transition rates are exogenous or setup-rate driven. It is false for nMSR: Section 5.1 restricts nMSR so that decreasing the number of scheduled jobs of a type occurs only at job completions, with transition rates at most mu_i * u_i(t), and Appendix F, Figure 6b labels the transition from state t_{1,4,0} to t_{0,4,0} with rate mu_1, meaning the transition occurs only when a type-1 job completes. In the coupling proof, if the MSR-1 system is empty while the MSR system has a type-1 job in service, a completion in the MSR system triggers an nMSR state transition that has no counterpart in the MSR-1 system; conversely, if the MSR system is empty, the completion that would drive the nMSR transition cannot occur, so the two modulating processes diverge. The induction in Appendix B does not address this case. Consequently, Theorems 6 and 8 do not support the abstract's claim of additive-tight response-time bounds for non-preemptive systems, and Section 7.2's use of these bounds to select the nMSR switching rate alpha* is unsupported. The authors should either restrict Theorems 6 and 8 to pMSR and sMSR policies, or develop a genuinely different comparison for nMSR.","section":"Section 6.1, Theorem 6, Appendix B"},{"comment":"The Foster-Lyapunov proof of Lemma 1 uses step (10), E[C(t) | Q(0)=q] = E[C(t)], which requires the potential-completion process C(t) to be independent of the queue state. For nMSR policies this independence fails: the switching-state transitions are driven by actual completions, and a modulating process can stall in a switching state when no job of the type needed for the next transition is present. Thus the 'if' direction of Lemma 1 is unproved for nMSR, and Theorem 4's construction, which invokes Lemma 1 to conclude stability from E[u^q] approximately equal to E[u^p], is incomplete. This is load-bearing for the claimed throughput-optimality of the nMSR class.","section":"Appendix A, Lemma 1"},{"comment":"The MIQCP objective defines rho_i = lambda_i / (pi W_p)_i, omitting the service-rate vector mu_i. Elsewhere in the paper (Section 6.3 and Definition 2), rho_i = lambda_i / E[u_i^{p-1}] = lambda_i / (mu_i E[u_i^p]). Unless all mu_i are equal to 1, which is the case only in the Appendix J example, equation (7) minimizes a different quantity from the per-type load that appears in the response-time bounds. The formulation should use lambda_i / (mu_i (pi W_p)_i) componentwise, otherwise the selected pMSR policy is not the one claimed to balance the loads that determine the Theta(1/(1-rho_i)) terms.","section":"Section 7.1, equation (7)"},{"comment":"The proof of Theorem 5 is only a two-sentence sketch (\"This proof is nearly identical to the proof of Theorem 4\") and does not define the sMSR switching states, their schedules, or the transition rates involving setup times, nor does it verify that the renewal-reward argument of Appendix E applies to the setup-time routes. Since throughput-optimality under setup costs is one of the paper's stated contributions, a complete proof or a detailed appendix is needed to support the theorem as stated.","section":"Section 5.1, Theorem 5"}],"minor_comments":[{"comment":"The phrase \"conditionally independent of the underlying queueing system given the system events (e.g. completions and setups)\" is ambiguous and does not by itself imply the independence used in Section 6.1; the two statements should be reconciled, especially in light of the nMSR transition rules.","section":"Section 3.3, Definition 1"},{"comment":"The coupling construction says to \"set u_i(t) exponential timers at any time t corresponding to an event ... in either system,\" but it does not specify what happens to timers when the MSR system has no job associated with a given timer, nor how timer expirations that are not completions affect the nMSR modulating process; the event construction should be made fully precise.","section":"Appendix B"},{"comment":"Equation (6) appears to have an extra factor mu_i on the second term: the preceding display (5) and the lemma statement use E[u_i^{p-1}] 1 - u^{p-1}_{*,i}, whereas (6) writes E[u_i^{p-1}] 1 - mu_i (u^{p-1}_{1,i}, ..., u^{p-1}_{N_p,i}). Please correct this typo or clarify the notation.","section":"Lemma 9, equation (6)"},{"comment":"The quantity P^{M/M/k*_i}_Q is used without a definition; please define the M/M/k queueing probability and state the parameter k*_i = E[u_i^p] explicitly before presenting the approximation.","section":"Section 6.4"},{"comment":"The evaluation sets alpha = 0.1 for the pMSR policy, although Section 7.1 recommends a large switching rate alpha; please explain whether this choice is specific to the Borg trace or represents a different normalization of alpha.","section":"Section 8.1"},{"comment":"The proof cites reference [7] for the claim that E[Q^{MaxWeight}] scales as Theta(1/epsilon); the heavy-traffic result for MaxWeight in generalized switches is more commonly attributed to [34], so the citation should be checked.","section":"Theorem 10 proof"}],"recommendation":"major_revision","confidential_remarks":"The nMSR issue is the key blocker: the response-time bounds and the stability condition both rely on an independence property that the paper itself contradicts for non-preemptive policies. If the authors restrict the response-time claims to pMSR/sMSR or repair the nMSR analysis, the paper could be suitable for publication. The reliance on the authors' own prior work [16] is disclosed and is used as a published theorem rather than a fitted quantity, so I do not view it as circular. The public code repository and the detailed example are strengths."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Punchline: this is the first low-complexity, provably throughput-optimal class of multiresource schedulers with response-time bounds, and the pMSR/sMSR results are solid. But the non-preemptive (nMSR) response-time bounds have a load-bearing gap.\n\nWhat's new and good: MSR policies are genuinely new. The Carathéodory argument for pMSR throughput-optimality (at most K schedules) is clean and self-contained. The decoupling to MSR-1 systems and the use of the RESET/MARC relative-completions results from [15,16] is a smart way to turn a hard multiresource problem into a single-server analysis. The Google Borg trace evaluation is reproducible (public code) and shows MSR with BackFilling compares well. The authors are candid about the exponential-service assumption and the phase-type limitations.\n\nThe soft spot that matters: Section 6.1 assumes the modulating process is independent of the system state. That is true for pMSR and sMSR, where transition rates are exogenous or setup-driven. It is not true for nMSR. An nMSR transition to a schedule with fewer type-i jobs is triggered by a type-i completion; if that queue is empty, the transition cannot fire. So the modulating process is queue-length-coupled. Theorem 6's coupling proof assumes the MSR and MSR-1 modulating processes stay in corresponding states, but when one queue is empty and the other is not, a completion in the MSR system forces an nMSR state transition with no counterpart in the MSR-1 system. The induction fails. Theorem 8 inherits the problem, so the additive-tight response-time claim for non-preemptive systems is unsupported. The same issue shadows Theorem 4's renewal-reward argument, since the switching-state sojourn times depend on whether a job is available to complete. This is not a nitpick: the Section 7.2 nMSR parameter tuning uses these bounds.\n\nMinor issues: Theorem 5 is asserted more than proved; equation (7) is under-specified; the Borg evaluation drops non-converged Randomized-Timers points and hand-tunes alpha. None of these change my read.\n\nWho this is for: queueing and cluster-scheduling researchers who want to know whether MSR is a credible alternative to MaxWeight. It deserves a real referee, and the referee should ask for major revision: prove the nMSR bounds under a correct coupling, or explicitly restrict the response-time guarantees to pMSR and sMSR and leave nMSR as a heuristic.\n\nRecommendation: send to peer review with majors. If the nMSR gap cannot be closed, the paper still stands as a solid pMSR/sMSR contribution, but the abstract must be adjusted.","headline":"New policy class with real throughput-optimality results, but the non-preemptive response-time bounds rest on an independence assumption nMSR violates.","tokens_in":36355,"tokens_out":7999,"would_cite":true,"duration_ms":76142,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60K25","68M20","90B35"],"pacs":[],"model":"deepseek-v4-flash","headline":"A queue-length-free Markov-chain policy class can stabilize any multiresource job system that any policy can stabilize.","keywords":["Markovian Service Rate policies","multiresource job scheduling","throughput optimality","mean response time","MaxWeight","Markov-modulated service rates","cloud scheduling","queueing theory"],"falsifier":"Run an nMSR policy from Section 7.2 on a two-type, two-resource system with deterministic or Pareto service times, using arrival rates strictly inside the capacity region; if the mean queue length exceeds the Theorem 8 upper bound or fails to stabilize while the exponential model predicts stability, the exponential assumption is doing the work.","tokens_in":35246,"feed_emoji":"⚙️","tokens_out":7317,"duration_ms":71917,"temperature":0.7,"pith_summary":"The paper's goal is to show that multiresource job scheduling—choosing which jobs that need CPU, memory, and other resources run simultaneously on one server—has a simple policy class that loses nothing on stability. It introduces Markovian Service Rate (MSR) policies, which use a finite-state Markov chain to switch among candidate schedules decided offline, with no dependence on queue lengths. The paper proves that whenever any scheduling policy can keep the system stable, an MSR policy with at most one candidate schedule per job type can too. It also proves bounds on mean queue length that are tight up to an additive constant, so a well-chosen MSR policy competes with MaxWeight in heavy traffic while running in constant time online. These results extend to preemptive, non-preemptive, and setup-time job models.","feed_headline":"MSR policies stabilize every stabilizable multiresource job system","feed_subtitle":"A finite-state Markov chain with at most one schedule per job type covers the entire throughput region and runs in constant time online.","key_machinery":"The load-bearing object is a finite-state CTMC whose states are candidate schedules $\\mathbf{u}\\in\\mathbb{Z}_+^K$ satisfying $\\mathbf{u}\\mathbf{D}\\le \\mathbf{P}$, with transition rates fixed offline and updates conditionally independent of queue lengths. Because the modulating process is state-independent, the $K$-type system decouples into $K$ independent $M/M/1$ queues with Markov-modulated service rates (the MSR-1 systems); the argument compares the original system to these via a coupling (Theorem 6) and uses the relative-completions function $\\Delta(s)$, computed by inverting the generator matrix, to bound mean queue length (Theorem 8). Carathéodory's theorem supplies the existence of at most $K$ schedules on the boundary of the convex hull of the schedulable set, and a MIQCP with load-balancing objective picks the candidate schedules.","core_discovery":"The central claim is that the class of MSR policies is throughput-optimal and analytically tractable: if a multiresource job system with $K$ job types and arrival vector $\\boldsymbol{\\lambda}$ can be stabilized by any policy, then an MSR policy with $N_p \\le K$ candidate schedules stabilizes it. For any MSR policy, the mean queue length of each job type is bounded by the mean queue length of a corresponding single-server Markov-modulated system plus at most the maximum number of jobs of that type served in parallel, which makes the bounds tight up to an additive constant. The paper further claims that the pMSR policy selected by minimizing the maximum per-type load is constant-competitive with MaxWeight in the heavy-traffic limit, and that the same construction works for non-preemptive jobs and for preemptions with setup times.","pith_inferences":["If the exponential service-time assumption is dropped, the paper's response-time bounds and the nMSR switching construction do not automatically survive; extending the relative-completions analysis to phase-type or general distributions is the natural next test, as the paper itself notes the phase-type extension blows up for nMSR policies.","Because the modulating process cannot react to queue lengths, MSR policies give up state-dependent gains; combining MSR with BackFilling—which the paper simulates but does not analyze—suggests a tractable hybrid that could improve response times at moderate loads.","The load-balancing objective in equation (7) is one of many possible objectives; re-solving the same MIQCP with fairness or tail-latency constraints is a direct extension of the paper's offline optimization approach."],"forward_implications":["The entire stability region of multiresource job systems is reachable by policies that do not look at queue lengths, so the expensive online bin-packing of MaxWeight is not needed for stabilization.","Mean response time of a well-tuned MSR policy is within a constant of MaxWeight in heavy traffic, with an offline MIQCP and constant-time online operation; this transfers to non-preemptive and setup-time settings.","The additive tightness of the bounds means the approximation formula from Section 6.4 can be used to select operating parameters such as the switching rate $\\alpha$.","Throughput optimality of nMSR and sMSR policies means preemption constraints alone do not shrink the capacity region below what is fundamentally stabilizable."],"supporting_citations":[{"why":"Supplies the relative-completions technique that bounds the MSR-1 system mean queue length used in Theorem 8.","marker":"[16]"},{"why":"Supplies the capacity-region characterization and the MaxWeight heavy-traffic comparison baseline.","marker":"[26]"},{"why":"Defines MaxWeight for multiresource jobs in the cloud; this is the policy the MSR approach competes against.","marker":"[25]"},{"why":"Provides the Randomized-Timers throughput-optimal policy that is the prior non-preemptive baseline.","marker":"[11]"},{"why":"Gives Carathéodory's theorem, used to prove existence of a stabilizing MSR policy with at most $K$ candidate schedules.","marker":"[8]"},{"why":"Gives the asymptotically tight queue-length bound for MaxWeight used in the heavy-traffic constant-competitiveness proof.","marker":"[7]"},{"why":"Provides the Borg trace used to evaluate MSR policies under real-world, non-exponential workloads.","marker":"[36]"}],"fun_headline_variants":["MSR policies: throughput-optimal with tight response time bounds","Finite-state MSR scheduling stabilizes any stabilizable multiresource system","Throughput-optimal MSR policies with simple implementation and analysis","MSR policies: finite-state, throughput-optimal, and analytically tractable"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole analysis assumes job service times are exponentially distributed, so the non-preemptive policy can time its switches by completions and the decoupled single-server comparison goes through; for general service-time distributions the response-time bounds are not proven and the nMSR state space can blow up.","fun_headline_variants_meta":{"raw":{"variants":["MSR policies: throughput-optimal with tight response time bounds","Finite-state MSR scheduling stabilizes any stabilizable multiresource system","Throughput-optimal MSR policies with simple implementation and analysis","MSR policies: finite-state, throughput-optimal, and analytically tractable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001084,"raw_usage":{"total_tokens":4574,"prompt_tokens":1030,"completion_tokens":3544,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":646,"completion_tokens_details":{"reasoning_tokens":3479}},"tokens_in":646,"tokens_out":3544,"duration_ms":27236,"temperature":1.0,"reasoning_tokens":3479,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T17:26:51.210210+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run an nMSR policy from Section 7.2 on a two-type, two-resource system with deterministic or Pareto service times, using arrival rates strictly inside the capacity region; if the mean queue length exceeds the Theorem 8 upper bound or fails to stabilize while the exponential model predicts stability, the exponential assumption is doing the work.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the relative-completions technique that bounds the MSR-1 system mean queue length used in Theorem 8."},{"cited_title":"Srikant, and Lei Ying","cited_arxiv_id":null,"evidence_quote":"Supplies the capacity-region characterization and the MaxWeight heavy-traffic comparison baseline."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines MaxWeight for multiresource jobs in the cloud; this is the policy the MSR approach competes against."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives Carathéodory's theorem, used to prove existence of a stabilizing MSR policy with at most $K$ candidate schedules."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the asymptotically tight queue-length bound for MaxWeight used in the heavy-traffic constant-competitiveness proof."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Borg trace used to evaluate MSR policies under real-world, non-exponential workloads."}],"review_version":1}