Convergence Rollup, BFS Tree Traversal & Reference Cycle Detection Subsystem Operational Architecture Guide

1. Executive Architectural Summary

The Convergence Rollup, BFS Tree Traversal & Reference Cycle Detection Subsystem (pkg/convergerollup) provides deterministic hierarchical graph traversal, reference cycle detection, multi-tier status rollup aggregation, and overseer child arbitration for convergence sessions in the ZQK Knowledge Kernel.

In the ZQK orchestration model, autonomous execution unfolds across multi-level convergence sessions and relational planning graphs:

  • Parent/Coordinator Convergence Sessions (convergence_session) anchor high-level strategic hypotheses, orchestrate subagents, and supervise nested child work streams.
  • Child Convergence Sessions encapsulate delegated, bounded, and token-budgeted problem-solving tasks spawned beneath coordinator sessions.
  • Relational Work Containers (Epics, Milestones, Priority Plans, Backlog Items) structure chronological and functional execution units.

To prevent infinite loops, split-brain completions, or premature session termination while child workers remain active, pkg/convergerollup establishes three invariant pillars:

  1. Depth-Bounded BFS Tree Traversal (CollectCVSTreeBFS): Traverses nested session hierarchies with strict depth ceilings (DefaultOverseerCVSTreeMaxDepth = 3), diamond deduplication, and non-CVS reference filtering.
  2. Cycle-Safe DFS Reference Gate (DetectCVSRefCycle): Validates parent-child relationships upfront before link mutation via depth-limited depth-first cycle path detection (MaxRelatedCVSHopDepth = 8).
  3. Multi-Surface Rollup Status Aggregation & Overseer Arbitration (ComputeRollupStatus, BuildArbitratedParentMessage): Synthesizes test bundle health, static gate exit codes, vetting matrix progress, and active child session states into a deterministic four-tier status (satisfied, ready_for_review, partial, blocked), computing normative primary measurement outcomes and actionable next steps.

2. Component Topology & Subsystem Architecture

The subsystem is organized into modular, orthogonal components designed for deterministic execution and high concurrency:

flowchart TD
    subgraph ClientLayer["CLI & Scheduler Callers"]
        SchedulerMeasure["zqk scheduler convergence measure"]
        AgentOrchestrate["zqk agent orchestrate / overseer"]
        NestCommands["zqk convergence nest / spawn"]
    end

    subgraph ConvergeRollupSubsystem["pkg/convergerollup Subsystem"]
        TreeBFS["BFS Tree Collector\n(CollectCVSTreeBFS)"]
        CycleDetector["Cycle Detector\n(DetectCVSRefCycle)"]
        NestValidator["Nest Link Validator\n(ValidateNestLink)"]
        RollupCompute["Rollup Status Computer\n(ComputeRollupStatus)"]
        OutcomeTaxonomy["Measurement Outcome Engine\n(ComputePrimaryMeasurementOutcome)"]
        NextActionBuilder["Recommended Next Action\n(BuildRecommendedNextAction)"]
        OverseerArbitrator["Overseer Arbitrator\n(BuildArbitratedParentMessage)"]
    end

    subgraph KernelStorage["Knowledge Kernel Storage"]
        CVSLoader["CVS Node Loader\n(related_object_refs, status, phase)"]
        TestBundles["Test Bundle Surfaces\n(.zqk/logs/scheduler/cvs/test-bundles)"]
        GatesSurface["Static AST & Env Literal Gates"]
    end

    ClientLayer -->|Inspect Hierarchy| TreeBFS
    ClientLayer -->|Validate Child Nesting| NestValidator
    ClientLayer -->|Evaluate Convergence| RollupCompute
    NestValidator -->|Depth Traversal| TreeBFS
    NestValidator -->|Cycle Guard| CycleDetector
    TreeBFS -->|Fetch Session Nodes| CVSLoader
    CycleDetector -->|Walk References| CVSLoader
    RollupCompute -->|Incorporate Bundles| TestBundles
    RollupCompute -->|Incorporate Gates| GatesSurface
    RollupCompute -->|Derive Next Step| NextActionBuilder
    RollupCompute -->|Determine Outcome| OutcomeTaxonomy
    OverseerArbitrator -->|Filter Active Children| TreeBFS
    OverseerArbitrator -->|Merge Directives| RollupCompute

