From dependencies to execution

This article follows the same argument and the same worked example as the film and the interactive explainer. The example's tasks, durations, check results and failures are invented teaching data; every schedule in it is computed from a stated model, and no number in it is a measurement. Statements about other systems name their source and the date it was read.

Inside the article

1A job, capable tools and limited time

You have a job, several capable tools and limited time. Which parts can happen together? What must wait? And what happens when one result is wrong?

Those sound like project-management questions, and partly they are. But once a job is handed to software, whether a build system, a workflow engine or a group of AI agents working side by side, the answers have to be precise enough for a machine to act on. They usually take the shape of a graph: pieces of work, and arrows between them. This article is about what those arrows mean, what turns a drawn graph into running work, and what that machinery does when the work goes wrong.

Watch the explanation

10:20 · captions optional

Follow one job through dependencies, limited capacity and checks on its results. Open the 4K film ↗

We'll call this graph engineering: choosing how to represent the work and its relationships, defining what each relationship means, and building the operations and constraints around them. That is a working name for this series, not a settled academic discipline. The ideas underneath it come from fields that are well established: graph theory, scheduling, build systems and distributed systems. Where the article relies on those, it cites them. Where it describes one product, it names the product and the date its documentation was read, because products change. Where it simplifies for teaching, or proposes a design of our own, it says so.

One ordinary job

Everything that follows is built on one small example: a weekly report on a team survey. Someone exports the survey responses and someone gathers the supporting documents. The responses are validated and cleaned, and statistics are computed from the clean table. Evidence is extracted from the documents. Then come a chart, a written interpretation and a methods note. Finally the report is assembled, and someone who wrote none of it checks it. That makes ten tasks.

The ten tasks. Durations are invented, in illustrative time units. The two writers of `references.md` each hold the file for their whole attempt, stage their changes privately, and replace only their own section when their result is accepted; an interrupted or rejected attempt publishes nothing. illustrative modelling choice
Task	Carried by	Units	Produces
Export survey responses	tool	2	`responses.csv`
Gather supporting documents	person	3	`documents/`
Validate and clean responses	code	3	`clean.csv`
Compute statistics	code	3	`stats.json`
Extract evidence from documents	agent	4	`evidence.md`, its own section of `references.md`
Write methods note	person	5	`methods.md`, its own section of `references.md`
Draw chart	tool	3	`chart.svg`
Write interpretation	agent	4	`interpretation.md`
Assemble report	code	1	`report.html`
Independently check report	person	2	`review-note.md`

The same ten tasks, with the same names and durations, run through the film and the interactive example. The report continues the survey example of the Those Dark Arts article What a Change Touches, which looks closely at what a changed input forces you to redo. This article starts earlier: how the work gets done at all.

2What a node is, and what an arrow means

Each node is a unit of work that produces something. Look at who carries each one. The export is a call to a tool. A person gathers the documents and writes the methods note. Cleaning and statistics are ordinary deterministic code. An AI agent extracts the evidence and drafts the interpretation. So a node is not the same thing as an agent. It is a piece of work, whoever or whatever does it, and the difference matters later: given the same complete inputs and task definition, deterministic code produces the same output again, while rerunning an agent may not.

A graph is only as useful as the meaning of its arrows, and that meaning has to be stated. In this example every arrow says the same thing: this task requires that accepted result. Cleaning requires the accepted export. Statistics are computed only from the accepted clean table. The interpretation needs the accepted statistics it will cite and the accepted evidence it will quote.

That is a deliberate choice, and a stronger one than the classical rule. In R. L. Graham's 1969 model of multiprocessor scheduling, the dependencies form a partial order drawn as a directed graph, and an edge from one task to another means the second cannot be started until the first has been completed (Graham 1969). Apache Airflow, by default, runs a task once all its direct upstream tasks have succeeded (Airflow 3.3.2 documentation), and there success means the task's process succeeded, not that anyone judged its output usable. Our arrow asks for more: the result must have passed its check and been recorded as accepted. Completed, succeeded and accepted are three different conditions, and several later sections turn on the difference. our design choice

Figure 1. The work graph. Each arrow means “requires this accepted result”. The heavier pink chain is the longest chain of durations, discussed in section 4. Illustrative example.

3What may happen together

Follow the arrows and some tasks are forced into sequence: export before cleaning, cleaning before statistics, statistics before the chart. Other pairs aren't related at all. No path of arrows connects exporting the responses with gathering the documents, so the graph says nothing about their order. They may run in either order, or at the same time. This is what it means for dependencies to form a partial order: some pairs of tasks are ordered, and the rest are left open.

