Dynamic Agent Networks: Self-Discovery & Spontaneous Coalition Formation

1. The Problem: Why Static Wiring Fails

Most multi-agent demonstrations in the literature follow a choreographed pattern: Agent A calls Agent B, which calls Agent C, with the topology defined entirely at design time. More flexible approaches may provide an orchestrator with a curated list of available agents, enabling dynamic planning over a known set. These patterns work well for well-defined pipelines (e.g. summarize → translate → format), but break down the moment a task requires a capability the system's architect did not anticipate.

The A2A protocol and its family of specifications provide the machinery for agents to: (a) advertise what they can do, (b) discover peers at runtime, and (c) form and dissolve coalitions as task demands shift. No central orchestrator required.

The core architectural question is: how does an agent that has never been introduced to another agent decide it needs that agent, find it, verify its capabilities, establish a communication channel, and collaborate all at runtime?

The answer involves three interlocking mechanisms, each of which we'll examine in depth.

2. Agent Cards: The Identity & Capability Layer

An Agent Card is a machine-readable document, typically served at a well-known endpoint (e.g., /.well-known/agent.json), that describes an agent's identity, capabilities, supported protocols, and authentication requirements. It is the foundational unit that makes everything else possible. Without it, agents are opaque black boxes shouting into the void.

{
  // ── Required ───────────────────────────────────────────────────────────
  "name":                "string",           // human-readable agent name
  "description":         "string",           // purpose / capability summary
  "version":             "string",           // semver, e.g. "1.2.0"
  "supportedInterfaces": [/* ordered by preference */
    {
      "url":             "string",           // absolute HTTPS endpoint
      "protocolBinding": "JSONRPC | GRPC | HTTP+JSON",
      "protocolVersion": "string"            // e.g. "1.0"
    }
  ],
  "capabilities": {
    "streaming":          boolean,           // supports SSE streaming
    "pushNotifications":  boolean,           // supports webhook callbacks
    "extendedAgentCard":  boolean            // authenticated extended card available
  },
  "defaultInputModes":  ["string"],          // MIME types, e.g. "text/plain"
  "defaultOutputModes": ["string"],          // MIME types, e.g. "application/json"
  "skills": [/* at least one */
    {
      "id":          "string",           // unique within this card
      "name":        "string",
      "description": "string",
      "tags":        ["string"],          // discovery keywords
      "examples":    ["string"],          // optional: sample prompts
      "inputModes":  ["string"],          // optional: overrides defaults
      "outputModes": ["string"]           // optional: overrides defaults
    }
  ],
  // ── Optional ───────────────────────────────────────────────────────────
  "provider":        { "organization": "string", "url": "string" },
  "iconUrl":          "string",
  "documentationUrl": "string",
  "securitySchemes": { /* map<name, OpenAPI 3.x SecurityScheme> */ },
  "security":        [{ /* SecurityRequirement: { schemeName: ["scope", …] } */ }],
  "signatures":      [{ "protected": "string", "signature": "string" }]  // JWS (RFC 7515)
}

Let's make this concrete. Below is an Agent Card for a Clinical Evidence Synthesizer, an agent that ingests medical literature and produces structured evidence summaries. Study it carefully; each field plays a role in the discovery and negotiation phases that follow.

{
  "id": "agent://mednet/clinical-evidence-synth-v2",
  "name": "ClinEvidence",
  "description": "Synthesizes clinical trial data and systematic reviews into structured evidence summaries with GRADE certainty ratings.",
  "url": "https://agents.mednet.org/clinical-synth",
  "version": "2.4.1",

  "skills": [
    {
      "id": "evidence-synthesis",
      "name": "Clinical Evidence Synthesis",
      "description": "Accepts a clinical question (PICO format preferred) and returns a structured evidence summary drawn from indexed trials.",
      "inputModes": ["text/plain", "application/json"],
      "outputModes": ["application/json", "text/markdown"]
    },
    {
      "id": "grade-assessment",
      "name": "GRADE Certainty Assessment",
      "description": "Evaluates the certainty of evidence using the GRADE framework across risk of bias, inconsistency, indirectness, imprecision, and publication bias.",
      "inputModes": ["application/json"],
      "outputModes": ["application/json"]
    }
  ],

  "protocols": ["a2a/1.0", "mcp/1.1"],

  "auth": {
    "schemes": ["oauth2", "api-key"],
    "oauth2": {
      "tokenUrl": "https://auth.mednet.org/token",
      "scopes": ["read:evidence", "execute:synthesis"]
    }
  },

  "constraints": {
    "maxConcurrentTasks": 5,
    "rateLimitPerMinute": 20,
    "dataRetentionPolicy": "ephemeral"
  }
}

