Architecture & Measurement-Design Analysis

THEMIS: Fair and Efficient GPU Cluster Scheduling

Source: Mahajan, K.; Balasubramanian, A.; Singhvi, A.; Venkataraman, S.; Akella, A.; Phanishayee, A.; Chawla, S. 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI '20), Feb. 25-27, 2020, Santa Clara, CA, pp. 289-304. URL: https://www.usenix.org/conference/nsdi20/presentation/mahajan ISBN: 978-1-939133-13-7 Affiliations: University of Wisconsin-Madison (Mahajan, Balasubramanian, Singhvi, Venkataraman, Akella, Chawla); Microsoft Research (Phanishayee). Reader: gemini-reader (patched to gemini-2.5-flash; the canonical gemini_read.py is pinned to a retired model). Full PyMuPDF text extraction of the 17-page proceedings PDF used as the authoritative source for every exact value below. Analyst: Vishwakarma Date: 2026-09-01

Table of Contents

1. System Architecture (the two-level semi-optimistic scheduler)
2. System-Under-Test Architecture (testbed, simulator, workloads, baselines)
3. Design-Space Diagram (axes swept, axes held fixed)
4. Algorithm & Control-Flow Diagrams (metric, bid construction, auction, rounds)
5. Quantitative Results -- Empirical Findings by Regime
6. Configuration-Regime Trade-off Tables
7. Bottlenecks & Insights Surfaced by the Measurements
8. Limitations of the Methodology
9. Note on NCCL Tuning
10. Analogy

1. System Architecture (the two-level semi-optimistic scheduler)

THEMIS is a GPU cluster scheduler whose architecture is dictated by a single mechanism requirement: an auction needs many apps to see the same resources at the same time, but exactly one app to be allocated each resource. The paper argues in Section 4.2.1 that no existing scheduler architecture supplies that combination, and derives a new one from it.

The system has three component types. The ARBITER is the centralized cross-app scheduler and holds the finish-time-fair policy. Each ML app runs an existing app-scheduler (a hyper-parameter tuning framework such as Hyperband or Hyperdrive), minimally modified. Between them sits an AGENT, co-located with each app-scheduler, whose only job is to translate app-specific state into a bid so that the app-scheduler itself needs almost no changes.

+------------------------------------------------------------------+
|                      THEMIS-managed GPU cluster                   |
|                                                                   |
|  +-----------------------------------------------------------+    |
|  |                        ARBITER                            |    |
|  |             (cross-app scheduler, centralized)            |    |
|  |                                                           |    |
|  |  +-----------------------+  +--------------------------+  |    |
|  |  | Round-by-round        |  | Partial Allocation (PA)  |  |    |
|  |  | filtering             |  | auction solver           |  |    |
|  |  |  sort apps on r       |  |  proportional-fair alloc |  |    |
|  |  |  take top 1-f         |  |  hidden payment 1-c_i    |  |    |
|  |  +-----------------------+  +--------------------------+  |    |
|  |  +-----------------------+  +--------------------------+  |    |
|  |  | GPU lease tracker     |  | Leftover allocator       |  |    |
|  |  |  (lease expiry ->     |  |  random assignment of L  |  |    |
|  |  |   resource-avail evt) |  |  to non-participants     |  |    |
|  |  +-----------------------+  +--------------------------+  |    |
|  +----------------------------+------------------------------+    |
|                               |                                   |
|            gRPC: offers / bids / winning allocations              |
|         +---------------------+---------------------+             |
|         |                                           |             |
|  +------v---------+                         +-------v--------+    |
|  |  App 1         |                         |  App n         |    |
|  | +------------+ |                         | +------------+ |    |
|  | |  AGENT     | |   . . . (one per app)   | |  AGENT     | |    |
|  | | build r(.) | |                         | | build r(.) | |    |
|  | | bid table  | |                         | | bid table  | |    |
|  | +-----+------+ |                         | +-----+------+ |    |
|  |       |  narrow API (Figure 7 of paper)  |       |        |    |
|  | +-----v------+ |                         | +-----v------+ |    |
|  | | app-sched  | |                         | | app-sched  | |    |
|  | | Hyperband /| |                         | | Hyperband /| |    |
|  | | Hyperdrive | |                         | | Hyperdrive | |    |
|  | +-----+------+ |                         | +-----+------+ |    |
|  |       |        |                         |       |        |    |
|  | +-----v------+ |                         | +-----v------+ |    |
|  | | jobs (TF,  | |                         | | jobs (TF,  | |    |
|  | | sync SGD,  | |                         | | sync SGD,  | |    |
|  | | checkpoint | |                         | | checkpoint | |    |
|  | | to HDFS)   | |                         | | to HDFS)   | |    |
|  | +------------+ |                         | +------------+ |    |
|  +----------------+                         +----------------+    |
+------------------------------------------------------------------+
^ Fig 1: THEMIS component architecture. The AGENT is the load-bearing
  piece of the design: it exists so that an unmodified hyper-parameter
  optimizer can participate in an auction without knowing that an
  auction is happening.

The AGENT is what makes the "widen the API" idea deployable. The paper's central interface claim is that the scheduler cannot predict how an app will react to a given allocation, so the app must say so itself -- but hyper- parameter frameworks were never written to answer that question. The AGENT absorbs the impedance mismatch: it queries a four-function API (Section 4.3) and turns the answers into a valuation table.

1.1 The five-step round

