# Execution Model: DAG, Scheduling, State

> Applies to: ChengOS v0.1.0+ ｜ Last verified: 2026-08-12 ｜ Source: `crates/cheng-engine/src/lib.rs`, `crates/cheng-engine/src/dag`, `crates/cheng-engine/src/executor/task_scheduler.rs`, `crates/cheng-core/src/types.rs`

The engine is built on one stated principle: **static on the left, dynamic on the right; state
as the safety net, scheduling in a closed loop.** Planning happens once, offline and
side-effect-free; scheduling happens at runtime; and the persisted state machine is what makes
the whole thing recoverable rather than merely fast.

## The two phases

```text
Static (offline, pure)              Dynamic (runtime)
┌──────────────────────┐            ┌──────────────────────┐
│ DAG planner          │            │ Task scheduler       │
│ ├─ layered plan      │            │ ├─ spawn tasks       │
│ ├─ topological sort  │            │ ├─ bound concurrency │
│ └─ stage selector    │            │ └─ write back results│
└──────────┬───────────┘            └──────────┬───────────┘
           ▼                                   ▼
┌──────────────────────┐  node completion ┌──────────────────────┐
│ Execution queue      │◄─────────────────│ events               │
│ (buffers ready nodes)│                  └──────────────────────┘
└──────────┬───────────┘
           ▼
┌──────────────────────┐
│ State machine        │
│ (the safety net)     │
└──────────────────────┘
```

The static half is **purely functional and stateless** — it analyses structure and produces a
plan without side effects. That is what makes graph validation cheap enough to run before every
execution and testable without a database.

## Static analysis

1. **Build the graph.** Nodes and edges become an adjacency-list DAG.
2. **Validate.** Reject cycles, dangling edges, and unreachable required inputs. A graph that
   cannot succeed is refused now rather than failing halfway through.
3. **Topologically sort.** Kahn's algorithm produces a valid order.
4. **Layer into stages.** Nodes with no dependency between them land in the same stage, which
   is what makes them eligible to run concurrently.
5. **Select ready nodes.** The stage selector identifies which nodes' dependencies are
   satisfied.

Because the plan is derived, not stored, changing a workflow can never leave a stale plan
behind.

## Runtime scheduling

The scheduler spawns each ready node as an async Tokio task, bounded by a semaphore.

| Setting | Default |
|---|---|
| Max concurrency | CPU cores × 3 |
| Task timeout | Enabled, 300 s (5 minutes) |

Concurrency is deliberately above the core count because most nodes are I/O-bound — waiting on
a model API, an HTTP call, or a database. Sizing to cores would leave the machine idle while
tasks wait on the network.

The loop is closed: a node finishing publishes a completion event, the queue re-evaluates which
nodes just became ready, and the scheduler spawns those. There is no polling and no fixed
stage-by-stage barrier — a node runs the moment its own dependencies are met, not when its
whole stage is done.

## State

Execution state is persisted, not merely held in memory, which is what "state as the safety
net" means: an execution can be inspected, resumed, or recovered after a restart.

**Execution states** — `pending`, `running`, `paused`, `waiting_for_review`, `completed`,
`failed`, `cancelled`, `timeout`. The last four are terminal.

**Node states** — `waiting`, `ready`, `running`, `completed`, `failed`, `skipped`. Nodes hold
no state of their own; status is tracked in the execution record while the run is in flight.

`waiting_for_review` deserves attention: it is entered when a tool returns
`requires_review: true`, and it suspends the execution durably until a decision arrives.
Because the approval bus is an in-memory broadcast channel, decisions are recorded on the
approval context as well — a decision published while no waiter is subscribed would otherwise be
lost forever.

## Values and streaming

Data flows as `NodeValue`, a tagged union including `file` and `stream` cases. Streams are what
let a model node emit tokens downstream as they arrive rather than buffering a whole response,
and files let large payloads move by reference.

Nodes come in three implementation shapes: `TypedNode` (synchronous, type-safe, for pure
compute), `AsyncTypedNode` (async, for I/O-bound or context-dependent work), and the lower-level
`AsyncNode` taking raw maps.

## Events

Each lifecycle transition publishes an event that reaches clients over WebSocket:
`EXECUTION_START`, `EXECUTION_PROGRESS`, `NODE_COMPLETE`, `NODE_FAILED`,
`EXECUTION_STATE_CHANGED`, and the terminal `EXECUTION_COMPLETE` / `EXECUTION_FAILED` /
`EXECUTION_CANCELLED`. Streaming nodes add `NODE_STREAM_*`; agents add iteration, tool, and turn
events. See [the WebSocket API](/docs/api-websocket).

## Containers and loops

Beyond the plain DAG, the engine supports container nodes — subflows, batch subflows, and
loops — which contain their own subgraphs. These get their own analysis pass and emit
`CONTAINER_STARTED` / `CONTAINER_COMPLETED` and `LOOP_ITERATION_*` events, so a batch of 100
items is observable per iteration instead of as one opaque node.

## Failure, retry, and cancellation

A node failure fails the execution by default. `POST /executions/:id/cancel` moves an active
run to `cancelled`; the engine also supports retrying a failed execution from its point of
failure, which produces a **new execution id** rather than mutating the old record — the failed
run stays intact as evidence.

## Next steps

- [Testing and debugging](/docs/editor-testing-debug) — observing all this in the editor.
- [WebSocket API](/docs/api-websocket) — consuming the event stream directly.
- [Execution failures](/docs/fix-execution-failures) — diagnosing a bad run.