Nothing in this graph leads back to where it started, so it is a directed acyclic graph, a DAG. Every DAG has at least one topological order, a sequence of all its tasks in which every arrow points forward, and usually it has many; a graph with a directed cycle has none (Erickson, Algorithms, ch. 6). Export first and gather second is one valid start; the reverse is another. A topological order is only a possible sequence, though. It says nothing about timing, and nothing about whether any result is right.

“No path between them” means independent as modelled. Two tasks with no arrow between them can still collide over something the graph doesn't show. In this example, evidence extraction and the methods note both add entries to the same references file, and only one may write to it at a time. That constraint is not a dependency, since neither needs the other's result. It belongs to a different picture of the job, the resources each task holds while it runs, and section 4 shows what it does.

Joins

Where arrows meet, a task joins its inputs. The interpretation has two incoming arrows, from the statistics and the evidence. Assembly has three, from the chart, the interpretation and the methods note. In this example a join waits for every required input to be accepted, never just the first to arrive. Build-system research states the same rule for parallel scheduling in dependency order: build the full dependency graph, and whenever all of a task's dependencies are complete, the task can start (Mokhov, Mitchell and Peyton Jones 2018, §6.2).

Not every system joins that way. Airflow offers other trigger rules, including one that runs a task as soon as one upstream task has succeeded. LangGraph, a framework for stateful agent workflows, activates a node when a message arrives on any incoming edge. Two separate edges into a node do not, by themselves, mean “wait for both”, and its documented ways to wait for all have their own edge cases (LangGraph documentation, 1.x, read 7 October 2026). None of these rules is wrong. They are different rules, and two arrows meeting on a diagram don't tell you which one applies. framework behaviour, dated

4Why fifteen, not ten?

Here is a question to carry through this section. The ten tasks add up to thirty units of work. There are three workers, where a worker is anything that carries one task at a time: a process, a person's turn, an agent session. Thirty divided by three is ten. So why does the report take fifteen?

Start the clock. At time 0 the export and the document gathering begin together, because nothing stands between them. The export finishes at 2 and cleaning starts. Gathering finishes at 3 and evidence extraction starts. Cleaning finishes at 5, and two tasks become ready at once: the statistics and the methods note. The statistics take the free worker. A third worker is also free, and the methods note is ready. Yet it doesn't start. Evidence extraction is still writing to the references file and will hold it until 7. For two units, a ready task waits beside an idle worker.

Figure 2. The three-worker schedule. The methods note is ready at 5 but cannot be placed until the references file is released at 7. Tasks on the longest chain have pink borders. Computed from the illustrative example's model.

Ready is not the same as placed. Whether a task is eligible depends only on the work graph: are all the results it requires accepted? Whether it can be placed now is a separate question: is there a worker free, and is everything else it must hold while running (here, the file) available? Graham's list-scheduling model already keeps the two apart. Processors scan a priority list for the first task whose predecessors are all complete, and a processor that finds none sits idle (Graham 1969, §2). His model has only identical processors, though. Shared files, memory, model availability and rate limits are extra resources it does not include. Treating them as a second test, after eligibility, is how this example extends the classical separation. explanatory simplification

Let the clock run on. The methods note runs from 7 to 12. The statistics finish at 8, which releases two tasks: the chart (8 to 11) and the interpretation (8 to 12). Assembly can only start when all three of its inputs are accepted, at 12, and takes one unit. The independent check runs from 13 to 15.

Now follow the longest chain of required results: export, clean, statistics, interpretation, assembly, check. Its durations are 2 + 3 + 3 + 4 + 1 + 2 = 15. That chain is the critical path, and it gives the first of two lower bounds that scheduling theory states plainly. No schedule, however many workers it has, can finish before its longest dependent chain. And no schedule on P equal workers can finish before the total work divided by P (Blumofe and Leiserson 1999, §2). Here the floors are 15 and 10. The higher floor is the earliest possible finish, and this schedule reaches it exactly, so no scheduler could beat fifteen with these tasks. The methods note's two-unit wait cost nothing: it still finished at 12, the same moment as the interpretation, so assembly was never delayed by it.

So the answer is not “thirty divided by three”. The report takes fifteen because of its longest chain of required results. Capacity only shows up when it is short. Change the number of workers and recompute, with everything else unchanged:

Finish time for each worker count, computed from the illustrative example's model.
Workers	1	2	3	4	5	6
Finish	30	18	15	15	15	15

One worker does everything in sequence: thirty. From three workers on, nothing moves, and extra capacity just waits. The ratio of total work to critical path, here 30 ÷ 15 = 2, is what Blumofe and Leiserson call the job's parallelism: an average, and a ceiling on the speedup any number of workers could give. It is not a head-count. This example's ratio is 2, yet under its rules two workers finish at 18 and it takes three to reach 15, because the shape of the graph, the shared file and the scheduling rule all matter.

