Validate Editable DAGs and Bound Runtime Repetition

A workflow platform lets users create and modify dependency graphs. It must reject cyclic DAG definitions, and it also supports dynamic conditional branches and bounded retry behavior at runtime. Design topology validation and runtime execution limits. The reported goal is sub-millisecond configuration validation, but no maximum graph size or edit size is supplied. Explain the assumptions under which that target might be achievable and why it cannot be promised for arbitrary graph submissions. ### Constraints & Assumptions - Dependency edges impose predecessor-before-successor ordering. - A run must have a well-defined graph version even when the user later edits the workflow. - Retries or dynamic transitions must not create an unbounded execution loop. - This is a platform-design question, not a request to invent a fixed numeric bound or benchmark result. ### Clarifying Questions to Ask - Are edits single-edge changes or whole-graph replacements, and how many vertices and edges can a definition contain? - Are running workflows pinned to immutable versions, or is live migration required? - Are retries represented as attempt state on one node or as new graph transitions? - What limits apply to attempts, dynamic node creation, and total run duration? ```hint Separate two notions of a loop A retry of one task can repeat work even when the static dependency graph is acyclic. Decide which validation belongs at definition time and which belongs in durable execution state. ``` ### What a Strong Answer Covers - A correct cycle check and its dependence on graph size. - Safe incremental validation with concurrency control around graph edits. - Immutable run bindings or an explicit migration protocol. - Persisted attempt, transition, expansion, and time budgets that survive scheduler restarts. ### Follow-up Questions - How can two individually valid concurrent edge additions jointly create a cycle? - Why does a local recursion counter fail to bound retries after a process restart? - How would a branch join distinguish a skipped predecessor from one that has not yet finished?