Whole-cluster jobs, not mean gang size, decide when size-based scheduling breaks

GPU cluster schedulingIsolating the cause of starvation日本語

This conclusion was later conditioned, and the detector was replaced

“Support including the whole cluster causes starvation” was rewritten by EP-0008 as a claim conditioned on concurrency. At the same probability, pool and load, coarsening only the background makes the starvation disappear — flow 0.307 to 0.997. Support was a proxy, not a cause. The statistic used to judge starvation was itself invalidated in EP-0011 and replaced in EP-0012. The 2×2 mechanism separation — only size priority combined with greedy packing breaks — still holds.

Follows A demand-mix phase diagram, and three stability detectors that failed.

The practical claim in this note has been demoted. EP-0004 measured the demand distributions of two public traces and found no Philly virtual cluster receiving a job that fills it, so the precondition this note requires was not met in the measured data. The rule “check whether whole-cluster jobs arrive” is withdrawn and replaced by a ratio test against pool capacity. That note also hit this note’s own stated falsification target. The mechanism below is unchanged and still holds inside the model; its reach is what narrowed. This note is kept as the record of what was claimed on 2026-09-13 and is not edited.

Current finding

Holding mean gang size fixed did not hold the outcome fixed. A mix capped at half the cluster stayed stable; a mean-matched mix containing rare whole-cluster jobs starved that class. The failure required size priority and greedy filling together. EP-0004 later found the exact precondition absent in the measured real pools, so this mechanism’s practical reach is narrower than first claimed.

Two earlier studies disagreed. EP-0001 found greedy SRPT winning on a mix whose mean gang size was 3.26 and whose largest job needed half the cluster. EP-0002 found greedy SRPT starving a demand class on a mix whose mean gang size was smaller, 2.37, but which included jobs needing the whole cluster. The mean pointed the wrong way, so we held it fixed and moved only the support.

With mean gang size matched at 4.076, a mix capped at half the cluster is stable under greedy SRPT — worst-class mean JCT 3.31 — while a mix containing 3 percent whole-cluster jobs starves, at worst-class mean JCT 655.7. The threshold is far lower than 3 percent: 15 whole-cluster jobs in 30,000 are enough, and it happens at rho 0.7 as readily as at 0.85. A two-by-two over priority rule and filling rule locates the cause in the combination of size-based priority with greedy work conservation; neither alone produces it. Preemption is not the cause and mildly mitigates it. Ten sealed predictions graded 7/10.

Key figure

What this research shows

• In the stated model, support containing a whole-cluster job—not mean gang size—separates the two outcomes.
• The two-by-two mechanism test locates failure in size priority plus greedy filling; preemption mildly mitigates it.

What this research does not show

• It does not show starvation in a production trace or at every job-to-pool ratio above one half.
• Its former rule, “check whether whole-cluster jobs arrive,” was withdrawn after EP-0004.

Research question

Is the trigger for whole-cluster starvation the support of the demand distribution containing the cluster size N, rather than the mean gang size? And is the starvation produced by size-based priority, by greedy work conservation, or only by the two together?

Why this matters

“Large-gang workloads break naive schedulers” is a statement about proportions, and it invites a capacity-planning response: watch the share of big jobs. If the real trigger is the presence of a job class that requires the entire cluster, the operational rule is different and much sharper — the question is not how many, but whether any.

It also changes what to monitor. The aggregate mean is blind exactly in the regime where whole-cluster jobs are rare, which is the regime in which they are easiest to overlook.

Method

Weights over needs 1 to 32 keep the theta = 0.4 shape and are renormalized to 1 - p64; the remaining mass p64 is placed on need 64 on a 64-server cluster. Only the support changes.

The control’s shape parameter was solved numerically so its mean gang size equals the p64 = 0.03 mix. If starvation tracked the mean, the control would starve too.

The mechanism factorial crosses priority rule against filling rule: greedy SRPT (size priority, greedy fill), ServerFilling-SRPT (size, exact fill), FCFS (arrival, greedy), ServerFilling-FCFS (arrival, exact), plus EASY backfill (arrival with reservation) and non-preemptive greedy SRPT. Two loads, five seeds, 30,000 jobs, and a 120,000-job horizon check on every cell. 432 runs.

Predictions were sealed with SHA-256 2f3b1808d806e9af888acaa77a7e00f7e9af86a13d58e42ac75e514a91157d05 and committed before any result file existed. Acting on the previous study’s lesson, the stability detector itself is written into the sealed file under detector.

Results

The mean-matched control settles it. Same mean gang size, opposite outcome.

The threshold is very low. At p64 = 0.0005 — 15 whole-cluster jobs among 30,000 — greedy SRPT already starves that class at both loads, with 64-GPU mean JCT of 312.5 against EASY backfill’s 5.40 and ServerFilling’s 1.21.