Each GPU carries a lease. Lease expiry is the only event that starts a round. The round runs in two phases across five steps, exactly as in Figure 6 of the paper.

   ARBITER              AGENT (per app)          app-scheduler
      |                       |                        |
      |  (1) ask ALL apps for r estimates              |
      |---------------------->|                        |
      |<--- r_current --------|                        |
      |                       |                        |
   [ sort apps on r_current; keep top (1-f) fraction ] |
      |                       |                        |
      |  (2) NON-BINDING offer of all free GPUs        |
      |      -> only to the filtered subset            |
      |---------------------->|                        |
      |                       |  getJobsInPhase(...) / |
      |                       |  getJobsRemaining(...) |
      |                       |----------------------->|
      |                       |<-- JobInfo list -------|
      |                       |                        |
      |          [ AGENT enumerates GPU subsets,       |
      |            computes r(G) for each  ]           |
      |                       |                        |
      |  (3) single bid = valuation table r(.)         |
      |<----------------------|                        |
      |                       |                        |
   V I S I B I L I T Y   P H A S E   ends here         |
   ------------------------------------------------------------
   A L L O C A T I O N   P H A S E   begins            |
      |                       |                        |
   [ (4) PA auction over bids -> {G_i}, leftover L ]   |
   [     allocate L at random to NON-participants  ]   |
      |                       |                        |
      |  (5) binding winning allocation                |
      |---------------------->|                        |
      |                       |  set GPU containers    |
      |                       |----------------------->|
      |                       |   (app-scheduler splits|
      |                       |    GPUs among its jobs)|
      v                       v                        v
   next lease expiry     cached r(.) kept        checkpoint/resume
^ Fig 2: One auction round. Steps 1-3 are the visibility phase; steps
  4-5 the allocation phase. The offer in step 2 is explicitly
  non-binding, which is what lets it go to many apps at once.

The separation is precise: visibility is multi-app, allocation is single-app. Step 2 broadcasts the same resource set to a whole cohort; step 4 hands each GPU to exactly one winner. Because the offer is non-binding, no conflict resolution is ever needed -- what shared-state optimistic schedulers pay for with transactions and retries.

1.2 Where THEMIS sits in the concurrency-control design space

  visibility granularity  |  allocation granularity  |  example
  ------------------------+--------------------------+-------------
   single app             |  single app              |  Mesos [17]
     (pessimistic)        |                          |
     -> cannot run an auction: no two apps ever see the same GPU
  ------------------------+--------------------------+-------------
   all apps               |  many apps concurrently  |  Omega [30]
     (fully optimistic)   |  (transactions, conflict |
                          |   resolution)            |
     -> auction possible, but a global policy is hard to enforce
        and conflicts are expensive under high contention
  ------------------------+--------------------------+-------------
   cohort of (1-f) apps   |  single app, conflict-   |  THEMIS
     (semi-optimistic)    |  free by construction    |
     -> auction possible AND global policy centralised AND
        allocations conflict-free by construction
  ------------------------+--------------------------+-------------
^ Fig 3: The architectural derivation. Semi-optimistic control is not
  a compromise between the other two -- it is the unique point that
  supplies both properties the auction mechanism requires.

The design choice has a direct consequence: because allocation stays centralized in the ARBITER, THEMIS can enforce a genuinely global objective (minimize max finish-time fairness) that Omega-style schedulers cannot; and because visibility is broadcast, it can run the auction that Mesos-style schedulers cannot. The cost is that the ARBITER is a single point of serialization for every allocation decision, which the paper measures rather than argues away (Section 5.4 below).

1.3 Implementation stack

  +-------------------------------------------------------------+
  |  TensorFlow training jobs                                   |  workload
  |   configurable hyper-parameters; checkpoint model params    |
  |   to HDFS every few iterations; resume from last checkpoint |
  +-------------------------------------------------------------+
  |  Submarine Application Master (MODIFIED)                    |  app level
  |   - ML app scheduler == Hyperband [21]                      |
  |   - THEMIS AGENT                                            |
  |   - profiler: parses TensorFlow logs -> iteration times     |
  |               (for S) and loss values (for early stopping)  |
  +-------------------------------------------------------------+
  |  gRPC interfaces: offers / bids / winning allocations       |  control
  +-------------------------------------------------------------+
  |  YARN Resource Manager                                      |  cluster
  |   + ARBITER as a separate module                            |  level
  |   + GPU lease tracking (to offer reclaimed GPUs)            |
  |   + Gurobi [14] solver for the partial allocation           |
  +-------------------------------------------------------------+
  |  Apache Hadoop YARN 3.2.0 + Submarine [1,2]                 |  base
  |   (Submarine CLIENT modified to submit a GROUP of jobs)     |
  +-------------------------------------------------------------+
  |  HDFS (checkpoint store)                                    |  storage
  +-------------------------------------------------------------+
^ Fig 4: Implementation. Every modification is at an existing seam:
  the client (to submit job groups), the AM (to host AGENT and
  app-scheduler), and the RM (to host the ARBITER).

Two details carry design weight. The profiler lives in the AM, not the ARBITER -- placement preference S is measured by the app that experiences it, consistent with the thesis that only the app can evaluate an allocation. And checkpointing to HDFS is the preemption mechanism, which makes lease length a real cost knob rather than a free parameter (Section 6.3).

2. System-Under-Test Architecture

2.1 Testbed

+---- Testbed: 64 GPUs, 20 machines, Microsoft Azure [23] ----------+
|                                                                   |
|   8 x NC12-series                     12 x NC24-series            |
|  +-------------------+               +-------------------+        |
|  | 2 x Tesla K80 GPU |  ... (x8)     | 4 x Tesla K80 GPU |  (x12) |
|  +-------------------+               +-------------------+        |
|                                                                   |
|      8 x 2 = 16 GPUs                    12 x 4 = 48 GPUs          |
|      ------------------------------------------------------       |
|                        total = 64 GPUs                            |
+-------------------------------------------------------------------+
^ Fig 5: Testbed. GPU-per-machine heterogeneity (2 vs 4) is the
  property under test -- it is what makes an allocation of "4 GPUs"
  mean different things depending on where those GPUs are.

