The question this answers
Given a set of tasks and what each one needs, which of them can actually run at the same time?
A five-stage data pipeline: A fetches and validates the raw export (5 min); B builds a search index, C computes summary statistics and D deduplicates records, all from A's output (4, 2 and 6 min); E enriches the deduplicated records against a partner API (7 min) and needs D.
Each task's output artefact, which is read by its successors. Nothing is concurrently mutable: a producer finishes writing before any consumer starts reading, and the edge is exactly the guarantee that makes that true.
No task starts before every one of its predecessors has completed and published its output — so every task reads finished, immutable inputs, and never a partially written one.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
The graph, the ready set, and the critical path
A dependency graph is a DAG: nodes are tasks, and an edge from X to Y means Y consumes something X produces. Three things fall straight out of it. The ready set at any moment is the tasks whose predecessors have all completed — that is exactly the set of things that may run simultaneously, and it changes as tasks finish. Any topological order is a valid sequential execution. And the critical path, the longest chain weighted by task duration, is the earliest possible finish time with unlimited workers.
For the pipeline above: A must run first, alone. When A completes, B, C and D all become ready simultaneously — three-way parallelism, available for free, requiring no locks because they consume A's finished output and produce separate artefacts. E waits for D specifically, not for B or C, and that specificity matters: a scheduler that treats "stage 2" as a barrier before "stage 3" would make E wait for B and C too, needlessly.
The critical path is A → D → E = 5 + 6 + 7 = 18 minutes. Every other path is shorter (A → B is 9, A → C is 7), so 18 minutes is the floor. Two consequences follow. Speeding up B or C changes the finish time by nothing at all — they already have slack. Speeding up D or E changes it directly. And total work is 5+4+2+6+7 = 24 minutes, so parallelism is 24/18 = 1.33: this pipeline can barely use two workers, which is worth knowing before provisioning four (Work and Span).
- Ready set = tasks with all predecessors complete. That set, at any instant, is your available parallelism.
- Critical path A→D→E = 18 min is the floor; B and C have 9 and 11 minutes of slack respectively.
- Optimising a task with slack does not move the finish time until the slack is consumed.
- Parallelism = W/S = 24/18 = 1.33, so this graph cannot keep two workers busy on average.
What changes with worker count — and what does not
Scheduling this graph on two workers versus four shows the pattern that makes dependency graphs worth drawing. With four workers, B, C and D start together the moment A finishes; C finishes at 7, B at 9, D at 11, E runs 11→18. Total: 18 minutes, which is the critical path, so four workers achieve the theoretical optimum. Two workers: A finishes at 5, then D and B run (D is longest and on the critical path, so a good scheduler starts it first), C waits until a worker frees at 9, E starts at 11 anyway. Total: still 18 minutes.
That is the interesting result — two workers and four workers finish at the same time, because the graph is critical-path-bound, not worker-bound. Provisioning four gains nothing. This is the sort of thing that is obvious from the graph and invisible from the code, and it is why build systems, CI pipelines and data orchestrators all expose their DAG.
It also shows why scheduling *order* matters when workers are scarce. If the two-worker scheduler had started B and C first and left D until 9, E would start at 15 and the pipeline would take 22 minutes — 4 minutes of pure scheduling loss. The rule that avoids it is to prioritise tasks by their remaining critical-path length rather than by duration, readiness order or arrival: run the task with the longest chain behind it first. Most schedulers do not do this by default, which is a common source of quiet loss in CI and batch pipelines.
The edge you forgot to draw
Everything above assumes the graph is right. The characteristic failure of dependency-driven execution is a missing edge: task Y actually reads something X produces, but nobody declared the dependency, so the scheduler treats them as independent and runs them concurrently. Sequentially the code was correct because the declaration order happened to match the real order; in parallel it is a race between a producer and a consumer.
The schedule below traces it. E is supposed to enrich deduplicated records, and someone declared it as depending on A rather than D — an easy mistake when both read from the same directory. With enough workers E starts as soon as A finishes, reads a partially written or entirely absent artefact, and produces output that is wrong rather than missing. Note the two properties that make this bug expensive: it does not reproduce when workers are scarce (E gets scheduled after D anyway), and it produces plausible output rather than an error.
The defences are structural. Derive edges from *declared inputs and outputs* rather than writing them by hand, which is what build systems and data orchestrators do and why their DAGs are trustworthy. Make artefacts appear atomically — write to a temporary path and rename — so a consumer either sees a complete artefact or none at all, converting a silent wrong answer into a loud missing-file error. And run the pipeline with maximum parallelism in CI, because a missing edge is only visible in schedules that a constrained machine never produces (Stress Testing: A Test That Passed Once Proves Nothing). A cycle, by contrast, is the benign failure: it is detected at scheduling time by the topological sort and reported before anything runs (Topological Sort in DSA is the algorithm).
| # | Scheduler | Worker running D (dedupe) | Worker running E (enrich) | State |
|---|---|---|---|---|
| 1 | A completes; compute ready set from declared edges | · | · | ready set=B, C, D, E declared E deps=A actual E deps=D ✕ E entered the ready set while the artefact it truly consumes does not exist. The graph is wrong, so every schedule derived from it is unsound. |
| 2 | · | start D — begins writing deduped.parquet incrementally | · | deduped.parquet=partial (0 rows flushed) |
| 3 | · | · | start E — open deduped.parquet | E reads=partial file |
| 4 | · | · | read 0 rows, call partner API for nothing, write enriched.parquet (empty) | enriched.parquet=0 rows exit code=0 ✕ E succeeded, produced a valid empty artefact, and reported success. No error is raised anywhere. |
| 5 | · | D completes, deduped.parquet now has 4.2M rows | · | deduped.parquet=4,200,000 rows |
| 6 | all declared tasks complete; pipeline reported green | · | · | pipeline=SUCCESS enriched rows=0 expected=4,200,000 ✕ A green pipeline with an empty downstream table. The failure surfaces days later as "the dashboard is blank", far from its cause. |
| 7 | rerun on a 2-worker agent — D happens to be scheduled before E | · | · | enriched rows=4,200,000 pipeline=SUCCESS |
Key points
- A dependency graph is a DAG; the ready set (tasks whose predecessors are all complete) is exactly what may run simultaneously.
- The critical path — the longest duration-weighted chain — is the earliest possible finish with unlimited workers.
- Tasks off the critical path have slack; optimising them changes the finish time by nothing until the slack is consumed.
- Worker count stops mattering once the graph is critical-path-bound: in the example, two workers and four finish at the same time.
- When workers are scarce, schedule by longest remaining critical path — readiness order or duration order loses real time.
- The characteristic bug is a missing edge, which is a producer/consumer race that only appears at high parallelism and produces plausible wrong output.
- A cycle is the benign failure: topological sorting catches it before anything runs.
The loop, answered
Every field is required, which is why no lesson here can recommend concurrency without naming the interleaving that breaks it, the complexity it adds, and the simpler thing to consider first.
- • Model tasks as nodes and "Y consumes X's output" as an edge X → Y; the result must be acyclic.
- • Topologically sort to detect cycles and to obtain a valid sequential order.
- • Compute the critical path by finding the longest duration-weighted path from any source to any sink; slack per task is the difference between its latest and earliest possible start.
- • At run time, maintain a ready set: a task joins it when its last predecessor completes.
- • Assign ready tasks to free workers, prioritising by longest remaining critical path when workers are scarce.
- • A task's completion publishes its output and decrements the pending-predecessor count of each successor, which is the only synchronization the whole scheme needs.
- • A completes; B, C and D enter the ready set together and run concurrently on three workers, touching disjoint outputs — every interleaving among them is equivalent.
- • On two workers a good scheduler starts D before B and C because D is on the critical path; the pipeline finishes at 18. Starting B and C first delays E to 15 and the pipeline to 22 — the same graph, four minutes lost to ordering.
- • A missing edge puts E in the ready set at t=5; E reads a partial artefact from D and writes empty output, and every task reports success.
- • A declared cycle (E → A added by mistake) is caught by the topological sort before execution: nothing runs, and the error names the cycle. This is the failure mode you want.
- • A task fails mid-graph: its successors never become ready, and whether the independent branches (B, C) are allowed to continue is a policy decision the graph does not make for you.
- • Two tasks write the same output path with no edge between them: the last writer wins, nondeterministically, and the graph gave no indication that they conflicted — an output collision is a missing edge in disguise.
- • Guaranteed: with a correct graph, a task sees only complete outputs from its predecessors — the edge is the happens-before relationship.
- • Guaranteed: any topological order is a correct sequential execution, which is why a single-worker run is a valid correctness test for everything except the missing-edge class of bug.
- • Guaranteed: cycles are detected at scheduling time rather than at run time.
- • NOT guaranteed: that the graph reflects the real data flow. Nothing validates hand-written edges against what the code actually reads.
- • NOT guaranteed: any order among tasks in the ready set. Two independent tasks run in any order or simultaneously, on every run.
- • NOT guaranteed: that more workers finish sooner. Past the critical-path bound they do not.
- • NOT guaranteed: atomic artefact publication. Unless the task writes-then-renames, a successor scheduled too early can read a partial file — and that is what turns a missing edge from a crash into a wrong answer.
- • Tasks in the ready set contend for workers, which is why priority order matters when workers are scarce.
- • Independent tasks frequently contend on a shared resource the graph does not model — the same database, the same partner API, the same disk — so a graph-optimal schedule can still overload something (Bounding Concurrency).
- • The ready-set structure itself is shared between the scheduler and completing tasks, though at task granularity that contention is negligible.
- • Fan-in nodes are synchronization points: a task with many predecessors waits for the slowest, exactly like a join (Fork/Join).
- • Missing edge: a producer/consumer race producing plausible wrong output, reproducible only at high parallelism.
- • Output collision between two unrelated tasks writing the same path — a missing edge that presents as nondeterministic content.
- • Non-atomic artefact publication turning an early read into silent corruption instead of a loud failure.
- • Over-constrained graph: spurious edges (or a stage barrier) serialising tasks that are genuinely independent — no incorrectness, real time lost.
- • Poor priority order on a worker-constrained scheduler, extending the makespan beyond the critical path.
- • Cycle introduced by a new edge, caught at scheduling time — the benign case.
- • A partial failure leaving downstream tasks permanently unready while independent branches complete, producing a half-updated system.
- • Build systems, CI pipelines and data orchestration, where the graph is large, mostly independent, and the parallelism is genuinely free.
- • Any workflow with heterogeneous task durations, where a stage barrier would waste time that explicit edges recover.
- • When you need to know the theoretical floor: the critical path is the answer to "how fast could this possibly be?".
- • When deciding where to optimise — the critical path names the tasks and rules out the rest.
- • For provisioning: the maximum ready-set size, and W/S, bound how many workers can be useful.
- • When the true dependencies are not knowable statically — a task that decides at run time what it reads cannot be scheduled from a static graph safely.
- • When tasks are small: per-task scheduling and artefact publication overhead exceeds the work (Parallel Overhead).
- • When the graph is nearly a chain: the machinery buys nothing over a sequential script, and it costs comprehensibility.
- • When it lulls you into ignoring resources the graph does not model — three "independent" tasks hammering one database are not independent in any way that matters.
- • When the graph is maintained by hand and drifts from the code, at which point it is worse than no graph because it is trusted.
- • Critical-path length against actual makespan. A gap means scheduling loss, imbalance or resource contention, not a structural limit.
- • Per-task slack, which identifies the tasks that are worth optimising and the many that are not.
- • Ready-set size over time — its maximum is the most workers that could ever be busy, and its average is the parallelism you will actually see.
- • Worker idle time while the ready set is empty, which is structural, versus idle while it is non-empty, which is a scheduling or resource problem.
- • Makespan at several worker counts: a flat result past a point confirms critical-path boundedness (Work and Span).
- • Run the pipeline at maximum parallelism repeatedly and compare outputs; any variation is a missing edge or an output collision.
- • The graph is a second artefact that must stay consistent with the code, and hand-maintained graphs drift.
- • Failure policy must be explicit: fail fast, continue independent branches, or retry — each gives a different partial-completion state.
- • Artefact publication must be atomic and idempotent for retries to be safe, which changes how every task writes its output.
- • Debugging spans tasks: the failure is in E and the cause is in the edge that was not drawn, which no stack trace contains.
- • Dynamic graphs — where a task creates successors at run time — are far more powerful and considerably harder to analyse or visualise.
- • A sequential script, when the graph is nearly a chain or the tasks are short — simpler, easier to reason about, and often not much slower.
- • Stage barriers (run all of stage 2, then all of stage 3), when the graph is regular: less optimal, much easier to understand, and the loss is often small.
- • Fork/join, when the shape is genuinely one split and one merge rather than an arbitrary graph (Fork/Join).
- • A message-driven pipeline, when tasks are long-lived and streaming rather than batch — dependencies become channel connections instead of graph edges (Pipeline Parallelism: Different Items, Different Stages, Channels).
- • Deriving the graph automatically from declared inputs and outputs instead of writing edges by hand, which is the same design with the missing-edge failure mode removed.
Scheduling a task graph
Work, span and the speedup ceiling
critical path A → D → F → G = 90 ms work 20 + 30 + 25 + 40 + 15 + 20 + 10 = 160 ms ceiling T₁ / T∞ = 160 / 90 = 1.78× no extra edges — toggle one above
Scheduler timeline
What people believe, and what is true
More workers will make the pipeline finish sooner.
Only until the critical path binds. In the example, two workers and four workers both finish at 18 minutes, and a fifth worker never receives a task at all.
The slowest task is the one to optimise.
Only if it is on the critical path. B takes 4 minutes and has 9 minutes of slack; making it instant changes the finish time by zero.
The pipeline is green, so the graph is right.
A missing edge produces success and wrong output. It is invisible on a machine with few workers and shows up only when parallelism is high enough to run the producer and consumer concurrently.
Independent tasks in the graph do not interfere.
They are independent in *data*, not in resources. Three tasks that call the same rate-limited API are perfectly independent in the graph and will still throttle each other.
Go deeper
Overview
Draw an arrow from each task to the tasks that need its output. Anything with no unfinished arrows pointing at it can run right now.
Practical
Find the critical path — it is the floor on finish time and the list of tasks worth optimising. Everything else has slack.
Advanced
With scarce workers, prioritise by longest remaining critical path. Derive edges from declared inputs and outputs, publish artefacts atomically, and run CI at full parallelism to expose missing edges.
Internals
Execution is a topological sort with a pending-predecessor counter per node: a completion decrements its successors' counters, and reaching zero moves a task into the ready set. That counter is the only synchronization the whole scheme requires.