Topological Readiness in Workflow Dependency Graphs

A workflow scheduler holds a set of tasks and a set of statements of the form “this task may not begin until that one has finished”. Everything else it does, whether queueing, retrying, or alerting, is built on top of the answer to one question, asked repeatedly: which tasks, given the current state of every task, are eligible to run. That question is a graph problem, and the shape of the graph determines how much of the work can happen at once.

The edge is a barrier, not a wire

The first thing to fix is what the arrow means. In a scheduler’s dependency graph, an edge from extract to transform says only that transform is not allowed to start until extract has reached a terminal state that counts as success. It does not say that rows flow along the edge, and in most workflow systems no data moves through the scheduler at all. The extract task writes a file or a table partition somewhere in storage; the transform task is configured to read that location; the edge merely guarantees that the write finished before the read began.

This is the structural difference between a workflow scheduler and a dataflow engine. In a dataflow engine the edge is a channel carrying records, and the engine can apply backpressure along it, partition it, and fuse operators across it. In a scheduler the edge is a timestamp comparison, and the data path is a separate system with its own consistency properties. The scheduler can therefore order tasks that share no data at all, and it can order tasks across systems that cannot talk to each other, which is why schedulers exist: a single job that loads a table, trains a model, and invalidates a cache has no common runtime to fuse into.

The cost of that separation is that the scheduler cannot observe the data. A task that reports success after writing half its output leaves the graph in a state that says the output is complete. Nothing in the dependency structure detects the lie. The mechanisms that compensate for it, such as commit protocols, sensors, and data-aware scheduling, are all attempts to give the scheduler a way to check something outside its own bookkeeping, and they are the subject of later articles in this cluster.

Readiness as in-degree

The classical algorithm for producing a valid execution order is Kahn’s: compute the in-degree of every node, put the zero-in-degree nodes in a queue, and repeatedly remove a node from the queue, emit it, and decrement the in-degree of each successor, enqueueing any successor that reaches zero. Each node is emitted once and each edge is examined once, so the cost is linear in the size of the graph.

For a scheduler the useful part is not the emitted order but the queue itself. The queue is the ready set: the tasks whose predecessors have all completed. A real scheduler runs a variant of this continuously, decrementing counters as completion events arrive from workers rather than walking the graph from the start.

from collections import deque

def ready_order(nodes, edges):
    """Kahn's algorithm; returns [] when the graph contains a cycle."""
    indeg = {n: 0 for n in nodes}
    succ = {n: [] for n in nodes}
    for a, b in edges:                 # a must finish before b starts
        succ[a].append(b)
        indeg[b] += 1
    q = deque(n for n in nodes if indeg[n] == 0)
    out = []
    while q:
        n = q.popleft()
        out.append(n)
        for m in succ[n]:
            indeg[m] -= 1
            if indeg[m] == 0:
                q.append(m)
    return out if len(out) == len(nodes) else []

The empty-list return is the cycle check. If any node remains with a nonzero in-degree after the queue drains, those nodes are in or downstream of a cycle, and no order exists. Schedulers reject such a graph at definition time rather than at run time, because a cycle discovered mid-run leaves tasks in a state that has no correct resolution: each is waiting on another, and the run can only be abandoned.

A single counter per task is enough because the completion condition is uniform: all predecessors must have succeeded. The moment the condition varies per edge, whether to run a task if any parent succeeded or even if a parent failed, the counter is no longer sufficient and the scheduler needs per-edge state and a trigger rule. That generalisation is where failure handling enters the graph.

What the graph does not bound

Two quantities govern how long a run takes. The first is the total work: the sum of task durations, which is what a fully serial execution would cost. The second is the critical path: the longest chain of dependent tasks, weighted by their durations. No amount of parallelism can finish the run faster than the critical path, because every task on it must wait for its predecessor. The ratio of total work to critical path is the maximum useful parallelism the graph admits.

A graph of independent daily extract tasks feeding one report has a critical path of roughly one extract plus the report, and a parallelism of the number of extracts. A chain of five transformations each depending on the last has parallelism one, and the only way to speed it up is to shorten a task, not to add workers. Adding workers past the width of the graph buys nothing and increases contention on whatever shared resource the tasks touch, which for data workloads is usually the storage system or the warehouse’s query slots rather than the scheduler.

The ready set is also where a scheduler’s fairness decisions live. When the queue holds more tasks than there are free worker slots, something must choose. Options include first-in-first-out by readiness time, priority by downstream critical path length, and per-owner quotas. Each trades latency for one class of work against another; none is universally correct, and the choice is visible in the order in which a congested run’s tasks appear in the log.

Fan-in and the cost of the join

A task with twenty predecessors is ready only when the last of the twenty finishes. Its readiness time is therefore the maximum of its parents’ completion times rather than the average, and one slow branch determines when the whole downstream half of the graph starts. This asymmetry is why a graph that looks balanced at the level of task count can behave like a single chain: fan-out is cheap because the branches start together, fan-in is expensive because it waits for the straggler.

The number of edges matters for a second reason. A task with k predecessors costs k bookkeeping entries in the scheduler’s run state, and the completion of each predecessor is a separate event that must be applied, checked, and possibly trigger an enqueue. A thousand-way fan-in produces a thousand events for one task, all serialised through whatever lock protects the run’s state. Schedulers that handle wide graphs usually batch these updates or aggregate predecessor states rather than recording every edge individually, at the price of a coarser picture of which parent is late.

There is also a scheduling order question hidden in the join. If the fan-in task needs only a summary of its parents, a count or a maximum date for instance, it can often be replaced by a single task that queries the storage layer for the aggregate, removing k edges from the graph and turning a wait into a read. Whether that is cheaper depends on the storage system’s metadata latency versus the scheduler’s event latency, and the substitution changes the failure semantics: a query that returns a partial answer because one partition is missing is harder to detect than a dependency that simply has not completed.

Where the model breaks down

Three failure modes recur in graphs that are correct on paper.

The first is the missing output. A task succeeds, the scheduler marks it done, and the artefact it was supposed to produce is absent or truncated. Every downstream task then runs against the wrong input and may itself succeed, propagating a bad result through the whole branch. Detecting this requires a check that reads the output, which is a different kind of assertion than the scheduler’s own state, and it is why commit protocols that make “success” mean “the data is durably visible at the expected path” matter more than the graph topology.

The second is the task whose duration is unbounded. The graph model assumes tasks terminate. A task that hangs holds every descendant in the ready-but-not-runnable state indefinitely, and the run has no progress signal other than the absence of completion. Timeouts attached to tasks are the graph’s only defence, and they convert a hang into an ordinary failure that the retry machinery can handle.

The third is the dependency on state the graph cannot see. Two tasks with no edge between them may still conflict: both writing the same partition, both holding a lock on the same table. The graph is silent about this because the conflict is in the storage system, not in the schedule. Schedulers offer pools and concurrency limits as a partial answer, capping how many tasks of a given class run at once, but the cap is a guess about the resource rather than a fact about it.

None of these invalidate the topological model. They mark its boundary: the graph orders tasks, and everything about whether a task’s effects are real has to be established by the task itself. The next question, once a task can fail, is what the graph should do with the failure, which is the domain of trigger rules and of idempotent task boundaries that make a second attempt safe.