Two workers is the instructive case. At time 8 the statistics are accepted, and the chart and the interpretation become ready together. One worker is busy with the methods note until 12, so only one is free. Something has to choose, and that something is the scheduler. This example's rule is “longest remaining chain first”. The interpretation has 7 units of chain left (4 + 1 + 2) and the chart has 6 (3 + 1 + 2), so the interpretation goes. The chart waits from 8 to 12, runs until 15, and assembly and the check follow: the report finishes at 18. A task that was off the critical path has become the limit, because capacity ran short at the moment it became ready.

That priority rule is our choice, not a law; many others exist. Scheduling theory does offer one guarantee that holds whichever rule is used. If the scheduler never leaves a worker idle while some task is ready, the finish time is at most the total work divided by the number of workers, plus the critical path. Since each of those terms is a lower bound, such a schedule is never worse than twice the best possible (Blumofe and Leiserson 1999, Theorem 1, crediting Brent and Graham). The guarantee belongs to the classical model, which has no shared files, no failures and no checks. The next sections add those back one at a time.

5Choosing among ready work

A scheduler only matters when there is a choice: several eligible tasks and not enough room for all of them. Graham's 1969 model makes the choice mechanical. The tasks are put in a fixed priority list. Whenever a processor is free, it takes the first task on the list whose predecessors have all completed, and if it finds none it sits idle until something finishes (Graham 1969, §2). The model assumes identical processors, tasks that run to completion once started, fixed durations, and no communication cost or failure.

Our example's scheduler works the same way, with one addition. Its list is ordered by remaining chain: a task's own duration plus the longest chain of durations from it to the end of the graph. Ties go to the task listed earlier. And because a ready task may still be unplaceable, the scheduler skips a task that cannot get every resource it needs and tries the next one. A lower-priority task may then use a slot the higher-priority one could not. illustrative modelling choice

What does any such rule guarantee? Graham proved that for list scheduling on identical processors, changing the priority list, relaxing the dependencies, shortening tasks or changing the number of processors can never make the finish time worse than 1 + (n − 1)/n′ times the original, where n and n′ are the processor counts before and after. With the same number of processors the factor is 2 − 1/n, and he showed that factor can actually be reached (Graham 1969, §3, Theorem 1). Following the same argument, any schedule that never idles a worker while a task is ready finishes within the total work divided by n, plus (1 − 1/n) times the critical path. That is a slightly sharper version of the bound in section 4. established theory

The same paper is better known for its counterexamples. In Graham's worked example, with three processors and a fixed priority list, the job finishes at 12. Give it a fourth processor and, with the same list, it finishes at 15. Shortening every task by one unit gives 13. Removing some of the ordering constraints gives 16, and merely reordering the list gives 14. In his words, relaxing the order, decreasing durations or increasing processors can all cause the finish time to increase (Graham 1969, §2).

Those anomalies come from a simple fixed-list policy, with no coordination cost, no messages and no model calls. They show that a plausible scheduling rule need not get better as resources grow. They say nothing directly about AI agents, whose costs and failure modes are different (section 13). In our own example, adding workers never made things worse (30, 18, 15, 15, 15, 15), but that is a property of this graph and this rule, not a guarantee.

6Something to run it: the runtime

None of this happens because a diagram exists. Something has to decide that a task is ready, start it, give it access to the tools and files it may use and no others, notice when it finishes, run its check, record the outcome durably, and tell the scheduler what has changed. We'll call that machinery the runtime, or harness. Products divide these duties differently, and some of them belong to the scheduler, some to a separate executor and some to the tool layer. The split used here, with five duties (state, dispatch, tool boundary, durable record and checks), is a teaching device, not a standard architecture. explanatory simplification

The runtime is not the diagram animated. The graph says what must hold; the runtime is what keeps it true when something fails. Our example's runtime follows a fixed order at each instant. First, finished attempts release their resources and are checked. Then an interruption, if one is due, stops every running attempt. Then, unless the runtime is down, the scheduler starts tasks in priority order. That order is a rule of the model. Without one, “finished at 7” and “started at 7” would be ambiguous.

Now interrupt the three-worker run at time 6, with the runtime down for one unit. At that moment evidence extraction has been running for three units and the statistics for one. Both are cut off and their partial work is discarded. Because evidence extraction publishes to the references file only on acceptance, the cut-off attempt has left nothing half-written there. illustrative modelling choice