The testbed is deliberately heterogeneous in machine width. That heterogeneity is not incidental: THEMIS's entire fairness argument rests on the claim that two allocations with identical GPU counts can differ in value, and a cluster of uniform machines would weaken the demonstration.

2.2 Simulator

The event-based simulator is used for scale and for every experiment requiring a controlled workload mix.

  Simulator (event-based), described as a 256 GPU cluster:
  +---------------------------------------------------------------+
  |  16 x  8-GPU machines   (4 slots, 2 GPUs per slot)  = 128 GPU |
  |   6 x  4-GPU machines   (4 slots, 1 GPU  per slot)  =  24 GPU |
  |  16 x  1-GPU machines                               =  16 GPU |
  +---------------------------------------------------------------+
  |  Locality model: 4-level hierarchical                         |
  |    individual GPUs -> slots -> machines -> cluster racks      |
  +---------------------------------------------------------------+
  |  Assumption: loss-function curves are known ahead of time,    |
  |  so the total iteration count of each job is predictable      |
  +---------------------------------------------------------------+
^ Fig 6: Simulator configuration. The composition is quoted verbatim
  from footnote 6 of the paper; the body text calls the same cluster
  "256 GPU". Note (my own observation, not a paper claim): the three
  machine classes as listed sum to 168 GPUs, so either the footnote
  or the "256 GPU" label is incomplete. I have not reconciled them
  and no result below is derived from the sum.

2.3 Workloads

The pair is a controlled experiment, and the paper is explicit about what it buys: in Workload 1 "all jobs are either 1 or 2 GPU jobs and almost all allocations, irrespective of the scheme, end up as efficient." Workload 1 is therefore the null condition for placement, and Workload 2 the treatment. Any efficiency or placement-score difference that appears only in Workload 2 is attributable to placement sensitivity rather than to scheduling order.

Model mix (Table 4 of the paper), identical to the mix used in Gandiva [39]:

The percentages in Table 4 are stated per category, not per model.

2.4 The production trace that motivates the design

The design premises are measured, not assumed. From the Microsoft cluster trace (a cluster supporting over 5000 unique users; the analysis is restricted to 85 ML training apps submitted through a hyper-parameter tuning framework):

The median task at 3.75 GPU hours is the number that invalidates DRF-style instantaneous fairness: schemes that redistribute resources on task completion need frequent task completions, and there are none here.

2.5 Baselines

The paper notes it does not model Gandiva's time-slicing and GPU packing, on the grounds that those system-level techniques would benefit THEMIS equally.

3. Design-Space Diagram (axes swept, axes held fixed)

+-------------------------------------------------------------------+
|                    THEMIS EVALUATION DESIGN SPACE                 |
|                                                                   |
|  Axis 1: SCHEDULING SCHEME (7 levels)                             |
|    [THEMIS] [Gandiva] [Tiresias] [Optimus] [SLAQ] [SRTF] [SRSF]   |
|                                                                   |
|  Axis 2: WORKLOAD (2 levels)                                      |
|    [Workload 1: production trace, 1-2 GPU jobs]                   |
|    [Workload 2: Hyperband-shaped, more tasks per job]             |
|                                                                   |
|  Axis 3: PLATFORM (2 levels)                                      |
|    [Testbed: 64 GPU K80, Azure]  [Simulator: larger cluster]      |
|                                                                   |
|  Axis 4: CONTENTION (3 levels, testbed, Workload 1)               |
|    [1x] [2x = half cluster] [4x = quarter cluster]                |
|                                                                   |
|  Axis 5: % NETWORK-INTENSIVE APPS (6 levels, simulator)           |
|    [0%] [20%] [40%] [60%] [80%] [100%]                            |
|                                                                   |
|  Axis 6: ESTIMATION ERROR X from [-X, X]: [0%] [5%] [10%] [20%]  |
|  Axis 7: STRATEGIC LYING X over [0, 100] (over/under-report S)    |
|  Axis 8: FAIRNESS KNOB f  (0 .. 1, simulator)                     |
|  Axis 9: LEASE TIME        (simulator)                            |
|                                                                   |
|  HELD FIXED for all macrobenchmarks:                              |
|    f = 0.8 | lease = 10 min | synchronous SGD | fixed mini-batch  |
|    app-scheduler = Hyperband | preemption = HDFS checkpoint       |
|    model mix = Table 4 (CV 10 / NLP 60 / Speech 30)               |
|    no GPU time-slicing or packing modelled                        |
|                                                                   |
|  NOT SWEPT anywhere:                                              |
|    collective / communication backend of the jobs                 |
|    network fabric type or bandwidth                               |
|    batch size, LR schedule, model architecture beyond Table 4     |
|    number of parameter servers vs workers                         |
|    admission control policy (assumed present, never evaluated)    |
+-------------------------------------------------------------------+
^ Fig 7: The nine swept axes. Axes 4-9 are all simulator or
  microbenchmark axes; the testbed carries only axes 1-2 and the
  contention sweep, which is the right allocation of a 64-GPU budget.

The most consequential entry is in the not swept block: placement sensitivity enters the evaluation only through a scalar slowdown factor S(G). The network fabric, the collective algorithm, and the communication library are never varied. Everything the paper says about "network-intensive apps" is therefore a statement about the shape of the S(G) function, not about any particular interconnect.

4. Algorithm & Control-Flow Diagrams

4.1 The metric: finish-time fairness

                        T_sh
                  r = --------
                        T_id

  T_sh : finish-time of the app IN THE SHARED CLUSTER.
         Encompasses slowdown due to placement AND any queuing
         delay experienced in getting scheduled.
         Worse placement  ->  higher T_sh.

  T_id : finish-time of the app in its own independent and
         exclusive 1/N share of the cluster.

  Sharing incentive (SI) is attained iff  r <= 1.
