Tenant Fairness & Backpressure

Assumptions and limits

• A finite, deterministic trace runs on a one-second clock. Completions happen before arrivals, scaling, and dispatch. At the cutoff only completions are processed; new work is not started.
• Each worker runs one non-preemptible job at a time. A job occupies one downstream slot for its entire service duration. This is a concurrency bottleneck, not a universal requests-per-second model.
• Admission is tail-drop at a global unfinished-job limit, including running work. Rejection is explicit and never retried automatically; tenant scheduling does not make admission tenant-fair.
• Round robin rotates by JOB, not CPU time. Priority is strict but non-preemptive. The per-tenant cap restricts simultaneous running jobs; idle capacity can remain when every queued tenant is capped.
• Completion percentiles describe only jobs completed before cutoff. Pending and rejected counts, and oldest unstarted wait, must be read alongside them; no service before cutoff is not proof of permanent starvation.
• Deadlines use acceptance/arrival time and include waiting plus service. Only accepted jobs whose deadlines have matured by cutoff enter the deadline count; rejected work remains a separate outcome.
• Worker-seconds count booting, idle, busy, and gracefully draining workers in [0, cutoff). No price, real scheduler behavior, retry storm, network latency, or production SLO is inferred.
• Bulk jobs arrive at the chosen spacing; every third bulk job is long. Interactive jobs are short and start arriving at second 1; reports are long and start at second 2, both using the quiet-tenant interval.
• Priorities are interactive, reports, then bulk. The same trace runs through FIFO, job-round-robin, strict priority, and round-robin with a per-tenant running limit.