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

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.

SettingDefault
Max concurrencyCPU cores × 3
Task timeoutEnabled, 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.

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