Parallel Tool Calls: Converging Branch Results with a Causal Commit Barrier

A travel agent queries flights, visa rules, and the budget concurrently, which appears to require only Promise.all. But if the flight result returns first and triggers an immediate booking, the visa result arriving later may already have invalidated the trip. If a price query times out and is retried, two different quotes may also wake downstream processing separately. Parallelism shortens wait time; it must not change the causal condition defining which evidence jointly authorizes an action.

The Agent Runtime State Machine defines how an entire run plans, waits, and recovers; this article addresses only how multiple tool branches expanded from the same plan node converge. Multi-Agent Result Provenance and Conflict Arbitration determines how to choose among competing claims, but this protocol operates earlier: until the preregistered dependencies are satisfied, no candidate is eligible to enter arbitration or produce effects.

Freeze the Branch Set and Closure Conditions

Before execution, publish an immutable parallelToolPlan.v1 containing planId, revision, canonical state version, policy epoch, principal, every branch ID, tool descriptor, input digest, branchMode, dependency edges, deadline, and barrier policy. Branches may only be READ_ONLY, verified DRY_RUN, or EFFECT_INTENT_ONLY; the gateway blocks external writes based on the descriptor and capabilities, because a self-reported effectClass alone does not qualify a branch for admission. ALL_REQUIRED is appropriate for veto checks; QUORUM(k) is appropriate only for independent sources that the contract explicitly declares interchangeable. Lowering k at runtime after observing a slow branch turns a performance optimization into a business-rule change.

schema: parallelToolPlan.v1
plan: trip-42@7
baseStateVersion: 311
barrier: ALL_REQUIRED
branches:
  - {id: fare, tool: flight.quote@4, mode: READ_ONLY, required: true}
  - {id: visa, tool: travel.requirements@9, mode: READ_ONLY, required: true}
  - {id: budget, tool: wallet.limit@2, mode: READ_ONLY, required: true}
decisionContract: tripDecision@5

Each branch state follows PENDING -> RUNNING -> SUCCEEDED | FAILED | CANCELLED_CONFIRMED. Reaching the local deadline first enters WAIT_EXPIRED; if the remote terminal state remains unknown, it enters OUTCOME_UNKNOWN and makes the barrier ineligible to commit. Failure to receive a result cannot be disguised as confirmation that the remote operation stopped. Results are first written to isolated staging under the key (planId, revision, branchId, attemptId), preserving the request and result digests, tool version, gateway execution receipt, and completeness. Duplicate callbacks with different digests are marked RESULT_EQUIVOCATION. Only when the policy explicitly permits missing data may a confirmed failure transition to NOT_REQUIRED with a recorded reason.

W3C PROV entity, activity, and derivation relationships can express which branch results a decision used, but the provenance graph itself does not provide serialization. The aggregate plan state is restricted to OPEN -> COLLECTING -> READY_TO_DECIDE -> COMMITTING -> COMMITTED, entering ABORTED when canceled or impossible to satisfy. The aggregator recomputes the required set and resultRoot from staging; an “all complete” Boolean carried in a message is not trusted.

The Barrier Has Only One Commit Point

The sole acceptance point is the commitDecision database transaction. It locks the plan record and verifies the revision, current canonical state version, policy and cancel generations, that each required branch has exactly one terminal state, the result root, and the decision contract. It then writes an immutable decision receipt, moves the plan to COMMITTED, and inserts a downstream outbox record unique to (planId, revision). PostgreSQL transaction isolation and unique constraints can implement this atomic boundary, but the application must still include the version in its conditional update; an ordinary SELECT followed by UPDATE cannot prevent concurrent replanning.

Downstream systems consume only the decision receipt and must not subscribe to individual branch success events. Booking, sending messages, or mutating data may be initiated only by the post-barrier outbox and must carry a business idempotency key and current authorization; parallel branches may produce at most an effect intent. If a legacy tool cannot prove that it is read-only and does not support prepare/release, a stable effect ID, and result lookup, it must not enter the parallel set. MCP Timeouts, Retries, and Idempotency constrains branch calls, while Multi-Agent Task Claims blocks late attempts; neither can replace the barrier.

Replanning creates revision 8 and atomically increments the old revision’s cancel generation. Old branches may complete and remain available for audit, but their result root can never satisfy the new plan. If resources change during parallel execution, commit must compare baseStateVersion or revalidate them. For example, if the budget balance changes from 311 to 312, the plan enters STALE_BASE instead of committing three internally consistent but stale results into the new world. PostgreSQL Transaction Isolation explains database-level anomalies; this protocol additionally links versions of external evidence.

Inject Faults into Every Completion Order

Tests generate every permutation of branch completion and inject duplicate successes, one permanently hanging branch, a late remote write after the deadline, a purportedly read-only tool accessing a write endpoint, two concurrent aggregators, a lost outbox ACK, a race between replan and commit, and a canonical state change before the barrier. The expected results are zero external effects before the barrier, zero advances by an old revision, at most one decision and one outbox record for each plan revision, zero commits while any required branch is UNKNOWN, and every equivocation blocking automatic decisions.

Quantitative gates require the terminal states of 10,000 randomly scheduled and fault-injected traces to match the reference reducer 100% of the time; 100% of downstream events must be traceable to the complete required result root; duplicate effects must remain at zero; p99 latency from barrier ready to commit must stay below 500 milliseconds; and timed-out plans must enter an explicit terminal state within 60 seconds. Rollout begins by computing the barrier in shadow mode while the serial path still executes, then enables it for 5% of read-only aggregations, and finally lets it control effectful decisions. During rollback, CAS switches the executor alias back to the serial implementation and increments the plan epoch; the old implementation must read the same staging data and decision receipts, and committed plans must never rerun because of the switch.