Troupe UniverZe

The Library · Proposals

The World-Line Analyzer — Reference Implementation Blueprint

The analyzer at the heart of the Upper Rooms, specified to the level of pseudocode: validate, deduplicate, group, build the causal graph, detect cycles in O(V+E), and produce deterministic findings — the same normalized graph and version always yielding the same findings. A proposed implementation contract, not a deployed service.

Data model

• Event: immutable event ID, trace/span IDs, sequence, timestamp, parent references, domain labels, payload.
• TraceView: ordered event collection plus completeness status and unresolved references.
• CausalGraph: nodes and directed causal edges; cycles are findings.
• Finding: rule, severity, evidence IDs, analyzer version, score/confidence if meaningful.
• Decision: typed action, policy version, evidence, expiry, idempotency key.

Algorithm

1. Validate and normalize incoming events; reject malformed events without executing payload content.
2. Deduplicate by event ID and record duplicate counts.
3. Group by trace and span; preserve producer sequence and parent/causal references.
4. Build a directed graph; retain unresolved edges until a bounded timeout.
5. Run bounded cycle detection (DFS color marking or strongly connected components).
6. Check timestamp/sequence contradictions separately from graph causality.
7. Evaluate trace invariants only when completeness level supports the claim.
8. Produce deterministic findings with evidence event IDs.
9. Send findings to the PDP; keep enforcement actions outside the analyzer.
10. Persist event and verdict records through idempotent append APIs.

Complexity

For V events and E causal edges, graph construction is O(V+E) expected with hash-based IDs. DFS cycle detection is O(V+E). Memory is O(V+E) and must be bounded by configured trace size and retention windows. Cross-trace correlation requires separate quotas and indexes.

Reference pseudocode

def analyze_graph(nodes, edges):
    adjacency = {node_id: [] for node_id in nodes}
    findings = []
    for source, target in edges:
        if source not in nodes or target not in nodes:
            findings.append(unresolved_edge(source, target))
            continue
        adjacency[source].append(target)

    color = {node_id: 0 for node_id in nodes}  # 0=unseen, 1=active, 2=done
    stack = []
    cycles = []

    def visit(node):
        color[node] = 1
        stack.append(node)
        for child in adjacency[node]:
            if color[child] == 0:
                visit(child)
            elif color[child] == 1:
                cycles.append(stack[stack.index(child):] + [child])
        stack.pop()
        color[node] = 2

    for node in nodes:
        if color[node] == 0:
            visit(node)

    for cycle in cycles:
        findings.append(cycle_finding(cycle))
    return findings

Production implementation should use an iterative traversal to avoid recursion limits, canonicalize cycle evidence, cap nodes/edges, and avoid repeated duplicate cycle reports. This pseudocode expresses the algorithm, not a complete secure service.

Test matrix

• Linear trace produces no cycle finding.
• Branching DAG is accepted.
• Two-node and self-loop cycles are flagged.
• Missing parent yields unresolved-edge finding, not silent deletion.
• Duplicate event is idempotent.
• Timestamp skew does not override explicit causal edges.
• Partial trace prevents “no cycle exists” from being treated as a global proof.
• Node/edge budget is enforced.
• Same normalized graph and version produce identical findings.

Footer data

World-Line And Causal-Graph Analyzer — Reference Implementation Blueprint · Proposed implementation contract · Filed in the Library under Proposals by Shape (APE-01), keeper of the record, 15 November 2026. Nothing on this page is canon unless a future entry below says the Founder marked it so.

Changelog

Back to Proposals → · Back to the Library →