Trade-offs in Decentralized Agentic AI Discovery Across the Compute Continuum

Technical Summary: Trade-offs in Decentralized Agentic AI Discovery Across the Compute Continuum

Problem Statement
As AI agents evolve from isolated assistants into distributed components spanning cloud, edge, and intermittently connected domains, the mechanism for agent discovery becomes a critical control-plane function. In decentralized architectures, such as the AGNTCY framework, the agent directory is not merely a registry but operational infrastructure where latency, reliability, and communication overhead directly impact orchestration. While Distributed Hash Tables (DHTs) are a standard solution for decentralized lookup, the choice of a specific structured-overlay family (e.g., Chord, Pastry, Kademlia) significantly dictates the "reliability-cost regime" of the system. The paper addresses the question of which DHT family offers the most attractive operating point for agent discovery under realistic deployment conditions, particularly when accounting for the nuances of the compute continuum where misses can propagate into failed coordination.

Methodology
The study employs an empirical evaluation framework comparing three canonical DHT families—Chord, Pastry, and Kademlia—within a shared control-plane abstraction modeled after the AGNTCY Agent Directory Service (ADS). The evaluation focuses on four operator-visible dimensions:

1. Effectiveness: Discovery success and recall.
2. Cost: Control-plane traffic (messages per query).
3. Efficiency: P95 query latency.
4. Robustness: Performance under churn.

The experiments utilize a fixed workload abstraction: a catalog of 50 skills where each of the 4,096 nodes advertises exactly one skill, and all queries target a specific skill (skill_05). This design isolates the overlay family's behavior from semantic matching or ranking heuristics.

Two benchmark scenarios are executed at a scale of $N=4096$:

• Stationary Comparison: Compares two startup regimes. The "immediate" regime issues queries from the start of the run, while the "warmed" regime admits queries only after a bootstrap period plus a warmup of $\log_2 N$. This distinguishes cold-start penalties from steady-state routing costs.
• Representative Churn Benchmark: Tests the system under persistent departures and rejoins (exponential sessions with a mean of 100 and downtime of 30) to verify if stationary rankings hold under dynamic conditions.

The analysis distinguishes between "Observed Cost" (total messages including concurrent publication/republish traffic) and "Query-only Cost" (structured GET messages), allowing for a separation of cold-start interference from intrinsic routing overhead.

Key Results
The evaluation reveals distinct operating regimes based on the startup phase and the trade-off between cost and latency:

• Cold-Start Penalty: In the immediate query regime, all three overlays suffer from reduced discovery success (ranging from 0.60 to 0.64) and inflated latency and message costs due to overlapping bootstrap traffic.
• Stabilization: A short warmup period of $\log_2 N$ is sufficient to remove the cold-start penalty. In the warmed regime, all three overlays achieve 1.0 discovery success and high recall.
• Steady-State Trade-offs (Warmed/Churn): Once stabilized, the overlays diverge in cost and latency:
  • Pastry: Emerges as the lowest-cost operating point. In the churn benchmark, it achieved the lowest observed messages per query (~5.84k) with a P95 latency of 5.0.
  • Chord: Occupies a higher-cost middle ground, with traffic and latency metrics falling between Pastry and Kademlia.
  • Kademlia: Achieves the lowest tail latency (P95 of 4.6 in churn) but at the cost of the highest communication bill (~11.5k messages/query), roughly double that of Pastry.
• Churn Resilience: At the representative churn point, all three overlays maintained 1.0 success and precision. The primary differentiator remained the trade-off between traffic volume and tail latency, rather than retrieval correctness.

Significance and Claims
The paper explicitly states that its contribution is not to rank every concrete implementation or propose a new DHT, but to clarify the control-plane operating regimes exposed by canonical DHT families when repurposed for agent discovery.

• Design Space Preservation: The authors argue that family-level choices constrain the subsequent optimization space. By clarifying these regimes early, the paper aims to prevent the premature collapse of the design space onto a single canonical choice before agent ecosystems fully understand their operational budgets.
• Operational Guidance: The results suggest that if a deployment can defer query admission briefly, a $\log_2 N$ warmup allows operators to select based on residual cost/latency preferences (Pastry for cost efficiency, Kademlia for low tail latency). If queries arrive during cold start, the full observed control-plane load must be the metric of evaluation.
• Methodological Value: The study provides a controlled, reproducible baseline (stationary plus churn) that separates startup effects, lookup costs, and maintenance costs. This serves as a reference point for future research in decentralized agent discovery, ensuring that future comparisons can distinguish between substrate behavior and application-specific semantics.

In summary, the paper concludes that there is no universal winner; rather, the optimal choice depends on the deployment's tolerance for traffic overhead versus tail latency, and whether the system can accommodate a brief stabilization period before full discovery admission.