Component Roster

  • cvs_tree_bfs.go: Implements breadth-first search tree collection across nested convergence_session objects via related_object_refs. Strictly enforces maxDepth ceilings and filters non-CVS- reference identifiers.
  • ref_cycle.go: Implements depth-first cycle path discovery. Detects circular dependencies within session linkages up to MaxRelatedCVSHopDepth (8 hops) and returns the full cycle path.
  • nest.go: Coordinates spawn requests, status queries, and pre-link verification via ValidateNestLink. Enforces coordinator tree membership, maximum nesting depth, and circular reference avoidance prior to storage writes.
  • rollup_status.go: Evaluates composite convergence across test bundles, static code gates (field_key_literals_gate, zqk_env_literals_gate), verification matrix rows, and child session states. Classifies status into satisfied, ready_for_review, partial, or blocked.
  • primary_measurement_outcome.go: Normalizes measured states into four primary outcome taxonomies: measurement_yields_convergence, measurement_yields_divergence, measurement_yields_halt_or_error, and measurement_yields_ambiguous_outcome.
  • recommended_next.go: Transforms blocker codes and rollup conditions into human-legible, deterministic command directives for agent prompts and human operators.
  • overseer.go: Evaluates coordinator descendant trees to gate parent session exits while active child sessions remain incomplete, formatting consolidated overseer directives.

3. BFS Tree Traversal & Hierarchy Topology

3.1 Depth-Bounded BFS Algorithm

The CollectCVSTreeBFS function traverses child references in strict FIFO breadth-first order:

func CollectCVSTreeBFS(
    rootID string,
    maxDepth int,
    nodeFor func(id string) (refs []string, status string, phase string, err error),
) ([]CVSTreeNode, error)
  1. Validation: Rejects empty root IDs, nil node loaders, or negative depth limits fail-closed.
  2. FIFO Queue Initialization: Enqueues {id: rootID, depth: 0} and allocates an identity set seen := make(map[string]bool).
  3. Visiting Nodes: Pops each entry. If already present in seen, it is skipped (diamond pattern deduplication).
  4. Depth Floor Evaluation: If cur.depth >= maxDepth, the node is appended to the results, but its children are omitted from queue expansion.
  5. Child Filtering: Only identifiers prefixed with CVS- are considered. Blank strings, non-CVS kinds (e.g. requirements, test cases, plans), and previously seen IDs are ignored.
flowchart TD
    Root["Coordinator CVS (Depth 0)"]
    ChildA["Child CVS-A (Depth 1)"]
    ChildB["Child CVS-B (Depth 1)"]
    NonCVS["Ignored Non-CVS Ref (e.g. Plan / Task)"]
    GrandchildA1["Child CVS-A1 (Depth 2)"]
    GrandchildA2["Child CVS-A2 (Depth 2)"]
    DeepChild["Depth 3 Ceiling (Not Expanded)"]

    Root --> ChildA
    Root --> ChildB
    Root -.->|Filtered| NonCVS
    ChildA --> GrandchildA1
    ChildA --> GrandchildA2
    GrandchildA1 --> DeepChild

3.2 Diamond Deduplication Guarantee

When multiple parent nodes reference a shared child session (e.g. a shared verification or testing session), the BFS traversal visits the shared node exactly once at its minimum discovery depth. This prevents duplicate accounting in overseer blockers and tree metrics.


4. Reference Cycle Detection & Nesting Invariant Gates

4.1 DFS Cycle Path Detection

Circular references in convergence session graphs cause infinite traversal loops, deadlocks in scheduler rollups, and invalid status cascades.

DetectCVSRefCycle walks the graph via depth-limited depth-first search (DFS):

  • Maintains the current branch traversal path: path []string.
  • If an edge targets any identifier already present in path, a cycle is detected and the complete path ending with the closing node is returned: [root, child1, child2, child1].
  • Traversal depth is capped at maxDepth (default: MaxRelatedCVSHopDepth = 8).
  • Non-CVS references and lookup errors do not halt traversal, ensuring robust handling of mixed graph references.

Before an agent or operator links a child session to a parent (ValidateNestLink), the link is vetted against four mandatory invariant gates:

sequenceDiagram
    autonumber
    participant Caller as Nesting Client
    participant Validator as ValidateNestLink
    participant BFS as CollectCVSTreeBFS
    participant Cycle as DetectCVSRefCycle

    Caller->>Validator: ValidateNestLink(coordinatorID, parentID, childID, maxDepth, nodeFor)
    Validator->>Validator: Verify IDs have CVS-* prefix & parentID != childID
    Validator->>BFS: CollectCVSTreeBFS(coordinatorID, maxDepth, nodeFor)
    alt Parent not in coordinator tree
        Validator-->>Caller: Error: parent not found under coordinator
    else Parent depth + 1 > maxDepth
        Validator-->>Caller: Error: nesting would exceed max depth
    end
    Validator->>BFS: CollectCVSTreeBFS(childID, maxDepth, nodeFor)
    alt Child tree contains parentID or coordinatorID
        Validator-->>Caller: Error: linking would create a cycle
    end
    Validator-->>Caller: Success (Link Authorized)
  1. Self-Nesting Gate: Rejects parentID == childID.
  2. Coordinator Ancestry Gate: Verifies parentID exists within the coordinator's BFS tree.
  3. Maximum Depth Ceiling: Ensures parentDepth + 1 <= maxDepth (default: 3).
  4. Subtree Inversion / Cycle Gate: Inspects the child's descendant tree; if parentID or coordinatorID is reachable from childID, linking is blocked.