^ Fig 8: The definition. Both terms are finish times, so r is
  dimensionless and directly comparable across apps of wildly
  different size -- the property that makes "minimize max r" a
  meaningful global objective.

For a single-job app with allocation vector G in a cluster C with R_C GPUs (Equation 1 of the paper, reproduced verbatim in structure):

  r(G)  = T_sh(G) / T_id

  T_sh  = T_current - T_start  +  iter_left * iter_time(G)
          \______________/        \_________________________/
           elapsed time,           remaining work at the
           incl. queueing          proposed allocation
           and starvation

  T_id  = T_cluster * N_avg

                       iter_time_serial * S(G)
  iter_time(G)  =  ---------------------------------
                   min( ||G||_1 , job_demand_max )

                     iter_total * iter_serial_time
  T_cluster     =  ---------------------------------
                   min( R_C , job_demand_max )

  where  ||G||_1  = number of GPUs in the allocation
         S(G) >= 1 = multiplicative slowdown penalty from the
                     PLACEMENT of those GPUs
         N_avg     = average contention: weighted average of the
                     number of apps present over the app's lifetime

For a multi-job app running successive halving (Equation 2):

  T_sh(i)   = max_j { T(G_j) }     phase i ends when its SLOWEST job ends
  T_sh      = sum_i T_sh(i)        app time = sum over phases

  T_cluster =            B
              ---------------------------
              min( R_C , app_demand_max )      B = total GPU-time budget

  T_id      = T_cluster * N_avg

Two modelling decisions are load-bearing. iter_time(G) assumes linear speedup, degraded by a single multiplicative S(G) -- all of communication cost is compressed into one scalar per placement. And T_id is defined against N_avg, the average contention over the app's lifetime, not the instantaneous app count, which is what makes r a long-term rather than instantaneous fairness measure.

4.2 Where S(G) comes from

  Offline path:
    profile the job for a few iterations at a given placement
                        |
                        v
                   exact S(G)

  Online path (footnote 3 of the paper):
        crude priors           measured refinement
   +---------------------+   +----------------------------+
   | same machine  = 1   |-->| ARBITER allocates an       |
   | cross-machine = 1.1 |   | UNSEEN placement           |
   | cross-rack    = 1.3 |   |        |                   |
   +---------------------+   |        v                   |
                             | profiler times iterations  |
                             |        |                   |
                             |        v                   |
                             | replace prior with the     |
                             | accurate estimate          |
                             +----------------------------+
                        |
             "the multi-round nature of allocations means
              that errors in early estimates do not have a
              significant effect"
^ Fig 9: Bootstrapping the placement model. Three hardcoded
  constants seed a table that measurement then overwrites, entry by
  entry, only for placements the scheduler actually hands out.

This is the paper's answer to the objection that S(G) is unknowable: it never needs to be known for placements that are never tried, and the round structure gives repeated opportunities to correct.

4.3 Bid construction inside the AGENT

The AGENT talks to the app-scheduler through a four-function API (Figure 7 of the paper):

  class JobInfo(int   itersRemaining,
                float avgTimePerIter,
                float localitySensitivity);

  // Successive Halving  (Hyperband, Google Vizier)
  List<JobInfo> getJobsInPhase(int phase, List<Int> gpuAlloc);
  int           getNumPhases();

  // Performance Curve Stopping  (Hyperdrive, Google Vizier)
  List<JobInfo> getJobsRemaining(List<Int> gpuAlloc);

  ARBITER offers resource set R
             |
             v
  +---------------------------------------------------------+
  | for each subset G of the offered GPUs:                   |
  |                                                          |
  |   SUCCESSIVE HALVING branch                              |
  |     n = getNumPhases()                                   |
  |     for phase i in 1..n:                                 |
  |        jobs = getJobsInPhase(i, G)                       |
  |        (hyper-param optimizer decides the WITHIN-phase   |
  |         GPU split and supplies S(G_j))                   |
  |        T_sh(i) = max over jobs of T(G_j)                 |
  |        -- for FUTURE phases the surviving jobs are not   |
  |           yet known, so use the MEDIAN job (by           |
  |           per-iteration time) as the estimate            |
  |     T_sh = sum_i T_sh(i)                                 |
  |                                                          |
  |   PERFORMANCE CURVE branch                               |
  |     jobs = getJobsRemaining(G)                           |
  |     for each running job: estimate the iteration at      |
  |       which it will be terminated                        |
  |     -- estimates are probabilistic, so OVER-ESTIMATE:    |
  |        use the most optimistic convergence curve, i.e.   |
  |        the maximum forecasted completion time            |
  |     T_sh = time at which the LAST job finishes           |
  |                                                          |
  |   r(G) = T_sh / T_id                                     |
  +---------------------------------------------------------+
             |
             v
  bid table: one row per subset G, value r(G)
^ Fig 10: Bid construction. Both branches assume the offered
  allocation G "lasts till app completion" -- a deliberate
  simplification that the round-by-round structure then corrects.

The successive-halving structure the AGENT is reasoning about: start with n hyper-parameter options, each a job with demand 1 GPU for I iterations; keep the best n/2, each now with maximum demand 2 GPUs for the same I iterations; repeat until one job remains with maximum demand n GPUs. That is log2(n) phases.

Example bid tables from the paper:

