# Which invariants prevent rollback storms in speculative multi-agent execution with tool-call fencing

**Date of Record:** 2026 November 9

**Scope:** Applies to orchestration runtimes where multiple agent branches execute speculatively against shared tool surfaces, with rollback and reconciliation on branch merge. Does not apply to single-branch linear agents, or to systems where tool calls are idempotent and side-effect-free by contract.

## Core Distinction

The failure mode is not "a rollback happened." It is "a rollback happened *after* a fenced tool call had already crossed the commit boundary." Speculative execution assumes rollback is cheap and total. That assumption holds for pure computation and for reads, but breaks at the moment a tool call produces an externally observable effect (a write, a message send, a payment, a deployment). The invariant that matters is not "branches are isolated" — it is **"no branch may observe or depend on the effects of a speculative tool call that has not been fenced-committed."** A system can have perfect branch isolation at the state layer and still fail catastrophically if a speculative tool call leaks an effect that a sibling branch then reads as ground truth, because reconciliation will reconcile against a fact that the rollback is about to erase.

## What Was Observed

A three-branch speculative plan (A, B, C) shared a tool surface. Branch B speculatively called `write_config(key=X, value=1)`. The fence token was issued but not yet committed. Branch C, running concurrently, called `read_config(key=X)` and received `1`. Branch C then made a *dependent* speculative call `deploy(version=2)` predicated on `X==1`. Branch A's result contradicted B; the reconciler rolled back B, which reverted `X` to its prior value `0`. C's deployment was now predicated on a value that no longer existed, but C had already passed its own fence check because its fence was on `deploy`, not on the read. The reconciler, seeing C's fence valid, committed C. Result: a deployment of version 2 against a config the system no longer believed in. The rollback did not "storm" in the sense of infinite loops; it stormed in the sense of **propagating an invalidation through a read that crossed the fence boundary without being fenced itself.**

The non-obvious part: the read was classified as "safe" because reads are side-effect-free. But reads are not *dependency-free*. A read that observes a speculative write creates an implicit edge in the dependency graph that the fence mechanism did not track.

## Condition of Validity

The invariant "rollback is safe" is valid only when the rollback set is **downward-closed under the observed-dependency relation**: if a speculative effect E is rolled back, every speculative effect that read E must also be in the rollback set. This holds trivially when no branch reads another branch's speculative writes. It fails the moment cross-branch reads of speculative state are permitted without recording a dependency edge. The fence must therefore cover *observations*, not just *mutations*. A fence on a write that does not also fence the transitive set of reads-of-that-write is a partial fence, and a partial fence is worse than no fence because it produces a false commit signal.

## Decision Boundary

When a speculative tool call is about to be fenced, the runtime must decide: commit, abort, or **escalate to dependency-closure commit**. The boundary is whether the fence's dependency closure contains any effect whose own fence is uncommitted. If closure is clean → commit. If closure contains an aborted effect → abort and cascade. If closure contains an uncommitted-but-live effect → the runtime must not commit; it must either wait for that effect's fence resolution or promote the whole closure to a single atomic fence. The failure occurs precisely when the runtime treats "my own fence is valid" as sufficient, ignoring closure state. The correct predicate is `fence_valid(f) AND closure_committed(f)`, not `fence_valid(f)`.

## Operational Effect

Once the closure-aware fence is enforced, rollback storms disappear because rollbacks can no longer invalidate committed facts — the reconciler either commits the entire closure atomically or aborts the entire closure, never a partial slice. The cost is increased fence latency (closure computation) and reduced speculation parallelism at dependency-dense points. The benefit is that reconciliation becomes a total function over the closure rather than a best-effort repair over a partially-ordered set of effects. Systems that skip closure tracking do not fail at low concurrency; they fail exactly when speculative branches happen to read each other's writes, which is rare enough to pass tests and common enough to corrupt production.

```python
from dataclasses import dataclass, field
from typing import Dict, Set


class FenceClosureError(RuntimeError):
    """Raised when a fence is committed while its dependency closure is not fully committed."""
    pass


@dataclass
class Effect:
    id: str
    kind: str                      # "write" | "read" | "deploy" | ...
    observes: Set[str] = field(default_factory=set)   # effect ids this read depended on
    fenced: bool = False
    committed: bool = False
    aborted: bool = False


class ClosureAwareFence:
    def __init__(self) -> None:
        self.effects: Dict[str, Effect] = {}

    def register(self, e: Effect) -> None:
        self.effects[e.id] = e

    def closure(self, root_id: str) -> Set[str]:
        seen: Set[str] = set()
        stack = [root_id]
        while stack:
            cur = stack.pop()
            if cur in seen:
                continue
            seen.add(cur)
            stack.extend(self.effects[cur].observes)
        return seen

    def commit(self, root_id: str) -> None:
        root = self.effects[root_id]
        if not root.fenced:
            raise FenceClosureError(f"effect {root_id} has no fence token")

        for dep_id in self.closure(root_id):
            dep = self.effects[dep_id]
            if dep.aborted:
                raise FenceClosureError(
                    f"fence {root_id} depends on aborted effect {dep_id}; "
                    f"must cascade abort, not commit"
                )
            if not dep.committed:
                raise FenceClosureError(
                    f"fence {root_id} depends on uncommitted effect {dep_id}; "
                    f"promote closure to atomic fence or wait"
                )
        root.committed = True


def reconcile(fence: ClosureAwareFence, candidate_fence_id: str) -> None:
    # The bug this guards against: checking only fence.fenced, not closure state.
    commit = fence.effects[candidate_fence_id]
    if commit.fenced and not commit.committed:
        fence.commit(candidate_fence_id)
```