Microsoft Agent Framework executes workflows with a superstep execution model — a loop of collect, route, execute, and synchronize that descends directly from Pregel, Google’s system for large-scale graph processing. Understanding the model is essential because the synchronization barrier between supersteps shapes latency, parallelism, and how you should structure your workflow graph.

The Idea in One Paragraph

Workflow execution is organized into discrete supersteps. Each superstep collects pending messages, routes them to target executors, runs all of them concurrently, waits for every executor to finish, and queues new messages for the next superstep. The wait between supersteps is a synchronization barrier. The model comes from Pregel, which is itself based on the Bulk Synchronous Parallel (BSP) model.

Where the Model Comes From

The Pregel paper (Malewicz et al., Google, 2010) describes a system for distributed graph processing. The computation is a directed graph of vertices, and each vertex runs the same user-defined function. Computation proceeds in supersteps separated by global synchronization points. During superstep S, a vertex:

  1. Reads messages sent to it in superstep S−1.
  2. Modifies its own state.
  3. Sends messages that other vertices receive in superstep S+1.

Two properties make the model safe:

  • No ordering within a superstep. The system exposes no way to detect it, so programs are free of deadlocks and data races.
  • All communication goes from superstep S to superstep S+1. Every superstep sees a consistent set of messages.

Termination works by voting. A vertex votes to halt when it has no more work, and a vertex that receives a message becomes active again. The algorithm ends when all vertices are inactive and no messages are in transit.

Fault tolerance comes from checkpointing at superstep boundaries. Recovery re-runs supersteps from the last checkpoint.

How Agent Framework Workflows Map to Pregel

Pregel concept Workflow equivalent
Vertex Executor (agent or function)
Edge Edge connecting executor output to executor input
Message Workflow event carried along an edge
Superstep One round of collect, route, execute, barrier

The Agent Framework calls its model a modified Pregel execution model. The difference: in Pregel every active vertex runs in every superstep, while in workflows only executors that received messages run.

The Superstep Loop

Each superstep does five things:

  1. Collect all pending messages from the previous superstep.
  2. Route messages to target executors based on edge definitions.
  3. Run all target executors concurrently.
  4. Wait for all executors to complete. This is the synchronization barrier.
  5. Queue any new messages for the next superstep.

What the Barrier Means for Latency

The barrier is the defining property. Within a superstep, triggered executors run in parallel, but the workflow does not advance until every executor in that superstep completes. The consequence: the duration of a superstep equals the slowest executor in it.

Fan-out exposes this sharply. Suppose one path is a chain A → B → C and another path is a single long-running executor D:

Superstep 1:   A ──┐
                D ──┤  (both run; barrier waits for D)
Superstep 2:      B  (cannot start until D finished)
Superstep 3:      C

A finishes quickly and queues a message for B, but B cannot run until the barrier, which waits for D. The chain stalls at every hop. The chained path cannot advance until the long-running executor completes — even though the two paths are logically independent.

Design Guidance

If you need independent parallel paths that do not block each other, consolidate sequential steps into a single executor. Instead of chaining step1 → step2 → step3, combine that logic into one executor. Both parallel paths then complete within a single superstep, and the slow path no longer serializes the fast one.

For AI workflows, LLM calls are the slow executors:

  • Overlap calls that can run concurrently in the same superstep.
  • Put dependent calls in different supersteps.

Why the Model Exists

  • Deterministic execution. Given the same input, the workflow always executes in the same order.
  • Reliable checkpointing. State can be saved at superstep boundaries for fault tolerance.
  • Simpler reasoning. No races between supersteps; each superstep sees a consistent view of messages.

Sources

  • Microsoft Learn: Agent Framework workflows, Execution Model: Supersteps — learn.microsoft.com
  • Pregel: A System for Large-Scale Graph Processing (Malewicz et al., Google) — pregel_paper.pdf