What happens next depends entirely on what was recorded. With a durable record, the export, the documents and the clean table were accepted before the cut and are restored on restart without running again. Only the two cut-off tasks run again, from the start, at 7. Evidence takes the references file again until 11, so the methods note, ready since 5, now waits until 11 and finishes at 16, which makes it the last input assembly needs. The report finishes at 19, and 34 units of work were spent instead of 30. With nothing recorded, every task runs again from 7, export included: the report finishes at 22, and 42 units were spent. The interruption cost one unit of downtime, but the missing record cost far more.

Notice also that the interruption moved the bottleneck. In the uninterrupted run the methods note had slack. After the interruption it is the last thing assembly waits for. Bottlenecks belong to a particular schedule, not to a task.

7Restore is not retry

Two different things happened to the tasks at time 7, and they are easy to blur. The export, documents and clean table were restored: their recorded results were returned without running those tasks' work again and without checking it again. If one of them had been subtly wrong, the restored copy would be wrong in the same way. The statistics and evidence were retried: the work ran again from the start. A retry repeats everything the work does, including any effect it has on the outside world. If the work had charged a card or sent an email, it could do so twice.

Durable workflow engines are built around this distinction. Temporal records every step of a workflow execution in a durable event history. If a worker crashes, another worker replays the workflow code against that history to rebuild its state and carry on (Temporal, Event History). During replay, the deterministic workflow code runs again, while the recorded results of completed Activities, the steps that do real work, are reused rather than re-executed (Event History walkthrough). For replay to work, the orchestration code must make the same decisions every time. Anything unpredictable, including calls to AI models, belongs in separately recorded Activities (Workflow Definition).

Temporal's documentation is also candid about the limit. Failed Activities are retried automatically by default. An Activity will be observed as completed exactly once, but it may be executed more than once, and may even partly complete more than once. One case it names is a worker that finishes an Activity and then crashes before reporting it. So Activities with outside effects should be idempotent: doing them twice has the same effect as once. That is usually enforced by the service being called, with an idempotency key, rather than by the Activity itself (Temporal, Activity Definition; Retry Policies; all read 7 October 2026). framework behaviour, dated

LangGraph draws the line in a different place. With a suitably durable checkpointer, it saves state at the boundary of each super-step, its unit of parallel progress, and keeps the outputs of nodes that did finish within a step that failed, so those are not run again. A node that was interrupted part-way, however, restarts from the beginning of its function, and any side effects before the interruption happen again. The documentation recommends idempotency keys, upserts or a read before each write (LangGraph persistence; Checkpointers). How much survives a crash depends on the durability mode and storage chosen: one mode cannot recover from a crash mid-execution, and the in-memory saver is meant for experimentation. framework behaviour, dated

So the unit of recovery differs. Temporal restores per recorded Activity completion, with deterministic replay. LangGraph restores per super-step checkpoint, plus the writes of nodes that finished. A build cache restores per task and exact set of inputs (section 12). All three “restore a recorded result”. None of them can promise that an outside effect happened exactly once, because that is not a property a lower layer can supply on its own. Saltzer, Reed and Clark made the general point in 1984: an application retrying after a timeout can create duplicate requests that look, to the communication system, like new ones, so suppressing duplicates has to be done by the application itself (Saltzer, Reed and Clark 1984). A runtime can record a step as completed once; it cannot, in general, make the world see it once. established theory

8Finished is not accepted

Go back to the uninterrupted three-worker run. At time 12 the interpretation finishes, but its check finds that it cites a mean which does not appear in the statistics. The process completed, and the output is rejected.

That verdict belongs to the interpretation's own named check, which decides whether its output may release the tasks that require it. In the example these verdicts are authored inputs that the runtime applies; it judges nothing itself. The chart and the methods note have been accepted, yet assembly holds. A plausible draft cannot release a join that requires accepted results. illustrative modelling choice

So the graph is revised. A correction node is added. It reads the rejected draft and the check's finding, and has the same required inputs as the original. Every task that required the interpretation now requires the correction instead. The correction runs from 12 to 14 and passes its check. Assembly runs from 14 to 15 and the independent check from 15 to 17, so the report finishes at 17 instead of 15, after 32 units of work. The rejected attempt is not erased; it stays on record, joined to its correction by a “revises” edge. This is a bounded revision. The interpretation has a limit of two attempts, and this was the second. In a variant of the example where the correction is rejected as well, at 14, no third attempt is added: assembly and the independent check stay held and the run stops for a person's decision. It does not loop.

There are now three different decisions in play, and they should not be confused. Each task's own check decides whether that task's output may release the next task; that is what held assembly at 12. The reviewer who wrote none of the report then makes a separate judgement on the assembled report, at the end of the run, from 15 to 17. That review cannot be the check that held assembly, because it had not started. And whether this explainer itself is any good is an editorial decision made outside the example altogether. illustrative modelling choice

