research34 min studyLesson 895 in Engineering

A task graph must encode evidence and effect dependencies as well as subgoal names

Make artifact versions, completion evidence, shared-state conflicts, and retry semantics explicit before parallelizing an agent's plan.

On this page

What you’ll understand

  • Calculate a fixed-duration dependency path with parallel read-only branches.
  • Identify read/write conflicts that invalidate an independence assumption.
  • Distinguish a planned effect, an attempted effect, and verified external completion.

Breaking a goal into a list of fluent subtasks does not establish that they can run independently or that their outputs satisfy the final objective. A useful task graph names required inputs, artifact versions, acceptance evidence, and effects. It also records when one action reads or changes state another action depends on. Parallel local analysis is different from issuing competing external writes. Durable orchestration can preserve execution state, but it cannot infer missing dependencies or make an incorrect plan logically correct.

Define what makes a node ready and complete

For each node, record preconditions, input identities, intended result, and a check that establishes completion. An analysis result can depend on a particular source revision, while a publishing action can require validation of the exact artifact to be published. A predecessor marked done without a matching version or evidence is not enough. Distinguish blocked preconditions from a failed attempt and from a completed effect. These states determine whether a node can be retried, skipped, or safely reused during replanning.

Edges express necessary ordering from data flow, validation, authorization, or shared-state effects. An ideal duration-weighted DAG gives a lower-bound schedule with sufficient resources; actual tools can queue or contend. If a tool returns before the effect completes, the node's completion boundary must include the required later confirmation. Do not start a consumer merely because a request was submitted. The graph should represent the external postcondition that matters rather than only the order of agent messages or internal plan statements.

E(v)=d(v)+max⁡u∈pred⁡(v)E(u),T=max⁡v∈sinks⁡E(v)E(v)=d(v)+\max_{u\in\operatorname{pred}(v)}E(u),\qquad T=\max_{v\in\operatorname{sinks}}E(v)
The finite acyclic graph has nonnegative node durations in a common time unit; sources use predecessor maximum zero. The ideal schedule assumes adequate independent resources and correctly modeled completion boundaries. Omitted conflict, queue, or effect-confirmation edges can make actual completion later.↔ Scroll wide equations horizontally.

Read/write conflicts can add required ordering

Two branches that only inspect immutable snapshots may be independent. If one changes a configuration, deletes an artifact, or updates a record the other reads, that assumption fails. A conservative conflict check uses their read and write sets, but those sets must include the actual external resources and versions. Commutative operations or transactions can permit more concurrency under additional semantics. A vague label such as research and edit does not describe those effects precisely enough to decide whether parallel execution preserves the intended task.

Keep speculation distinct from real-world actions. Exploring two possible plans in local state does not authorize both branches to publish or mutate shared state. A durable workflow may retry an activity after uncertain completion, so effectful operations need an idempotency or reconciliation contract. Temporal documentation distinguishes observing one completed activity from the possibility that its code executes more than once. A plan or workflow checkpoint therefore does not by itself guarantee exactly-once external effects; retain operation IDs and verify the appropriate service postcondition.

WA∩(RB∪WB)=∅,WB∩(RA∪WA)=∅W_A\cap(R_B\cup W_B)=\varnothing,\qquad W_B\cap(R_A\cup W_A)=\varnothing
These are conservative disjoint read/write-set conditions for avoiding direct state conflicts between two operations. They require complete resource sets and suitable snapshot/effect semantics. They are not sufficient to establish every form of independence, authorization, capacity, or correctness, and commutative operations may admit other valid protocols.↔ Scroll wide equations horizontally.

Validate decomposition with failures and version changes

Test a predecessor failure, a changed source after analysis, a lost effect acknowledgment, and two branches touching the same external state. Verify which descendants remain valid and which require new checks. Preserve successful immutable work where its inputs still match, but do not reuse a result only because its node has a familiar name. Measure completed-task success and duplicate or unsupported effects alongside elapsed time. A faster plan that omits a required validation or assumes an unobserved effect succeeded is a changed correctness contract rather than a clean scheduling improvement.