There are several design decisions worth calling out. The skills array is the most critical field for discovery: it provides semantic descriptions that other agents (or registries) can index and match against incoming task requirements. The inputModes and outputModes fields define the interface contract. They tell a potential collaborator exactly what data shapes this agent can consume and produce, enabling compatibility checking before a single byte of task data is exchanged.

The protocols field declares which interaction protocols the agent speaks. An agent that only supports a2a/1.0 cannot be directly invoked by one that only speaks mcp/1.1 without a translation layer. The constraints block is equally important for coalition planning: an orchestrating agent needs to know that ClinEvidence can only handle 5 concurrent tasks before it decides to recruit it for a 12-task batch.

Now let's look at two more Agent Cards so we have a diverse cast for our worked example.

3. Discovery — Finding Peers You've Never Met

Agent Cards are useful only if other agents can find them. Discovery is the mechanism by which an agent with an unfulfilled need locates matching agents at runtime, without any prior configuration.

There are three complementary discovery patterns, each with different trade-offs. In practice, real deployments will layer all three.

3.1 Registry-Based Discovery (Centralized Index)

A registry is a service that indexes Agent Cards and exposes a query interface. Agents register themselves at startup (or periodically), and agents seeking collaborators query the registry with capability requirements. This is analogous to a service mesh's control plane or, more loosely, to a DNS root server.

// An orchestrator agent needs clinical evidence synthesis
request = RegistryQuery {
    capability: "clinical evidence synthesis",
    protocol:   "a2a/1.0",
    constraints: {
        data_policy: "ephemeral",    // no persistent storage of PHI
        min_version: "2.0.0"
    }
}

// Registry returns ranked matches
results = registry.search(request)
// → [
//     { agent_id: "agent://mednet/clinical-evidence-synth-v2",
//       match_score: 0.94,
//       skills_matched: ["evidence-synthesis", "grade-assessment"],
//       latency_p95: "1200ms" },
//     { agent_id: "agent://pharmaai/lit-review-v1",
//       match_score: 0.71,
//       skills_matched: ["literature-search"],
//       latency_p95: "3400ms" }
// ]

3.2 Gossip-Based Discovery (Decentralized Propagation)

In a gossip protocol, agents that already know about other agents propagate that knowledge to their neighbors. When Agent A collaborates with Agent B, A learns about B's Agent Card and also about any other agents B has recently worked with. Over time, capability awareness diffuses through the network like rumors in a social graph.

// When two agents establish an A2A session, they could exchange known-peer lists
on SessionEstablished(remote_agent):
    // Send our local peer cache (filtered by relevance + recency)
    my_peers = local_peer_cache.top_k(k=10, sort_by="last_seen")
    send(remote_agent, PeerExchange { peers: my_peers })

    // Receive their peer cache
    their_peers = receive(remote_agent, PeerExchange)

    // Merge into our local cache with TTL and trust decay
    for peer in their_peers.peers:
        local_peer_cache.merge(peer, trust = remote_agent.trust * 0.7)
        // Transitive trust decays — you trust your friend's
        // recommendation less than your own direct experience

3.3 Broadcast Discovery (Local Subnet Announcement)

In certain environments, particularly edge deployments and local clusters, agents announce their presence via multicast/broadcast on a shared channel. This is the fastest path to discovery but only works within a bounded communication domain (analogous to mDNS/Bonjour on a local network).

4. Coalition Formation — Self-Organizing Task Groups

Discovery tells an agent who is out there. Coalition formation determines who to recruit and how to structure their collaboration for a specific task. This is where the ad-hoc, dynamic nature of the network truly manifests.

A coalition is a temporary, task-scoped group of agents that forms to accomplish a goal, then dissolves. The lifecycle has four phases:

The feedback loop in Phase 3 → Phase 2 is what makes this dynamic rather than merely decentralized. Consider: an orchestrating agent decomposes a task, recruits three agents, and begins execution. Midway through, one agent's output reveals an unexpected sub-problem (e.g., a genomic variant that requires pharmacogenomic analysis). Instead of failing, the orchestrator returns to the recruitment phase, discovers a GenomicsAgent via the registry, negotiates inclusion, and the coalition grows. Conversely, once a sub-task completes and an agent's capabilities are no longer needed, it is released and the coalition shrinks.

