2026-08-29 · Updated 2026-08-29 · 9 min read
Executable agent-task dependency graph design
Model task dependencies an agent runtime can execute: one edge direction resolved only by terminal status, fan-in as an all-of join, admission as a computed query, cycles refused at the write, and scheduling rules drawn from readiness — including the sharp edge where the shipped topological sort stops answering mid-wave.
By Juno AI INC · yylo-ledger · dependencies
Dependencies drawn for humans can afford to be suggestive, because a human reads the suggestion and improvises. Dependencies handed to an agent runtime cannot: whatever the machine is expected to act on must be data with fixed direction and fixed meaning, and every decision the machine makes — what may start, what must wait, what to run first — must be computable from that data alone. That is the design problem this page works through, with YYLO Ledger as the worked implementation: its graph engine exists for exactly this job, as its own module preamble puts it — it "Enables dependency-aware task scheduling for parallel execution." Everything below was verified against the released CLI, its committed README, and its graph module on 2026-08-29, with the sharp edges exercised live rather than inferred.
One edge, one direction, one meaning
The whole design starts from refusing to have several kinds of ordering. There is one edge, declared on the dependent: blocked_by. It reads blocker to dependent, and it means exactly one thing — the dependent's admission waits on the blocker reaching a terminal status. Resolution is terminal-only: the graph module draws the line in one comment, "Statuses that mean a blocker is resolved (task is finished)", and the finished set is done or archive, nothing else. No percentage-complete, no "mostly landed", no soft states. A blocker is finished or it is not, and a runtime that must schedule without judgment needs exactly that bluntness.
From one edge, two shapes fall out, and both are load-bearing. Fan-out: one blocker holding several dependents — its terminal transition releases every direct dependent at once, which is what makes completing a root feel like a wave breaking. Fan-in: one dependent declaring several blockers — and here the semantics must be pinned precisely, because this is where hand-drawn designs go soft. Fan-in is an all-of join. The dependent waits until every declared blocker is terminal; the last one to land gates the release, whenever it lands. Declaring two blockers and treating one as advisory is not a lighter dependency — it is a different graph, and the runtime would be computing a different answer than the author believed they had drawn.
The command surface stays as small as the model. Declare at creation, mutate later, inspect any time:
That third command is the graph's answer to "what did I actually declare": the README documents its contract in one line — "# Returns: blockers (met/unmet), dependents, priority score". Run against a diamond we built for this page — one schema task, two implementers blocked by it, one ship task blocked by both — with the root complete and one implementer merged, it reported the ship task is_blocked: true, the merged implementer under met blockers, the open one under unmet, and an empty dependents list. The graph states its own verdict, per task, at whatever moment you ask.
Readiness is a computed join, not an inference
The query that turns this graph into a dispatch decision is ready, and its semantics deserve to be read as a specification: a task is ready when it holds an actionable status and every declared blocker exists and each carries a terminal status. Three consequences fall out, each verified live. Resolution is monotone — the moment a blocker's completion lands, the dependent appears in the answer; nothing else has to happen. Actionable spans backlog, todo, and in_progress, so a bare query hands back claimed work too — and note that the filtering form in the block above narrows by status group, it does not exclude claims; a dispatcher that must not re-admit claimed work passes an explicit --status list omitting in_progress, and the batch-admission pattern built on that filter belongs to the autonomous queue guide. And a blocker missing from the board does not quietly pass: the module is explicit that "Missing forward references remain unresolved dependencies." — declare an edge to a task this board does not hold and the dependent simply waits, the reference held open until a task carrying that exact ID lands (a sibling worktree's board merging in, or a validated import), never guessed at. That is what makes pre-declaring a wave's edges safe: the edge is satisfied by real state or it holds.
The fan-in verification is worth stating as an execution record, because the all-of rule is the one schedules actually break on. In the diamond above, with the root and the first implementer complete, ready still excluded the ship task and deps showed one met and one unmet blocker; after the second implementer completed, the same query included it. No recompute command, no cache nudge — readiness followed the state rather than any dispatcher's belief about it. Any runtime you evaluate should have to clear that same bar: admission recomputed from declared state on every query, never cached in prose, never inferred from sentence order. The failure-anatomy guide takes apart what happens to dispatchers that infer instead.
Refuse cycles at the write, not at the deadlock
A cycle in stored dependency data raises nothing at admission. Both tasks simply hold each other out of ready forever; every dispatch round skips them; nothing logs, the wave just never ends. That is why cycle enforcement belongs at the declaration, and the ledger puts it exactly there: the mutation surfaces that add an edge to an existing task — deps add and update --blocked-by — check before writing, and the check's contract is stated in its own docblock: "Return whether adding task_id -> blocker_id closes a dependency cycle." The usage help says it in one parenthesis — "Add dependency (cycle-checked)" — and the refusal names its evidence. Closing our diamond backwards — declaring the root blocked by the ship task that already waits on it — was refused with Error: Dependency cycle detected: yr91ox → 1UEqG1 → yr91ox, a nonzero exit, and no bytes moved. The same guard catches the degenerate loop: "Task cannot be blocked by itself".
One boundary of the guard is worth knowing precisely rather than discovering by surprise: the cycle check runs against the edges that exist on the board. The write path is explicit — "Cycle detection on existing IDs only, using the indexed graph." — and forward references to not-yet-created tasks are stored with a warning rather than traversed as proof of acyclicity. The design stance is honest: an edge to a task that does not exist yet is a promise about future structure, and the guard checks what is real now. Keep that in mind when you pre-declare waves whose shape arrives from outside.
Completion and retirement are guarded by the same graph
The graph does not only gate starts; it gates the terminal transitions that make its own answers true. Attempting to complete a task whose declared blocker is still open is refused outright — our first attempt to complete the diamond's first implementer while the schema root was still open ended with Error marking task: cannot complete task osk0Vk; unmet blockers: yr91ox and no write. The rule works in the direction that matters for evidence: you cannot record finished work whose prerequisite is unfinished, so the dependency relation and the completion record cannot disagree. Retirement is the other resolution: archiving a dead-end blocker releases its dependents the same instant, and the recovery patterns built on that release — requeue, retire, resume — are the queue guide's operations, not repeated here. What belongs to this page is the invariant both rest on: terminal means resolved, resolved releases, and neither can be made to lie retroactively — reopening a resolved blocker that completed dependents lean on is refused too, a refusal the failure-anatomy guide demonstrates from the other side.
Scheduling rules for parallel agents
Everything above compresses into rules a dispatcher can follow without judgment, and each rule is checkable against the queries you already have.
Admit only from readiness. The backlog is intent; admission is the computed join. Whatever batching, quotas, and isolation discipline you wrap around the answer belongs to the parallel execution playbook — the graph's contribution is that the answer itself is never a guess.
Treat fan-in as all-of when you plan concurrency. A task with two open blockers is not "nearly ready"; it is as blocked as a task with five. The scheduling consequence is concrete: when one dependent waits on two independent blockers, running those blockers concurrently is the only thing that shortens the wait — sequence them and you have built the critical path yourself. Which brings the last resource into the frame: when more tasks are ready than slots, spend the slots where downstream work concentrates. The score is defined without sentiment — "Count of tasks that transitively depend on this one." — and in our diamond it read 3 for the root, 1 for each implementer, 0 for the ship task. order --scores prints the whole ranking.
And one sharp edge, documented from a live run because it is the kind that erodes trust silently. The order command is honest about its scope — the help text reads "Show execution order (topological sort of open tasks)" — and the implementation means it: the graph for ordering is built after one explicit step, "Filter to only open tasks for ordering". The consequence: once any open task's blocker has resolved, that resolved edge no longer has its blocker node in the graph, the dependent's indegree never drains, and the sort reports the unreachable remainder as a loop. Executing order on our diamond with only the root complete failed exactly so:
No cycle existed — the named tasks were the ship task and its two open blockers, all waiting on a root that was already finished. The IDs are from the recorded run; fresh runs mint fresh IDs, and the shape is the contract — the sort names exactly the open tasks stranded behind resolved blockers. The working discipline follows the tool boundaries: use order to plan a wave at creation, when every declared blocker is still open; once the wave is in flight, dispatch from ready, whose indexed join resolves completed blockers correctly and released our dependents the moment their blockers landed. Treat the misreported "cycle" as a diagnosis rather than a verdict: on a board whose edges passed the write-time guard, the likely cause is open work behind resolved blockers, while a genuine loop carried in by an import reads the same — and the named IDs are exactly the list to check with deps.
Where graph design hands off
The rules this page owns are the static contract: one edge direction, terminal-only resolution, all-of fan-in, admission as a query, cycles refused at the write, completion guarded by the same graph. Around it, the published neighbors carry their own ground: the parallel execution playbook for quota ceilings, worktree isolation, and run artifacts once the wave widens; the autonomous queue guide for batch admission, stale claims, and stop conditions; the failure-anatomy guide for why the prose checklist this design replaces loses work; the storage-format guide for the on-disk contract underneath; the task-truth guide for what such state buys as agent memory; and the Ledger documentation for the complete command surface. Selecting dependency-ready work for parallel dispatch has its own guide in the dependency-ready selection walkthrough, and the reusable library of dependency-graph examples and diagrams has now shipped as the dependency-pattern library. Install YYLO Ledger from PyPI, initialize it where your agents already work, declare one wave as a graph rather than a checklist, and let the first ready answer teach the rest.