A merged dependency is a cut, not a status

If you orchestrate AI agents over a backlog of GitHub issues, you have probably built some version of this: read the tickets, find the ones with no blockers, fan out N agents, run them in parallel.

That works — until it does not. Issue #3 cannot merge because its base includes an unmerged sibling. #5 is blocked on #4, which is blocked on #2, which finished yesterday. Your wave diagram says “Wave 2,” so you wait for the whole wave even though #3 was independently ready an hour ago.

The mistake is subtle and it compounds. Parallelism should be determined by dependencies, not by ticket count — and the dependency graph, not a global phase barrier, decides what is ready. I have been building a planner that enforces this, and the most counterintuitive idea in it is this:

A merged dependency is a cut, not a status.

When work is merged, you stop traversing through it. Downstream work does not inherit the cycles or unresolved blockers that lived upstream of that merge. The merge is the wall; what reached the default branch is what matters, not the messy history behind it.

Why “complete” is tempting to treat as just another status

The natural design is to give every node a status enum — eligible, blocked, complete, unresolved — and propagate facts through the graph uniformly. Completed nodes satisfy their dependents and you move on.

That is almost right, and it is wrong in a way that silently corrupts plans. Consider this graph, where arrows mean blocks:

graph LR
    I1["#1 unresolved"] --> I2["#2 complete"]
    I2 --> I3["#3 selected"]
    style I2 fill:#4caf50,color:#fff

#1 was never resolved. #2 once depended on #1 — but #2 got merged anyway (maybe #1 was abandoned, superseded, or worked around). Now you are planning #3.

If you propagate uniformly, #3 inherits #1’s unresolved state and comes out blocked_external. But that is absurd: #2 already shipped. Whatever #1’s status is, it is irrelevant to new work that depends only on #2’s integrated result. The merge of #2 cut the graph.

Here is the model, run against the real implementation:

const plan = buildDependencyWaveGraph({
  schemaVersion: 1,
  maxConcurrency: 2,
  selectedIds: ["i3"],
  nodes: [
    { id: "i1", issueNumber: 1, status: "unresolved" },
    { id: "i2", issueNumber: 2, status: "complete" }, // merged
    { id: "i3", issueNumber: 3, status: "eligible" },
  ],
  edges: [
    { blockerId: "i1", blockedId: "i2" },
    { blockerId: "i2", blockedId: "i3" },
  ],
});

plan.graph.selected[0].disposition; // → "ready"
plan.graph.runnable; // → true

#3 is ready. It did not catch #1’s disease. The planner excluded the completed node — and its incident edges — from the active graph used for traversal, while keeping every input edge in the output so the explanation of why #3 is ready is never lost.

Three facts a merge cuts

A completed node is not a polite neighbor that quietly satisfies its dependents. It is a wall that stops three things from crossing:

Crossed upstream of a merge	Effect on downstream selected work
An unresolved boundary blocker	Not inherited — work can be ready
A dependency cycle	Not detected — irrelevant cycle is ignored
An invalid selected sibling	Not propagated — work is not poisoned

The third row is the one that surprised me most. Suppose #9 (invalid) → #10 (complete) → #11 (selected). Should #11 be blocked_invalid_selected because #9 was invalid? No. #10 merged, and #9’s invalidity died with the pre-merge history. New work trusts the integrated tip, not the ghosts behind it.

This is the difference between satisfying a dependency and cutting the graph. Satisfying answers “is this blocker done?” Cutting answers “does anything upstream of this done blocker still matter?” Only the second question keeps plans from rotting.

The other half: levels are for display, not for runtime

Once you accept that release is per-dependency, a second correction follows. Topological levels — the “Wave 1 / Wave 2 / Wave 3” grouping — are a way to explain a plan to a human, not a synchronization barrier at runtime.

graph LR
    I1["#1 contract"] --> I3["#3 backend"]
    I2["#2 UI design"] --> I4["#4 frontend"]
    I3 --> I5["#5 integration"]
    I4 --> I5

A display plan shows #1, #2 at level 1, #3, #4 at level 2, #5 at level 3. But at runtime, #3 is released the instant #1 merges — it does not wait for #2, nor for “level 2” to begin. A slow #4 never blocks unrelated work. Only #5, which depends on both of its own blockers, waits for convergence.

If you build your scheduler around level barriers, you will serialize work that could have run concurrently, and you will blame the graph for latencies your barrier introduced.

What I got wrong first

The first version of my planner treated complete exactly like the other statuses — a fact that propagated forward like any other. The plans were technically reachable but semantically wrong: a single abandoned ticket upstream of a long-since-merged branch would mark a dozen perfectly ready issues as blocked. The planner was not lying; it was being loyal to a model that did not match how merges actually work.

The fix was not more propagation. It was less traversal — explicitly removing completed nodes from the active subgraph before running cycle detection and blocker propagation. The output still carries every input edge for explanation; the computation just refuses to walk through a merge.

There is a hidden coupling I am not proud of: my strongly-connected-components routine flags a component as cyclic only when it has more than one node (cyclic: nodeIds.length > 1). That is correct only because the validator rejects self-loops before SCC ever runs. If a self-loop slipped through, a single-node SCC with an edge would be a cycle that goes undetected. It works, but the precondition lives in a different file than the assumption. I will add a guard before this code sees a contributor.

When this matters

This model is not specific to AI agents. Any system that schedules work over a dependency graph — build pipelines, migration runners, feature-flag rollout sequences — has the same trap: treating done as a fact to propagate instead of a cut to respect.

The cost of getting it wrong is invisible at small scale and brutal at scale: ready work sits idle behind phantom blockers, cycles that a merge already resolved keep poisoning new plans, and your “smart” parallelism converges to the speed of your slowest, stalest assumption.

Treat the merge as a wall. Compute readiness on the active graph. Let levels explain, not gate.

---

The planner described here is part of pi-github-waves — a dependency-driven orchestrator for GitHub Issues. The graph core is implemented and tested; the GitHub adapters and worker dispatch are on the roadmap. The code output above was captured from the actual buildDependencyWaveGraph run, not invented.