# Topology and Concrete Lineage

URL: https://docs.nexart.io/docs/governed-execution/topology

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

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.
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 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`.