The queue lab models backlog, not dependency readiness. Reset, set both λ=4 and μ=2, predict backlog four initially and five after one Step, then inspect. Reset and set both λ=1 and μ=3 for backlog three after one Step and zero at two seconds. Its fluid formula is max(0,4+(λ−μ)t), with no DAG or external effects. The separate stable M/M/1 residence readout has Poisson/exponential assumptions. It illustrates service pressure only; actual node readiness and safe parallelism follow the explicit task and resource dependencies.

Independent analysis branches share a required final join

A toy task reads an immutable source in 2 seconds, then runs independent read-only analyses A and B taking 4 and 6 seconds. A1-second merge requires both results, and a 3-second verified publication requires the merged validated artifact. Assume adequate resources, no other dependencies, and the necessary authorization already holds.

  1. Both analyses begin at 2 seconds. A finishes at 6 and B at 8; the merge finishes at 9, and verified publication finishes at 12 seconds. The dependency result is 2+max(4,6)+1+3=12.

  2. Summing all durations gives 16 seconds and double counts the analysis overlap. The 12-second prediction is conditional on their read-only independence and correctly included publication completion boundary.

  3. If A instead writes the same source B reads, add a suitable ordering or snapshot/transaction rule and recompute. Retaining the 12-second prediction without resolving that new conflict would assume the very independence that changed.

The result

A task graph is useful when its edges describe evidence and effects. Fluent subgoal names and parallel launches alone do not establish a valid completed task.

Explore the model

Interactive lab

Interactive lab · queue

Service pressure cannot establish task readiness

Reset, set both λ=4 and μ=2, predict backlog 4 initially and 5 after one Step, then inspect. Reset and re-enter both λ=1 and μ=3 for backlog 3 after one Step and zero at 2 seconds. The fluid model starts from 4 and has no task nodes, dependencies, versions, effects, or retry IDs. Its separate stable M/M/1 mean is not a task-scheduler simulation.

Service pressure cannot establish task readinessFluid backlog starts at 4 and follows max(0, 4 + (λ − μ)t). The separate M/M/1 residence-time formula assumes Poisson arrivals, exponential service and λ < μ. Current readings: Fluid backlog: 4; Net rate · λ − μ: −1 /s; M/M/1 mean residence: 1 s. All parameters are adjustable with the labeled controls below.02.557.51001.534.56Elapsed time · sFluid backlogλ < μ
Fluid backlogCurrent time
Fluid backlog
4
Net rate · λ − μ
−1 /s
M/M/1 mean residence
1 s
t = 0 s

Fluid backlog starts at 4 and follows max(0, 4 + (λ − μ)t). The separate M/M/1 residence-time formula assumes Poisson arrivals, exponential service and λ < μ. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.

Look forMake preconditions and effect conflicts explicit before using parallelism to reduce elapsed time.

Check your understanding

Two planned branches have different names but one writes a resource the other reads. What is required before treating them as independent?

Try it yourself

A2-second source precedes parallel read-only tasks lasting 3 and 5 seconds, followed by a 2-second join-dependent check. Compute ideal completion. If a new required 3-second confirmation follows the check, what is the revised boundary?

Take a moment to make a prediction or work it out on paper. Open a hint when you need one.

Give me a hint

Use the longest branch, then include every required sink operation.

Compare with the solution

Initial ideal completion is 2+max(3,5)+2=9 seconds. Adding the required confirmation gives 12 seconds. Both calculations assume sufficient resources, immutable inputs, and all relevant effect or queue constraints already modeled; submission alone is not confirmation.

Take it with you

  • Nodes need versioned inputs, preconditions, and externally checkable completion.
  • Data, validation, authority, and effects can all impose dependency edges.
  • Durable execution and parallel branches do not guarantee correct plans or exactly-once external actions.

Read further

Original sources and deeper explanations to follow at your own pace.

Optional progress, saved in this browser when available. Revisit any lesson at any time.

Lesson not marked complete.