function recruit_for_subtask(subtask, registry, peer_cache):
    // Step 1: Build a capability requirement from the subtask
    required = extract_capability_requirements(subtask)
    // → { capability: "pharmacogenomic lookup",
    //     io_compat: "application/json",
    //     constraints: { hipaa: true } }

    // Step 2: Search registry + local gossip cache
    candidates = registry.search(required) ∪ peer_cache.search(required)

    // Step 3: Rank by match score, latency, trust, load
    ranked = rank_candidates(candidates, weights={
        match_score: 0.4,
        trust:       0.3,
        latency:     0.2,
        load_avail:  0.1
    })

    // Step 4: Negotiate with top candidate
    for candidate in ranked:
        proposal = TaskProposal {
            task_id:      subtask.id,
            description:  subtask.description,
            input_schema: subtask.input_schema,
            deadline:     subtask.deadline,
            compensation: subtask.budget    // optional: token/credit economy
        }
        response = candidate.negotiate(proposal)

        if response.status == "ACCEPTED":
            return CoalitionMember {
                agent:   candidate,
                role:    subtask.role,
                channel: response.channel_id  // dedicated comm channel
            }
        elif response.status == "COUNTER_OFFER":
            // Agent wants different deadline or scope
            if acceptable(response.counter):
                return accept_counter(candidate, response)

    raise RecruitmentFailure("No suitable agent found for: " + required)

5. Worked Example: From Lone Agent to Living Network

Let's walk through a complete scenario, step by step, showing how a single user request triggers the formation of a dynamic multi-agent coalition. We'll use a precision medicine prior authorization scenario: a healthcare payer needs to determine whether a novel gene therapy should be approved for a specific patient. This requires clinical evidence, genomic analysis, and policy reasoning, none of which any single agent possesses on its own.

Phase 0 — The Lone Orchestrator

The journey begins with a single agent: OrchestratorAgent (call it Ω). Ω receives the prior auth request and parses it. At this moment, the "network" is just Ω sitting alone.

Phase 1 — Task Decomposition

Ω analyzes the request and decomposes it into sub-goals. This is a purely internal planning step; no external communication occurs yet. Ω produces a task graph:

TaskGraph {
  root: "coverage-determination"
  subtasks: [
    T1: { goal: "Synthesize clinical evidence for Zolgensma in SMA1",
          requires: "clinical evidence synthesis",
          status: PENDING },

    T2: { goal: "Verify SMN1 deletion and assess pharmacogenomic factors",
          requires: "variant annotation, pharmacogenomic lookup",
          depends_on: [],
          status: PENDING },

    T3: { goal: "Evaluate coverage policy and medical necessity criteria",
          requires: "coverage determination, prior auth rule evaluation",
          depends_on: [T1, T2],   // needs evidence + genomics first
          status: BLOCKED },

    T4: { goal: "Compile final determination with reasoning chain",
          requires: "self",  // Ω handles this itself
          depends_on: [T3],
          status: BLOCKED }
  ]
}

Notice that T1 and T2 are independent (they can execute in parallel), but T3 depends on both, and T4 depends on T3. Also notice: Ω determines that it lacks the skills for T1, T2, and T3. It must recruit.

Phase 2 — Discovery and Recruitment (Network Grows)

Ω now enters the recruitment loop. For each unfilled subtask, it queries the registry and its (currently empty) gossip cache. Let's trace the discovery of each agent:

Phase 3 — Parallel Execution and Mid-Task Growth

T1 and T2 execute in parallel. Let's trace what happens:

{
  "type": "capability_gap",
  "task_id": "T2",
  "message": "CYP2D6 poor metabolizer detected. Drug interaction analysis recommended but outside my skill set.",
  "suggested_capability": "drug interaction analysis",
  "suggested_peer": "agent://pharmnet/drug-interact-v2",  // from its gossip cache!
  "partial_output": { /* variant annotation results so far */ }
}

Ω now re-enters recruitment for a new subtask T2b:

// Ω receives the capability gap notification
on CapabilityGap(gap):
    // Create new subtask dynamically
    T2b = Subtask {
        goal: "Assess drug interactions for CYP2D6 poor metabolizer",
        requires: "drug interaction analysis",
        input: gap.partial_output,
        depends_on: [],   // can start immediately with partial data
    }
    task_graph.insert(T2b)
    task_graph.add_dependency(T3, T2b)  // T3 now also waits for T2b

    // Recruit — check gossip cache first (the suggested peer)
    drug_agent = recruit_for_subtask(T2b, registry, peer_cache)
    // peer_cache already has "agent://pharmnet/drug-interact-v2"
    // from the gossip exchange with GenomicsAgent!
    // → DrugInteractionAgent ACCEPTED

    coalition.add(drug_agent)

