DAGs, dependency resolution and trigger rules
What does an edge in a DAG claim, and how does failure travel along it?
DAG definition and dependency resolution
Why acyclic
The graph must have no cycles. This is not for looks. A cycle makes "complete" undefinable. If A waits for B and B waits for A, there is no order in which both can be authorized, and the scheduler's readiness test never becomes true for either. Acyclicity is exactly the property that guarantees a topological order exists (an ordering of all tasks in which every task comes after the tasks it depends on), and therefore that the run terminates. Everything else about DAGs follows from wanting a proof of termination for free.
Resolution is trivial
Dependency resolution is simple in principle. Keep the set of tasks whose predecessors have all reached an acceptable end state. Hand that set to the resource scheduler. The scheduler is a readiness predicate (a yes/no test) evaluated in a loop. Its cost is O(edges) per tick, which is nothing. This confirms again that coordination overhead is free here.
A tiny sketch of the whole idea:
def ready_tasks(tasks, state):
"""tasks: {name: [upstream names]}; state: {name: 'success'|'failed'|'skipped'|None}"""
return [t for t, ups in tasks.items()
if state.get(t) is None # not started yet
and all(state.get(u) == 'success' for u in ups)] # default rule: all upstream succeededWhat an arrow means
The hard part is what an edge means. An edge says: "B may start after A finishes." It does not say "B reads what A wrote." The orchestrator has no access to either side's input and output, so it cannot check. The edge is an unverifiable assertion by whoever wrote the definition file.
Two failure modes follow directly. They are the two most common orchestration bugs in existence:
| Failure | What happens | Visible? |
|---|---|---|
| Edge declared, no data dependency | False serialization: you pay latency for an order that nothing needed. | Harmless, invisible, everywhere. |
| Data dependency exists, no edge declared | The tasks run at the same time and a race decides the result. It passes for months and then fails on the day the upstream is slow. | Silent until the bad day. |
The second row is Tomás's Monday. It is the earlier principle at its purest: independence assumed, not true. And it fixes the economics of every graph: declared dependencies are the ones you maintain; undeclared ones are the ones that page you. Omitting an edge does not remove the coupling. It removes the visibility.
Trigger rules: how failure travels
A trigger rule is the failure-propagation policy attached to each task. It is a three-valued problem that looks like a two-valued one. A predecessor can end as success, failure or skipped, and the successor needs a rule for each combination:
| Rule | Runs when | Typical use |
|---|---|---|
| all success | every predecessor succeeded | normal work; fail-fast: failure is contagious |
| all done | every predecessor finished, whatever the outcome | cleanup and notification tasks; fail-degraded |
| at least one success | one predecessor succeeded | the join after a branch |
| none failed | no predecessor failed (skips allowed) | joins that tolerate skipped branches |
This makes the choice "fail-fast versus fail-degraded" explicit per task rather than per system. That is unusual and good, because most systems force one global choice.
The default is contagious failure, and it is the right default. A downstream task whose input did not appear will either crash later or, far worse, succeed on stale data and publish it. Silent success on stale input is the worst outcome this mechanism can produce, because it is the only one that does not raise an alert.
An edge is an unverifiable human claim about ordering; failure propagates along it by policy, and the dangerous default is the one that lets a task run on yesterday's data.