Trigger Rules and Failure Propagation Across a Dependency Graph

The readiness rule described in the previous article, in which all predecessors must succeed, is the default because it is the safest, not because it is the only useful condition. A workflow that cleans up temporary tables after a failure cannot wait for success; a workflow that merges whichever shards arrived cannot require all of them. Once the completion condition becomes a parameter rather than a constant, the scheduler needs a richer notion of what a task’s state means to its successors, and the propagation of that meaning is where most surprising workflow behaviour lives.

Five terminal states, not two

A task does not simply succeed or fail. The states that matter downstream are success, failure, and skip, with skip splitting into two kinds that behave identically for propagation purposes but differently for the run’s overall verdict: a task explicitly skipped by an operator, and a task skipped because its upstream condition was not met.

The distinction between “failed” and “skipped because upstream failed” is essential. If every task downstream of a failure were marked failed, the run’s error count would grow with the size of the remaining graph, every cleanup task would be reported as broken, and an operator scanning the failure list would have no way to find the task that actually broke. Marking descendants as skipped instead keeps the failure count equal to the number of genuinely broken tasks, which is the number an operator needs.

Skipped is also a state that must be produced promptly rather than lazily. A scheduler that leaves descendants in a waiting state after their parents have resolved will hold the run open indefinitely; the run only finishes when every task has reached a terminal state. So when a task fails and no successor’s trigger rule can still be satisfied by the remaining parents, the scheduler walks the graph forward marking each unreachable descendant skipped. That walk is the same in-degree decrement as before, with the counter replaced by a rule evaluation.

The rule set and what each one admits

The common rules form a small algebra over the multiset of parent states.

all_success requires every parent to have succeeded. It is the default and the only rule under which the graph’s ordering guarantee is unconditional: if a task runs, all its inputs were produced.

all_failed requires every parent to have failed, and exists for the inverse case, a recovery branch that should only run when the normal path is entirely broken.

all_done requires every parent to be terminal, whatever the outcome. Cleanup belongs here: temporary resources should be released whether the work succeeded or not, and a cleanup task gated on success will not run in precisely the case where it matters most.

one_success admits the task as soon as a single parent succeeds and the rest are terminal. It expresses “any of these inputs is enough”, and it is the rule that most often hides a data problem, because a merge that runs on one shard out of twelve produces a result that looks complete.

one_failed admits as soon as any parent has failed. Alerting belongs here, and so does the compensating action for a partial failure.

none_failed admits when no parent has failed, which means all succeeded or some were skipped. It is the rule for a task that should run if the path is not broken, even if part of the path was deliberately bypassed.

none_failed_min_one_success tightens that: at least one parent must have succeeded, and none may have failed. Without the second clause, a task whose entire upstream was skipped would run on no input at all, which is a common way to produce an empty output that silently overwrites a good one.

none_skipped requires every parent to have run to success or failure, and is used to assert that a branch which was expected to execute actually did.

Why the rule is per task, not per edge

Some systems allow a rule per incoming edge, such as run if this parent succeeded and ignore that one, and the resulting semantics are harder to reason about than the per-task form. With per-task rules, the condition is a pure function of the multiset of parent states, so a task’s readiness can be recomputed from the run state alone at any time. That property is what makes a scheduler recoverable: after a restart, it reads the stored states and recomputes which tasks are ready, without needing to have observed the events that produced those states.

With per-edge conditions, readiness depends on which edges were evaluated and in what order, and a recomputation must replay the same sequence. The gain in expressiveness is real but small; most per-edge needs can be expressed as two tasks with different rules feeding a third. The per-task rule also makes the failure-propagation walk tractable: to decide whether a descendant is still reachable, the scheduler checks whether any assignment of the unresolved parents’ future states could satisfy the rule. For the rules above this check is trivial: all_success fails as soon as one parent fails, while one_success survives as long as one parent is unresolved or has succeeded.

def reachable(rule, states):
    """states: parent states, 'pending' for those not yet terminal.
    Returns False only when no completion of the pending parents can satisfy the rule."""
    done = [s for s in states if s != 'pending']
    pending = len(states) - len(done)
    if rule == 'all_success':
        return 'failed' not in done and 'skipped' not in done
    if rule == 'all_done':
        return True
    if rule == 'one_success':
        return 'success' in done or pending > 0
    if rule == 'none_failed':
        return 'failed' not in done
    raise ValueError(rule)

The all_done case returning True unconditionally is correct and worth noticing: a task with that rule can never be skipped by propagation, because no configuration of its parents makes it unreachable. It will wait for every parent to resolve, however long that takes.

Where propagation gets expensive

The walk forward from a failure is proportional to the number of descendants, not the number of tasks, and in a graph with heavy fan-out the two differ by a large factor. A failure near the root of a thousand-task graph can mark nearly all of them skipped, producing a thousand state transitions for one event. Schedulers that store one row per task attempt handle this by updating rows in batches; schedulers that emit a message per transition can flood their own event queue, and the flood arrives at the same time as the retries the failure triggered.

The interaction with retries is the subtler problem. A task that has failed once but will be retried is not terminal, so propagation must not run yet. If the scheduler marks descendants skipped on the first failure and the retry then succeeds, the descendants must be un-skipped, which means the skip decision has to be reversible or deferred. Deferring is the simpler design: only a task in a terminal failed state, with retries exhausted or marked failed by an operator, triggers propagation. The consequence is that a run with long retry backoffs holds its descendants in waiting for the full retry duration, and the graph’s apparent progress stops while a single task cycles. That is the correct behaviour and it looks like a hang, which is why retry counts and backoff ceilings are visible configuration rather than hidden defaults.

A third cost is that propagation crosses the boundary between scheduling and execution. The scheduler knows a task failed; it does not know whether the failure left a partial write behind. A descendant marked skipped will not run, so it will not read the partial output, which is a benefit. But the partial output remains, and the next run of the same logical date may read it. Propagation protects the current run’s consistency and says nothing about the next one, which argues for task boundaries that either commit fully or leave nothing visible, as described in idempotent task boundaries.

Terminal states and the run verdict

Once every task is terminal, the scheduler computes the run’s status. A run containing any failed task is failed; a run with none failed and at least one skipped is usually reported as successful with skips, and the distinction matters because a run that skipped its main branch produced no output while reporting green. Treating skips as a warning requires the scheduler to know which tasks are optional, and the trigger rules do not carry that information, since a task is either part of the graph or not.

The practical resolution is to make the assertion explicit: a task that checks for the presence of the expected output and fails when it is missing, placed downstream with all_done. That task converts a silent skip into a loud failure without changing the scheduler’s model. It costs one extra task per branch and it is the only mechanism in the rule set that verifies anything about the data rather than about the schedule.

What the rule set cannot express is a condition on the content of a parent’s output. Rules see states, and a task that succeeded while producing an empty file is a success. Bridging that gap requires the parent to fail when its output is unacceptable, either through validation inside the task or through a downstream check task, and once the check exists, its failure is an ordinary failure that propagates under the ordinary rules. The remaining question is what to do when that failure is transient, which is the subject of retry policies.