5. Status Rollup & Primary Measurement Outcomes

5.1 Rollup Status Classification Model

ComputeRollupStatus evaluates four distinct surface inputs:

  1. Test Bundles (TestBundleInput): ReadyForSessionCompletion, FailingFingerprintsNow, and DeltaAssessment (trending_away vs trending_toward).
  2. Literal Code Quality Gates: Exit status of AST field key literal gate and environment variable literal gate.
  3. Verification Matrix: Pending human-scope .go matrix rows or unreadable matrix files.
  4. Child Sessions (ChildSessionInput): Active, completed, or errored child convergence sessions.
flowchart TD
    Start["Surface Evaluation"] --> HardCheck{"Any Hard Blocker?\n- Failing Fingerprints\n- Trending Away\n- Gate Exit != 0\n- Matrix Unreadable\n- Child Session Error"}

    HardCheck -- Yes --> StatusBlocked["RollupStatus = blocked\n(ready_for_parent_completion = false)"]
    HardCheck -- No --> ReadyCheck{"Test Bundles Ready?\n(ReadyForSessionCompletion == true)"}

    ReadyCheck -- No --> StatusPartial["RollupStatus = partial\n(bundle_gate_not_ready blocker)"]
    ReadyCheck -- Yes --> BlockerCheck{"Any Remaining Blockers?\n(Pending Matrix Rows or Child Sessions)"}

    BlockerCheck -- "Soft Blockers Only" --> StatusReview["RollupStatus = ready_for_review"]
    BlockerCheck -- "None" --> StatusSatisfied["RollupStatus = satisfied\n(ready_for_parent_completion = true)"]

5.2 Primary Measurement Outcome Taxonomy

The computed RollupStatus and blockers are mapped into the normative four-fold measurement outcome taxonomy:

Primary Outcome Operational Condition Actionable Guidance
measurement_yields_convergence RollupStatus == RollupStatusSatisfied with zero blockers. All surfaces green. Advance session phase or complete session.
measurement_yields_divergence Blocked with failing test bundles, trending_away delta, active child sessions, or pending matrix rows. Stabilize failing tests, resolve pending rows, or complete child sessions.
measurement_yields_halt_or_error Static literal gate failure (exit != 0) or unreadable vetting matrix. Halt autonomous loop; resolve AST/literal violations or matrix configuration.
measurement_yields_ambiguous_outcome Test bundle window incomplete (bundle_gate_not_ready) or gates skipped. Await test runner execution completion and re-measure.

6. Sequence Diagrams of Status Rollup Propagation

6.1 Multi-Tier Planning Container & Convergence Hierarchy

The Knowledge Kernel orchestrates autonomous delivery by cascading status updates up the planning DAG and convergence session tree:

sequenceDiagram
    autonumber
    participant Subagent as Subagent / Worker
    participant BLI as Backlog Item / Task
    participant Plan as Priority Plan
    participant ChildCVS as Child Convergence Session
    participant CoordCVS as Coordinator Session
    participant Rollup as convergerollup Subsystem

    Subagent->>BLI: Complete implementation and verification
    BLI->>Plan: Trigger milestone/plan progress recalculation
    Subagent->>ChildCVS: Mark child session phase complete
    ChildCVS->>ChildCVS: Set status = 'completed'

    Note over CoordCVS,Rollup: Coordinator periodic measurement pass
    CoordCVS->>Rollup: CollectCVSTreeBFS(coordinatorID, maxDepth)
    Rollup-->>CoordCVS: Descendant tree nodes
    CoordCVS->>Rollup: ActiveChildIDsUnderCoordinator(tree)
    Note over CoordCVS: Active children count == 0
    CoordCVS->>Rollup: ComputeRollupStatus(tb, gates, matrix, children)
    Rollup-->>CoordCVS: status: satisfied, ready_for_parent_completion: true
    CoordCVS->>CoordCVS: Parent session transitions to completed

7. Production Configurations, Memoization & Operational Recipes

7.1 Configuration Parameters

The subsystem exposes key constants aligned with kernel architecture policies:

Parameter Location Default Value Operational Purpose
DefaultOverseerCVSTreeMaxDepth pkg/convergerollup/cvs_tree_bfs.go 3 Maximum nesting depth for overseer BFS tree expansion from coordinator.
MaxRelatedCVSHopDepth pkg/convergerollup/ref_cycle.go 8 Maximum hop distance evaluated during reference cycle DFS traversal.
ObjectStatusActive pkg/objects "active" Status marker identifying in-flight child convergence sessions.
ObjectStatusError pkg/objects "error" Status marker identifying errored sessions triggering hard rollup blocks.