4.4 The worked end-to-end example (Section 4.3.3, verbatim values)

  Setup: 16-GPU cluster, this app + 3 others  (so N = 4)
         4 ML jobs, successive halving
         serial per-iteration times: 80, 100, 100, 120 seconds
         total budget B = 10,000 seconds of GPU time
         job_demand_max = 8 GPUs,  S(G) = 1

  Phases chosen by the hyper-parameter optimizer:
         phase 1: 4 jobs      ~8  iterations
         phase 2: 2 jobs      ~16 iterations
         phase 3: 1 job       ~36 iterations

  T_id  = 10000 * 4 / 16 = 2500 s

  Bid for the ||G||_1 = 2 case:
    phase 1: 4 jobs serialized 2 at a time on 2 GPUs
             T_sh(1) = (120*8) + (80*8) = 1600 s
    phase 2: 2 jobs, one per GPU, MEDIAN job assumed (100 s/iter)
             T_sh(2) = 100 * 16          = 1600 s
    phase 3: 1 job on 2 GPUs, 36 iterations, median job
             T_sh(3) = (100*36)/2        = 1800 s
             ---------------------------------------
             T_sh    = 1600+1600+1800    = 5000 s

    r = 5000 / 2500 = 2

  REVISION in a later round, if the surviving jobs turn out to have
  iteration times 120 and 100 rather than the median 100:
             T_sh(2) = 120 * 16          = 3200 s
             T_sh(3) = (120*36)/2        = 2160 s
^ Fig 11: The median-job estimator and its correction. The revision
  is not error recovery bolted on -- it is the normal operation of
  the round structure, and it is why an optimistic first bid is
  acceptable.

Note the non-linearity the paper points out: job_demand_max = 8 means the r value at 16 GPUs does not decrease linearly from the value at 8 GPUs. The valuation function is deliberately allowed to saturate.

4.5 The partial allocation auction

  procedure AUCTION({A_i}, {r_i(.)}, R):

  (1) PROPORTIONAL-FAIR ALLOCATION
      G_i,pf = arg max  PROD_i  1 / r_i(G_i)
      -> maximizing the product of inverse valuations
      -> this allocation is Pareto Efficient [5]

  (2) COUNTERFACTUAL: re-solve WITHOUT app i
      G^-i_j,pf = arg max  PROD_{j != i}  1 / r_j(G_j)

  (3) HIDDEN PAYMENT FACTOR
                PROD_{j != i} 1 / r_j( G_j,pf )
      c_i  =  ------------------------------------
                PROD_{j != i} 1 / r_j( G^-i_j,pf )

      c_i is directly proportional to the decrease in the
      collective valuation of the OTHER apps caused by i's
      presence.   c_i < 1.

  (4) FINAL ALLOCATION      G_i = c_i * G_i,pf
  (5) LEFTOVER              L   = sum_i (1 - c_i) * G_i,pf

  return {G_i}, L
^ Fig 12: The PA mechanism. Step 3 is the truth-telling device: an
  app that inflates its own r is charged, through c_i, in proportion
  to the harm it claims to do to everyone else.

The guarantee rests on r(.) being homogeneous. Theorem 3.2's proof argues that for ML jobs it is: hold the machine set M fixed and scale the GPUs allocated on those machines by a factor, and S is unchanged (slowdown is set by the slowest interconnect between machines in M, which has not changed), T_sh scales proportionally, T_id is unchanged, so r scales by the same factor. The paper prints this as r(m*G) = m*r(G) while the prose describes r decreasing as the allocation grows -- the two imply opposite directions. I flag the discrepancy rather than resolve it; the claim in use is that r is homogeneous of degree one, which is what the PA mechanism of Cole et al. [5] requires.

The stated properties:

Theorem 3.2's failure of SI is structural: the hidden payments leave GPUs unallocated, so PA is not work-conserving and cannot guarantee r <= 1. The multi-round wrapper exists precisely to repair that.

4.6 Round-by-round auctions

  procedure ROUNDBYROUNDAUCTIONS({A_i}, {r_i(.)}):
    while True:
      ON RESOURCE-AVAILABLE EVENT R0:            <- lease expiry
        A_sort   = SORT({A_i}) on r_current_i
        A_filter = top (1 - f) fraction of A_sort   (GREATEST r)
        r_filter = get updated r(.) from apps in A_filter
        {G_filter}, L = AUCTION(A_filter, r_filter, R0)
        A_unfilter = {A_i} - A_filter
        allocate L to A_unfilter AT RANDOM

The convergence argument is a feedback loop, not a proof of optimality. A losing app gets nothing, so its r grows with waiting time, so it stays in the top (1-f) cohort and reappears; a winner's r improves and it drops out. Taken to the limit, an app that loses several rounds "will eventually lose its lease on all resources and make no further progress, causing its r to become unbounded" -- at which point any non-zero allocation wins it the round.

A presentational inconsistency worth recording: Section 3.3.2 and Pseudocode 1 line 17 both filter the 1-f fraction with the greatest r, while Section 4.2.2 describes the offer as going "to a fraction f ∈ [0,1] of ML apps with worst finish-time fair metrics." The sensitivity results in Section 6.4 (f=1 means "only a single app with highest r value participates") are consistent with the 1-f reading, which is the one used throughout this document.

5. Quantitative Results -- Empirical Findings by Regime

Default configuration for all macrobenchmarks: f = 0.8, lease = 10 minutes.

5.1 Fairness (testbed, Figures 9-10)

The paper also reports qualitatively that THEMIS "has a narrower distribution for the r values which means that THEMIS comes closest to giving all jobs an equal sharing incentive." The abstract's 2.25X and Section 6.2's 2.2X lower bound differ slightly; both are reproduced here as printed.

5.2 Cluster efficiency (testbed, Figures 11-12)

These two Workload-2 numbers are the ~5% to 250% range quoted in the abstract and introduction. The metric is aggregate GPU time to execute the complete workload (lower is better).