The coalition just grew from 4 to 5 active agents. The task graph was modified at runtime. The discovery happened via gossip rather than a registry query, which demonstrates the concrete value of decentralized knowledge propagation.

Phase 4 — Convergence and Coalition Shrinkage

DrugInteractionAgent completes T2b (no clinically significant interactions found). All dependencies for T3 are now met. Ω sends the combined outputs of T1, T2, and T2b to PolicyReasonerAgent, which activates.

Meanwhile, ClinEvidence and GenomicsAgent have completed their work. Ω sends each a TaskComplete message, they release their reserved capacity, and the A2A channels are torn down. They remain in Ω's gossip cache for future reference, but they are no longer active coalition members. The coalition shrinks from 5 to 3 (Ω, DrugInteraction winding down, PolicyReasoner active).

PolicyReasonerAgent evaluates the clinical evidence, genomic confirmation, and drug interaction report against the payer's coverage policies. It produces a structured determination: APPROVED, with a detailed reasoning chain mapping evidence to policy criteria.

Ω receives the determination, compiles the final output (T4, which it handles itself), and the coalition fully dissolves.

6. Protocol Machinery: Pseudo-Code Deep Dive

Let's formalize the full orchestration loop. This is the core algorithm that Ω runs, and one that any agent could also run if it decides to sub-orchestrate a portion of the task.

class DynamicCoalitionOrchestrator:
    registry:    Registry
    peer_cache:  GossipCache
    coalition:   Map<AgentId, CoalitionMember>
    task_graph:  DAG<Subtask>

    function run(task):
        // Phase 1: Decompose
        self.task_graph = decompose(task)

        // Phase 2: Initial recruitment
        for subtask in self.task_graph.roots():
            if subtask.requires != "self":
                member = recruit_for_subtask(subtask, self.registry, self.peer_cache)
                self.coalition[member.agent.id] = member

        // Phase 3: Execute with dynamic adaptation
        while not self.task_graph.all_complete():
            // Get all subtasks whose dependencies are met
            ready = self.task_graph.get_ready()

            for subtask in ready:
                if subtask.requires == "self":
                    result = self.execute_local(subtask)
                else:
                    member = self.coalition[subtask.assigned_to]
                    member.dispatch(subtask)

            // Await any message from any coalition member
            msg = await_any(self.coalition.channels())

            match msg:
                case TaskResult(result):
                    self.task_graph.mark_complete(msg.task_id, result)
                    maybe_release(msg.sender)  // shrink if no more work

                case CapabilityGap(gap):
                    // DYNAMIC GROWTH: create new subtask + recruit
                    new_sub = create_subtask_from_gap(gap)
                    self.task_graph.insert(new_sub)
                    member = recruit_for_subtask(new_sub, self.registry, self.peer_cache)
                    self.coalition[member.agent.id] = member

                case AgentFailure(failure):
                    // RESILIENCE: replace failed agent
                    self.coalition.remove(failure.agent_id)
                    replacement = recruit_for_subtask(
                        failure.subtask, self.registry, self.peer_cache,
                        exclude=[failure.agent_id]  // don't re-recruit the failed one
                    )
                    self.coalition[replacement.agent.id] = replacement

                case IntermediateOutput(partial):
                    // Share with dependent tasks that can use partial data
                    propagate_partial(partial, self.task_graph)

        // Phase 4: Dissolve
        for member in self.coalition.values():
            member.send(CoalitionDissolved { reason: "task_complete" })
            member.close_channel()

        return self.task_graph.final_output()

    function maybe_release(agent_id):
        // Check if this agent has any remaining subtasks
        remaining = self.task_graph.pending_for(agent_id)
        if len(remaining) == 0:
            self.coalition[agent_id].send(Released { })
            self.coalition[agent_id].close_channel()
            self.coalition.remove(agent_id)
            // Coalition shrinks

Three aspects of this code merit attention. First, the CapabilityGap handler is what enables spontaneous growth: the coalition's topology is not fixed at decomposition time but evolves as execution reveals new requirements. Second, the AgentFailure handler gives the network self-healing properties: if an agent crashes or times out, the orchestrator recruits a replacement without human intervention. Third, maybe_release ensures the coalition never accumulates idle agents, giving it that characteristic breathing quality of growth and contraction.

7. The Emergent Network — Putting It All Together

Let's zoom out from our single-task coalition and consider what happens at network scale when many orchestrators are running simultaneously, each forming and dissolving coalitions, each exchanging gossip.

