N-Agent Orchestration Patterns

active advanced

N-Agent Orchestration Patterns

Hypothesis

We hypothesize that hierarchical coordination with domain-local autonomy scales sub-linearly (O(N log N) message complexity) compared to flat peer-to-peer coordination (O(N^2) message complexity), and that the hierarchical approach can sustain coherent behavior across 400+ agents with coordination latency below 50ms at p95 and decision consistency above 98%.

Background

The Prismatic Platform operates 434 AIAD agents at runtime, making it one of the largest autonomous multi-agent systems in production. These agents span 14 domains including intelligence gathering, security operations, quality enforcement, evolution management, and infrastructure monitoring. Each agent is an independent OTP process with its own state, decision logic, and communication patterns.

As the agent population grew from the initial 50 to over 400, coordination challenges became the primary scaling bottleneck. Early designs used a centralized orchestrator that received all agent communications and dispatched responses. This approach failed spectacularly at 120 agents when the orchestrator's message queue exceeded 50,000 pending messages, causing coordination latency to spike above 5 seconds.

The platform evolved through three coordination paradigms: centralized orchestration (Gen 1-5), gossip-based peer-to-peer (Gen 6-12), and the current hierarchical domain-local model (Gen 13-18). Each paradigm solved problems while introducing new ones. This experiment systematically evaluates all three paradigms plus a novel hybrid approach at scale points of 5, 20, 100, and 434 agents.

Understanding coordination overhead is critical because the No Mercy doctrine requires that all agents reach consensus on quality decisions within strict time bounds. A quality gate that takes 5 seconds to propagate across the agent swarm effectively creates a 5-second window where non-compliant code could be committed.

Methodology

Four coordination patterns were evaluated at each scale point:

Pattern A: Centralized -- Single orchestrator process receives all inter-agent messages and routes them to destinations. Simple but O(N) bottleneck on the orchestrator.

Pattern B: Gossip -- Each agent maintains a partial view of the swarm and propagates state updates through random peer selection. Eventual consistency with O(N log N) message complexity but unbounded convergence time.

Pattern C: Hierarchical -- Agents organized into domain supervisors. Intra-domain coordination is local. Inter-domain coordination flows through domain leaders. Two-level hierarchy.

Pattern D: Hybrid Hierarchical-Gossip -- Hierarchical structure for command propagation, gossip for state synchronization. Combines the bounded latency of hierarchy with the resilience of gossip.

For each pattern at each scale, we measured:

  • Coordination latency (time for a decision to propagate to all agents)
  • Message complexity (total messages per coordination round)
  • Decision consistency (percentage of agents agreeing on the outcome)
  • Failure resilience (behavior when 10% of agents crash simultaneously)
  • Resource consumption (memory and CPU per agent attributable to coordination)

Setup

The hierarchical coordinator with domain-local autonomy:

defmodule PrismaticAgents.Coordination.HierarchicalCoordinator do
  use GenServer

  defstruct [
    :domains,
    :domain_leaders,
    :global_state,
    :pending_decisions
  ]

  def start_link(opts) do
    GenServer.start_link(__MODULE__, opts, name: __MODULE__)
  end

  @impl true
  def init(opts) do
    domains = discover_domains()
    leaders = elect_domain_leaders(domains)

    state = %__MODULE__{
      domains: domains,
      domain_leaders: leaders,
      global_state: %{},
      pending_decisions: %{}
    }

    {:ok, state}
  end

  def propagate_decision(decision) do
    GenServer.call(__MODULE__, {:propagate, decision}, 10_000)
  end

  @impl true
  def handle_call({:propagate, decision}, _from, state) do
    start_time = System.monotonic_time(:microsecond)

    # Phase 1: Send to domain leaders in parallel
    tasks =
      state.domain_leaders
      |> Enum.map(fn {domain, leader_pid} ->
        Task.async(fn ->
          GenServer.call(leader_pid, {:domain_propagate, decision}, 5_000)
        end)
      end)

    # Phase 2: Await all domain confirmations
    results = Task.await_many(tasks, 8_000)

    elapsed = System.monotonic_time(:microsecond) - start_time

    consistency =
      results
      |> Enum.count(&match?({:ok, _}, &1))
      |> Kernel./(length(results))

    :telemetry.execute(
      [:prismatic_agents, :coordination, :propagation],
      %{latency_us: elapsed, consistency: consistency},
      %{pattern: :hierarchical, agent_count: total_agents(state)}
    )

    {:reply, {:ok, %{latency_us: elapsed, consistency: consistency}}, state}
  end

  defp discover_domains do
    PrismaticSupervisor.DomainConfig.all_domains()
    |> Enum.map(fn domain ->
      agents = PrismaticAgents.Registry.agents_for_domain(domain)
      {domain, agents}
    end)
    |> Map.new()
  end