The attributed cause is architectural, not algorithmic: "global visibility of app placement preferences due to the auction abstraction enables globally optimal decisions. Gandiva in contrast takes greedy locally optimal packing decisions."

5.3 Sources of improvement (testbed, Table 5)

The paper's explanation is a property of the r metric itself: "With less than ideal allocations, even though long apps see an increase in T_sh, their r values do not increase drastically because of a higher T_id value in the denominator. Whereas, shorter apps see a much more drastic degradation, and our round-by-round filtering of farthest-from-finish-time fairness apps causes shorter apps to participate in auctions more often."

5.4 Systems overheads (testbed, Section 6.2.3)

Both tails are attributed to search-space size: the AGENT's because "enumeration of possible bids needs to traverse a larger search space when the number of resources up for auction is high," the ARBITER's because it appears "when both the number of offered resources and the number of apps bidding are high." Both are judged small relative to the 10-minute lease.

5.5 Placement scores (testbed, Figure 13)

• THEMIS gives the best placement scores (closer to 1.0 is better) in Workload 2.
• Gandiva and Optimus come closest.
• Workload 1: "almost all allocations have a placement score of 1 irrespective of the scheme" because jobs have very low GPU demand.
• Reason given for the others being poor: they do not account for placement preferences; Gandiva does greedy local packing and Optimus greedy throughput scaling, and neither is globally optimal.

5.6 Contention (testbed, Workload 1, Figure 14)

Cluster reduced to half and to a quarter of its original size, inducing 2x and 4x contention.

• "THEMIS is the only scheme that maintains sharing incentive even in high contention scenarios."
• "SRSF comes close as it preferably allocates resources to shorter service apps" -- behaviour the paper identifies as similar to THEMIS's induced altruistic shedding by long apps.

5.7 Placement-preference mix (simulator, Figures 15-16)

Six synthetic workloads sweeping the percentage of network-intensive apps from 0% to 100%.

The 40%/60% result is the most interesting one in the paper's microbenchmarks: the hardest case for every scheduler is not the extreme, it is the mix. A homogeneous workload -- all compute-bound or all network-bound -- lets any scheduler make a uniform decision. A heterogeneous mix requires the scheduler to distinguish between apps, which is exactly the capability the baselines lack.

5.8 Robustness to estimation error (simulator, Figure 17)

All apps are assumed equally susceptible to error; the percentage error is sampled at random from [-X, X] per app, applied to the estimation of the number of iterations and the slowdown S.

X is swept over 0%, 5%, 10% and 20%. Only the endpoint is quoted numerically: "Even with X = 20%, the change in max finish-time fairness is just 10.76% and is not significant." The 5% and 10% points appear on the figure axis but their values are not stated in prose, so they are not reproduced here.

5.9 Truth-telling (simulator, Figure 18)

  Setup: 64 GPUs.  8 identical apps with equivalent placement
         preferences.  ONE 8-GPU machine; all others are 2-GPU
         machines.  The 8-GPU machine is the most preferred
         allocation.  7 truthful apps, 1 strategically lying app.

  Lie: in every round it participates in, the lying app
       over-reports the slowdown with staggered machine placement
       OR under-reports the slowdown with dense machine placement,
       by X%.   X swept over [0, 100].

   completion
     time
       |                                          _______
       |  lying app                              /
       |  -------------------------------------+/   <- tipping
       |                                        X = 34%
       |
       |  truthful apps (average)
       |  --------____
       |              -------________
       +--------------------------------------------------- X
       0%          20%         34%        60%        100%
^ Fig 13: Strategic lying is detrimental. Curve SHAPES are drawn
  from the paper's prose -- "at first the lying app does not
  experience any decrease in its own app completion time", "the
  truthful apps do better", and "a sudden tipping point at X > 34%".
  Only X = 34% is a stated value; no y-axis magnitudes are stated in
  the text and none are implied here.

Mechanism, in the paper's words: "the hidden payment from the partial allocation mechanism in each round of the auction for the lying app remains the same while the payment from the rest of the apps keeps decreasing." At X > 34% "there is a sudden increase in the hidden payment for the lying app and it loses a big chunk of resources to other apps."

5.10 Sensitivity to f and lease time (simulator, Figure 19)

   max r                                        GPU time
     |                                            |
     |  \                                    /    |             /
     |   \                                  /     |            /
     |    \                            ____/      |        ___/
     |     \_____________         ____/           |    ___/
     |                   \_______/                | __/
     +--------------------------------- f         +----------------- f
     0            0.8                 1           0              1

     better fairness as f -> 0.8;             efficiency falls
     ~1.5X worse beyond 0.8                   monotonically with f