Why insist on checks that know what a result is for? The end-to-end argument of Saltzer, Reed and Clark holds that some functions can be implemented completely and correctly only with the knowledge of the application at the end points. Lower-level checks are useful aids, but they do not remove the burden on the application (Saltzer, Reed and Clark 1984). The paper is about communication systems. Applying it to who decides whether a piece of work can be used is our analogy, not something the paper proves.

Build-system research makes a related point precisely. A build is correct if every result equals what its task would compute from the final inputs, which means correct relative to the task description, not to what anyone wanted (Mokhov, Mitchell and Peyton Jones 2018, §3.6). If the description is wrong, a correct build reproduces the wrong thing faithfully.

And checks can be shallow. A NeurIPS 2025 study of failures in multi-agent LLM systems found that having a verifier is not a cure. In one case a generated chess program compiled and passed its review phases, yet broke the rules of chess, because the checks were superficial (Cemri et al. 2025, §4). In the same paper's case study, making one coding system loop until its review step was satisfied, with a cap on iterations, raised task success on a 32-task set from 25% to about 41%. That is one framework on one small custom benchmark, with no repeated runs reported for it. And because the change added a bounded loop as well as a check, the gain cannot be credited to verification alone.

9When an input changes

Results stay valid only as long as their inputs do. Suppose that after the report is finished, one gathered document is replaced by a corrected version. Which work needs to be done again?

Follow the arrows forward from the changed task. The work that may need redoing is the change itself and everything reachable from it along the arrows. Here that is the document gathering, evidence extraction, the interpretation, assembly and the independent check. The other five tasks keep their accepted results: export, cleaning, statistics, chart and methods note. Rerunning the affected five takes 14 units.

The affected set follows the requires arrows only. Sharing a file or a resource does not make a task affected. The evidence rerun replaces only its own section of references.md, and the methods note's section stays as it was. That keeps the methods note out of the rerun, as it should be: nothing it relied on has changed. illustrative modelling choice

This is the standard picture in build systems. In Mokhov, Mitchell and Peyton Jones's example, editing a header that every file includes forces a full rebuild, because all the tasks depend on it transitively; editing one source file needs only a partial rebuild (Mokhov et al. 2018, §2.1). The same paper defines a minimal build as one that runs each task at most once, and only if something it depends on has changed. established theory

Some build systems go further, with early cutoff. If a redone step produces exactly the same output as last time, its dependants are not rerun: adding a comment to a source file need not relink the program (Mokhov et al. 2018, §2.3). Shake and Bazel support this; the paper explains why Make cannot and Excel finds it difficult. Our model compares nothing, so it applies no early cutoff.

Two cautions carry over to work done by people and agents. Identical means unchanged, not correct: early cutoff establishes that a result is the same as before, which is only as good as whatever accepted it before. And steps that are not deterministic can produce different bytes that are equally acceptable. The paper's example is a compiler run in parallel that produces different but semantically identical results, so byte equality is too strict a test of “the same” as well as too weak a test of “right” (§6.3). A third complication is that some tasks discover what they need only while running, so the set of affected work cannot always be computed in advance (§2.2–2.3).

How to decide what a change touches, when byte equality is the wrong test and some reads go unrecorded, is the subject of the follow-up study What a Change Touches. It uses the same survey report.

10Not every graph is a DAG

Add one wrong arrow to the example: the interpretation now requires the accepted review. But the review needs the assembled report, and the report needs the interpretation. Run it with three workers. Seven tasks finish, the last of them, the methods note, at 12. The interpretation, assembly and the check never start. Each waits for another that is itself waiting. That is a dependency cycle, and it deadlocks.

The theory says why. A graph with a directed cycle has no topological order (Erickson, ch. 6). Under an all-required-inputs rule, no task on the cycle can ever become ready. Build systems therefore assume their task graphs are acyclic. Every build system in Mokhov et al.'s survey is correct only under that assumption, and cyclic dependencies are typically not allowed, with rare exceptions (Mokhov et al. 2018, §2.1, §3.6). established theory

Yet section 8 had a loop: attempt, check, correct, check again. The difference is where the loop lives. In this example it lives in control flow: the possible transitions of one task's attempt. An attempt runs and is checked. On a pass, its output is accepted. On a failure with an attempt left, a correction is added. On a failure at the limit, everything that depends on it is held for a decision. Each pass through the loop adds a new node to the work graph, so the work graph stays acyclic at every revision, and the attempt limit bounds the loop.

