DAG Execution

DAG Execution

Establish efficient parallel execution of tasks using Directed Acyclic Graph (DAG) structures to maximize throughput while respecting dependencies.

What is DAG Execution?

A DAG (Directed Acyclic Graph) represents tasks as nodes and dependencies as directed edges. This structure enables:

• Parallel Execution: Independent tasks run simultaneously
• Dependency Respect: Tasks wait for prerequisites
• Optimal Ordering: Topological sort ensures valid execution
• Clear Visualization: Easy to understand task flow

DAG Structure

Node Definition

interface TaskNode {
  id: string;              // Unique task identifier
  name: string;            // Human-readable name
  agent: string;           // Assigned agent type
  dependencies: string[];  // IDs of prerequisite tasks
  level: number;           // Execution level (computed)
  status: 'pending' | 'running' | 'completed' | 'failed';
  priority: number;        // Higher = more important
  outputs?: any;           // Task results
}

Edge Definition

interface DependencyEdge {
  from: string;  // Source task ID
  to: string;    // Target task ID
  type: 'hard' | 'soft';  // hard = blocking, soft = preferred
}

Level Computation

Tasks are assigned execution levels based on dependencies:

Algorithm (Topological Sort)

1. Find all nodes with no dependencies → Level 0
2. Remove Level 0 nodes from graph
3. Find nodes whose dependencies are all assigned → Level 1
4. Repeat until all nodes assigned

Example

Task A (no deps)      → Level 0
Task B (no deps)      → Level 0
Task C (depends on A) → Level 1
Task D (depends on B) → Level 1
Task E (depends on C, D) → Level 2

Visual Representation

Level 0:  [Task A] ←→ [Task B]     Execute in parallel
              ↓           ↓
Level 1:  [Task C] ←→ [Task D]     Wait for L0, then parallel
              ↓           ↓
Level 2:      [Task E]              Wait for L1

Execution Strategy

Level-Based Parallel Execution

1. Initialize: Compute levels for all tasks
2. Execute Level 0: Launch all L0 tasks in parallel
3. Wait: Block until all L0 tasks complete
4. Proceed: Move to Level 1, repeat
5. Continue: Until all levels complete

Parallel Execution Rules

Failure Handling

When a task fails:

1. Mark Failed: Update task status
2. Cascade Check: Find dependent tasks
3. Block Dependents: Mark as blocked
4. Continue Others: Execute unaffected tasks
5. Recovery Option: Retry or manual intervention

Building a DAG

From Task List

tasks:
  - id: explore-codebase
    name: "Explore existing codebase"
    agent: code-explorer
    dependencies: []

  - id: gather-requirements
    name: "Gather requirements"
    agent: requirements-analyst
    dependencies: []

  - id: design-architecture
    name: "Design solution architecture"
    agent: architect-supreme
    dependencies: [explore-codebase, gather-requirements]

  - id: implement-core
    name: "Implement core functionality"
    agent: coder
    dependencies: [design-architecture]

  - id: implement-tests
    name: "Write test suite"
    agent: unit-tester
    dependencies: [design-architecture]

  - id: run-tests
    name: "Execute test suite"
    agent: test-runner
    dependencies: [implement-core, implement-tests]

Resulting Levels

Level 0: explore-codebase, gather-requirements
Level 1: design-architecture
Level 2: implement-core, implement-tests
Level 3: run-tests

DAG Validation

Before execution, validate the DAG:

Validation Checks

Cycle Detection Algorithm

1. Perform DFS from each node
2. Track visited nodes in current path
3. If revisit node in current path → CYCLE
4. If complete without revisit → VALID

Optimization Strategies

Critical Path Analysis

Identify the longest path through the DAG:

• These tasks determine minimum completion time
• Prioritize critical path tasks
• Allocate best resources to critical path

Load Balancing

Distribute work evenly across agents:

• Track agent workload
• Assign new tasks to least-loaded agent
• Consider task complexity in assignment

Speculative Execution

For soft dependencies:

• Start task before dependency completes
• Cancel if dependency fails
• Commit if both succeed

State Management

Task State Transitions

PENDING → RUNNING → COMPLETED
                  ↘ FAILED → RETRYING → COMPLETED
                                      ↘ BLOCKED

State Persistence

Checkpoint task states for recovery:

dag_checkpoint:
  timestamp: "2025-12-13T10:00:00Z"
  tasks:
    - id: "task-1"
      status: "completed"
      outputs: {...}
    - id: "task-2"
      status: "running"
      started_at: "2025-12-13T09:55:00Z"
    - id: "task-3"
      status: "pending"

Integration with Phases

DAG execution integrates with the 6-phase protocol:

Saga Pattern for Recovery

When tasks fail, use saga pattern for compensation:

Compensation Chain

Task A completes → Task B fails
                    ↓
         Compensate A (rollback)
                    ↓
         Return to known good state

Compensation Actions

Additional Resources

Reference Files

• references/dag-algorithms.md - Detailed algorithms
• references/optimization.md - Advanced optimization techniques

Examples

• examples/sample-dag.json - Complete DAG example
• examples/execution-trace.json - Execution log example