^ Fig 14: Sensitivity schematic. SHAPES only -- drawn from the
  stated trends and the single stated magnitude ("worsens by around
  a factor of 1.5X" beyond f = 0.8). No axis values are given in the
  paper's prose and none are asserted here.

Chosen operating point: f = 0.8, lease = 10 minutes, described as giving "maximum fairness while also utilizing the cluster efficiently."

6. Configuration-Regime Trade-off Tables

6.1 Fairness metric

The last row is the design's pivot. DRF and LAS are computable from data the scheduler already has; r is not, and the paper accepts a wider API and a per-app AGENT rather than accept a metric the scheduler can compute alone. For a workload with a median task of 3.75 GPU hours, prefer a long-term, placement-aware ratio metric: the "requires frequent task completions" row alone disqualifies instantaneous fairness, and the "encodes placement preference" row disqualifies pure attained service.

6.2 Scheduler concurrency-control architecture

For any scheduler whose policy is a global optimization over app-supplied valuations, prefer semi-optimistic control. The two capabilities THEMIS needs -- broadcast visibility and exclusive allocation -- are individually available in the other two architectures and jointly available in neither. The price is a centralized solve, and the paper's answer to that price is measurement: at 354 ms median against a 600-second lease, the ARBITER consumes roughly one part in 1700 of the round it governs.

6.3 The fairness knob f and the lease

Prefer f = 0.8 with a 10-minute lease. Both knobs are pure fairness- versus-efficiency dials pointing in opposite directions, and both have an interior optimum rather than a monotone answer -- f because the extreme starves the auction of bidders, the lease because the extreme drowns the system in checkpoints. The f=1 failure is the more instructive of the two: it shows that a filter designed to concentrate resources on the neediest app becomes harmful once it concentrates them on only the neediest app, since a single bidder has no competitive pressure to discover a good placement.

6.4 Mechanism: one-shot versus multi-round

Prefer the multi-round wrapper. The one-shot mechanism is strictly stronger in stated guarantees and strictly unusable in practice: it strands GPUs by construction and has no notion of an app arriving. The wrapper trades an exact guarantee for an empirical one -- the paper's own framing is that it "empirically... gets r <= 1 for most apps, even without admission control."

7. Bottlenecks & Insights Surfaced by the Measurements

7.1 Placement changes throughput by 22% -- for some models and not others

Table 1 of the paper is a two-model, two-placement measurement on 4 P100 GPUs:

   images/s
     |
 250 +  o=======o    Inception-v3: 242 -> 243  (flat)
     |
 150 +
     |   x
 100 +   |\          VGG16: 103.6 -> 80.4
     |   | \
  50 +   |  x
     |
     +---------------------------------------------
       1 server        2 servers

   Same GPU COUNT. Same GPU TYPE. Different value.
^ Fig 15: The measurement that defeats count-based fairness. Any
  scheduler whose fairness metric is a function of GPU count assigns
  these two allocations the same value; one of the two models
  disagrees by 22% and the other does not care at all.

The paper's mechanism: "VGG-like architectures have very large number of parameters and incur greater overheads for updating gradients over the network." The consequence is stated as Theorem 3.1 and demonstrated with two concrete DRF instances (Figure 5 of the paper):

  Instance 1: two 4-GPU machines
              A1 = VGG16 (1 job, 4 tasks), A2 = VGG16 (1 job, 4 tasks)
              DRF gives each 4 GPUs, both SPREAD across servers
              -> both would be faster with a dedicated server each
              -> SI violated for BOTH apps

  Instance 2: one 4-GPU machine + two 2-GPU machines
              A1 = Inception-v3 (placement-INsensitive)
              A2 = VGG16        (placement-sensitive)
              A1 gets the 4-GPU machine; A2 spread over the 2-GPU ones
              -> A2 prefers A1's allocation          => EF violated
              -> swapping helps A2 without hurting A1 => PE violated
^ Fig 16: Two counterexamples. Instance 2 is the sharper one: the
  allocation is not merely unfair, it is Pareto-dominated by a pure
  relabelling that costs nothing.

Instance 2 is the strongest argument in the paper. It shows the failure is not about how much each app gets -- the counts are identical before and after the swap -- but about the scheduler being unable to represent that identical counts have non-identical value.

7.2 The metric's denominator manufactures altruism

The most elegant result in the evaluation is not a speedup, it is a behaviour the metric produces without any explicit mechanism.

   Long app:   T_id is LARGE   (it would take a long time even alone)
               a bad allocation raises T_sh
                   but r = T_sh / T_id barely moves
               -> long app rarely enters the (1-f) filter
               -> long app CEDES resources without being told to

   Short app:  T_id is SMALL
               the same absolute delay raises r sharply
               -> short app enters the filter often
               -> short app WINS auctions often

   Net effect (Table 5): 4-GPU / 580-min app moves 0.9 -> ~1
                         2-GPU /  83-min app moves 1.9 -> ~1.2
^ Fig 17: Altruism as a side effect of normalization. There is no
  "be nice to short jobs" rule anywhere in THEMIS; the behaviour
  falls out of dividing by each app's own solo runtime.

This is a general design lesson about choosing the denominator of a fairness ratio. Normalizing by each app's own independent finish time makes long apps structurally insensitive to short-term unfairness and short apps structurally sensitive -- which is precisely the sensitivity ordering you want, because a short app has no time to amortize a bad round and a long app has plenty. The paper gets a scheduling policy for free by choosing the right normalizer.

7.3 The hardest workload is the mixed one

Figure 15's shape is the counterintuitive result: sharing incentive degrades most at 40% and 60% network-intensive apps, not at 100%.

The reason is that a homogeneous workload does not require the scheduler to discriminate. If every app wants consolidation, consolidate; if none does, pack freely. Only in a mixed workload does the scheduler have to know which app is which -- and that information exists nowhere in a count-based or service-based metric. Heterogeneity of preference, not intensity of demand, is what a placement-aware mechanism buys you.

7.4 The mechanism is robust to bad inputs in two different senses

THEMIS's inputs are estimates, and the paper stress-tests them against both random and adversarial corruption:

The two robustness properties come from different places, which is worth separating. Random-error tolerance comes from the round structure: an estimate that is wrong this round is re-solicited next round, and the paper makes the same argument for the crude S priors (1 / 1.1 / 1.3). Adversarial tolerance comes from the mechanism: the hidden payment c_i is computed from the counterfactual harm to other bidders, so exaggeration is self-taxing. A system that had only one of these would fail against the other threat model.

7.5 The bid is an enumeration, and that is the scaling limit

The AGENT "generates r using the above procedure for all possible subsets of {G}." The measured consequence is the 95th-percentile bid time of 334 ms, which the paper attributes directly to search-space size, and the ARBITER's 1398 ms tail when "both the number of offered resources and the number of apps bidding are high."

  offered GPUs R  ---->  subsets to evaluate  ---->  bid table rows
        |                                                  |
        |                                                  v
        |                                      ARBITER solves PA over
        |                                      (apps x table rows)
        v                                                  |
   grows with cluster size                                 v
   AND with lease expiry batching              Gurobi time grows in BOTH

  Two mitigations already in the design:
    (a) round-by-round filtering caps the number of bidding apps
        at (1-f) -- explicitly justified as making "the auction
        computationally tractable"
    (b) the lease bounds how often the solve happens
^ Fig 18: The cost structure. Filtering is doing double duty --
  it is a fairness device in Section 3.3.2 and a tractability
  device in the same paragraph.

That double duty is the reason f cannot be tuned purely on the fairness curve: raising f improves fairness up to 0.8 and shrinks the solve, while lowering it improves efficiency and grows the solve. The knob's two effects happen to be aligned on the computational axis and opposed on the performance axis.

7.6 Preemption cost is the hidden constraint on every other choice

Checkpointing costs 5-10 s on average and is "driven largely by the overhead of check-pointing to HDFS"; container reconfiguration costs 35 s median and 50 s at the 95th percentile. Together these set a floor on the lease: the 10-minute lease exists because reallocation costs tens of seconds, and the sensitivity analysis confirms that "lower lease values mean that models need to be check-pointed more often... and hence higher lease values are more efficient."

Every conclusion about round frequency, and therefore about how quickly r converges, is conditional on this cost. A cheaper preemption mechanism would move the fairness-efficiency frontier in Figure 19 outward on both axes at once, because the lease could shorten without the checkpoint penalty.

8. Limitations of the Methodology

The two limitations that most constrain generalization are the scalar S(G) model and the admission-control assumption. The first means THEMIS's placement awareness is only as good as the profiler's ability to summarize an allocation's communication behaviour in one multiplicative constant; any workload whose slowdown depends on more than the machine set -- congestion from concurrent tenants, for example -- falls outside the model. The second means the paper's defining property, r <= 1, is offered as an empirical outcome ("we find that it gets r <= 1 for most apps") rather than as the guarantee the formalism suggests.

9. Note on NCCL Tuning

The transferable pattern is THEMIS's treatment of S(G), the placement slowdown factor. THEMIS needs a performance model over a combinatorial space it cannot afford to measure exhaustively, so it seeds the model with three crude topology-derived constants -- same machine 1.0, cross-machine 1.1, cross-rack 1.3 -- and then overwrites entries by profiling only the placements the system actually hands out, relying on the multi-round structure to ensure "errors in early estimates do not have a significant effect." A collective-library tuner faces the identical shape of problem: the space of algorithm, protocol, channel and thread settings is too large to sweep, but a topology-derived prior costs nothing and measurement is cheap for configurations that are being executed anyway. The second transferable point is the robustness result: 20% random error in the performance estimates moved the objective by only 10.76%, which argues that a tuner does not need an accurate cost model, only one whose ordering is mostly right. The third is the lease: THEMIS bounds reconfiguration frequency at 10 minutes because each change costs 35 s of container churn plus 5-10 s of checkpoint, an explicit acknowledgement that a tuner which re-decides more often than its switching cost amortizes will lose to one that does not.

10. Analogy

THEMIS is a shared machine shop run by sealed-bid auction rather than by a sign-up sheet.

The old sign-up sheet gave every member the same number of hours on the same number of machines, and called that fair. But the shop's benches are not interchangeable: three of them sit against the same wall and share a dust extractor, while the others are scattered across two rooms. A cabinetmaker whose work requires constantly passing a half-assembled frame between benches needs the three adjacent ones and is crippled by any other arrangement. A member who is turning small independent parts on a lathe does not care where the benches are at all. The sign-up sheet cannot express the difference, so it routinely hands the adjacent benches to the lathe operator and scatters the cabinetmaker -- an assignment that is worse for one member and no better for anyone, which is the exact meaning of the Pareto violation in the paper's Instance 2.

THEMIS replaces the sheet with an hourly cycle. Every bench carries a one-hour ticket -- the lease -- and when tickets expire the shop manager takes back the freed benches and holds a round. The manager first asks everyone a single question: how far behind are you, relative to how long this project would have taken you in your own private shop? That ratio is finish-time fairness, and its denominator is what makes the scheme humane. A member building a six-month boat is barely affected by losing one hour; a member finishing a two-day repair is severely affected by the same hour. So the boat-builder's ratio stays near one while the repairer's spikes -- and the manager, who only invites the twenty percent furthest behind to bid, invites the repairer. The boat-builder yields without ever being asked to.

The invited members are then shown all the free benches at once and asked what each combination is worth to them. This is the architectural trick: showing a bench to five people costs nothing, giving it to five people is impossible, so the shop separates the showing from the giving. And because members would obviously exaggerate, the manager charges a fee computed from a counterfactual: how much worse off would everyone else be because you were in the room? A member who overstates his need inflates that number and is billed for it in withheld bench-time. The paper's measurement is that the fee is invisible until you exaggerate by more than a third, and ruinous after -- which is the economist's version of a guard rail.

Two details keep the shop honest about its own costs. The manager's fee scheme strands a few benches every round, so those are handed out at random to whoever was not invited to bid, and nothing sits idle. And nobody re-shuffles more often than the hour, because packing up a half-finished project and setting it back up costs most of a minute either way; the one-hour ticket is not a fairness parameter, it is an amortization of the cost of moving. The result is a shop that is fairer over a week than the sign-up sheet ever was, while getting slightly more finished work out of the same floor space -- and the reason it can be both is that it stopped measuring fairness in benches and started measuring it in finished projects.