That is also the established engineering answer. Mokhov et al. describe LaTeX, which may need rebuilding until its output stops changing, and argue for encoding it not as circular tasks but as a series of iterative steps. They stress that the number of executions is bounded, as Excel's iterative calculation is (Mokhov et al. 2018, §6.6).

Other systems allow cycles directly, with different semantics. LangGraph graphs may loop. The designer supplies a stopping condition, and a recursion limit caps the number of super-steps; from version 1.0.6 the default is 1,000, and exceeding it raises an error (LangGraph Graph API). A step limit bounds steps, not cost or correctness. This works because a LangGraph node does not wait for all its predecessors; it runs when a message arrives. That is a different rule, not a refutation of the deadlock argument.

Conditional paths need equally explicit rules. Airflow documents that after a branch, the path not taken is skipped. Under the default join rule the skip cascades into the join, so the join is skipped too unless its rule is changed (Airflow 3.3.2). LangGraph's list-form join has a mirror-image trap: if one listed branch never runs, the join never runs either, and no error is raised (Use the Graph API). Airflow's own documentation notes that its term “Dag” has evolved well beyond the mathematical object.

None of this makes a DAG a safety property. A DAG guarantees that an order exists and rules out deadlock from dependencies alone. It says nothing about whether the tasks are right, whether hidden inputs exist, or whether checks are deep enough.

11Four kinds of graph

The word “graph” has been carrying several meanings, and they are worth separating. Here is the same report drawn four ways.

As a knowledge graph, it relates entities and claims. Team A's mean score supports the claim “Team A scored highest this week”, and both are about Team A. A respondent's comment on the new export also supports the claim, and is found in a document, the release notes. Nothing here says when anything runs.

As a work graph, it relates tasks and artifacts through “requires” and, after a revision, “revises”. This is the only picture the scheduler reads for order, and in this example it is acyclic at every revision.

As a control-flow graph, it shows what may happen to one attempt: then, on pass, on fail. It may contain a bounded loop. It describes possibilities, not dependencies.

As a resource graph, it shows what each task holds while it runs: one of three workers for every task, and the single-writer references file for evidence extraction and the methods note. It decides where and when a ready task can run, never whether it is ready.

The separation matters because operations on one picture are easily mistaken for operations on another. A retrieval over the knowledge graph can hand “Write interpretation” the passages it should quote. Deciding when that task runs is a separate operation, on a different graph with a different edge meaning. The four-way split is our editorial distinction, not a standard taxonomy. Each kind does appear in the sources read for this article with its own edge meaning: a task order (Graham), dependencies between tasks and keys (Mokhov et al.), message and control edges (LangGraph). editorial distinction

12How real systems package these ideas

Real systems combine the mechanisms above in different proportions. Three families show the range, each through the guarantee it actually documents.

Build systems

Build Systems à la Carte separates a build system into two choices that turn out to be independent: a scheduler, which decides in what order tasks run, and a rebuilder, which decides whether a task needs to run again at all. Make, Ninja, CloudBuild, Buck, Excel, Bazel, Shake and Nix each sit at a different point in that grid (Mokhov, Mitchell and Peyton Jones 2018, §4, Table 2). Its models are deliberately simple approximations; there is, for instance, no formal specification of Make. A topological scheduler needs every dependency known before the build starts. When dependencies are discovered on the way, a system either aborts a task and restarts it later, possibly wasting work already done, or suspends it until its new dependency is ready (§4.1).

A rebuilder can also restore. A build cache stores results keyed by the exact inputs that produced them, and can copy a recorded result instead of doing the work (§2.4, §4.2.3). That is sound for a result recorded for the same complete inputs and task definition, under the system's cache and consistency rules. Tracking every real input is needed for that, but untracked inputs are not the only hazard: non-deterministic and volatile tasks need rules of their own (§6.3–6.4). The authors' executable models are published as a Haskell package. established theory

Durable workflow engines

Temporal, read here as one example, puts recovery first: a durable event history, deterministic workflow code replayed against it, recorded Activity results reused, automatic retries, and idempotency left to the application (section 7). Its documented guarantee is the honest one: completion recorded once, execution possibly repeated. framework behaviour, dated

Stateful agent frameworks

LangGraph, read here as one example, starts from shared state. A graph has a state object; nodes are functions that read it and return updates; edges decide which node runs next, either fixed or through a routing function (LangGraph Graph API). It runs in rounds called super-steps, in which every node with a new incoming message runs, possibly in parallel. A node may launch a variable number of parallel tasks at run time. Its edges are control and message flow, not “requires this accepted result”.

