Which Jobs Can Start Before the Model Is Ready?

Dependencies Outlive a Single Script

BOTIE

A job cannot use an input that another job has not produced yet. Large project networks made that ordering problem important well before ML pipelines. A. B. Kahn’s 1962 paper presented a method for topological sorting: arrange network activities so prerequisites come before the activities that depend on them. A cycle means that no ordering can satisfy all those dependencies.

Workflow systems such as Airflow apply dependency graphs to executable tasks. A directed edge says which task must precede another; an acyclic graph has no route that leads back to itself. For Botie, preparing training data must finish before the job that fits the model. The readiness matrix below isolates that ordering question. A real workflow also needs to identify the actual dataset version and record task failures.

Sources for this history

The Evaluation Job Read Yesterday’s Features

Botie starts data preparation and evaluation together. Evaluation finishes first because it found a file from yesterday. Every process returned successfully, but the result does not describe the model we intended to assess.

A workflow needs explicit dependencies: evaluation must wait for the preparation work it uses. It also needs run-specific artifacts, meaning the files or saved results produced by this particular run. A job becoming runnable means its prerequisites are satisfied. It does not mean the job has succeeded.

The matrix is a validated DAG snapshot with binary flags. Claiming jobs and committing outputs are separate runtime responsibilities.

Step 1 of 1

A training run has prerequisites

A row says which completed jobs a waiting job requires.

A one marks a dependency; it is not a duration or a probability.
Waiting job	Needs preparation	Needs fitting
fit	1	0
evaluate	1	1

fit
Needs preparation
1
Needs fitting
0
evaluate
Needs preparation
1
Needs fitting
1

A one marks a dependency; it is not a duration or a probability.

Describe the jobs before launching them

Each row counts only its own required completions.

Release only the ready jobs

Botie needs to know which waiting ML jobs have all their prerequisites.

BOTIE

Botie needs to know which waiting ML jobs have all their prerequisites.

Choose an example

Dependency matrix

1

2

1

2

Completed prerequisite flags

1

2

Number of dependencies per row

1

2

Jobs whose dependencies are complete

01
10

Follow the operations

1. Dependency matrix
1 0
1 1
2. Completed prerequisite flags
1. 01
2. 10
3. Matrix times vector
1. 01
2. 11
4. Number of dependencies per row
1. 01
2. 12
5. Threshold gate
1. 01
2. 10
6. Result
1. 01
2. 10

The matrix is a validated DAG snapshot with binary flags. Claiming jobs and committing outputs are separate runtime responsibilities.

1. Describe the jobs before launching them

Use a dictionary from job ID to a set of prerequisite IDs. Sets avoid counting the same dependency twice. Keep run status separate from this static structure.

A job with no prerequisites can start immediately. A job whose dependencies are all complete can start next, unless it is already running or complete.

A production scheduler needs an atomic claim so two workers do not both start the same ready job.

2. Count satisfied dependencies

The dependency matrix has one row per waiting job and one column per possible prerequisite. Multiplying by the completion flags counts completed prerequisites in each row. Compare that with the row’s total requirement.

dependencies = [[1,0], [1,1]]
completed = [1,0]
satisfied = [1,1]
required = [1,2]
ready = [1,0]

The workshop only receives waiting jobs. Otherwise readiness would also need to exclude jobs already claimed or completed.

Which prerequisites are still missing?

A set difference names the unmet dependencies of one job.

Python

required = {"prepare", "fit"}
completed = {"prepare"}
print(sorted(required - completed))

Output

['fit']

The set contains job IDs. A nonempty result means this job is still waiting.

Check yourself

What permits a job to start?

Question 1 of 2

Which waiting job can start?

Use the information below.

Fit needs prepare. Evaluate needs fit. Only prepare is complete.

3. A cycle cannot be solved by waiting longer

If fitting requires evaluation and evaluation requires fitting, neither can start. A topological ordering repeatedly removes jobs whose dependencies have been resolved. If unresolved jobs remain with no candidate, report a cycle.

Unknown dependency IDs are a different error. Validate references before sorting so a misspelled job is not reported as a mysterious deadlock.

Feedback between training rounds belongs in explicitly bounded iterations or separate runs, not a hidden cycle in one run’s DAG.

4. Successful execution needs the intended artifact

Mark a prerequisite complete only after its output is committed and identified. A filename alone can point at stale data. Use run-specific identities and pass them to downstream jobs.

Retries should reuse the same logical input and avoid publishing partial output. This extends the fitted-object rule: state has an owner and a lifecycle.

An order checker verifies graph structure. Integration tests must still inspect which model and dataset each job actually read.

5. A retry needs a commit boundary

A preparation job may write half its output before failing. Marking it complete because a path exists lets evaluation consume that partial file. Write to a temporary artifact identity, validate the result, then publish a complete manifest as the commit boundary.

A retry of the same logical job should either find the verified complete artifact or produce a new complete attempt. An orchestrator’s successful task status and an artifact’s publication should agree; test the interruption between them.

This connects task dependencies to the later lineage lesson. Scheduling order alone does not establish output integrity.