7.2 In-Memory Memoization & Performance Hygiene

  1. Visited Set Memoization: Both BFS and DFS traversals track visited node IDs in in-memory sets (seen := make(map[string]bool)), bounding time complexity to \(O(V + E)\) where \(V\) is session count and \(E\) is reference edges.
  2. Zero Hot-Path Allocations: Slice builders pre-allocate capacity based on discovered candidate lengths where known, minimizing garbage collection pressure during continuous scheduler passes.
  3. Pure Function Invariants: Calculation methods (ComputeRollupStatus, BuildArbitratedParentMessage, ComputePrimaryMeasurementOutcome) do not mutate input data structures, ensuring thread safety without locking overhead.

7.3 Operational CLI Recipes

Inspecting Descendant Session Trees

# Measure convergence status and view descendant session tree
zqk scheduler convergence measure --session-id CVS-20261030-001 --format json
// Validate link before adding child CVS ID to parent's related_object_refs
err := convergerollup.ValidateNestLink(
    coordinatorID,
    parentID,
    childID,
    convergerollup.DefaultOverseerCVSTreeMaxDepth,
    nodeLoader,
)
if err != nil {
    return fmt.Errorf("nest link rejected: %w", err)
}

Arbitrating Coordinator Status in Agent Overseer

// Generate arbitrated parent message for agent prompt
msg := convergerollup.BuildArbitratedParentMessage(rollupMap, treeNodes, coordinatorID)
// Injects warning if active children exist: "N active child session(s) in tree..."

8. Troubleshooting Matrix & Diagnostic Runbook

Symptom / Error Root Cause Remediation Protocol
nesting under CVS-xxx would exceed max depth 3 Attempted to spawn a child session under a parent that is already at maximum permitted depth. Flatten session hierarchy. Link new task to coordinator directly or complete existing intermediate sessions.
linking CVS-xxx under CVS-yyy would create a cycle The proposed child session references an ancestor session, creating a circular graph. Inspect related_object_refs on child session. Remove upstream references before linking.
parent CVS-xxx not found under coordinator CVS-yyy The targeted parent session does not belong to the coordinator's descendant tree. Verify session ancestry or use the correct coordinator ID as root.
Rollup status is blocked with test_bundles_failing One or more test bundle fingerprints have failed in recent scheduler runs. Run zqk test run on failing test cases; inspect .zqk/logs/scheduler/cvs/test-bundles/.
Rollup status is blocked with field_key_literals_gate Go source code contains hardcoded object field key strings instead of pkg/objects constants. Replace raw string literals with canonical constants from pkg/objects.
Rollup status is ready_for_review but parent does not complete Child sessions remain in active state, or verification matrix has pending rows. Verify child session outputs, transition completed children to completed or archived, then re-measure.
Rollup status is partial with bundle_gate_not_ready Test bundle execution has not completed or test evidence window is stale. Trigger test run via zqk test run and allow scheduler background worker to update bundle state.

9. Concurrency & Concurrency Safety Invariants

The pkg/convergerollup subsystem is verified against data races under continuous parallel execution:

  • Thread-Safe Read Access: Functions operate on immutable point-in-time snapshots and caller-provided node loader functions.
  • Race Condition Invariant: All package tests pass under go test -race ./pkg/convergerollup/... with zero data races.
  • Safe Multi-Agent Access: Multiple worker agents can concurrently evaluate convergence status, traverse BFS trees, and inspect parent messages without shared state contention.

10. Verification & Test Coverage Invariant

In accordance with platform quality standards:

  • Target Coverage: Statement test coverage \(\ge 85.0\%\) across all package functions (target 100.0%).
  • Achieved Coverage: 98.8% statement test coverage across pkg/convergerollup.
  • Per-Function Breakdown:
  • CollectCVSTreeBFS: 100.0%
  • ValidateNestLink: 100.0%
  • AppendRelatedObjectRef: 100.0%
  • RelatedObjectRefsFromMap: 100.0%
  • NestStatus: 100.0%
  • ChildSessionFields: 100.0%
  • ActiveChildIDsUnderCoordinator: 100.0%
  • BuildArbitratedParentMessage: 100.0%
  • ComputePrimaryMeasurementOutcome: 100.0%
  • blockerCodes: 100.0%
  • hasCode: 100.0%
  • ambiguousPartialBlockers: 100.0%
  • BuildRecommendedNextAction: 100.0%
  • actionLineForBlocker: 100.0%
  • DetectCVSRefCycle: 100.0%
  • ComputeRollupStatus: 94.0%
  • Payload Integrity: Free of literal nanosecond kernel IDs and studio lineage markers, verified with scripts/open-core/check-public-release-payload.sh.