A scheduler sees two jobs with four units of remaining work each. Should it treat them as interchangeable? Only if the work can be exposed to workers in the same way. Four tasks in a chain and four independent tasks have identical totals but very different opportunities for parallel execution.
Decima represents job dependency graphs with learned node, job, and global summaries. Messages move from descendants toward their parents so a node's representation can include downstream structure. Its architecture is designed to express useful graph aggregations rather than flattening every job into one fixed-length inventory. Decima, Section 5.1.
Decima's 25-node Spark evaluation reports at least 21% lower average job completion time than hand-tuned heuristics, with gains up to 2× during high load. Those results rely on a learned scheduling policy and its training setup. The structural test here addresses why the dependency representation has information that a remaining-work scalar cannot supply.
Count work and count the longest dependency chain
Construct three original jobs. In the chain, A precedes B, B precedes C, and C precedes D. In the diamond, A precedes B and C, and both precede D. In the independent graph, A, B, C, and D have no dependencies. Every task takes one tick and needs one worker.
All three jobs contain four worker-ticks of work. With two workers, a work-only lower bound says completion cannot take less than ceil(4/2) = 2 ticks. That is necessary but insufficient. The chain needs four ticks because no two tasks can run at once. The diamond needs three: A, then B and C together, then D. Only the independent graph finishes in two ticks.
For these unit tasks, define the downstream critical-path value of a task as one plus the largest value among its children; a leaf has value one. The job's longest path is the largest task value. Combining work and dependencies gives the lower bound max(ceil(work/workers), critical_path). It is exact for our three examples, although that does not make it an exact formula for arbitrary scheduling instances.
Make the missing information visible
The Python illustration calculates critical paths recursively with memoization, then runs a simple tick scheduler. At each tick, it admits up to two unfinished tasks whose parents have completed. Completion happens after the tick, so a child cannot start in the same tick as its parent. This event ordering is essential: updating the completed set too early would erase the very dependency delay we want to measure.
The script prints a schedule as well as work, critical path, and makespan. Its assertions check that each task appears exactly once and that the completed schedule respects the lower bound. Alphabetical tie-breaking is deliberately uninteresting here; the example is about information retained in the state, not about discovering an optimal priority rule.
The three DAGs and their two-worker timelines expose the same four nodes arranged differently. The chain leaves a worker idle every tick; the diamond leaves idle slots before and after its middle pair. A single remaining-work scalar conceals that structure.
Representation is not yet a scheduling result
Giving a model a graph does not automatically make it a good scheduler. Conversely, a carefully chosen scalar feature such as critical path can already distinguish these particular jobs. The sharper question is which distinctions a representation preserves across the intended workload, and whether the policy uses them effectively.
A next experiment could pair equal-work graphs with different shapes, then compare a work-only policy with one that also receives critical-path and ready-task counts. Keep worker count, arrivals, and evaluation graphs fixed across comparisons. Only after that baseline would a learned graph representation provide an informative additional test. The present calculation establishes why dependency structure can matter before any learning takes place.
Even work and critical path can be insufficient
The extension adds a six-task barrier graph. A, B, and C are independent roots. D, E, and F each require all three roots to finish. All tasks still take one tick. On two workers, the total-work bound is ceil(6/2) = 3 ticks and the critical-path bound is two. Their maximum is three, but no three-tick schedule exists.
The root layer needs two ticks, because three tasks cannot occupy two workers simultaneously. Every child waits until both root ticks have elapsed. The child layer then needs another two ticks. Four is therefore both a lower bound for this graph and the makespan of the returned schedule. The unused slot in the first layer cannot be filled with a child before the dependency barrier clears.
This is a concrete counterexample to treating max(work/workers, critical path) as an exact completion-time formula. The original three four-task examples happen to attain that bound. Their success should not be generalized to a broader graph family without another argument.
The notebook sweeps worker counts one, two, three, four, and six for all four graphs and checks dependencies at the beginning of each tick. A child's parents must be in the completed set before that tick, not merely scheduled somewhere in it. This ordering check is as important as the feature design: a simulator that accidentally permits same-tick parent and child work would make the graph look more parallel than it is.