Skip to content

CONCEPT Cited by 1 source

Tentative schedule

Tentative schedule is an algorithmic primitive for online scheduling: the scheduler "maintains a tentative schedule by assigning the jobs that have already arrived to disjoint time intervals" and revises it as new jobs arrive via a fixed sequence of update actions (Source: sources/2026-02-11-google-scheduling-in-a-changing-world-time-varying-capacity).

The name is load-bearing: the schedule is tentative, not committed. A job assigned to a time interval in the tentative schedule is not yet running — the commitment is revisable until execution begins. When a new job arrives, the scheduler can shuffle which jobs are in the tentative schedule and in which order, subject to whatever update-action vocabulary the algorithm defines.

Contrast: greedy commit on arrival

The naive online-scheduling policy is greedy commit on arrival: when a job arrives, decide immediately whether to run it, and if yes, run it to completion (under non-preemptive semantics) or until preempted (under preemptive semantics). Greedy commit is simple to implement but gives up the flexibility to reshuffle once the future arrival shape becomes clearer.

Tentative-schedule-with-revision sits in the middle:

  • Not committed on arrival — the job is slotted into a placeholder time interval but hasn't started executing.
  • Revisable as new jobs arrive — the existing tentative interval-assignment can be shuffled in response to new arrivals.
  • Becomes committed at execution start — at some point the scheduler begins actually running the first interval's job, and from then on revisions apply only to later intervals.

The tentative-schedule primitive is what makes constant- competitive online scheduling achievable under common deadlines in the interrupt-without-restart model — general-case online scheduling without the ability to revise commitments is adversarially unwinnable (competitive ratio approaches zero).

Mechanism (unit-capacity common-deadline variant)

The 2026-02-11 post describes the unit-capacity common- deadline algorithm shape: on each job arrival, the algorithm "modifies the tentative schedule by taking the first applicable action out of the following four actions" (Source: sources/2026-02-11-google-scheduling-in-a-changing-world-time-varying-capacity).

The four actions themselves are not in the raw capture — the wiki scope ends at the algorithm's framing-and-setup. What the captured fragment establishes:

  • Jobs that have already arrived are slotted into disjoint time intervals.
  • On a new arrival, the first applicable action is chosen from a fixed ordered list of four.
  • "Unit capacity profile": at any one time, a single job runs. General capacity-profile variants exist but are not developed in the captured fragment.

The algorithm's point is the ordering — by fixing a canonical first-applicable-action rule, the algorithm is deterministic, its behaviour on any arrival sequence is fully specified, and its worst-case ratio against the offline optimum can be bounded.

Tentative-schedule-with-revision is a broadly applicable shape for online decision-making under uncertainty:

  • LARS (Google 2025-10-17) — after VM placement, continue tracking lifetime predictions and migrate when the updated picture makes the current placement inefficient. Revision is driven by continuous reprediction rather than new arrivals, but the structure is the same: commit a tentative plan, keep planning, revise when the picture shifts enough.
  • TCP congestion control — the cwnd / ssthresh pair is a tentative plan for how many bytes can be in flight, revised on each ACK.
  • Optimistic-concurrency-control transactions — the database maintains a tentative version of the transaction's read/write set, committed only at validation time; if a concurrent transaction invalidates the tentative state, the transaction aborts and retries.
  • Speculative execution in CPUs — branch predictors execute speculatively on a tentative control-flow plan; misprediction rolls back.

The common thread: commit decisions under uncertainty, but keep them revocable as long as possible. The benefit over greedy-commit-on-arrival is the ability to recover from commitments that turned out to be suboptimal once the world revealed itself; the cost is the bookkeeping and revision-action complexity.

Seen in

Last updated · 200 distilled / 1,178 read