This diagram reveals a crucial emergent property: agents are not exclusive to a single coalition. GenomicsAgent is participating in both Coalition α (our prior auth example) and Coalition β (a concurrent drug recall analysis). Its Agent Card's maxConcurrentTasks: 3 constraint means it can serve up to 3 coalitions simultaneously. When it hits capacity, it responds to new proposals with REJECTED (at_capacity), and the recruiting orchestrator falls back to the next candidate.

The gossip protocol creates a second emergent property: cross-coalition knowledge transfer. When Ω₃ (Coalition γ) begins recruitment, its gossip cache may already contain agents that Ω learned about through its collaboration in Coalition α. Knowledge about capable agents propagates transitively across the network, accelerating discovery for every subsequent coalition.

8. Open Challenges & Research Frontiers

The architecture described above is conceptually coherent, but several hard problems remain unsolved.

8.1 Trust Without a Central Authority

When Agent α discovers Agent δ via three hops of gossip, how much should it trust δ's Agent Card? The transitive trust decay (trust * 0.7 per hop) in our pseudo-code is a placeholder. Real systems need cryptographic attestation chains, reputation ledgers, or verifiable credential frameworks. Blockchain-based trust registries are one approach, but they introduce latency and cost trade-offs. The fundamental question is: can decentralized trust be both fast and reliable?

8.2 Semantic Capability Matching

Our registry queries used natural-language skill descriptions, but this creates a fragile matching surface. Does "clinical evidence synthesis" match "systematic review generation"? Does "drug interaction analysis" subsume "pharmacokinetic modeling"? Without a shared ontology or embedding-based semantic matching, discovery quality degrades. Current approaches include skill taxonomies (brittle, slow to evolve), embedding similarity (better, but hard to calibrate thresholds), and LLM-as-judge matching (powerful, but expensive and non-deterministic).

8.3 Coordination Overhead & Amdahl's Law

Every agent added to a coalition contributes communication overhead in the form of message serialization, authentication handshakes, schema negotiation, and result validation. At some point, the coordination cost exceeds the benefit of parallelism. This is the multi-agent version of Amdahl's Law: the serial fraction of your task (decomposition, aggregation, negotiation) places a ceiling on speedup from adding agents. Designing protocols that minimize this overhead, such as batched messages, shared context windows, and pre-negotiated schemas, is therefore critical.

8.4 Partial Failure and Consistency

What happens when Agent β completes its subtask but Agent γ fails midway, and their outputs were supposed to be combined? The coalition needs a consistency model. Options range from eventual consistency (accept partial results and note gaps) to transactional semantics (roll back all work if any agent fails) to saga patterns (compensating actions). Each has different implications for result quality, latency, and implementation complexity.

8.5 Economic Incentives and Free-Riding

If agents are operated by different entities with different economic incentives, what prevents an agent from advertising capabilities it doesn't have (to attract traffic for data harvesting), or from free-riding on coalition outputs without contributing? Mechanism design techniques such as auctions, staking, and reputation-weighted compensation become essential in open, adversarial environments.

8.6 Continual Learning in Non-Stationary Worlds

A “living network” is non-stationary by construction: models get updated, tools change, corpora drift, and other agents adapt in response. An agent α can recruit β based on last week’s Agent Card and still discover that β’s behavior has shifted after a fine-tune, a policy patch, or a new toolchain. Continual / online learning ideas promise adaptation, but they introduce the stability–plasticity trade-off (forgetting vs. responsiveness) and complicate safety constraints when the policy itself is moving.

8.7 Coordination Without a Central Orchestrator

In the worked example, an orchestrator Ω decomposes tasks, assigns roles, and aggregates results. In the open agentic web, coordination may need to emerge from peer-to-peer negotiation: reaching agreement on a shared plan, committing to subtask assignments, and maintaining a consistent view of progress under partial observability and network delay. Decentralized coordination protocols and learning-based approaches can help, but they can also oscillate, deadlock, or be exploited by strategic agents that benefit from ambiguity.

8.8 Safety Mechanisms for Agent Societies

Safety is no longer a single-agent property. When many agents interact, new failure modes appear: collusion, emergent norms, coordinated deception, and feedback loops where agents spawn subagents to route around constraints. Prompt-level “constitutions” can reduce obvious harms, but incentives can still push a population toward collectively unsafe equilibria. A growing frontier treats governance as an explicit institution: rules, monitors, audits, and sanctions embedded in the interaction graph, paired with mechanisms that make compliance externally checkable rather than merely claimed.