Only the combination breaks. Flow balance of the 64-GPU class at rho 0.85, where 1.0 means the class completes as fast as it arrives:

Size priority alone does not starve; greedy filling alone does not starve. Both together do. The proposed mechanism: a job needing the whole cluster can start only when it is the global minimum of remaining time, but its remaining time never decreases, because it never runs. Arrival-order priority escapes the trap because head-of-line blocking drains the cluster; exact filling escapes it because descending-need fill reserves a slot for the largest job.

The delay is unbounded, not merely large. Over a 4x horizon the starved class’s mean JCT grows 2.83x while the 1-GPU class grows 1.02x.

Preemption is not the cause. The non-preemptive variant is worse, with flow balance of exactly 0.000: while arrivals continue, not one whole-cluster job completes. Preemption lets such a job seize the cluster if it ever reaches the head, so it mitigates.

The blindness of the aggregate has a boundary. Greedy SRPT’s mean JCT against EASY backfill’s runs 0.756, 0.800, 0.982, 1.695 as p64 goes 0, 0.0005, 0.002, 0.008. At p64 = 0.002 the ratio is 0.982 — indistinguishable from a healthy policy — while the whole-cluster class is 63x worse. By p64 = 0.008 the aggregate does notice. The metric is blind precisely where the rare class is rare.

What changed

EP-0002 offered “the support contains N” as a hypothesis. With the mean-matched control it becomes a separated result, and the operational reading changes from a proportion to a predicate: the question is whether any job requires the whole cluster, not how many do.

Two further revisions: preemption moves from suspected aggravator to demonstrated mitigator, and the claim “the aggregate metric cannot see class starvation” acquires a condition — it holds while the class is rare.

What failed

Three of ten sealed predictions failed.

R10 failed on a hairline: completion was 1.000, nothing aborted, and flow balance improved with the horizon. The threshold was not moved after the fact, so it stands as a failure.

One analysis defect was corrected after seeing results, in the direction that makes grading harder: the horizon comparison originally divided a single-seed long run by a five-seed short-run mean, letting seed variation leak into the growth ratio. It is now seed-paired. R10’s verdict did not change.

Evidence boundary

Supported: Under this simulator and these mixes, whole-cluster starvation under greedy size-based scheduling tracks the support of the demand distribution rather than its mean; it appears at a whole-cluster share of 0.0005; it requires both size priority and greedy work conservation; and preemption mitigates rather than causes it.

Not supported: No production-cluster claim. The needs grid is powers of two, so the boundary between “half the cluster” and “the whole cluster” is untested between 33 and 63. Preemption cost was zero. Service times were exponential. No real trace has been run, so whether real GPU clusters contain a whole-cluster job class at all — the precondition for this entire finding to matter in practice — is unverified here.

UNKNOWN

• Whether the threshold is exactly need = N or begins somewhere above N/2. Only 32 and 64 are on the grid.
• Whether non-zero preemption cost removes the mitigation.
• Whether heavy-tailed service times change the share at which the aggregate metric starts to notice.
• Whether the non-preemptive variant starves for the same reason or merely because it cannot preempt.
• Real-trace demand distributions, the highest-priority open item: the share of whole-cluster jobs in Philly or Alibaba PAI can be compared directly against the 0.0005 threshold.

Falsification targets

• An independent simulator finds the mean-matched control starving, which would restore mean gang size as the driver.
• A mix containing whole-cluster jobs runs stably under greedy SRPT at any load.
• The starved class’s JCT converges under a longer horizon.
• ServerFilling-FCFS or FCFS starves the whole-cluster class, which would break the priority-by-filling separation.
• Public traces show no whole-cluster job class, which would leave the finding true of the model and irrelevant to practice.

Reproduce

Quick artifact and grading check

python -m pip install -r requirements-reproduce.txt
python scripts/reproduce.py --quick gpu-phase

Full rerun

cd reproduction/gpu-scheduling-phase
python run_e4.py
python analyze_e4.py

run_e4.py carries its own 120,000-job horizon check on every cell, so no verdict depends on an unadjudicated assumption.

Evidence / Artifacts

• Public reproduction package
• Sealed PRED-003, including the stability detector
• E4 grading
• E4 report, with the mean-matched control

External audit

• Independent replications: 0
• Failed replications: 0
• Confirmed bugs: 0
• Open critiques: 0

Next experiment

Measure the whole-cluster job share in public production traces — Philly via Blox, Alibaba PAI via the Kubernetes scheduler simulator — and compare it against the 0.0005 threshold. Until that is done, this finding describes the model and not any real cluster. A secondary experiment drops the power-of-two constraint to locate the starvation boundary between half and full cluster size.

How this was reached