end

The domain leader manages intra-domain coordination:

defmodule PrismaticAgents.Coordination.DomainLeader do
  use GenServer

  @impl true
  def handle_call({:domain_propagate, decision}, _from, state) do
    agent_pids = state.domain_agents

    # Parallel fan-out within domain
    results =
      agent_pids
      |> Task.async_stream(
        fn pid ->
          try do
            GenServer.call(pid, {:accept_decision, decision}, 2_000)
          catch
            :exit, _ -> {:error, :agent_unavailable}
          end
        end,
        max_concurrency: 50,
        timeout: 3_000
      )
      |> Enum.to_list()

    accepted = Enum.count(results, &match?({:ok, {:ok, _}}, &1))
    total = length(agent_pids)

    {:reply, {:ok, %{accepted: accepted, total: total}}, state}
  end
end

Results

Coordination latency (p95, milliseconds):

ScaleCentralizedGossipHierarchicalHybrid
51.23.42.12.8
204.812.75.36.1
10089.447.214.816.2
4345,247312.438.741.3

Message complexity (messages per coordination round):

ScaleCentralizedGossipHierarchicalHybrid
510251218
20401804872
1002002,100228412
43486818,7409121,647

Decision consistency (%):

ScaleCentralizedGossipHierarchicalHybrid
5100%100%100%100%
20100%98.7%100%100%
10097.2%94.1%99.8%99.9%
43482.4%91.3%99.1%99.4%

Failure resilience (consistency after 10% agent crash):

ScaleCentralizedGossipHierarchicalHybrid
4340% (orchestrator dead)88.7%95.3%97.1%

Analysis

The results decisively confirm our hypothesis. The hierarchical pattern achieves O(N log N) message complexity (912 messages at N=434 compared to the O(N^2) gossip pattern's 18,740). Coordination latency of 38.7ms at p95 is well under the 50ms target, and decision consistency of 99.1% exceeds the 98% threshold.

The centralized pattern's catastrophic failure at 434 agents (5,247ms latency, 82.4% consistency) validates the decision to abandon it in Gen 6. The orchestrator becomes a single point of failure and a throughput bottleneck simultaneously.

The gossip pattern shows interesting scaling characteristics: its message complexity grows quadratically, but its latency grows only logarithmically because messages propagate in parallel. At 434 agents, gossip achieves 312ms latency with 91.3% consistency -- acceptable for eventual consistency use cases but insufficient for the platform's strong consistency requirements.

The Hybrid pattern adds marginal resilience improvement (97.1% vs 95.3% under failure) at the cost of 2x message complexity. This trade-off is worthwhile for mission-critical coordination but unnecessary for routine operations.

The most significant finding is the failure resilience gap. When 10% of agents crash, the centralized pattern fails completely (the orchestrator is among the crashed 10% with probability 1 at sufficient scale). Hierarchical and Hybrid patterns gracefully degrade because domain leaders and agent processes are distributed.

Conclusions

  1. Hierarchical coordination is the correct pattern for 400+ agent swarms requiring strong consistency.
  2. Gossip is useful only for state synchronization, not for command propagation.
  3. The Hybrid approach provides marginal resilience at 2x message cost -- deploy selectively.
  4. Domain-local autonomy is essential -- intra-domain decisions should not require global coordination.
  5. Sub-50ms coordination latency is achievable at scale with two-level hierarchies.

Next Steps

  • Evaluate three-level hierarchies for planned scaling to 1,000+ agents
  • Implement adaptive leader election that accounts for agent load and latency
  • Test coordination under sustained network degradation (not just sudden failure)
  • Benchmark with realistic decision payloads (current tests use minimal payloads)
  • Integrate with SEADF for autonomous coordination pattern evolution

Connect & Contribute

Created by Tomáš Korcak (korczis) | Open Source under GHL

Back to Lab