Assistant/docs/proposals/ADR-0021-multi-agent-work-graph-v1.md

Proposal ADR-0021 — Multi-Agent Work Graph V1

Status: Proposed Task: DEV-000105

Problem and evidence

The audit found durable Work and Delegation records but no multi-agent DAG, fan-out/fan-in scheduler, budgets, leases, conflict resolution or independent verifier. Adding parallel agents without those controls would create duplicate work, unbounded cost, hidden disagreement and false completion.

Decision proposed

1. work owns the durable graph: WorkGraph, GraphRevision, WorkNode, NodeDependency, ResultCandidate, ConflictSet and synthesis/verification gating. Capability remains the source of eligible agent implementations; Artifact owns result metadata; Continuity owns human attention.
2. A graph is immutable by revision. Each revision contains typed nodes, dependency edges, requested capabilities, budgets, cancellation policy, synthesis policy and verifier requirements. Acyclicity and ownership are validated before dispatch; edits create a new revision rather than mutating a running graph.
3. Node identity and idempotency are stable within a revision. Independent nodes may fan out only after graph admission checks. A dependent node is dispatchable only when all required prerequisites have accepted results. Partial results and failed nodes remain attributable and do not erase sibling results.
4. Scheduling enforces durable per-goal, per-user, per-resource and per-graph budgets for concurrency, attempts, time, tokens and external mutation class. Backpressure and starvation detection are explicit; a role or agent cannot bypass a budget.
5. Assignment uses the Agent Execution Plane lease/fencing rules. Pause, cancel, reprioritize and resume are durable graph decisions propagated to eligible nodes. Restart/replay rebuilds from graph revision and execution events, not process-local queues.
6. Agent outputs are ResultCandidate records with author run, node, graph revision, artifact refs, evidence and claims. Conflicting candidates form a ConflictSet; dissent and unresolved conflict remain visible.
7. Synthesis is a candidate, never an authority shortcut. A verifier with a distinct run/identity from the author consumes declared evidence and emits a typed verification result. Work completion requires the graph's verifier policy and does not occur from fan-in text alone.
8. Specialized roles are capability profiles and evidence-based selection hints, not hardcoded authority classes. One agent may hold multiple roles; role selection never grants credentials or permission.

Lifecycle and failure semantics

Graph states are DRAFT, ADMITTED, RUNNING, PAUSED, CANCELLING, PARTIAL, VERIFYING, COMPLETED, FAILED, UNKNOWN and RECOVERING. Node states distinguish BLOCKED_PREREQUISITE, READY, LEASED, RUNNING, SUCCEEDED, FAILED, CANCELLED, UNKNOWN and RECOVERING. A failed node may trigger policy-defined retry or human attention; it never deletes other node evidence. Unknown external outcomes block unsafe replay until reconciled.

Alternatives and rationale

• A shared in-memory task queue was rejected because restart loses graph state and violates durable scheduling semantics.
• A flat list of independent agents was rejected because dependencies, fan-in, cycle rejection and partial completion cannot be represented safely.
• Majority vote without provenance was rejected because disagreement and source quality would be hidden.
• Agent roles as privileged classes were rejected because capability evidence, not labels, must determine eligibility and authority remains separate.

Consequences, migration and rollback

The graph enables bounded parallel work and attributable synthesis, at the cost of durable event ordering, budget accounting and verifier capacity. No runtime, schema or scheduler is included in this proposal. Implementation must begin with a deterministic fake graph harness, cycle/budget/conflict tests and opt-in dispatch. Rollback disables new graph admission and drains or recovers active leases without deleting graph history or artifacts.

Revisit if a graph node needs authority outside its capability, if cross-owner joins become necessary, if synthesis cannot preserve dissent, or if the verifier cannot be made independent of the author run.