Dependency Graph Scheduling¶
Scheduling algorithm — instantiates Deferred Fulfillment Placeholder
Orders a graph of interdependent placeholders and releases each dependent the moment its predecessors resolve — or partially resolve.
Dependency Graph Scheduling operates on the whole graph of pending placeholders at once. Where a single registration attaches one continuation to one placeholder, this mechanism holds the entire web of who-depends-on-whom and uses it to decide what becomes runnable when. Its defining move is topological release: it treats placeholders as nodes and dependencies as edges, and it fires each dependent exactly when the predecessors it needs have resolved — no sooner, no later — maximizing how much can proceed in parallel while never letting a step start before its inputs exist. It also understands partial fulfillment: when a predecessor can release enough of its result to unblock a dependent before it is fully done, the scheduler can start that dependent early. It owns the structure and the timing of the dependent set; it is not itself a callback, and it does not push progress bars to consumers.
Example¶
A general contractor runs a building project as a graph of pending deliverables: the foundation, the framing, the electrical rough-in, the drywall, the inspection sign-offs. Each is a placeholder that resolves when that work completes, and each has predecessors — drywall cannot start until framing and electrical rough-in are done. Dependency Graph Scheduling holds this whole graph. As the foundation placeholder resolves, it releases framing; it runs plumbing and electrical rough-in in parallel because neither depends on the other; and it holds drywall until both of its predecessors are done. The longest chain through the graph is the critical path, and the scheduler keeps everything off it moving in parallel so the project isn't serialized needlessly.
It also uses partial markers: the electrician finishes the west wing before the east. Rather than making drywall wait for the entire building's rough-in, the scheduler reads the partial-fulfillment marker and releases west-wing drywall while east-wing electrical is still in progress. The graph, not a single hand-off, is what tells it exactly when each crew can start.
How it works¶
- Build the dependency graph. Represent placeholders as nodes and "needs the value of" relationships as directed edges, forming a DAG of the pending work.
- Compute a release order. Derive a topological ordering so every node is scheduled only after its predecessors; identify which nodes are independent and can proceed concurrently.
- Release on resolution. As each placeholder resolves, mark its dependents' prerequisites satisfied and release any dependent whose predecessors are now all complete.
- Exploit partial fulfillment. When a predecessor emits a partial-fulfillment marker sufficient for a given dependent, release that dependent early rather than waiting for full completion.
- Detect cycles and stalls. Refuse or flag a graph with a dependency cycle (which can never resolve) and surface nodes blocked on a predecessor that has stalled.
It orchestrates timing across many placeholders; it does not resolve them, and it does not register the individual continuations it fires — those come in already attached.
Tuning parameters¶
- Concurrency width — how many independent nodes to run at once. Wider finishes faster but competes for shared resources; narrower is gentler but slower.
- Partial-release threshold — how much of a predecessor's result must be ready before a dependent is released early. Aggressive early release shortens the critical path but risks starting on a partial that later changes.
- Priority / critical-path weighting — whether to preferentially advance nodes on the longest chain. Prioritizing the critical path minimizes total time; ignoring it can leave the bottleneck starved.
- Cycle policy — reject a cyclic graph outright, or break the cycle with a designated seed. Rejection is safe; breaking is pragmatic but risky.
- Rescheduling cadence — static plan computed once, or dynamic re-planning as resolutions (and failures) arrive. Dynamic adapts to reality at scheduling overhead.
When it helps, and when it misleads¶
Its strength is turning a tangle of interdependencies into the maximally parallel correct order: a topological schedule[n1] runs everything that can run and holds only what must wait, which no per-placeholder callback can see because none of them knows the whole graph. Partial-fulfillment awareness sharpens this further, shaving the critical path by starting dependents on the first usable slice of a predecessor.
Its failure mode is the undetected cycle or stalled predecessor: a dependency cycle can never satisfy its own prerequisites (deadlock), and a single stalled node silently holds up everything transitively downstream. A classic misuse is scheduling aggressively on partial results that later change, so dependents built on an early slice must be torn down and redone. The guarding discipline is to validate the graph is acyclic before scheduling, to monitor for predecessors that have gone quiet (leaning on a deadline mechanism to break stalls), and to release on partial results only when the partial is genuinely stable — an internal check that an early-released slice won't be revised.
How it implements the components¶
Dependency Graph Scheduling fills the orchestration components:
dependent_continuation_set— holds and traverses the whole graph of dependents, releasing each when its predecessors resolve, rather than binding one continuation to one placeholder.partial_fulfillment_marker— reads predecessors' partial-completion markers to release dependents early when a usable slice is ready before full resolution.
It does not implement fallback_value_or_path — registering a single continuation and its alternate branch on one placeholder is the twin, Callback or Continuation Registration; scheduling orders the graph of continuations rather than authoring any one of them or its fallback. Nor does it implement progress_signal, the consumer-facing stream of Await or Subscription.
Related¶
- Instantiates: Deferred Fulfillment Placeholder — the mechanism that coordinates timing across many interdependent pending values.
- Consumes: Callback or Continuation Registration — the continuations it schedules are the ones registered onto the placeholders it orders.
- Sibling mechanisms: Callback or Continuation Registration · Await or Subscription · Promise Creation Protocol · Resolution Event Commit · Pending State Polling · Cancellation Propagation · Failure Propagation · Resolved Value Memoization · Timeout Expiration Handler
Editorial Notes¶
Form Classification¶
Form family: Control, Automation & Runtime
Rationale: Dependency Graph Scheduling operates as a live operational control that automatically routes, enforces, adapts, or responds during execution because it orders a graph of interdependent placeholders and releases each dependent the moment its predecessors resolve — or partially resolve.
Independent corroboration: The frozen evidence defines Dependency Graph Scheduling as 'Orders a graph of interdependent placeholders and releases each dependent the moment its predecessors resolve — or partially resolve', so its operative form is Control, Automation & Runtime.
Review outcome: Independent reviewer agreement; high confidence.
Origin Attribution¶
Primary origin: Operations Research
Origin pattern: Convergent development
Present-day reach: Multi-domain
Rationale: Project scheduling cohered precedence-network schedules, critical paths, and release of work when predecessors complete.
Related originating lineages:
- Computer Science & Software Engineering — Build systems and task schedulers independently implemented topological release over directed acyclic graphs.
Review outcome: Independent reviewer agreement; high confidence.
Notes¶
[n1] A topological ordering of a directed acyclic graph lists each node after all its prerequisites; it is the schedule a dependency graph admits, and its longest such chain is the critical path that bounds total completion time. ↩