Shared state brings a cost the work graph above avoids by giving every file a single owner. When parallel nodes in the same round write the same field and that field has no combining rule, a reducer, the run stops with an error rather than picking a winner. With a reducer, such as appending to a list, the writes are merged, and the order of updates within one round is not guaranteed (LangGraph, concurrent graph update error). Someone has to design the merge rule. framework behaviour, dated

Where each puts acceptance

Across the three, the meaning of “done” varies. In Airflow the default join waits for upstream success, which is task-process success, not acceptance of the output (Airflow 3.3.2). A build system's correctness is relative to the task description. Temporal records completion. None of them, out of the box, decides whether a written interpretation says something true. That decision has to be designed in as a check with a stated owner, which is what the example's “accepted” edge does. All product descriptions in this section reflect documentation read on 7 October 2026 (LangGraph 1.x, current release 1.2.14; Airflow 3.3.2; Temporal's continuously published documentation), and products change.

13More agents is not automatically better

If work can be split, it is tempting to assume that more agents means faster or better results. Section 5 showed one reason to doubt that even for a mechanical scheduler. For AI agents the evidence is more specific, and more mixed.

A study by researchers at Google Research, Google DeepMind and MIT compared a single agent with four multi-agent designs across 260 configurations, six agentic benchmarks and models from three providers. Prompts, tools and the total token budget were held fixed (Kim et al., arXiv:2512.08296, version 3, 8 April 2026). Whether coordination helped depended on the task. Multi-agent designs ranged from about 81% better than the single agent on a decomposable financial-analysis benchmark to 70% worse on a sequential planning benchmark, where every multi-agent variant did worse. The authors' most robust pattern was capability saturation: once a single agent already scored above roughly 45% on a task, adding coordination tended to give diminishing or negative returns. They also report substantial coordination overhead, with multi-agent designs using several times the tokens of a single agent depending on design. Under their fixed total budget, that is budget not spent on the task itself.

The authors list the limits themselves. There were six benchmarks, two of them evaluated on 20-task subsets. Teams had at most nine agents. Prompts were not tuned per model, and the regression explains a modest share of the variance. The study also reports a striking difference in how errors propagate between designs, but in its own controlled analysis that measure did not predict success, so it is not repeated here as a finding. empirical result with scope

The NeurIPS 2025 study met in section 8 looked at the failures themselves. Its authors annotated over 1,600 execution traces from seven open-source multi-agent frameworks on coding, maths and general-assistant benchmarks. They grouped the failures they found into 14 modes in three categories: system design, misalignment between agents, and task verification (Cemri et al. 2025). They argue that many failures come from how a system is organised (roles, workflow, information flow and checking) rather than only from the underlying model, and they offer it as a conjecture that better base models alone will not be enough. The taxonomy is explicitly not exhaustive, and the failure rates it reports belong to particular systems on particular benchmarks, not to multi-agent systems in general. empirical result with scope

Read together, the worked example and these studies point the same way without proving anything about any particular system. Splitting work helps when the work really is independent and capacity is the constraint. It costs coordination, shared writes need merge rules, and every extra hand-off is another place a check can be shallow. Neither study measures the way we split work in our own factory, and we have not run such a comparison. The next section describes what we built, not that it is better.

14Our work, dated

The mechanisms above are not abstract for us. Our own production factory is one dated example of engineering choices, described here as the version we used in October 2026, not as a recommendation and not as evidence of superiority.

In that version, each task in the graph names what it depends on, which files it alone may produce, and which agent provider carries it. Every node is agent work; this version has no separate node kinds for plain code or tool calls. Before anything runs, the factory refuses a graph with a dependency loop or a dependency on a task that does not exist. Changing the plan is done by revising the graph, not by looping inside it: a revision keeps the run's identity, reopens only the tasks it names and keeps every result that still stands. A task starts only when everything it needs has succeeded, and a failed required input blocks its dependants. Tasks that are ready together start together, in rounds, and the next round begins when the current one ends. There is no capacity model and no resource placement. The task scheduler decides when work may start, not which machine runs it.

Finishing is not accepting there either. A task counts as complete only when every file it owns exists, is non-empty and is committed on its own. That is a mechanical check of completion. A separate verifier then decides whether the product passes. A rejected result goes back to the same agent session with the exact error, within a small attempt budget. Agent sessions are saved, so an interrupted run resumes the same work, and refuses to start a duplicate if a worker may still be running. When a worker needs a decision only the operator can make, new work waits and the answer returns to that same session.

Placement on hardware is a separate layer. Our model requests pass through a gateway and a queue that track each machine's health, load, available models and GPU memory. Those are observations, and observations can be out of date. We have not verified the placement rule itself for this article, so it is not described here.

Two case studies

Luna — Changing a connected system covers 4–5 September 2026. During a model comparison, a model returned a valid answer in a different response format, and our adapter reported a failure. The same assumption sat in the chat worker and in the evaluation tool, so both had to change together. The fix had a small work graph: independent repairs ran in parallel, and verification waited for them to join. Loki then extended the work to adapt his iterative resolution pattern, a bounded loop inside the request runtime, which has a different structure from the work graph that changed the system. A separate review asked whether it was the right adaptation; it made the two-reflection ceiling structural and reopened affected work. Tests used local fixtures; the case notes attribute the supplied live observation to Loki. These revisions deployed nothing, and no quality improvement is claimed. The film's animation of that case reconstructs its dependencies; it is not a recorded timeline.

LOOM — orchestrating an investigation covers LOOM, a modular instrument we were moving from the browser into a native application, with the browser version defining correct sound within set tolerances. One patch still sounded different. The investigation split into independent questions, and a combined experiment waited for the repairs it needed. Source reading, small probes and a counterfactual together pointed to a Chromium behaviour that stopped an oscillator's phase. The final check, in early October 2026, reported all 323 audio fixtures within the existing tolerances. Physical hardware and some delivery checks remained, and offline tests do not cover every machine.

Design, not deployment

We are also designing a next stage in which a dependency would count only once its result is accepted at a specific version, and in which feedback creates a new attempt or revision rather than tasks waiting on each other. That is design work, not a running system, and nothing in this article depends on it. our design proposal

15The questions, answered

What does an edge mean? Whatever you define; here, “requires that accepted result”. Other systems mean “completed”, “succeeded” or “a message arrived”, and the difference decides what waits.

Why is a task waiting? A result it requires isn't accepted yet, or there is nowhere to run it: no free worker, or a resource such as the references file is held.

What can safely overlap? Work with no dependency path between it, when there is enough capacity and no conflicting access to shared state.

What survives interruption? What was recorded. Restoring returns it as it was; everything else is retried, with its outside effects.

Who decides a result can be used? Each task's own check, then a separate review of the whole. Whether the explanation itself is good is a decision outside the example.

A job, capable tools and limited time. The graph shows what must wait. The runtime carries the work through failure. And acceptance decides what is ready to use.

Definitions used in this article

These are the meanings the article uses throughout. The four kinds of graph at the end are an editorial distinction, not a standard taxonomy.

Terms

Work graph: Tasks (units of work carried by code, a tool, a person or an agent) and the artifacts they produce, connected by dependency edges. In this example it is acyclic at every revision.
Edge meaning: The stated condition an arrow encodes. Here: “the target cannot start until the source's output has passed its check and been recorded as accepted”. Other systems use “completed” or “succeeded”.
Partial order: The ordering the edges impose: a task comes before another if a path of arrows leads from one to the other. Tasks with no path between them are unordered and may overlap, unless a shared resource prevents it.
Join: A task with several incoming edges. The join rule says what it waits for. In this example it waits for all required inputs to be accepted; other systems activate on any input, or on upstream success.
Critical path: The longest chain of durations through the dependencies. No schedule finishes sooner, however many workers it has.
Eligibility and placement: Eligible (ready): every required result is accepted. Placed: a worker and every other resource the task must hold are free at that moment, so it actually starts. They are separate tests.
Scheduler and runtime (harness): The scheduler chooses which eligible work to start when there is a choice. The runtime, or harness, does the rest of running it: it keeps each task's state, dispatches it, limits its tools, records its results durably and runs its checks. Products divide these responsibilities differently. explanatory simplification
Completion and acceptance: Completion: the process finished. Acceptance: its output passed a check that knows what the output is for, and that verdict was recorded. Only acceptance releases dependants in this example.
Restore and retry: Restoring returns a result that was recorded earlier, without running that task's work again or checking it again. What can be restored depends on what the system recorded durably, and at what unit. Retrying runs the work again, along with any outside effects it has.
Bounded revision: After a rejected result or a changed input, the graph is revised: a new attempt is added as a new node that replaces the rejected one for its dependants. A limit on attempts stops the process for a decision rather than looping.
Four kinds of graph: Knowledge graphs relate entities and claims. Work graphs relate tasks and artifacts. Control-flow graphs show possible transitions, and may contain bounded loops. Resource graphs show machines, capacities and what each task holds. editorial distinction

How the article labels claims: established theory peer-reviewed or textbook results; framework behaviour, dated one product's documented behaviour on the date read; empirical result with scope a measured finding with what was measured; explanatory simplification a teaching device; illustrative modelling choice a rule adopted for this worked example; our design proposal design work, not a running system.