Appendix A — Agent patterns

Appendix A - 5. Merge-train MIS batching

The Structure of Merge-train MIS batching — its shape at a glance:

Build a conflict graph — worktrees are nodes, a shared file is an edge — then compute an independent set: the largest group with pairwise-disjoint footprints. That group is non-conflicting by construction and lands together; the rest defer.

flowchart LR
  WTs[/Ready worktrees/] --> Graph[Build conflict graph]
  Graph -->|shared file = edge| MIS{{Independent set}}
  MIS -->|disjoint footprints| Land([Land batch this tick])
  MIS -->|remainder| Defer([Defer to next tick])

Accessible description: ready worktrees form a conflict graph where a shared file is an edge; an independent-set routine picks the largest group with disjoint footprints, lands that group together this tick, and defers the remainder to the next.

Projected from the catalogue entry gates-and-merge-train / Merge-train MIS batching.

On this page: Intent · Motivation · Applicability · Structure · Sample Code · Consequences · Example use within DocAble · Related Patterns

Intent

Intent — A merge-train that lands the largest set of non-conflicting agent worktrees per tick by computing a Maximum Independent Set over their file footprints, so many agents' work merges in one conflict-free pass instead of thrashing sequentially.

Motivation

With 6–8 agents committing concurrently, a naïve sequential merge serializes all of them and conflicts thrash: each merge risks colliding with the last, and the throughput of the whole fleet collapses toward one-at-a-time. Hot-spot files that many agents touch (the merge tool itself, CLAUDE.md, shared config) become bottlenecks that stall everything behind them. The failure recurs every merge tick and worsens as the fleet grows: more agents, more collisions.

Applicability

Structure

The Structure diagram appears at the top of this page.

Sample Code

Model the tick as a graph problem: worktrees are nodes, a shared file makes an edge, and a greedy independent set picks a batch whose members share no file. Because no two members touch the same file, the batch cannot conflict — independence proves it, rather than hoping each merge misses the last.

def conflicts(a: set[str], b: set[str]) -> bool:
    return bool(a & b)   # two worktrees conflict iff they share a changed file

def independent_batch(footprints: dict[str, set[str]]) -> list[str]:
    """Greedy maximum independent set over the conflict graph.
    Prefer small footprints first — they exclude the fewest others."""
    batch, claimed = [], set()
    for wt in sorted(footprints, key=lambda w: len(footprints[w])):
        if not conflicts(footprints[wt], claimed):
            batch.append(wt)
            claimed |= footprints[wt]
    return batch

if __name__ == "__main__":
    ready = {"wtA": {"x.py"}, "wtB": {"x.py", "y.py"}, "wtC": {"z.py"}}
    print("land together:", independent_batch(ready))   # -> wtA (or wtC) + wtC (or wtA); wtB defers

Consequences

Example use within DocAble

Contents
⇐ Beginning of this partNext part ⇒Next chapter ›⇤ BeginningEnd ⇥Index
© James C. Davis, 2026–present