Topology and Concrete Lineage

Static workflow topology describes what could execute; concrete lineage records what did. How parentEdges and parentStepIds relate in multi-agent execution evidence.

Concept	Meaning
Static topology	Possible workflow relationships
Concrete execution graph	Relationships that actually occurred
`parentEdges`	Legal possible parent relationships (per node name)
`parentStepIds`	Actual selected parent step IDs for one execution

Normative semantics

Source: @nexart/governed-execution@0.4.2 README, CHANGELOG and docs/cage-governance-v1.md.

Static topology

MAY contain cycles and self-edges. Example: evaluator: [execution_analyst] and execution_analyst: [evaluator].

Concrete lineage

MUST be acyclic. Example: step 4 cannot be a parent of step 2.
MUST NOT list a step as its own parent.
MUST only reference earlier steps. A parent ID that is missing or later in steps is invalid.
MAY repeat a nodeName when each stepId is unique. Example: two evaluator steps below.
MAY join several parents in one step.

Selected parents versus topology

MUST pick each parent from the legal direct or contracted candidates. Otherwise: ILLEGAL_EXECUTED_EDGE.
MAY pick a subset. Example: the HITL case below records one of two possible parents.
A verifier MUST NOT require every possible parent to appear in parentStepIds.
Contraction MUST be branch-local; an unresolvable cycle fails with UNRESOLVABLE_CONTRACTION_CYCLE.

Terminal path

terminalPath MUST be checked with the precedence ladder (happy_path, then cbf_block, loop_breaker, nemo_block, unknown), not by comparing the last node with terminalNode.

Bounded refinement loop

execution_analyst  <==>  evaluator  --->  finalizer

parentEdges:
  execution_analyst: [evaluator]
  evaluator:         [execution_analyst]
  finalizer:         [evaluator]

Diagram A: possible static topology. The cycle between execution_analyst and evaluator describes allowed transitions. It is a declaration of what may happen, not a record of what happened.

step 1  execution_analyst   parents: []
   |
step 2  evaluator           parents: [step 1]
   |
step 3  execution_analyst   parents: [step 2]
   |
step 4  evaluator           parents: [step 3]

Diagram B: one concrete execution. A finite, acyclic path through the cyclic topology. Repeated node names have distinct step IDs. A cyclic static declaration does not imply a cyclic execution.

The complete sealed CER for this execution is on the schema page.

Human-in-the-loop parent subset

Possible (topology):            Actual (this execution):

safety_check ----+              safety_check
     |           |                   |
     v           |                   v
hitl_interrupt   |              hitl_interrupt
     |           |                   |
     v           v                   v
   governed_trader              governed_trader
parentEdges.governed_trader     parentStepIds = [hitl_interrupt step]
 = [safety_check, hitl_interrupt]

Possible parents versus actual parents. Topology lists both safety_check and hitl_interrupt as possible parents of governed_trader. This execution correctly records only hitl_interrupt. A subset of legal parents is valid.

HITL evidence (verified OK with SDK 0.4.2)

{
  "bundle": {
    "bundleId": "6e7f8a9b-0c1d-4e2f-8a3b-4c5d6e7f8a9b",
    "threadId": "thread-hitl-001",
    "startedAt": "2026-10-01T10:00:00.000Z",
    "completedAt": "2026-10-01T10:00:04.000Z",
    "terminalPath": "happy_path",
    "steps": [
      {
        "stepId": "1c2d3e4f-5a6b-4c7d-8e9f-0a1b2c3d4e5f",
        "nodeName": "safety_check",
        "parentStepIds": [],
        "timestampUtc": "2026-10-01T10:00:01.000Z",
        "durationMs": 120,
        "signals": {},
        "metadata": {},
        "stateHash": "1111111111111111111111111111111111111111111111111111111111111111"
      },
      {
        "stepId": "2d3e4f5a-6b7c-4d8e-9f0a-1b2c3d4e5f6a",
        "nodeName": "hitl_interrupt",
        "parentStepIds": [
          "1c2d3e4f-5a6b-4c7d-8e9f-0a1b2c3d4e5f"
        ],
        "timestampUtc": "2026-10-01T10:00:02.000Z",
        "durationMs": 120,
        "signals": {},
        "metadata": {},
        "stateHash": "2222222222222222222222222222222222222222222222222222222222222222"
      },
      {
        "stepId": "3e4f5a6b-7c8d-4e9f-a0b1-2c3d4e5f6a7b",
        "nodeName": "governed_trader",
        "parentStepIds": [
          "2d3e4f5a-6b7c-4d8e-9f0a-1b2c3d4e5f6a"
        ],
        "timestampUtc": "2026-10-01T10:00:03.000Z",
        "durationMs": 120,
        "signals": {},
        "metadata": {},
        "stateHash": "3333333333333333333333333333333333333333333333333333333333333333"
      }
    ]
  },
  "topology": {
    "nodes": [
      "intake",
      "safety_check",
      "hitl_interrupt",
      "governed_trader"
    ],
    "parentEdges": {
      "safety_check": [
        "intake"
      ],
      "hitl_interrupt": [
        "safety_check"
      ],
      "governed_trader": [
        "safety_check",
        "hitl_interrupt"
      ]
    },
    "terminalNode": "governed_trader",
    "interruptNode": "hitl_interrupt"
  }
}

Wrong versus correct

Wrong assumption

parentStepIds must equal every possible parentEdges candidate

Correct rule

Every selected parentStepId must be legal, but the selected set may be a subset.

Contraction through omitted nodes

For each possible parent, the resolver walks through omitted and non-attestation nodes and stops at the nearest previously recorded attestation boundary, selecting that node's latest prior concrete step. Converging candidates are deduplicated. A branch-local visited set prevents infinite traversal of static cycles. A cycle consisting only of unrecorded nodes fails with UNRESOLVABLE_CONTRACTION_CYCLE. A selected parent outside the candidates, including a stale earlier instance of a repeated node, fails with ILLEGAL_EXECUTED_EDGE.