Abandoning DNS for Autonomous Agent Mesh: Why We Use Bloom-Filter Based Peer Discovery

When you run a swarm of autonomous agents—each making decisions, coordinating tasks, and passing data—the last thing you want is a brittle discovery mechanism. DNS is the default choice for most networked systems, but in a mesh of self-healing agents, it becomes a single point of failure, a latency bottleneck, and a configuration nightmare. We abandoned DNS in our agent mesh and replaced it with a Bloom-filter-based peer discovery protocol. Here is why, and how it works.

The Problem with DNS in Agent Meshes

Centralized Dependency

Even with redundant DNS servers, the system still depends on a hierarchical namespace and a handful of root servers. If your agent mesh runs in an air-gapped or edge environment—say, a factory floor with intermittent connectivity—DNS resolution can fail. Worse, DNS updates propagate slowly (TTL), so when a new agent spawns or a node goes down, the rest of the swarm may not learn about it for minutes.

Configuration Overhead

Every agent typically needs to know the DNS server IP, domain, and sometimes SRV records. In a dynamic swarm where agents join and leave frequently, maintaining DNS records becomes a chore. Automating DNS updates (RFC 2136) adds complexity and security risks. For a mesh that should self-organize, this is unacceptable.

Not Designed for Peer-to-Peer

DNS is a client-server protocol. It expects clients to query a server. In a mesh, every node is both client and server. You end up with a central registry (like Consul or etcd) backing DNS, which re-introduces a single point of failure. A true peer-to-peer mesh should have no such dependencies.

Why Bloom Filters?

A Bloom filter is a space-efficient probabilistic data structure that answers the question: "Is this element a member of a set?" It can produce false positives but never false negatives. That means if the filter says an agent is not present, it is definitely not present. If it says it is present, it might be—but with a controlled error rate.

In peer discovery, each agent maintains a Bloom filter containing the identifiers (e.g., public keys or UUIDs) of all known alive agents. Agents periodically gossip their filters to a few random peers. When an agent wants to find a specific peer, it queries its local filter. If the filter says the peer is present, the agent initiates a direct connection; if not, it asks neighbors. Since false positives only cause a failed connection attempt (which is cheap), the probabilistic nature is harmless.

Advantages Over DNS

• No central registry: Every node has a copy of the membership set (encoded as a Bloom filter). The mesh is fully decentralized.
• Fast propagation: Gossip protocols propagate changes in seconds, not minutes. A new agent can be discovered by the whole mesh in under 100ms with a well-tuned gossip interval.
• Low memory: A Bloom filter for 10,000 agents with a 1% false positive rate consumes about 12 KiB. That fits in L1 cache.
• Offline tolerance: If an agent goes offline, its absence propagates via gossip. No DNS TTL to wait out.
• Zero configuration: No DNS server IP, no domain, no SRV records. Agents auto-discover by exchanging filters on a multicast or DHT bootstrap.

Implementation Details

We built our mesh using Go, with a custom gossip layer on top of UDP. Each agent has a 256-bit Ed25519 public key as its identity. The Bloom filter uses 128-bit MurmurHash3 with k=7 hash functions (optimized for n=10,000, p=0.01).

type Agent struct {
    ID        [32]byte // Ed25519 public key
    Bloom     *bloom.BloomFilter
    Peers     map[[32]byte]*PeerInfo
    GossipCh  chan GossipMessage
}

Every second, each agent picks a random subset of known peers (fanout=3) and sends its current Bloom filter. On receiving a filter, the agent merges it with its own (logical OR). To detect stale entries, we include a timestamp of the last update per agent ID in a separate delta list (not in the filter).

Handling Churn

When an agent leaves gracefully, it broadcasts a "goodbye" message. If it crashes, other agents detect timeout (missing heartbeats) and remove it from their local peer list. The Bloom filter is updated by subtracting the agent's bits? No—Bloom filters do not support deletion. Instead, we rebuild the filter from scratch every 10 seconds using the current peer list. This is cheap because the filter is small and the list is typically a few hundred entries.

False Positive Handling

If agent A queries its filter for agent B and gets a positive, it attempts a direct TCP connection. If B is not actually alive, the connection fails (e.g., after a 1-second timeout). A then marks B as "suspect" and asks its neighbors for confirmation. If multiple neighbors report B absent, A removes B from its list and the filter will reflect that in the next rebuild. False positives are rare (1% or less) and cause negligible overhead.

Comparison with Existing Solutions

Consul / etcd + DNS

These are centralized. They work well for static clusters but fail in high-churn or partitioned environments. Our mesh handles 1000 agents joining and leaving per second without any central coordination.

SWIM (Scalable Weakly-consistent Infection-style Membership)

SWIM is a gossip-based membership protocol used by Serf and HashiCorp's memberlist. It is excellent but uses a fixed-size membership list. Bloom filters allow us to compress the membership into a constant-size message, reducing gossip bandwidth. For a 10,000-node mesh, SWIM's full membership list would be ~320 KiB per message; our Bloom filter is 12 KiB.

DHT-based Discovery (Kademlia)

DHTs like Kademlia are great for storing values, but they require iterative lookups that can take multiple RTTs. Our Bloom filter gives an instant answer locally. If the agent is not in the filter, we fall back to a gossip query that still resolves in one or two hops.

Real-World Performance

We deployed a 500-agent mesh across 10 Raspberry Pi 4s (4 GB RAM, 1.5 GHz ARM Cortex-A72) in a lab simulating edge nodes. Each agent ran a lightweight model (Llama 3.2 1B via llama.cpp) and communicated via gRPC. The Bloom filter gossip consumed less than 1% CPU and 5 MB memory per node. Discovery latency for a new agent joining was <500ms (95th percentile). False positive rate was 0.8%, causing only occasional failed connection attempts that were retried on the next gossip cycle.

In contrast, a DNS-based setup using CoreDNS with etcd backend on the same hardware required a central server (one Pi dedicated as DNS) and showed discovery latency of 2-10 seconds due to TTL and propagation delays. When the central server went down, the entire mesh lost the ability to discover new peers until it recovered.

Caveats

Bloom filters are not a silver bullet. They cannot list all members—only test membership. If you need to enumerate the swarm (e.g., for a dashboard), you must maintain a separate list. We use a small delta list of recently changed entries for that purpose.

Also, false positives can be annoying if your connection setup is expensive. In our case, gRPC handshake is ~1ms, so it is fine. If you use heavy TLS mutual auth, you might want to reduce the false positive rate by increasing filter size.

Conclusion

DNS is a legacy protocol designed for a different era. For autonomous agent meshes that demand resilience, low latency, and zero configuration, Bloom-filter-based peer discovery is a superior alternative. It removes central points of failure, reduces bandwidth, and simplifies operations. We have been running it in production for six months, and it has survived network partitions, node crashes, and massive churn without a hiccup.

If you are building a self-organizing agent swarm, do not reach for DNS. Reach for a Bloom filter.