Overlays divide into two families:

Structured overlays assign keys to nodes deterministically, enabling efficient O(log n) lookups. Distributed Hash Tables (DHTs) are the canonical example. Every key maps to a well-defined set of responsible nodes, so queries converge predictably. This determinism is what makes content-addressed discovery via provider records practical.

Unstructured overlays form random or interest-based graphs. Queries use flooding, random walks, or supernodes. Examples include early Gnutella and the gossip-based dissemination used in Real-time Messaging and PubSub. Unstructured overlays are simpler to build but less efficient for exact lookups.

Many production systems combine both: a structured DHT for precise lookups and unstructured gossip for bulk dissemination.

Kademlia is the most widely deployed DHT algorithm. It uses an XOR distance metric to organize nodes into k-buckets, each covering an exponentially larger portion of the 160-bit (or 256-bit) address space. Lookups are iterative: a node queries its closest known peers, which return closer ones, converging in O(log n) steps.

Kademlia powers the discovery layer in:

libp2p (the Amino DHT for IPFS/Filecoin peer routing and content routing)

IPFS and Filecoin (provider records: "I have block X")

BitTorrent (BEP-5 mainline DHT—one of the largest DHTs in operation with tens of millions of nodes)

Hypercore (Hyperswarm's topic-based DHT)

I2P (the netDB for router and service discovery)

Key properties:

k-buckets: each bucket holds k contacts (typically k=20) at a given distance range. Stale contacts are evicted only when proven unreachable, naturally favoring long-lived, stable nodes.

Parallel lookups: α concurrent queries per step (typically α=3) reduce latency by not waiting for slow peers.

Iterative vs recursive: Kademlia traditionally uses iterative lookups (the querier drives each hop), giving it more control than recursive approaches where intermediate nodes forward on your behalf.

Replication: values are stored on the k closest nodes to the key and refreshed periodically; this provides redundancy under churn.

Self-healing: as nodes join and leave, bucket refresh and lookup-driven updates automatically repair the routing table.

Historical structured overlays with different routing geometries:

Chord (Stoica et al., 2001) arranges nodes on a ring of size 2^m. Each node maintains a finger table with O(log n) entries pointing to nodes at exponentially increasing distances. Lookups traverse O(log n) hops. Chord's simplicity made it influential, but its ring structure creates hotspots under skewed key distributions.

Pastry (Rowstron & Druschel, 2001) uses prefix-based routing with proximity-aware neighbor selection. Each hop resolves one more prefix digit. Pastry's leaf sets provide robust local routing even under failures.

Tapestry (Zhao et al., 2004) also uses prefix routing but with a different approach to fault tolerance and object location.

These systems established the theoretical foundations for structured P2P routing. Modern systems overwhelmingly use Kademlia due to its simplicity, symmetry (no distinguished nodes), and proven robustness at scale.

Not every node should participate fully in DHT routing. libp2p distinguishes:

DHT server mode: publicly reachable nodes that store records and respond to queries. These form the DHT backbone.

DHT client mode: nodes behind NATs (see Transport and Connectivity) that issue queries but don't store records for others.

This hybrid is an instance of the superpeer pattern: capable nodes carry the routing burden while lightweight clients still benefit from decentralized lookup.

Real-world DHTs face security threats that academic prototypes didn't anticipate:

Neighbor diversity: ensure k-buckets span different network prefixes, ASes, and geographic regions to resist eclipse attacks.

Signed records: authenticate stored values using identity keys to prevent poisoning. libp2p uses signed peer records and IPNS records.

Sloppy hashing: relax exact-key placement for caching and load balancing, reducing hotspots.

Proximity routing: prefer physically closer peers for lower latency lookups, often using RTT measurements.

Disjoint-path lookups: query along multiple independent paths to detect routing manipulation.

Record validation: application-level validators that reject malformed or outdated records before storage.

Not every P2P system uses a DHT for discovery:

Trackers and rendezvous servers: centralized or semi-centralized discovery as in BitTorrent trackers or libp2p rendezvous servers. See Design Patterns.

Social graph routing: Secure Scuttlebutt uses the follow graph instead of a DHT.

mDNS/local discovery: find peers on the same LAN without any external infrastructure.

Pinecone: Matrix's experimental spanning-tree overlay for P2P routing.

DHTs provide the discovery layer that Transport and Connectivity builds connections on top of. Content Addressing uses DHTs for provider records ("who has this CID?") and mutable name resolution (IPNS). Identity and Capabilities leverages DHTs for key discovery and revocation record publication. PubSub topic rendezvous can be implemented as DHT keys. Privacy is challenged by DHT queries which can reveal interest metadata, motivating query privacy techniques. Testing of DHTs requires network emulation to model churn and adversarial conditions.