Paper deep dive

SemDHT: Certified Semantic Discovery for Peer-to-Peer Agent Networks over Exact-Key DHTs

Taotao Wang, Chonghe Zhao, Shengli Zhang, Soung Chang Liew

Year: 2026Venue: arXiv preprintArea: cs.NIType: PreprintEmbeddings: 155

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%

Last extracted: 9/27/2026, 2:49:09 AM

Summary

The paper introduces SemDHT, a certified semantic index for discovering agent-accessible capabilities in peer-to-peer networks using exact-key Distributed Hash Tables (DHTs). It employs a two-layer semantic sketch (coarse cells and residual codes) to map semantic descriptors to exact keys, allowing providers to publish at bounded keys and requesters to probe within a lookup budget. Anchor committees certify the publication-key sets to prevent exposure inflation. SemDHT demonstrates higher efficiency than Locality-Sensitive Hashing (LSH) on DHTs, achieving comparable recall with significantly fewer lookups and faster completion times.

Entities (6)

SemDHT · system · 100%DHT · technology · 95%Anchor Committee · component · 90%LSH · algorithm · 90%ToolBench · benchmark · 90%libp2p · framework · 85%

Relation Signals (5)

Anchor Committee → certifies → publication-key set

confidence 95% · Anchor committees certify each descriptor's publication-key set...

SemDHT → uses → DHT

confidence 95% · SemDHT is a certified semantic index for discovering agent-accessible capabilities over exact-key DHTs.

SemDHT → achievesrecallon → ToolBench

confidence 90% · SemDHT achieves recall@10 of 0.947 against ToolBench relevance labels.

SemDHT → outperforms → LSH

confidence 90% · SemDHT achieves mean completion-time speedups of 3.64x and 4.11x over LSH, respectively.

SemDHT → implementedin → libp2p

confidence 85% · A Go/libp2p prototype deployed on same-region and cross-region 200-peer cloud overlays

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:Agents may need capabilities exposed through external agent endpoints or service APIs. When a requester is not already bound to a provider, it must discover advertised capabilities matching its task and interface requirements. Over exact-key distributed hash tables (DHTs), broad retrieval transfers large candidate lists, whereas selective retrieval may miss relevant providers or require more replication and lookups. Open publication also lets providers inflate their exposure unless publication bounds are enforceable. We present SemDHT, a certified semantic index for discovering agent-accessible capabilities over exact-key DHTs. A two-layer semantic sketch uses coarse cells to group nearby descriptors and residual codes to narrow candidate selection. Providers publish at a bounded set of derived keys, while requesters probe precision keys before broader recall keys within a lookup budget. Anchor committees certify each descriptor's publication-key set, enabling storage services and requesters to enforce descriptor-to-key consistency. On real API descriptors and task queries, SemDHT achieves recall@10 of 0.955 against exact embedding-space neighbors and 0.947 against ToolBench relevance labels. On a corpus with controlled density augmentation, it matches the candidate exposure of tuned locality-sensitive hashing (LSH) over a DHT at recall 0.95 with 7.7x fewer lookups and reduces publication fan-out from 16 to 10. A Go/libp2p prototype deployed on same-region and cross-region 200-peer cloud overlays replays 299 Internet queries. With parallel probes and cold certificate caches, SemDHT achieves mean completion-time speedups of 3.64x and 4.11x over LSH, respectively.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

152,093 characters extracted from source content.

Expand or collapse full text

SemDHT: Certified Semantic Discovery for Peer-to-Peer Agent Networks over Exact-Key DHTs Taotao Wang22 2 Equal contribution. Correspondence: ttwang@szu.edu.cn. Chonghe Zhao22 2 Equal contribution. Correspondence: ttwang@szu.edu.cn. Shengli Zhang Soung Chang Liew Shenzhen University Guangzhou University Shenzhen University The Chinese University of Hong Kong Abstract Tasks involving external data or operational state may require capabilities exposed through agent endpoints or service APIs. When a service requester is not already bound to a service provider, it must discover advertised capabilities matching its task and interface requirements. Over exact-key distributed hash tables (DHTs), broad retrieval transfers large candidate lists, whereas selective retrieval may miss relevant providers or require more replication and lookups. Open publication also lets providers inflate their exposure unless publication bounds are enforceable. We present SemDHT, a certified semantic index for discovering agent-accessible capabilities over exact-key DHTs. A two-layer semantic sketch uses coarse cells to group nearby descriptors and residual codes to narrow candidate selection. Service providers publish at a bounded set of derived keys, while requesters probe precision keys before broader recall keys within a lookup budget. Anchor committees certify each descriptor’s publication-key set, enabling storage services and requesters to enforce descriptor-to-key consistency. On real API descriptors and task queries, SemDHT achieves recall@10=0.955recall@10=0.955 against exact embedding-space neighbors and 0.9470.947 against relevance labels from ToolBench, a benchmark for language-model tool use. On a corpus with controlled density augmentation, it matches the candidate exposure of tuned locality-sensitive hashing (LSH) over a DHT at recall 0.950.95 with 7.7×7.7× fewer lookups and reduces publication fan-out from 16 to 10. A Go/libp2p prototype deployed on same-region and cross-region 200-peer cloud overlays replays 299 Internet queries. With parallel probes and cold certificate caches, SemDHT achieves mean completion-time speedups of 3.64×3.64× and 4.11×4.11× over LSH, respectively. Keywords: agent-accessible services; semantic capability discovery; distributed hash tables; certified publication. 1 Introduction An agent carrying out a task may need data or operational state held by an external provider [26]. Consider a user arriving in an unfamiliar city who asks their personal assistant agent, “Find an eye clinic with an appointment available tomorrow.” The agent can interpret the request using a language model, but must obtain current appointment availability from a clinic’s service. The clinic may expose its appointment-query capability through an appointment assistant agent or a structured service API [1, 26]. In either case, the user’s personal assistant acts as the service requester and needs access to an externally provided capability. Preconfigured services suffice when the required provider and interface are known. We study requests for which suitable providers must first be identified from independently published capability descriptions [14]. In the appointment example, the personal assistant first discovers services advertising the relevant query capability, then contacts candidates to check location and current availability. This example illustrates discovery before service interaction; the index returns candidate descriptions, while subsequent interaction uses the selected service’s interface and authorization requirements. We consider this discovery problem in peer-to-peer (P2P) agent networks with independently managed providers [38, 37]. Centralized search makes discovery depend on one service, while flooding incurs work that grows with the network. We seek a decentralized semantic index that discovers capabilities from task intent expressed in natural language, while bounding publication fan-out and budgeting network lookups. Distributed hash tables (DHTs) provide exact-key routing to responsible peers without a central directory [34, 23, 31]. Recent agent-discovery systems match task and capability semantics [14, 39, 40]. Such matching depends on semantic similarity, whereas a DHT lookup requires an exact key. DHT routing alone does not identify providers whose capabilities match a task. (a) Shared semantic neighborhoodhard constraints match ⇒n⁡(d)∈q n(d) _qcell 17centroid μ17 _17cell 42centroid μ42 _42descriptor d (zdz_d)query q (zqz_q) same cell IDs: Zq∩Zd=17,42Z_q∩ Z_d=\17,42\ similar within-cell residual codes (b) Bounded exact-key overlapdescriptor ddpublication-key setKpub(d)K_pub(d)κ1 _1κ2 _2κ3 _3⋯·squery qqbudgeted probe-key setKqry(q,Lq)K_qry(q;L_q)κ1 _1κ7 _7κ3 _3⋯·sexact-key overlapκ1,κ3\ _1, _3\publish cap|Kpub(d)|≤ρ⁡(1+J)|K_pub(d)|≤ρ(1+J)lookup budget|Kqry(q,Lq)|≤Lq|K_qry(q;L_q)|≤ L_q(c) Exact-key responsibility routingprovider pdp_dcertified publishrequester issues qqbudgeted lookupunchanged DHTresponsibility routingsharedkey κ1 _1merge shortlist⁡(q)C(q)ordinary DHT routing reachesthe posting-list service Figure 1: SemDHT compiles semantics before the DHT. (a) Matching hard constraints ensure that the descriptor’s namespace label n⁡(d)n(d) belongs to the query’s allowed namespace-label set qN_q; nearby embeddings zq,zdz_q,z_d yield overlapping coarse-cell ID sets Zq,ZdZ_q,Z_d and similar residual codes. (b) These codes become exact keys: the publication-key set Kpub(d)K_pub(d) and budgeted probe-key set Kqry(q,Lq)K_qry(q;L_q) overlap on κ1,κ3 _1, _3. Publication uses at most ρ⁡(1+J)ρ(1+J) keys, where ρ is the number of selected coarse cells and J is the number of residual-code families (one recall publication key plus J precision publication keys per coarse cell); queries use at most LqL_q. (c) Publication and lookup for each shared key follow unchanged exact-key routing to the same responsible peer, whose posting-list service returns postings for local merge. The ring denotes ownership only, not Chord; evaluation uses Kademlia-style routing. Locality-sensitive hashing (LSH) supplies a direct construction: publish each descriptor under several LSH-derived keys and probe the query’s own and neighboring hash codes [13, 21, 41, 15, 19]. Coarse codes expose large candidate lists; finer codes can separate related descriptors and require more publication keys or probes to recover them. This couples retrieval quality to the amount of replicated index state and remote lookup work. Open publication adds an enforcement requirement: providers can increase exposure by placing descriptors at additional high-traffic keys. Storage services must therefore verify that each posting’s target key follows from its descriptor before accepting it. We present SemDHT, a certified semantic index that bounds publication fan-out and budgets network lookups for agent-accessible capability discovery over exact-key DHTs. Namespace labels encode interface and execution constraints; requesters use task semantics to distinguish capabilities within that compatibility scope. A two-layer semantic sketch maps descriptor and task embeddings to exact keys. Coarse cells organize nearby capabilities, and residual codes narrow candidate selection within each cell. Providers publish at a bounded set of keys derived from the sketch, while requesters probe precision keys before broader recall keys within a physical lookup budget. Overlapping publication and probe keys expose the provider’s posting to the requester, as illustrated in Figure 1. An anchor committee independently recomputes each descriptor’s publication-key set and issues a membership certificate binding the set to the descriptor. Storage services and requesters verify the certificate and Merkle inclusion proof. These checks make the per-descriptor publication bound enforceable at storage without requiring every replica to run the semantic encoder. Ordinary DHT routing locates responsible peers, whose posting-list services store multiple certified postings per key. Stable lineage handles and physical sharding extend the design to descriptor updates, revocation, and changing storage demand. On real API descriptors and task queries, SemDHT achieves recall@10=0.955recall@10=0.955 against exact embedding-space neighbors and 0.9470.947 against relevance labels from ToolBench, a benchmark for language-model tool use [28]. On a corpus with controlled density augmentation, it matches the candidate exposure of the best configurations in our LSH-on-DHT sweep at recall 0.950.95 with 7.7×7.7× fewer exact-key lookups and reduces publication fan-out from 16 to 10. We implement a Go/libp2p prototype and deploy two 200-peer overlays on cloud virtual machines (VMs), one within a region and one across eight regions. We replay 299 queries over the Internet, measuring routing, paged reads, verification, and candidate reconstruction. Both systems use the same posting format and replica policy. With parallel probes and cold certificate caches, SemDHT uses 130.91 application RPCs per query versus 777.85 for LSH, with similar message volume. Fewer RPCs yield mean completion-time speedups of 3.64×3.64× and 4.11×4.11× within and across regions. Separate simulations evaluate publication membership under attack, descriptor migration, and physical sharding. This paper makes three contributions: (1) a semantic key construction and probe schedule that connect retrieval quality to publication fan-out and a physical lookup budget, with a precision-key hit-probability analysis; (2) a certified publication protocol that makes descriptor-to-key consistency verifiable at storage and retrieval; and (3) a Go/libp2p implementation and an evaluation on cloud VMs over the Internet, showing how index selectivity, replicated reads, and verification affect network lookup work and completion time. 2 Problem and Overview Semantic keys, certified publication, and budgeted lookup Provider Clinic service assistant agent / API n⁡(d),xdn(d),x_d Semantic sketch coarse cells residual codes Kpub(d)K_pub(d) Anchor committee recompute Kpub(d)K_pub(d) issue d,Σd Cert_d, _d Service requester Personal assistant Eye-clinic query q,xq,LqN_q,x_q,L_q Query sketch allowed namespaces coarse cells residual codes Probe stages P1,P2,P3P_1,P_2,P_3 precision before recall Kqry(q,Lq)K_qry(q;L_q) Exact-key DHT route each key to responsible peers Posting-list service verify and store postings per key Verify and merge fetch descriptors rank shortlist ⁡(q)C(q) Two cells, two families: six publication keys Every lookup consumes the query’s budget LqL_q. d¯ d to committee; d,Σd Cert_d, _d to providerprovider publishes certified postingsbudgeted probe keys Figure 2: Publication and lookup share the semantic-key construction. Namespace labels select compatible providers; coarse cells and residual codes match tasks within that scope. The committee recomputes publication keys from the complete descriptor and certifies their membership. The provider publishes the certified postings. Exact-key DHT routing reaches posting-list services; the requester verifies returned postings and reconstructs candidates. The clinic advertises an appointment-query capability through an appointment assistant agent or a service API. The user’s personal assistant is the service requester; it discovers candidates under supported interface contracts and queries live slots afterward. SemDHT connects four participants: a service provider advertises a descriptor, an anchor committee certifies its publication keys, posting-list services store postings at responsible peers, and a service requester retrieves candidates. Figure 2 follows their publication and query paths. A service provider is the authenticated principal publishing a capability description. It exposes that capability through an agent endpoint or a service API callable by agents. In the appointment example, the clinic is the provider and the user’s personal assistant agent is the service requester. A requester may perform discovery through a client acting on its behalf. DHT peers supply routing and posting-list storage; they need not themselves execute the advertised capabilities. 2.1 Discovery and Lookup Budget A provider advertises a descriptor version d containing compatibility conditions, semantic text xdx_d, and a retrieval URI for the complete descriptor d¯ d. This URI locates the description; it is not, by definition, the service’s invocation endpoint. The namespace label n⁡(d)n(d) encodes the compatibility conditions to delimit the compatible search scope. A requester issues q=(q,xq,kq,Lq)q=(N_q,x_q,k_q,L_q), specifying allowed namespace labels qN_q, task text xqx_q, shortlist size kqk_q, and physical lookup budget LqL_q. In the appointment example, the clinic publishes a descriptor version d whose semantic text xdx_d describes eye-clinic appointment queries; its complete descriptor d¯ d records the interface contract and other compatibility conditions summarized by n⁡(d)n(d). Discovery has two parts. First, the assistant chooses qN_q from the namespaces supported by its client or adapters, such as one whose interface accepts a department and date and returns appointment records. A candidate must satisfy n⁡(d)∈qn(d) _q. Second, the assistant expresses “Find a service for querying eye-clinic appointments” in xqx_q; semantic matching compares this intent with xdx_d to find relevant services within that scope. After discovery, the assistant checks location and other task constraints, obtains any required authorization, and invokes a selected service with the requested date to learn whether appointments are available tomorrow. The indexed text xdx_d advertises the query capability; current slots come from the service. An eye clinic and a dental clinic can publish descriptors with the same namespace label n⁡(d)n(d) if they use the same interface contract, admission class, and execution-policy class; their respective texts xdx_d distinguish their specialties. Conversely, an eye clinic offering a different conversational interface requires support for that contract before it can be included through qN_q. Whether the provider exposes an agent or an API does not by itself determine namespace membership: the compatibility conditions do. Let D denote the descriptor population, the set of descriptor versions indexed by the system. The namespace-compatible population for query q is q=d∈:n⁡(d)∈q.D_q=\d :n(d) _q\. (1) SemDHT retrieves and ranks candidates from qD_q using semantic matching. To retrieve candidates, SemDHT maps the query to exact keys and accesses their posting lists through DHT lookups. A DHT routes an exact key to responsible peers in O⁡(log⁡Nnet)O( N_net) hops, where NnetN_net is the peer count [34, 23]. Those peers run a posting-list service because many descriptors can share a key. An entry point is a peer through which the requester initiates a DHT lookup. Each exact-key lookup consumes one unit of LqL_q. Looking up the same key through another entry point, or looking up a physical shard key, consumes an additional unit. Routing hops, replica RPCs, and page requests within a lookup do not consume additional units of LqL_q; we measure their communication and processing costs separately. Thus, LqL_q bounds the number of physical lookups, while kqk_q specifies the desired shortlist size. If the budgeted lookups yield fewer than kqk_q eligible candidates, the requester returns a shorter shortlist. 2.2 Publication and Query Workflow For the clinic service provider introduced above, publication begins by encoding its semantic text xdx_d into an embedding. The provider constructs a semantic sketch by selecting nearby coarse cells and computing residual codes within each cell. Suppose it selects two cells and uses two residual-code families. Following the key construction described in Section 3, it then derives a publication-key set Kpub(d)K_pub(d) containing six keys: one recall key and two precision keys per cell. The recall key groups descriptors assigned to that cell, while each precision key selects those sharing a residual code. The anchor committee independently derives Kpub(d)K_pub(d) from the complete descriptor d¯ d and issues a membership certificate d Cert_d binding the descriptor to this publication-key set. It authenticates d Cert_d with a committee signature Σd _d. At each key, the provider publishes a posting containing a provider-signed posting body, the membership certificate d Cert_d, the committee signature Σd _d, and a Merkle inclusion proof that the key belongs to the certified set. SemDHT uses ordinary DHT routing to locate the peers responsible for each key. Their posting-list services verify the posting before storing it. The user’s personal assistant, acting as the service requester, specifies the supported namespace labels qN_q and expresses its discovery task in xqx_q, such as “Find a service for querying eye-clinic appointments.” It encodes xqx_q and constructs a semantic sketch using the same configuration as the provider. If their sketches select a common cell and agree on a residual code, the requester derives a precision key at which the provider has published its posting. The requester orders its probes in three stages: exact precision keys in P1P_1, neighboring-code and additional-cell precision keys in P2P_2, and recall keys in P3P_3. The keys selected within the physical lookup budget LqL_q form the budgeted probe-key set Kqry(q,Lq)K_qry(q;L_q). It then verifies returned postings, merges them by descriptor commitment, fetches complete descriptors, and ranks eligible candidates to produce the candidate shortlist ⁡(q)C(q), following the verification and ranking procedure described in Section 4. 2.3 LSH-on-DHT Locality-sensitive hashing (LSH) maps similar vectors to the same hash code with higher probability than dissimilar vectors [13]. LSH-on-DHT uses these hash codes to construct exact keys: providers publish descriptors under keys derived from their embeddings, and requesters probe keys derived from query embeddings to retrieve candidates [41, 15, 19]. Longer hash codes improve selectivity; more independently seeded hash functions or neighboring-code probes recover recall at additional publication and lookup cost [21]. Our evaluation tunes these choices at matched recall, using the baseline key construction detailed in Appendix A.4. 3 Semantic Index SemDHT’s semantic index maps a descriptor to a bounded publication-key set and a query to an ordered probe sequence. Namespace labels define the compatibility scope; the semantic sketch determines which descriptors within that scope are likely to share the query’s keys. 3.1 Descriptors and Compatibility Let d¯ d be the complete descriptor for version d. It records the provider public key pd pk_p_d, a provider-local capability identifier, compatibility fields, semantic text xdx_d, metadata, and a retrieval address d ptr_d. With cryptographic hash H and deterministic canonicalization CanonCanon, its commitment is Cd=H⁡(Canon⁡(d¯)).C_d=H(Canon( d)). (2) The requester verifies a fetched descriptor against CdC_d. Whereas CdC_d identifies one descriptor version, a stable lineage handle ιd _d, derived from the provider key and capability identifier, identifies the same capability across versions. The anchor committee assigns a lineage epoch ede_d to each version to order versions within that lineage, enabling requesters to distinguish newer certified versions from older ones. Appendix A.1 gives the complete descriptor format for d¯ d. We collect the descriptor’s hard compatibility requirements in a namespace label, defined as n⁡(d)=(τd,σd,ψd),n(d)=( _d, _d, _d), (3) where τd _d is an admission class, σd _d identifies a compatible input/output contract, and ψd _d is an execution-policy class. For the appointment-query interface introduced in §2.1, an illustrative label uses τd=generic _d=generic, which adds no admission distinction, σd=appointment-query-v1 _d=appointment-query-v1 identifies the department/date request and appointment-record response contract, and ψd=web-enabled _d=web-enabled permits external network access. These values specify the compatibility scope; the eye-clinic specialization remains in xdx_d. The versioned namespace registry ℛνR_ν contains canonical labels whose fields use protocol identifiers; compatible schema variants share an interface contract, as specified in Appendix A.2. Fields enter the label when a mismatch prevents compatible execution or violates policy. Task specializations and preferences remain in xdx_d; adding a capability under an existing contract requires no new label. A resolver maps the query’s explicit hard requirements to q⊆ℛνN_q _ν, retaining the task wording in xqx_q. Providers, anchor committees, and requesters share a signed, content-addressed semantic-index configuration, identified by the semantic-index configuration ID ν. The configuration specifies the namespace registry, canonical label encoding and compatibility map, tokenizer and encoder weights, canonical input and numeric-normalization rules, codebook centroids, and residual-code projection seeds. A deterministic reference implementation or canonical quantization rule ensures that identical inputs yield identical labels, cell IDs, and residual codes across participants. Queries and descriptors are encoded separately. 3.2 Coarse Cells and Residual Codes To support semantic matching within the compatibility scope defined by namespace labels, the provider converts xdx_d into a semantic sketch. The sketch comprises coarse-cell IDs that group nearby embeddings and residual codes that distinguish descriptors within each cell. The encoder produces zd=Encν(xd)z_d=Enc_ν(x_d), which the two layers discretize: • Coarse-cell layer: The shared codebook is Uν=μcc=1McodeU_ν=\ _c\_c=1^M_code, where McodeM_code is the number of centroid vectors and μc _c is the centroid of coarse cell c. Sorting the cell IDs c by cosine distance from zdz_d to μc _c gives the descriptor’s coarse-cell ranking. We write Zd=Topρ(zd,Uν)Z_d=Top_ρ(z_d;U_ν) for the set of the top-ρ cell IDs, where ρ is the descriptor’s coarse-cell depth. Retaining more than one cell (ρ=2ρ=2 or 33 in practice) covers descriptors near a cell boundary. For each selected cell ID c∈Zdc∈ Z_d, the residual vector rd,c=zd−μcr_d,c=z_d- _c represents the descriptor’s position relative to centroid μc _c. • Residual-code layer: Each of J independently seeded residual-code families maps rd,cr_d,c to an ℓ -bit residual code bd,c(j)=Codeν(j)(rd,c)b_d,c^(j)=Code_ν^(j)(r_d,c), j=1,…,Jj=1,…,J. Our concrete instantiation uses sign projection: family j contains projection vectors aj,ra_j,r, r=1,…,ℓr=1,…, , and packs the signs of ⟨aj,r,rd,c⟩ a_j,r,r_d,c into bd,c(j)b_d,c^(j). Figure 3 illustrates how the coarse-cell and residual-code layers produce publication keys for a descriptor and probe keys for a query. In the figure’s concrete example, Zd=17,42Z_d=\17,42\, so the coarse layer retains cell IDs 17 and 42 for descriptor d. In the zoomed view of cell 17, the residual rd,17=zd−μ17r_d,17=z_d- _17 has sign pattern 0000 under residual-code family j=1j=1, giving bd,17(1)=00b_d,17^(1)=00. A query that also selects cell 17 and obtains code 0000 under this family later derives the corresponding probe key that matches d’s publication key. μ9 _9μ42 _42μ17 _17zdz_dZd=Topρ(zd,Uν)=17,42Z_d=Top_ρ(z_d;U_ν)=\17,42\, ρ=2ρ=2cell 17 (local, zoomed)b=00b=00b=01b=01b=11b=11b=10b=10μ17 _17rd,17r_d,17bd,17(1)=b_d,17^(1)= 00 Figure 3: Left: zdz_d selects top-ρ=2ρ=2 coarse-cell IDs Zd=17,42Z_d=\17,42\ (blue/orange), while a farther centroid μ9 _9 (gray) is not selected. Right: inside cell 17, the residual rd,17=zd−μ17r_d,17=z_d- _17 is discretized by a sign-projection residual-code family into a residual code; each residual-code family uses independent projection vectors, giving residuals separated by one projection boundary additional opportunities to match. Coarse-cell overlap provides coverage, while residual-code agreement provides discrimination within a shared cell. Multiple residual-code families mitigate projection-boundary effects: residual vectors separated by one family’s boundary can receive the same code under another family. Increasing ρ or J adds opportunities for shared keys and increases publication fan-out; coverage depends on the budget. Appendix B derives the precision-key hit-probability model; Section 6.2 tests its residual-code component. 3.3 Exact Keys and Bounded Publication For each c∈Zdc∈ Z_d, the provider derives one recall key and one precision key per residual-code family. For namespace label n, cell c, family j, and residual code b, the constructors are κνR(n,c)=H(“R”∥ν∥n∥c), _ν^R(n,c)=H(``R′\|ν\|n\|c), (4) κν,jP(n,c,b)=H(“P”∥ν∥n∥c∥b∥j). _ν,j^P(n,c,b)=H(``P′\|ν\|n\|c\|b\|j). (5) The tags distinguish recall and precision keys; j separates residual codes from different families. Including n enforces exact compatibility boundaries. The provider substitutes n⁡(d)n(d) and bd,c(j)b_d,c^(j) to obtain Kpub(d)=⋃c∈Zd(κνR(n⁡(d),c)∪κν,jP(n⁡(d),c,bd,c(j))j=1J).K_pub(d)= _c∈ Z_d (\ _ν^R(n(d),c)\∪\ _ν,j^P(n(d),c,b_d,c^(j))\_j=1^J ). (6) Each selected cell contributes at most 1+J1+J keys, yielding |Kpub(d)|≤ρ⁡(1+J).|K_pub(d)|≤ρ(1+J). (7) This bound is independent of corpus size. Certification binds the descriptor to this set before publication; see Section 4.2. 3.4 Budgeted Probe Sequence The requester computes zq=Encν(xq)z_q=Enc_ν(x_q) and a ranked cell sequence ZqordZ_q^ord; its first ρq _q IDs form the primary-cell set ZqZ_q. For each cell, it computes residual codes using the provider’s construction and substitutes n∈qn _q into the key constructors. Probes follow three stages. P1(q)P_1(q) contains exact precision keys for primary cells. P2(q)P_2(q) probes codes at Hamming distances one through rHr_H from the query’s residual codes in ZqZ_q, then exact precision keys for secondary cells ranked ρq+1 _q+1 through ρext _ext. Here rH=0r_H=0 disables neighboring-code probes, and ρext _ext bounds the considered cell ranks. P3(q)P_3(q) contains recall keys for ZqZ_q in cell-rank order. Within each stage, the requester interleaves allowed namespace labels. The logical sequence is ⁡(q)=Dedup⁡(P1(q)‖P2(q)‖P3(q)),P(q)=Dedup (P_1(q)\|P_2(q)\|P_3(q) ), (8) where ∥\| concatenates sequences and Dedup retains each key’s first occurrence. Appendix A.3 gives the deterministic ordering rules. With one entry point, unsharded keys, and no lineage-resolution lookups, each probe costs one lookup, giving the budgeted key set Kqry(q,Lq)=set⁡(PrefLq(⁡(q))),K_qry(q;L_q)=set(Pref_L_q(P(q))), (9) where PrefLPref_L takes a sequence’s first L elements. Shared publication and probe keys expose candidate postings. The order uses selective residual matches before broader recall lists; a smaller LqL_q stops the sequence earlier. Lineage resolution, repeated entry-point probes, and manifest or shard lookups draw from the same remaining budget, leaving fewer lookups for subsequent probes, as detailed in Section 4. 4 Certified Publication and Lookup Certification makes the publication bound enforceable at storage: the committee derives the allowed keys, and posting-list services verify each posting’s membership. Requesters apply the same checks to returned records before admitting candidates. 4.1 Threats and Certification Assumptions An adversary may control providers, routing peers, and up to fAf_A members of an anchor committee. We consider publication at unauthorized keys, posting-list stuffing, suppression of valid postings, and replay of stale versions. Certification establishes consistency between a committed descriptor and its publication keys; capability truthfulness and execution behavior are outside discovery. For example, a membership certificate for the clinic’s appointment service does not establish clinical credentials, slot availability, or the personal assistant’s permission to invoke that service. Namespace matching checks declared compatibility; it does not attest runtime policy enforcement. The deployment authenticates public keys and configuration ν and assigns each lineage to an nAn_A-member committee with signing threshold tAt_A. With unforgeable signatures and collision-resistant hashes, fA<tAf_A<t_A ensures that a valid committee signature includes an honest member that recomputes the publication keys. Availability also requires nA−fA≥tAn_A-f_A≥ t_A and progress of the signing service. The committee serializes registrations, renewals, updates, and revocations, rejects incompatible states at one epoch, and preserves lineage history across committee changes. This state-serialization service is an additional deployment assumption. Admission and committee-selection policies constrain creation of provider identities and grinding for favorable committees; quotas apply to admitted providers. 4.2 Certified Publication The provider submits the complete descriptor and a signed registration request to the committee assigned to lineage ιd _d. The stable anchor key κA(ιd)=H(“A”∥ιd) _A( _d)=H(``A′\| _d) locates that lineage’s certified state. The committee verifies the provider signature, descriptor commitment, and requested lineage transition. It recomputes the namespace, embedding, and publication-key set under ν, then commits to the sorted keys with a Merkle tree [24]: d=MerkleRoot⁡(sorted⁡(Kpub(d))). root_d=MerkleRoot(sorted(K_pub(d))). (10) The membership certificate d Cert_d binds this root to CdC_d, the provider key, namespace, configuration, lineage, epoch, predecessor, live or tombstone state, and lease. The committee signs it as Σd _d. For each target key κ, the provider constructs a posting body md,κm_d,κ that binds κ, descriptor commitment CdC_d, retrieval address, lease, and certificate hash. The body includes the provider’s signature. It publishes Posting⁡(d,κ)=⟨md,κ,d,Σd,πd,κ⟩,Posting(d,κ)= m_d,κ, Cert_d, _d, _d,κ , (11) where πd,κ _d,κ proves the key’s inclusion under d root_d. The signed certificate supplies the provider key, so verification does not require fetching the complete descriptor. Appendix A.5 specifies the record fields. 4.3 Posting and Candidate Verification A posting-list service checks that the received key matches the posting body and that the body’s commitment, provider key, namespace, lineage, epoch, lease, and certificate hash agree with d Cert_d. It verifies the provider signature, the assigned committee’s signature and threshold, the supported configuration, and the Merkle proof. These checks restrict an accepted posting to Kpub(d)K_pub(d). Keeping one active posting per (Cd,κ)(C_d,κ) prevents repeated publication from enlarging the list; together with Equation (7), it enforces the logical fan-out bound. Optional admission-layer quotas bound active states per provider and namespace, as specified in Appendix A.6. Both the service and requester authenticate an incoming certificate before adding it to observed lineage state. They select the highest observed epoch, then require a consistent live state and an unexpired lease. Epoch and revocation evidence survives expiry; an expired highest epoch does not restore an older version. Missing predecessor links or conflicting states trigger resolution at the stable anchor key, using the requester’s remaining lookup budget. Probing and resolution stop when LqL_q is exhausted; unresolved lineages supply no candidates. The requester verifies returned postings using its own time and observations. It merges accepted postings by CdC_d, fetches each complete descriptor once, and checks its commitment, provider key, namespace, and lineage against the certificate. After checking n⁡(d)∈qn(d) _q and resolving versions, it computes zd=Encν(xd)z_d=Enc_ν(x_d) from the verified descriptor and ranks by the base score: sbase(d∣q)=sim⁡(zq,zd).s_base(d q)=sim(z_q,z_d). (12) Here simsim denotes cosine similarity, and ⁡(q)C(q) contains up to kqk_q highest-scoring eligible candidates. Certificate consistency and freshness determine eligibility before ranking. A rejected posting alone does not attribute misconduct to its provider: a peer can alter proofs or replay old postings. 4.4 Maintenance and Additional Lookup Paths Renewal extends the lease of a certified live state at the same epoch; an update advances the epoch, and a tombstone terminates the lineage. An update can also change the publication-key set, so requesters probing old keys need a way to discover the successor. During a bounded migration window, the provider publishes the successor at its new keys and leaves Move hints at the old keys. Each hint carries the successor’s membership certificate and committee signature. The requester verifies the hint and resolves the lineage through the stable anchor key before applying the candidate checks in Section 4.3. Read-repair propagates verified lineage state to posting-list services that return older versions. The requester sends the newer membership certificate, committee signature, and necessary predecessor evidence; the recipient verifies the signatures and lineage transitions before updating its state. Requester DHT lookups for migration and repair consume the remaining LqL_q; direct repair messages and recipient background fetches are accounted for as maintenance traffic. Appendix C specifies the transitions and verification rules. Physical sharding redistributes a posting list while preserving its logical key and membership checks; manifest and shard lookups consume LqL_q, as detailed in Appendix D. A requester can also repeat selected keys across entry points to obtain observations through different paths. Each repetition consumes budget, trading probe depth for additional observations. Appendix A.7 defines the multi-view schedule and optional coverage-based ranking. 5 Implementation We implement SemDHT’s storage and lookup paths in Go. The prototype combines a DHT overlay with a replicated posting-list service. Providers publish certified postings to responsible peers; requesters locate those peers, retrieve and verify postings, and merge the results. 5.1 DHT Routing and Posting-List Service The prototype uses Go 1.25.7 with libp2p v0.49.0 for peer connections [3] and go-libp2p-kad-dht v0.42.1 for exact-key routing [23]. Many providers can publish at one key, so the posting-list service supplies multi-record storage beyond libp2p’s single-value API. Replicas acknowledge postings after verification, journaling, and indexing by logical key and descriptor commitment. 5.2 Certified Records and Verification The wire format uses canonical CBOR [7]. Providers sign posting bodies with Ed25519 [17]; committee signatures use CIRCL’s BLS12-381 implementation [6, 5]. Each member signs a message derived from the common certificate digest and its member index; a bitmap identifies the signers. A shared verifier retrieves their public keys and threshold from the committee registry. At storage admission and requester retrieval, it checks the target key, consistency with the membership certificate, provider-key binding, lease, both signatures, and Merkle inclusion proof. 5.3 Paging, Replica Reads, and Certificate Caching Paging bounds each response’s size. Replicas return postings in commitment order with a continuation cursor, a generation counter for list changes, and a total record count. The requester checks ordering, cursor progress, duplicate commitments, generation consistency, and the final count before accepting the replica’s response. It reads replicas concurrently, waits for every attempt to finish, requires the read quorum, and merges valid postings by descriptor commitment. This completion policy lets a slow replica delay the lookup even after a quorum responds. A bounded FIFO cache reuses committee-signature verification across keys. Its key hashes the complete encoded membership certificate and committee signature, including the signer bitmap and aggregate signature. Hits skip committee-signature verification but retain all posting-specific checks, including the current lease check. Invalid certificates are never cached; changing the signature changes the cache key. 5.4 Execution and Validation Scope Before network execution, we freeze embeddings, publication keys, probe sequences, and expected candidate commitments, then materialize and publish certified postings. The driver replays these fixed plans on the running overlay, timing routing, paged reads, verification, and candidate reconstruction. Encoding, committee issuance, complete-descriptor retrieval, and capability execution remain outside this interval. The prototype exercises the common index and posting-verification path using API-derived descriptors. It does not implement an appointment application or adapters for conversational agent endpoints and arbitrary service APIs. The store retains observed lineage state to reject local rollback; distributed renewal, migration, and shard-layout mechanisms are evaluated separately, as detailed in Appendices C and D. 6 Evaluation We first evaluate retrieval effectiveness and index efficiency, measuring recall, candidate exposure, publication fan-out, and lookup work in Section 6.2. We then test whether lookup savings translate into lower completion time over the Internet, and examine scheduling, verification, and resource costs in Section 6.3. Finally, Section 6.4 validates candidate reconstruction and protocol behavior under faults, unauthorized publication, and descriptor updates. Section 8.1 discusses the evaluation’s scope and deployment limitations. 6.1 Experimental Setup The source corpus is ToolBench/RapidAPI metadata [28]: 39,529 API descriptors after filtering near-empty descriptions, spanning 1,433 namespaces identified by n⁡(d)=(τd,σd,ψd)n(d)=( _d, _d, _d). Query traffic comprises 8,087 ToolBench retrieval queries. Its relevance judgments were generated by an LLM that reconstructed task intents from known relevant APIs. These API descriptions exercise the common capability index and its network lookup path. The evaluation does not measure conversational interaction with agent endpoints or downstream service execution. The appointment scenario is an illustrative use case, not a deployed application in this workload. We encode descriptor and query text with the 384-dimensional all-MiniLM-L6-v2 checkpoint [30], using Sentence Transformers 5.6.1, normalized float32 vectors, and the same canonical input template for descriptor and query encoding. The coarse layer uses Mcode=16M_code=16 centroids trained for 25 k-means iterations. Each of three reported seeds regenerates the codebook and residual-code families and is carried in the versioned semantic-index configuration, so providers and requesters use the same authenticated semantic-index configuration. Because roughly a third of query-reachable namespaces are too sparse to expose selectivity, the larger stress corpus adds 41,295 query-conditioned, semantically adjacent LLM variants, capped at 20 per real seed. Hard-constraint fields are copied from the source descriptor and every generated descriptor retains provenance. This controlled density augmentation yields 80,824 descriptors. Section 6.2 first reports the real-only corpus, while the parameter, baseline, and robustness sweeps use the combined stress corpus unless noted. Namespace-scoped exact cosine top-k over the same encoder is our index-fidelity oracle; ToolBench relevance labels provide a non-circular but noisier measurement. 6.2 Retrieval Effectiveness and Index Efficiency On the real-only corpus, before density augmentation, one calibrated configuration reaches recall@10=0.955recall@10=0.955 against exact cosine neighbors at physical lookup budget Lq=32L_q=32, and 0.9470.947 against ToolBench’s dataset labels. The two measurements assess agreement with the encoder’s nearest neighbors and with the dataset’s relevance labels. The reported configurations tie query and publication coarse depth, ρq=ρ _q=ρ, and list their shared value as ρ. We obtain a sharper view than a single recall number by sweeping (ρ,J,rH)∈1,2,3,4×1,2,3,4×0,1,2(ρ,J,r_H)∈\1,2,3,4\×\1,2,3,4\×\0,1,2\ (48 configurations, with ℓ and ρext _ext derived from ρ rather than swept independently, since an uncalibrated ℓ simply produces degenerate key populations rather than new information) on the combined corpus. We report three selectivity-first operating points in Table 1. recall target (ρ,J,ℓ,rH,Lq)(ρ,J, ,r_H,L_q) recall exposure fan-out 0.90 (3,4,3,1,32)(3,4,3,1,32) 0.902 62.6% 15 0.95 (2,3,3,1,128)(2,3,3,1,128) 0.950 72.8% 8 0.97 (3,2,3,2,64)(3,2,3,2,64) 0.970 80.1% 9 Table 1: Selectivity-first operating points from the full parameter sweep. “exposure” is the fraction of the query’s reachable candidate population actually exposed at that budget—lower is more selective at the same recall. Figure 4: Recall versus exposure for 432 budgeted operating points from 48 (ρ,J,rH)(ρ,J,r_H) configurations on the combined corpus. Blue points are the 276 operating points retained by the four-objective Pareto filter; the curve traces the two-dimensional recall–exposure frontier. The three marked operating points correspond to Table 1. We apply the four-objective Pareto filter to all 432 operating points; Figure 4 presents the full and retained sets. The operating points expose the interaction between sketch depth and the query budget. Increasing ρ, J, or rHr_H at fixed LqL_q lengthens the precision-probe prefix and can delay the coarse-recall fallback enough to reduce recall. The Pareto filter therefore retains tradeoffs among recall, exposure, lookup count, and publication fan-out. At recall at least 0.900.90, the smallest observed exposure is 62.6%62.6\% of the reachable population. Raising recall to the sweep’s maximum of 0.99760.9976 requires 95.0%95.0\% exposure. Two additional codebook seeds preserve the ordering of the three representative points: their recall ranges are 0.9020.902–0.9190.919, 0.9500.950–0.9600.960, and 0.9700.970–0.9780.978, respectively. Exposure varies by 3–5 percentage points across seeds. Appendix E.3 reports the query-bootstrap intervals and the baseline selection details. Publication and lookup cost. We compare SemDHT with LSH-on-DHT over the same namespaces and corpus, selecting configurations at matched recall. The LSH sweep combines signature widths wLSH∈4,6,8w_LSH∈\4,6,8\, table counts T∈1,2,4,8,16T∈\1,2,4,8,16\, and Hamming radii rH∈0,1,2r_H∈\0,1,2\: 45 configurations at nine budgets, yielding 405 operating points. For each system, we linearly interpolate each configuration’s budget curve to the target recall and select the configuration with the smallest exposure. Centralized HNSW [22] and exact FlatIP provide local retrieval references. We sweep HNSW graph degree MHNSW∈8,16,32M_HNSW∈\8,16,32\ and search breadth efSearch∈8,…,256efSearch∈\8,…,256\. We also evaluate exact-key hashing of capability names and an inverted BM25 index [32] within the same namespaces. At recall 0.900.90, SemDHT and LSH expose 62.1%62.1\% and 61.6%61.6\% of the reachable candidate population, while issuing 33.7 and 173.2 exact-key lookups on average. At recall 0.950.95, both expose 72.7%72.7\%, with 32.9 versus 253.5 lookups. The corresponding lookup reductions are 5.1×5.1× and 7.7×7.7×; publication fan-out at recall 0.950.95 is ten versus sixteen. Thus, the key construction reaches comparable candidate populations through fewer posting-list accesses. Appendix E.3 gives the complete matched-recall table and explains why its interpolated fan-out-ten point differs from the directly selected fan-out-eight point in Table 1. Figure 5 shows how this lookup advantage varies across the four recall targets. The gap narrows at 0.970.97, where the selected LSH signature width and probe radius change. Figure 5: Mean exact-key DHT lookups issued to reach a given recall target, SemDHT versus the best-tuned LSH-on-DHT configuration at that target, using the data presented in Table 10. SemDHT is cheaper at all four targets; the gap is largest at recall 0.950.95 and narrows at 0.970.97 because the matched LSH optimum switches from the hash-width/radius pair (wLSH,rH)=(8,2)(w_LSH,r_H)=(8,2) to (6,1)(6,1). HNSW reaches recall 0.9850.985 at MHNSW=16M_HNSW=16 and efSearch=16efSearch=16, while exact FlatIP reaches 1.01.0. Their reported times measure local batch CPU work. With verbatim API-name matching, exact-key hashing reaches recall 0.0650.065. BM25’s top-10 ranking reaches about 0.3980.398 recall with mean publication fan-out 26.226.2 (p95=39p95=39); its candidate population contains enough relevant items for oracle recall 0.9530.953. This difference separates candidate coverage from ranking quality. Two LSH seeds give recall 0.940.94–0.960.96 and preserve the lookup-cost ordering at the tested targets. Residual-code hit model. Multiple residual-code families give a query–descriptor pair additional opportunities for a precision-key hit, as described in Section 3.2. We test how well the angle-based prediction and approximate-independence assumption in Appendix B.1 describe measured residual-code hits. We use query–descriptor residual pairs from the combined corpus across three codebook seeds: 80,85880,858 namespace-correct nearest pairs and 80,83080,830 random reachable negative pairs. Figure 6 compares measured and predicted single-family hit probabilities. For the residual-code component with J=4J=4, the observation-weighted mean absolute error is 0.00220.0022. The maximum normalized conditional covariance between residual-code families is 0.01310.0131, below the prespecified 0.050.05 threshold for approximate independence. Figure 6: Measured single-family hit probability versus residual angle θ at a representative calibrated configuration (ρ=2,ℓ=3,rH=1ρ=2, =3,r_H=1), against the closed-form pℓ,rH(θ)p_ ,r_H(θ) prediction from Appendix B.1. Marker area is proportional to the number of real observations in that bin; error bars are 95% confidence intervals. The fit is close across the well-populated 30∘30 –100∘100 range and only visibly departs in the sparsely observed tails. At a different configuration (ρ=4,ℓ=4,rH=1,J=4ρ=4, =4,r_H=1,J=4), the sparse 100∘100 –110∘110 residual-angle bin shows a measured hit rate of 0.5810.581 against a predicted 0.6270.627, an error of −0.0461-0.0461. This bin covers 0.363%0.363\% of that configuration’s observations. The aggregate error and conditional covariance support the residual-code component of the precision-key hit-probability model over the bulk of the observed distribution, with a narrow tail deviation consistent with anisotropy in the embeddings. 6.3 Network Performance and System Overhead Deployment and workload. We evaluate whether fewer logical key accesses translate into lower lookup completion time over the Internet. We deploy two 200-peer overlays on Alibaba Cloud with the placements and machine specifications in Table 2. The requester runs on a dedicated VM and replays queries sequentially against both deployments. A separate 4-vCPU, 8-GB controller VM in Frankfurt manages deployment and artifact collection. Each overlay uses three replicas, write and read quorums of two, pages of at most 64 postings, and at most 32 concurrent logical lookups. Lookup and RPC timeouts are 60 s. Replica reads use the wait-all completion policy described in Section 5. Both SemDHT and LSH use the same certified posting format, replica policy, and posting-list service. Deployment Region VMs Peers/VM vCPU RAM Same-region Frankfurt 8 25 4 8 GB Cross-region Eight regions 8 25 4 8 GB Requester Frankfurt 1 – 8 16 GB Table 2: Network-replay deployment. Each overlay has eight virtual machines (VMs), each hosting 25 peer processes. The cross-region deployment places one VM in each of Frankfurt, Tokyo, Singapore, Hong Kong, Virginia, Silicon Valley, São Paulo, and Dubai. Peers/VM counts overlay service processes; hardware specifications are per VM. All machines use Intel Xeon Platinum CPUs and 64-bit Ubuntu 24.04, with 10 Mb/s of configured bandwidth per machine. The replay uses posting lists and probe sequences materialized from the frozen 500-query workload. Setup publishes the postings and reads back the planned keys, including empty keys, to verify their contents before timing. The executable operating points use probe-key budgets of 64 for SemDHT and 256 for LSH. Their candidate-exposure recall on the 8,087-query source workload is 0.95198 and 0.95185, respectively; these configurations are fixed before network execution. The replay measures system cost and checks candidates against each plan’s expected commitments. We report 299 complete queries from this frozen workload. Each query runs under all 16 combinations of system, region placement, parallel or stage-barrier scheduling, and cold or warm certificate cache. Query order is seeded, and a balanced Latin square interleaves the conditions. Scheduling and measurement. For each query and system, both schedulers execute every key in the same budgeted probe sequence. The parallel scheduler lets keys from all stages compete for the 32 lookup slots. The stage-barrier scheduler permits concurrency within a stage but admits the next stage only after every lookup in the current stage finishes. The query budget determines the key set before execution; retrieved candidates do not trigger early stopping. We time the lookup path described in Section 5, using one batch for parallel scheduling and summing stage-batch times for stage-barrier scheduling. Cache prewarming precedes this interval. We preserve the frozen sample weights and resample whole queries, retaining all 16 conditions together, for 2,000 bootstrap repetitions. We report weighted means and P95 with 95% intervals. Appendix E.1 details the conditions, sampling, and late-run CPU instrumentation. Figure 7: Measured lookup completion with parallel scheduling and a cold certificate cache. Bars show the weighted mean and P95; error bars are 95% query-cluster bootstrap intervals. Sample: 299 complete queries. Completion time and lookup work. Figure 7 presents completion times with parallel scheduling and a cold certificate cache. SemDHT completes in 3.819 s on average within a region and 7.038 s across regions, compared with 13.897 s and 28.938 s for LSH. These correspond to 3.64×3.64× and 4.11×4.11× lower mean completion times. P95 is 10.289 s versus 19.721 s within a region, and 14.178 s versus 33.318 s across regions. The paired mean reductions have 95% intervals of [9.839, 10.294] s and [21.438, 22.313] s, respectively. Placement System Lookups RPCs MiB Same SemDHT 32.59 130.91 2.913 Same LSH 256.00 777.85 2.945 Cross SemDHT 32.59 130.91 2.913 Cross LSH 256.00 777.85 2.945 Table 3: Weighted mean work per query, parallel scheduling and cold certificate cache. Lookups count logical keys; RPCs include replica reads and pagination; MiB counts requester application-message frames. Table 3 reports per-query work. The probe-key budgets are upper bounds; SemDHT issues 32.59 logical lookups on average, versus 256 for LSH, a reduction of 87.3%. Replica reads and pagination produce 130.91 and 777.85 application RPCs, respectively, while message volume remains close at 2.913 versus 2.945 MiB. The systems transfer comparable posting volumes, while SemDHT accesses fewer keys. Each key requires routing and replica reads, so fewer keys reduce the remote operations that must complete under the same concurrency limit. Bytes count requester application frames, excluding connection setup, other DHT routing traffic, transport retransmissions, and IP/TCP headers. Placement System Cache Mean difference [95% CI] (s) P95 difference [95% CI] (s) Same SemDHT Cold 0.157 [0.075, 0.235] 1.118 [-0.948, 2.124] Same SemDHT Warm -0.091 [-0.139, -0.045] -0.127 [-0.246, 0.291] Same LSH Cold -0.067 [-0.175, 0.044] 0.014 [-0.618, 0.742] Same LSH Warm 0.000 [-0.118, 0.116] -0.064 [-0.521, 0.809] Cross SemDHT Cold 2.679 [2.540, 2.834] 4.133 [2.315, 5.101] Cross SemDHT Warm 2.259 [2.114, 2.409] 0.854 [-0.478, 3.830] Cross LSH Cold 3.224 [2.947, 3.517] 2.973 [1.794, 4.392] Cross LSH Warm 3.085 [2.833, 3.339] 2.835 [2.299, 4.018] Table 4: Scheduling contrasts over the same 299 query clusters: stage-barrier minus parallel completion time. Positive values indicate longer completion with barriers. P95 contrasts subtract the two weighted P95 estimates; they are not percentiles of per-query differences. Intervals retain query pairing and frozen sample weights. Scheduling and completion. Table 4 compares scheduling policies while holding each query’s keys fixed, for both placements and cache states. Stage barriers have a larger effect across regions: with cold caches, they increase mean completion time by 2.679 s for SemDHT and 3.224 s for LSH. Within-region changes are small; the cold-cache LSH interval includes zero. The cross-region mean increases persist after certificate prewarming, while within-region changes stay below 0.1 s in magnitude. Cold-cache P95 shows the same placement dependence: stage barriers increase cross-region P95 for both systems, while both within-region intervals include zero. With warm caches, the cross-region P95 interval remains positive for LSH but includes zero for SemDHT. Under the wait-all replica policy, a lookup remains active until its last replica attempt ends. A stage barrier extends this wait to later stages; parallel scheduling lets their keys occupy free slots while the slow lookup finishes. The benefit is larger across regions. Both policies preserve SemDHT’s lookup-count advantage. With cold caches and stage barriers, SemDHT achieves mean completion speedups over LSH of 3.48×3.48× within a region and 3.31×3.31× across regions. Across all 4,784 measured query-condition pairs, nine of 2,173,436 application RPCs report errors. Every logical lookup still meets its read quorum, and every reconstructed candidate set matches its expected set. All error-bearing observations remain in the analysis. Appendix E.1 gives the error breakdown and recording boundaries. Certification cost and cache behavior. We isolate the cost of posting validation with the protocol-v2 wire format and CIRCL’s portable BLS implementation on Windows/amd64. The fixture has 16 authorized keys and five signers from a seven-member committee. Each operation has ten independent benchmark repetitions; Table 5 reports their means and Student-t 95% intervals. Full validation takes 10.650 ms per posting. Reusing an already verified certificate reduces this to 48.7 μ , a 218.5×218.5× reduction for this validation operation. Appendix E.2 details the fixture’s 839-byte posting, including its provider signature, membership certificate, committee signature, and Merkle inclusion proof. Validation path Mean (ms) 95% CI (ms) Cold certificate 10.6496 [10.5570, 10.7422] Verified certificate cached 0.0487 [0.0471, 0.0504] Table 5: Per-posting validation with five of seven committee signers and a 16-key publication set. Cache hits retain posting-specific checks. The replay uses a separate 65,536-entry certificate cache for each overlay, cleared before each condition. A warm condition first preverifies the same query’s certificates; this prelude is recorded separately. For SemDHT with parallel scheduling, warm-cache mean completion is 3.009 s within a region and 6.836 s across regions, compared with cold-cache means of 3.819 s and 7.038 s. Warm requests have no certificate-cache misses. Their prelude itself averages 5.021 s and 5.026 s, respectively, so the warm results describe reuse after verification. The remaining lookup work makes the query speedup much smaller than the isolated validation speedup. Node CPU and memory use. We measure per-node resource use in a separate 400-node deployment, with 375 nodes, the controller, and the requester on a local server, and 25 nodes on one Hong Kong VM with the same 4-vCPU, 8-GB configuration as the network-replay data VMs. The cloud nodes run with GOMAXPROCS=1. We publish posting lists for 50 queries from the frozen workload and replay the same queries under all eight combinations of system, scheduler, and certificate cache state. Three rounds yield 24 complete batches and 1,200 query executions. Each batch has a 300-second baseline followed by the query phase. Every 10 seconds, we sample each cloud node’s cgroup CPU counter and process resident set size (RSS). CPU utilization divides consumed core-seconds by elapsed time; 100% denotes one fully occupied logical core. Table 6 reports time-weighted per-node means, averaged over the 25 nodes and then equally over the three rounds. The query phase includes certificate prewarming, waiting, and background DHT activity. CPU (%) RSS (MiB) Scheduler Cache SemDHT LSH SemDHT LSH Parallel Cold 0.326 0.394 52.17 52.85 Parallel Warm 0.291 0.440 52.16 53.00 Stage-barrier Cold 0.336 0.410 52.50 52.68 Stage-barrier Warm 0.294 0.431 51.68 52.89 Table 6: Observed per-node resource use during the query phase on the Hong Kong VM. Values average three rounds of 50 queries per condition. Appendix E.8 reports baseline values, round-to-round ranges, and query-validation results. Across these conditions, SemDHT averages 0.291–0.336% of one core per node, compared with 0.394–0.440% for LSH. RSS is similar: 51.68–52.50 MiB for SemDHT and 52.68–53.00 MiB for LSH. Baseline CPU means are similar, at 0.398–0.416%. 6.4 Robustness and Protocol Validation We validate candidate reconstruction and protocol behavior under faulty responses, unauthorized publication, and descriptor updates. Implementation checks exercise the prototype, while controlled simulations isolate publication membership and update behavior. The appendices add multi-view lookup and storage experiments. Implementation checks. Before network replay, a four-peer run with three replicas and read and write quorums of two reconstructs the expected candidate sets for all 500 queries under both systems. It publishes 398,196 postings and reads all 103,545 planned keys, including empty lists. Separate fault-injection checks cover missing or duplicate page contents, generation changes, slow replicas, insufficient quorums, tampering after cache prewarming, and cache eviction. Go and Python also agree on the protocol-v2 canonical encodings and certificate digests. The following experiments evaluate the design under controlled publication attacks and state changes. Publication membership. The 80,824-descriptor stress corpus contains 49,575 simulated providers, grouped by distinct source provider identifier. We sample malicious providers at fractions from 0%0\% to 50%50\% and have each publish to a hot logical key outside its certified publication-key set. With perfect routing and uncompromised certification, membership verification rejects every injected posting. At 20%20\% malicious providers, skipping membership verification produces 1.692×1.692× query-weighted exposure; verification retains the honest recall of 0.95000.9500. Figure 8 shows the full sweep: amplification reaches 2.73×2.73× without membership verification and remains 1.000×1.000× with it. Figure 8: Query-weighted candidate-acceptance amplification versus malicious-provider fraction under perfect routing and uncompromised certification. Membership verification keeps the measured ratio at 1.000×1.000× across the sweep. Provider quotas. At Qns=128Q_ns=128, admission-layer quota accounting retains 99.42%99.42\% of honest descriptors and reduces honest recall by 0.00230.0023. Under a fixed attack budget, stuffing amplification rises from 1.137×1.137× with one attacking provider per namespace to 2.081×2.081× with 16 attacking providers. The quota limits one admitted provider’s publication volume, while additional identities supply additional quota slots. Descriptor updates. Controlled simulations evaluate migration and read-repair. For 512 lineages with disjoint old and new publication-key sets, a Move window covering the query-switch interval preserves discoverability throughout the update. The model assumes successful Move resolution and excludes its additional DHT lookup cost. At replica turnover rate 0.100.10 per normalized time unit, read-repair lowers the p95 time for all eight replicas to hold the new epoch from 17.9617.96 to 8.958.95 units. Both arms include background anti-entropy; repair adds an average of 1,538 direct messages per 512-lineage run over three seeds. A separate replay check rejects older postings after a verified update or tombstone, before their leases expire. Appendices E.6 and E.7 give the setups, window and turnover sweeps, and maintenance costs. Multi-view lookup and storage. Appendix E.4 evaluates entry-path suppression. At capture probability f=0.20f=0.20, repeating the complete probe prefix through two entries raises attacked recall from 0.79570.7957 to 0.91910.9191 with twice the lookup cost. At fixed cost, the shorter repeated prefix reduces clean recall from 0.95000.9500 to 0.85530.8553. Appendix E.5 reports how sharding redistributes response work under query skew and how cache revalidation affects candidate acceptance. Physical-budget accounting, including repeated entry-point probes and shard lookups, is evaluated in Appendix D.4. 7 Related Work Agent-accessible services and capability discovery. A2A describes agent capabilities through Agent Cards, with discovery through known locations, catalogs, or configuration [1]. MCP defines tool descriptions and invocation [26], and its registry catalogs MCP servers [25]. ToolBench studies task-based API retrieval and tool use [28]. SemDHT studies the index and network costs of discovering advertised capabilities under supported interface contracts, whether a provider exposes an agent endpoint or a service API. Agent-network architectures develop capability announcements, topology-independent naming, and semantic communication [37, 33, 12, 39, 40]. Guo et al. combine semantic profiles, compact codes, and continual retrieval over a capability registry [14]. SemDHT connects task matching to exact-key responsibility and posting-list retrieval, with a budget for network lookups. Semantic retrieval over DHTs. pSearch organizes documents in a semantic overlay [35]; LSH-on-DHT systems map semantic or multidimensional neighborhoods to hash buckets [41, 15], and NearBucket-LSH uses nearby buckets to improve recall per message [19]. LSH and multi-probe search supply the underlying collision and probe mechanisms [13, 21]. Coarse quantization with residual encoding is established in centralized approximate retrieval [16]. SemDHT uses coarse cells and residual codes to construct separate recall and precision keys, then allocates a physical lookup budget across their ordered probes. Distributed retrieval and structured resource discovery. PlanetP combines a gossip-replicated compact index with distributed content search and ranking [9]. INS resolves attribute–value descriptions, SWORD evaluates multi-attribute resource constraints, and Mercury supports range queries with overlay load balancing [2, 27, 4]. SemDHT encodes hard compatibility conditions in namespace labels and matches task semantics within that scope. It retains Chord and Kademlia’s exact-key responsibility abstraction [34, 23]; posting-list services provide multi-descriptor storage at the responsible peers. Routing and storage defenses. Secure DHT work studies malicious routing peers [8], while the Sybil attack shows why unconstrained identities weaken open systems [11]. Whanau addresses Sybil-resilient DHT routing under a social-graph trust assumption [20]. These works protect routing and identity; SemDHT instead verifies whether a returned posting is authorized for its logical key. DHT implementations and measurements examine latency, throughput, replication, and Internet-scale routing behavior [10, 36]. OpenDHT provides expiring values and storage-allocation controls [31], while Beehive uses proactive replication for skewed lookup demand [29]. Load-balancing schemes redistribute key ranges or items across peers [18]. These mechanisms complement SemDHT’s certified publication, which verifies descriptor-to-key consistency. Physical sharding redistributes the resulting posting lists while preserving their logical keys and charging each shard lookup to the query budget. 8 Discussion and Conclusion 8.1 Limitations and Future Work SemDHT targets requests for which suitable providers must be identified beyond a requester’s preconfigured service set. Our experiments measure descriptor retrieval and the network execution of discovery. They do not establish how frequently such requests arise in deployed agent applications, or whether dynamically selected providers improve task outcomes after integration and authorization costs. The model admits both agent endpoints and service APIs, but the measured workload uses API descriptions. Interface adapters and application-level studies are needed to evaluate the broader setting. Exact-cosine recall measures fidelity to the chosen encoder. ToolBench provides LLM-generated relevance judgments, and the augmented corpus controls capability density; these results do not establish human semantic correctness or natural capability frequencies. Namespace policy labels follow deterministic rules and lack independent human validation. Two effects remain unmeasured: embedding similarity within versus across policy classes at fixed input/output contracts, and how increasing J changes the near–far pair hit-probability gap beyond the residual-code fit in Section 6.2. The namespace registry and resolver define a deployment’s compatibility contracts. An unresolved alias can exclude a relevant provider before semantic matching. Registry evolution and resolver coverage across independently governed deployments remain to be evaluated. Encoder and registry changes require coordinated configuration adoption and descriptor republication because ν is part of each semantic key. The prototype implements certified posting storage and the live lookup path measured in Section 6.3. Protocol simulations supply committee state serialization and controlled routing or entry-path observations; they do not evaluate distributed committee agreement, committee capture, or identity admission. The analytic routing backend in Appendix D.4 is checked against held-out Kademlia simulation runs. Committee state serialization, distributed descriptor updates, and authenticated shard-manifest synchronization remain to be integrated and evaluated for candidate availability under churn, with query and maintenance costs. Section 5 specifies the measured execution path, and Section 4.1 states the certification assumptions. 8.2 Conclusion We presented SemDHT, a certified semantic index for discovering agent-accessible capabilities from natural-language task intent in P2P networks. Providers may expose these capabilities through agent endpoints or service APIs. Its key construction and probe schedule bound per-descriptor publication and budget network lookups over exact-key DHTs, while membership certificates make descriptor-to-key consistency verifiable at storage and retrieval. On API descriptors, comparable recall and candidate exposure can be achieved with fewer publication keys and DHT lookups than tuned LSH. Our Go/libp2p prototype on cloud virtual machines shows that these lookup reductions translate into faster query completion on same-region and cross-region Internet deployments. Controlled protocol experiments validate publication enforcement and characterize availability and repair costs during descriptor updates. SemDHT thus connects semantic retrieval quality to enforceable publication rules and explicit network budgets within a decentralized discovery protocol. References [1] A2A Project. Agent2Agent Protocol Specification. https://a2a-protocol.org/v0.3.0/specification/. Version 0.3.0. Accessed September 20, 2026. [2] William Adjie-Winoto, Elliot Schwartz, Hari Balakrishnan, and Jeremy Lilley. The design and implementation of an intentional naming system. ACM SIGOPS Operating Systems Review, 34(5):186–201, 1999. [3] Juan Benet. IPFS—content addressed, versioned, P2P file system. arXiv preprint arXiv:1407.3561, 2014. [4] Ashwin R. Bharambe, Mukesh Agrawal, and Srinivasan Seshan. Mercury: Supporting scalable multi-attribute range queries. In Proceedings of ACM SIGCOMM, pages 353–366, 2004. [5] Dan Boneh, Craig Gentry, Ben Lynn, and Hovav Shacham. Aggregate and verifiably encrypted signatures from bilinear maps. In Advances in Cryptology—EUROCRYPT 2003, volume 2656 of Lecture Notes in Computer Science, pages 416–432. Springer, 2003. [6] Dan Boneh, Ben Lynn, and Hovav Shacham. Short signatures from the Weil pairing. Journal of Cryptology, 17(4):297–319, 2004. [7] Carsten Bormann and Paul Hoffman. Concise binary object representation (CBOR). RFC 8949, RFC Editor, 2020. [8] Miguel Castro, Peter Druschel, Ayalvadi Ganesh, Antony Rowstron, and Dan S. Wallach. Secure routing for structured peer-to-peer overlay networks. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI), pages 299–314. USENIX Association, 2002. [9] Francisco Matias Cuenca-Acuna, Christopher Peery, Richard P. Martin, and Thu D. Nguyen. PlanetP: Using gossiping to build content addressable peer-to-peer information sharing communities. In Proceedings of the IEEE International Symposium on High Performance Distributed Computing (HPDC), pages 236–249, 2003. [10] Frank Dabek, Jinyang Li, Emil Sit, James Robertson, M. Frans Kaashoek, and Robert Morris. Designing a DHT for low latency and high throughput. In Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI), pages 85–98. USENIX Association, 2004. [11] John R. Douceur. The Sybil attack. In Proceedings of the International Workshop on Peer-to-Peer Systems (IPTPS), volume 2429 of Lecture Notes in Computer Science, pages 251–260. Springer, 2002. [12] Charles Fleming, Vijoy Pandey, Ramana Kompella, and Luca Muscariello. A layered protocol architecture for the internet of agents. arXiv preprint arXiv:2511.19699, 2025. [13] Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Similarity search in high dimensions via hashing. In Proceedings of the International Conference on Very Large Data Bases (VLDB), pages 518–529, 1999. [14] Shaolong Guo, Yuntao Wang, Zhou Su, Yanghe Pan, Qinnan Hu, and Tom H. Luan. Agent discovery in internet of agents: Challenges and solutions. IEEE Network, pages 1–9, 2026. [15] Parisa Haghani, Sebastian Michel, and Karl Aberer. Distributed similarity search in high dimensions using locality sensitive hashing. In Proceedings of the International Conference on Extending Database Technology (EDBT), pages 744–755, 2009. [16] Hervé Jégou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(1):117–128, 2011. [17] Simon Josefsson and Ilari Liusvaara. Edwards-curve digital signature algorithm (EdDSA). RFC 8032, RFC Editor, 2017. [18] David R. Karger and Matthias Ruhl. Simple efficient load balancing algorithms for peer-to-peer systems. Theory of Computing Systems, 39(6):787–804, 2006. [19] Naama Kraus, David Carmel, Idit Keidar, and Meni Orenbach. NearBucket-LSH: Efficient similarity search in P2P networks. arXiv preprint arXiv:1511.07148, 2015. [20] Chris Lesniewski-Laas and M. Frans Kaashoek. Whanau: A sybil-proof distributed hash table. In Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI), pages 111–126. USENIX Association, 2010. [21] Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li. Multi-probe LSH: Efficient indexing for high-dimensional similarity search. In Proceedings of the International Conference on Very Large Data Bases (VLDB), pages 950–961, 2007. [22] Yu A. Malkov and D. A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4):824–836, 2020. [23] Petar Maymounkov and David Mazières. Kademlia: A peer-to-peer information system based on the XOR metric. In Proceedings of the International Workshop on Peer-to-Peer Systems (IPTPS), pages 53–65, 2002. [24] Ralph C. Merkle. A digital signature based on a conventional encryption function. In Advances in Cryptology—CRYPTO ’87, volume 293 of Lecture Notes in Computer Science, pages 369–378. Springer, 1988. [25] Model Context Protocol. MCP Registry. https://github.com/modelcontextprotocol/registry. Accessed September 20, 2026. [26] Model Context Protocol. Tools. https://modelcontextprotocol.io/specification/2025-06-18/server/tools. Specification dated June 18, 2025. Accessed September 20, 2026. [27] David Oppenheimer, Jeannie Albrecht, David Patterson, and Amin Vahdat. Distributed resource discovery on PlanetLab with SWORD. In Workshop on Real, Large Distributed Systems (WORLDS). USENIX Association, 2004. [28] Yujia Qin, Shihao Liang, Yining Ye, Kunlun Zhu, Lan Yan, Yaxi Lu, Yankai Lin, Xin Cong, Xiangru Tang, Bill Qian, Sihan Zhao, Lauren Hong, Runchu Tian, Ruobing Xie, Jie Zhou, Mark Gerstein, Dahai Li, Zhiyuan Liu, and Maosong Sun. ToolLLM: Facilitating large language models to master 16000+ real-world APIs. In The Twelfth International Conference on Learning Representations, 2024. [29] Venugopalan Ramasubramanian and Emin Gün Sirer. Beehive: O(1) lookup performance for power-law query distributions in peer-to-peer overlays. In Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI). USENIX Association, 2004. [30] Nils Reimers and Iryna Gurevych. Sentence-BERT: Sentence embeddings using siamese BERT-networks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, pages 3982–3992, 2019. [31] Sean Rhea, Brighten Godfrey, Brad Karp, John Kubiatowicz, Sylvia Ratnasamy, Scott Shenker, Ion Stoica, and Harlan Yu. OpenDHT: A public DHT service and its uses. ACM SIGCOMM Computer Communication Review, 35(4):73–84, 2005. [32] Stephen Robertson and Hugo Zaragoza. The probabilistic relevance framework: BM25 and beyond. Foundations and Trends in Information Retrieval, 3(4):333–389, 2009. [33] Roland R. Rodriguez. Agent identity URI scheme: Topology-independent naming and capability-based discovery for multi-agent systems. arXiv preprint arXiv:2601.14567, 2026. [34] Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, and Hari Balakrishnan. Chord: A scalable peer-to-peer lookup protocol for internet applications. IEEE/ACM Transactions on Networking, 11(1):17–32, 2003. [35] Chunqiang Tang, Zhichen Xu, and Sandhya Dwarkadas. Peer-to-peer information retrieval using self-organizing semantic overlay networks. In Proceedings of ACM SIGCOMM, pages 175–186, 2003. [36] Liang Wang and Jussi Kangasharju. Measuring large-scale distributed systems: Case of BitTorrent Mainline DHT. In Proceedings of the IEEE International Conference on Peer-to-Peer Computing (P2P), pages 1–10, 2013. [37] Taotao Wang, Lizhao You, Jingwen Tong, Chonghe Zhao, and Shengli Zhang. Agentic peer-to-peer networks: From content distribution to capability and action sharing. IEEE Communications Magazine, 2026. To appear. [38] Yuntao Wang, Shaolong Guo, Yanghe Pan, Zhou Su, Fahao Chen, Tom H. Luan, Peng Li, Jiawen Kang, and Dusit Niyato. Internet of agents: Fundamentals, applications, and challenges. IEEE Transactions on Cognitive Communications and Networking, 2025. [39] Wenxin Xu, Taotao Wang, Yihan Xia, Shengli Zhang, and Soung Chang Liew. Agent-OSI: An interoperability architecture for communication and settlement in the decentralized internet of agents. arXiv preprint arXiv:2602.13795, 2026. [40] Shengli Zhang, Deen Ma, Zibin Lin, and Taotao Wang. Distributed general-purpose agent networks: Architecture, key mechanisms, and prototypes. arXiv preprint arXiv:2606.17368, 2026. [41] Yingwu Zhu and Yiming Hu. Efficient semantic search on DHT overlays. Journal of Parallel and Distributed Computing, 67(5):604–616, 2007. Appendix A Protocol Details A.1 Complete Descriptor and Canonicalization We use d to denote a particular version of a capability descriptor and d¯ d to denote the complete descriptor for that version. We write the complete descriptor as the tuple d¯=(d,pd,τd,σd,ψd,xd,d,d), d=( id_d,\ pk_p_d,\ _d,\ _d,\ _d,\ x_d,\ meta_d,\ ptr_d), (13) where pdp_d is the provider that owns and publishes d. A provider is an authenticated principal identified by its public key pd pk_p_d. The field d id_d is a provider-local capability identifier that remains fixed across versions of the same capability; τd _d is a protocol-level admission class, with a common generic value when no additional admission distinction is required; σd _d identifies a canonical interface-compatibility family, which groups descriptors with compatible input/output requirements (e.g., accepting a department and date and returning appointment records); and ψd _d is a coarse execution-policy class, such as no-network or web-enabled. The field xdx_d expresses task intent and capability details for semantic encoding: the clinic service’s supported specialties and query functions are described here, together with supported languages, example I/O, and domain tags such as outpatient-appointments. The field d meta_d carries freshness and version hints (e.g., the declared software version, model revision, and last-update time), while d ptr_d locates a copy of the complete descriptor that can be fetched again for verification (e.g., through a stable HTTPS URI). A deterministic canonicalization function Canon⁡(⋅)Canon(·) fixes field order and strips noise. Let H denote the protocol’s cryptographic hash function. The descriptor commitment is Cd=H⁡(Canon⁡(d¯))C_d=H(Canon( d)), as defined in Equation (2). After fetching the complete descriptor through d ptr_d, the requester applies the same canonicalization and hash functions and compares the result with CdC_d to verify that the retrieved content matches the referenced descriptor version. Here, CdC_d commits to one descriptor version; it is not a stable capability identifier. To link versions of the same capability, we compute a lineage handle as ιd=H⁡(“LINEAGE”‖pd‖d) _d=H(``LINEAGE′\| pk_p_d\| id_d) (14) where the fixed tag separates lineage handles from other hash outputs. The lineage handle binds a provider public key and a provider-local capability identifier across descriptor versions. Each certified descriptor version has a lineage epoch ede_d, assigned by its anchor committee. The requester deduplicates postings by descriptor commitment CdC_d and resolves updates and revocations by lineage handle ιd _d, as detailed in Appendix C. A.2 Namespace Registry A namespace defines the compatibility scope within which semantic discovery operates. Its label records the admission, interface, and execution-policy conditions that a provider must satisfy for a request. Within that scope, the semantic sketch matches task intent to capability descriptions. Providers offering different capabilities can therefore share a namespace when these conditions are compatible. Adding a capability under an existing compatibility contract requires a new descriptor, without adding a namespace label. Each deployment publishes a versioned namespace registry ℛνR_ν of canonical namespace labels. The registry uses a small set of admission and policy classes, together with registered interface-compatibility families. These are stable protocol identifiers with a public byte encoding. An interface-family identifier refers to a defined input/output contract; compatible schema variants use the canonical family specified by the registry. Descriptor d has namespace label n⁡(d)=(τd,σd,ψd)n(d)=( _d, _d, _d), as defined in Equation (3). A field belongs in the namespace label when a mismatch makes execution incompatible or violates policy. Task specializations and other preferences remain in the semantic text and affect ranking. For example, the clinic’s appointment-query API in §2.2 may share a namespace with appointment APIs for other specialties that use the same registered request/response contract, admission class, and execution-policy class. Their semantic texts distinguish the advertised specialties and functions. Merely accepting and returning JSON does not establish interface compatibility. The clinic’s appointment assistant agent uses a different interface family unless it exposes the same contract, directly or through an adapter. A query may admit several namespace labels. A deployment-supplied resolver maps the requester’s explicit hard requirements to an allowed namespace-label set q⊆ℛνN_q _ν; the original task wording remains in xqx_q. A descriptor is eligible exactly when n⁡(d)∈qn(d) _q. For example, the personal assistant’s query using the generic admission class, the illustrative appointment-query-v1 interface family, and the web-enabled policy resolves to the label in §2.2, while its eye-clinic query intent remains in xqx_q. A client supporting multiple registered contracts may include their labels in qN_q; discovery does not synthesize an adapter. The namespace registry and resolver must agree across providers and requesters: an unresolved alias or incompatible registry version can exclude a relevant descriptor. Namespace eligibility is encoded in the keys. A publication key is a logical key under which the provider publishes a posting; a probe key is a logical key accessed by the requester. Publication-key construction includes n⁡(d)n(d), and probe-key construction includes only labels in qN_q. Different namespace labels therefore yield different logical keys even when coarse-cell IDs and residual codes match, as specified in Section 3.3. The requester also checks n⁡(d)∈qn(d) _q after fetching the complete descriptor. The anchor committee validates the registered descriptor fields and recomputes the namespace label before certifying the publication-key set, as described in Section 4.2. When qN_q contains multiple labels, the requester constructs a probe sequence for each label and interleaves these sequences under one physical lookup budget LqL_q, following the schedule in Section 3.4. A.3 Deterministic Probe Ordering The requester computes zq=Encν(xq)z_q=Enc_ν(x_q) and orders the coarse-cell IDs by distance to obtain ZqordZ_q^ord. Its primary coarse-cell set ZqZ_q contains the first ρq _q IDs. For each considered coarse cell c, the requester computes rq,c=zq−μcr_q,c=z_q- _c and residual codes bq,c(j)b_q,c^(j) using the same construction as the provider. Substituting n∈qn _q, c, and bq,c(j)b_q,c^(j) into Equations 4 and 5 gives the recall probe keys and precision probe keys. The requester prioritizes selective precision probe keys before accessing the larger posting lists at recall probe keys. The logical probe sequence has three stages: P1(q)P_1(q) for top-cell precision probe keys, P2(q)P_2(q) for neighboring-code and secondary-cell precision probe keys, and P3(q)P_3(q) for recall probe keys. P1P_1 contains exact precision probe keys for the primary cells and orders them by cell rank and then residual-code-family index. For a configured Hamming radius rHr_H (rH=0r_H=0 disables this step), P2P_2 recovers projection-boundary cases by substituting into Equation 5 codes at Hamming distances 11 through rHr_H from bq,c(j)b_q,c^(j), ordered by distance, cell rank, family index, and residual-code bytes; it then adds exact precision probe keys for cells ranked ρq+1,…,ρext _q+1,…, _ext, where ρext _ext is the largest coarse-cell rank admitted for secondary-cell probing. P3P_3 orders recall probe keys by cell rank. Within each stage, the per-label probe-key sequences are interleaved round-robin in lexicographic namespace-label order. These rules also provide deterministic tie breaking. The resulting logical probe sequence is the concatenation in Equation (8), where ∥\| denotes sequence concatenation and Dedup keeps the first occurrence of each probe key. In the single-namespace, single-view, unsharded case, every probe key costs one physical lookup, so the budgeted probe-key set is the prefix set in Equation (9), where PrefL(S)Pref_L(S) returns the first L elements of sequence S. As detailed in Appendices A.7.1 and D.4, the general scheduler expands each probe key across entry views and physical shards and charges every resulting lookup to the same LqL_q. A descriptor can be retrieved through a shared logical key when Kpub(d)∩Kqry(q,Lq)≠∅K_pub(d)∩ K_qry(q;L_q)≠ . A.4 LSH Key Construction LSH-on-DHT maps embedding similarity to collisions at exact keys [41, 15, 19]. Let ν identify a shared semantic-index configuration, including the encoder and namespace encoding. The baseline encodes descriptor text as zd=Encν(xd)z_d=Enc_ν(x_d) and applies T independently seeded LSH functions h1,…,hTh_1,…,h_T. Descriptor d is published at the keys κiLSH(d)=H⁡(“LSH”‖ν‖n(d)‖i‖hi(zd)), _i^LSH(d)=H(``LSH′\|ν\|n(d)\|i\|h_i(z_d)), (15) for i=1,…,Ti=1,…,T, where H is a cryptographic hash function. A requester computes zq=Encν(xq)z_q=Enc_ν(x_q) and, for each allowed namespace label, probes the corresponding hash codes. Multi-probe LSH also accesses neighboring codes [21]. Hash width determines the selectivity of each posting list. Increasing the width reduces candidate exposure but also reduces near-neighbor collisions. More tables or neighboring-code probes can recover recall, at the cost of additional publication or lookup work. Our evaluation sweeps all three parameters and compares LSH-on-DHT with SemDHT at matched recall. Section 3 develops the two-layer semantic sketch used by SemDHT to allocate coverage and discrimination to separate keys. A.5 Registration and Certified Records For lineage ιd _d, the stable anchor key is κA(ιd)=H(“A”∥ιd) _A( _d)=H(``A′\| _d). The anchor committee assigned to this key, ℋ⁡(ιd)H( _d), certifies successive descriptor versions without changing its assignment when descriptor content changes. The provider submits RegisterAnchor⁡(d)=⟨ιd,d¯,Cd,ν,ed,d,pdreg⟩,RegisterAnchor(d)= _d, d,C_d,ν,e_d, lease_d, sig_p_d^reg , (16) where d lease_d is the requested expiration time and pdreg sig_p_d^reg signs all preceding fields. The anchor committee verifies the signature using the provider public key in d¯ d, checks Cd=H⁡(Canon⁡(d¯))C_d=H(Canon( d)), derives ιd _d from pd pk_p_d and d id_d (Eq. (14)), and validates the requested transition against its lineage state. The anchor committee then recomputes n⁡(d)n(d), zdz_d, and Kpub(d)K_pub(d) under configuration ν. It constructs a Merkle tree over the sorted publication-key set and issues the membership certificate d= Cert_d= ⟨ιd,Cd,pd,ν,n⁡(d),ed,d,d,d,d⟩, _d,C_d, pk_p_d,ν,n(d),e_d, lease_d, root_d, prev_d, mode_d , (17) d= root_d= MerkleRoot⁡(sorted⁡(Kpub(d))), (sorted(K_pub(d))), with committee signature Σd _d over d Cert_d. The provider public key is copied from the verified complete descriptor. Carrying this key in d Cert_d lets a posting-list service verify a posting without first fetching d¯ d. The predecessor commitment d prev_d and state d∈live,tomb mode_d∈\ live, tomb\ support the transitions in §C. Supersession is a local judgment derived from an observed successor; it does not modify a signed membership certificate. Initial registration uses ed=0e_d=0, d=⊥ prev_d= , and d=live mode_d= live. For each target logical key κ, the provider creates a posting body md,κ=⟨κ,Cd,pd,n⁡(d),d,ιd,ed,d,H(d),d,κpost⟩, splitm_d,κ= &κ,C_d, pk_p_d,n(d), ptr_d, _d,e_d, lease_d,\\ &H( Cert_d), sig_d,κ^post , split (18) where d ptr_d locates the complete descriptor and d,κpost sig_d,κ^post signs all preceding fields. The posting sent to the posting-list service is the envelope in Equation (11), where πd,κ _d,κ proves κ’s inclusion under d root_d. Ordinary DHT routing locates the responsible peers; their posting-list services perform acceptance and storage. A.6 Posting Verification and Quotas The posting-list service first binds the posting body to its membership certificate and target logical key. Bind⁡(md,κ,d,κ)Bind(m_d,κ, Cert_d,κ) holds when the body’s target key equals the received logical key; its commitment, provider public key, namespace label, lineage handle, epoch, and lease equal the corresponding certificate fields; and its certificate reference equals H⁡(d)H( Cert_d). Acceptance requires five checks: Accept⁡(d,κ)=1⇔ (d,κ)=1 Bind⁡(md,κ,d,κ) (m_d,κ, Cert_d,κ) (19) ∧VerifySigpd(md,κ) \,VerifySig_ pk_p_d(m_d,κ) ∧VerifyThresh⁡(d,Σd) \,VerifyThresh( Cert_d, _d) ∧VerifyMerkle⁡(d,κ,πd,κ) \,VerifyMerkle( root_d,κ, _d,κ) ∧⁡(d,tnow). \, FreshAccept(d,t_now). The provider-signature check uses the key in d Cert_d. The committee-signature check verifies the assigned anchor committee, threshold, and supported configuration ν. The lineage-aware predicate FreshAccept, defined in §C.4, uses the service’s current time and observed certified state. This predicate admits ordinary live postings. The posting-list service verifies and stores tombstones and Move hints using the lineage and historical key-membership checks in §C.2–C.3. An unauthorized target key fails the Merkle check. Repeated publication is handled separately: the posting-list service retains one active posting per (Cd,κ)(C_d,κ), replacing it when a valid monotonic renewal arrives. Replaying the same posting therefore does not add entries to that posting list. Distinct descriptor versions and lineages require broader accounting. An optional quota QnsQ_ns limits the simultaneously active certified descriptor states of one admitted provider within a namespace. Because the count spans lineages and anchor committees, the deployment’s admission or quota-accounting layer supplies an authenticated quota-slot authorization before a new state is certified. A renewal of unchanged state reuses its slot. This quota bounds per-provider publication volume; its effect depends on the admission policy in §4.1. A.7 Multi-View Lookup and Ranking A.7.1 Probe Schedule and Provenance Membership verification detects invalid returned postings. To observe differences in which valid postings are returned, the requester uses entry points Eq=u1,…,u|Eq|E_q=\u_1,…,u_|E_q|\ drawn from distinct routing zones or bootstrap neighborhoods. A view is an entry-point and probe-stage pair (u,Pi)(u,P_i), giving the configured view set q=Eq×P1,P2,P3V_q=E_q×\P_1,P_2,P_3\. A lookup action (u,κ)(u,κ) probes logical key κ through entry point u. For each selected key, the requester issues the action through each entry point before advancing to the next key. Entry points therefore probe the same keys. With uniform lookup costs, these keys form a common prefix of ⁡(q)P(q), preserving the stage order in §3.4. Every action consumes physical lookup budget. In the unsharded case, |Eq||E_q| entries can repeat at most ⌊Lq/|Eq|⌋ L_q/|E_q| keys within budget LqL_q. Appendix D.4 accounts for manifests and physical shards. Repetition across entry points trades semantic probe depth for observations of the same keys through different paths. For each returned posting, the requester constructs a provenance record Πd,κ,u=⟨(u,Pi),κ,ℬd,κ,u,,H⁡(d)⟩, _d,κ,u= (u,P_i),κ,B_d,κ,u, ts,H( Cert_d) , (20) using its issued action, local receipt time ts, and the authenticated identities of responsible peers whose posting-list services returned the posting. These identities form ℬd,κ,uB_d,κ,u; a responder’s unverified account of other peers does not add identities to the set. The provenance record is maintained by the requester and is separate from the posting. Routes from different entry points may converge at the same responsible peer, whose identity is counted once when records are merged. A.7.2 Coverage Features and Ranking The requester applies Eq. (19) to every returned posting using its own time and observed lineage state. Only accepted postings contribute candidates or coverage observations. A failed check rejects that posting; it does not by itself establish provider misconduct. In particular, the Merkle inclusion proof is outside the provider-signed posting body and can be replaced by a routing peer, while a valid old posting can be replayed without the provider’s participation. The requester merges accepted postings by CdC_d and fetches each complete descriptor once. It checks the commitment, recomputes the namespace label and lineage handle, compares them and the provider public key with d Cert_d, and requires n⁡(d)∈qn(d) _q. Descriptor versions are then resolved by lineage using §C.4. This resolution distinguishes lease renewal from conflicting state. Define the certified state identity hstate(d)=H⁡(CLOSEιd‖Cd‖pd‖ν‖n(d)‖ed‖dOPEN‖d‖d). splith_state( Cert_d)=H(& _d\|C_d\| pk_p_d\|ν\|n(d)\|e_d\| root_d\\ &\| prev_d\| mode_d). split (21) A monotonic lease renewal preserves this identity; the full H⁡(d)H( Cert_d) in each provenance record identifies the particular membership certificate returned. If authenticated certificates claim incompatible states at the same lineage epoch, the requester consults the stable anchor key and withholds that lineage while the conflict remains unresolved. Repeated observations of one state do not resolve the conflict. For an eligible descriptor version d, let q(d)⊆qV_q(d) _q contain the views that returned an accepted posting, and let ℬq(d)=⋃κ,uℬd,κ,uB_q(d)= _κ,uB_d,κ,u contain its distinct authenticated responders. Define q(d)=|q(d)|3|Eq|,q(d)=min⁡(1,|ℬq(d)|b0), cov_q(d)= |V_q(d)|3|E_q|, rep_q(d)= (1, |B_q(d)|b_0 ), (22) where b0>0b_0>0 is the configured responder count at which responder coverage saturates. View coverage uses the configured view set: a stage that receives no probe budget contributes no observation. Coverage therefore depends on both semantic overlap and the executed probe schedule. Entry-path comparisons use matched (Pi,κ)(P_i,κ) actions across entry points; disjoint keys would confound path effects with semantic selection. Among verified, namespace-eligible, current descriptor versions, the requester ranks by score⁡(d∣q)=λsemsim(zq,zd)+λcovq(d)+λrepq(d),score(d q)= _semsim(z_q,z_d)+ _cov cov_q(d)+ _rep rep_q(d), (23) with nonnegative weights. Certificate consistency and freshness determine eligibility before this ranking step. An optional provider-diversity cap limits how many descriptor versions from one provider enter ⁡(q)C(q). Appendix E.4 evaluates the coverage signal and the recall–cost trade-off of repeated probes. Appendix B Precision-Key Hit Analysis B.1 Precision-Key Hit Probability The two-layer sketch yields a precision-key hit through two successive events: the query and descriptor first select at least one common primary cell, and their residual codes then agree within the configured Hamming radius in at least one residual-code family. Equivalently, for some c∈Zq∩Zdc∈ Z_q∩ Z_d and family j, a precision probe key derived by the query exactly equals one of the descriptor’s precision publication keys. We analyze this primary-cell precision path before the physical budget LqL_q truncates the logical probe sequence. The model excludes schedule-dependent secondary-cell and P3P_3 recall paths. For a namespace-eligible query–descriptor pair, let δ⁡(q,d)=1−sim⁡(zq,zd)δ(q,d)=1-sim(z_q,z_d). In this subsection, conditioning on δ abbreviates conditioning on δ⁡(q,d)=δ(q,d)=δ. Define the coarse-overlap event A=Zq∩Zd≠∅A=\Z_q∩ Z_d≠ \, and let BJB_J denote the event that, on at least one shared primary cell, at least one of the J residual-code families yields a matching precision key. A precision-key hit on the primary-cell path occurs when A∩BJA∩ B_J occurs. The coarse-cell overlap probability is gρ,ρq(δ)=Pr⁡[A∣δ]g_ρ, _q(δ)= [A δ]. Conditioned on a realized pair satisfying A, let p⁡(q,d)p(q,d) denote the probability, over one randomly seeded residual-code family, that at least one shared cell yields a matching precision key. This is a per-pair probability: it depends on the realized residual geometry of q and d, rather than only on their embedding distance δ. If the J families are approximately independent after conditioning on that geometry, then Pr[BJ∣q,d,A]≈1−(1−p(q,d))J. [B_J q,d,A]≈ 1- (1-p(q,d) )^J. (24) Averaging over residual geometries and applying the probability product rule gives the precision-key hit-probability model Phit(δ) P_hit(δ) =Pr⁡[A∩BJ∣δ] = [A∩ B_J δ] (25) =Pr[A∣δ]Pr[BJ∣A,δ] = [A δ] [B_J A,δ] ≈gρ,ρq(δ)⋅[1−(1−p(q,d))J|A,δ]. ≈ g_ρ, _q(δ)·E\! [1- (1-p(q,d) )^J\, |\,A,δ ]. The first two lines apply the probability product rule to coarse-cell overlap and residual-code agreement. Only the final line is approximate, because it models the J residual-code families as conditionally independent. The expectation remains outside the nonlinear union because, in general, ⁡[1−(1−p)J]≠1−(1−⁡[p])JE[1-(1-p)^J]≠ 1-(1-E[p])^J. The single-family probability has a closed-form cell-level component. For a shared cell c, let θc(q,d)=∠⁡(rq,c,rd,c) _c(q,d)= (r_q,c,r_d,c) be the angle between the query and descriptor residuals. Under sign projection, one bit agrees with probability pbit(θ)=1−θ/πp_bit(θ)=1-θ/π. With ℓ independent projection bits, the probability that the two residual codes differ in at most rHr_H positions is pℓ,rH(θ)=∑i=0rH(ℓi)(1−pbit(θ))ipbit(θ)ℓ−i.p_ ,r_H(θ)= _i=0^r_H i (1-p_bit(θ) )^ip_bit(θ) -i. (26) This is exactly the probability that the descriptor’s code lies within the query’s Hamming-rHr_H precision probes for that cell; rH=0r_H=0 reduces it to the exact-code probability pbit(θ)ℓp_bit(θ) . The pair-level p⁡(q,d)p(q,d) combines these cell-level opportunities over all cells in Zq∩ZdZ_q∩ Z_d. Increasing J gives a near-neighbor pair more opportunities to match a precision probe key, but also increases publication fan-out and can expose more distant descriptors. The query budget further limits how many of these opportunities are used. Section 6.2 evaluates the residual-code term and the conditional-independence approximation on real residual pairs. Appendix C Descriptor Updates and Freshness A provider can renew a descriptor, publish a new descriptor version, or revoke a capability. Each action changes which postings a requester may use. This section defines these transitions, preserves discoverability when publication keys change, and explains how requesters resolve and propagate the resulting lineage state. C.1 Lineage State The clinic service provider in §2.2 may revise its supported specialties or interface contract while retaining the same capability identifier. Changing appointment slots does not update the descriptor. Let d be its current descriptor version and d′d its successor. The versions share ιd′=ιd _d = _d, while the anchor committee assigns ed′=ed+1e_d =e_d+1 and sets d′=Cd prev_d =C_d in d′ Cert_d , using the membership certificate defined in §4.2. A membership certificate records the state signed by the anchor committee. Its mode is live for a descriptor version or tomb for revocation. Observing a certified successor makes an older live version superseded in local lineage state; neither the older membership certificate nor its signature changes. The anchor committee serializes transitions under §4.1. Responsible peers at the stable anchor key κA(ιd) _A( _d) retain certified lineage state as publication keys change. Expiration times use a common time basis. The deployment bounds clock error and includes that bound in its expiration checks; the notation below treats those checks as comparisons against local time. The anchor committee retains the highest epoch and any revocation across lease expiry and committee changes. Posting-list services likewise retain the highest epoch they have learned when they remove expired postings. C.2 Renewal, Update, and Revocation Table 7 summarizes the three transitions. In each case, the provider signs a request identifying the lineage, the preceding membership certificate, and the requested change. Transition Certified change and publication action Lease renewal Keep the epoch and certified state identity; extend the lease and replace postings with newly signed posting bodies. Version update Advance the epoch by one; certify the successor and publish at its publication keys. Revocation Advance the epoch by one; issue a tombstone and disseminate it through the stable anchor and prior publication keys. Table 7: Lineage transitions. Supersession is derived locally from an observed successor. Lease renewal. The anchor committee renews only its current live epoch. At approval time tapprovet_approve, it requires tapprove t_approve <old, < lease_old, (27) old lease_old <new≤tapprove+Δmax, < lease_new≤ t_approve+ _ , where Δmax _ is the maximum lease duration. All fields in hstate(d)h_state( Cert_d) (Eq. (21)) remain unchanged. The provider obtains the renewed membership certificate and committee signature, then signs replacement posting bodies containing the new lease and H⁡(d)H( Cert_d). The publication-key set and Merkle inclusion proofs remain valid, so renewal does not recompute the semantic sketch. The pre-expiry condition applies when the anchor committee approves the renewal. A replica receiving the renewed membership certificate later may install it if the new lease is still valid and its local state contains no higher epoch, revocation, or conflict. Expiry before approval ends the renewal path; an admitted provider can request a new epoch chained to the last certified state, with full certification. Version update. A change to the complete descriptor requires a new epoch. The anchor committee checks ιd′=ιd _d = _d, ed′=ed+1e_d =e_d+1, and d′=Cd prev_d =C_d, then recomputes the successor’s namespace label, semantic sketch, and publication-key set. The provider publishes the resulting postings at Kpub(d′)K_pub(d ). Participants that observe d′ Cert_d mark lower live epochs superseded. If the publication-key set changes, the provider also installs the Move hints defined in §C.3. Revocation. After authenticating the provider’s request, the anchor committee issues a tombstone using the membership-certificate schema. It retains the preceding certificate’s descriptor metadata, advances the epoch by one, sets the predecessor commitment to CdC_d, and changes mode to tomb. The tombstone terminates that lineage: the anchor committee accepts no later renewal or successor. Publishing the capability again requires admission of a new lineage handle. The lease field does not expire the revocation. The provider publishes the tombstone and committee signature at κA(ιd) _A( _d). At a prior publication key κ, it additionally supplies the prior membership certificate, committee signature, and Merkle inclusion proof for κ. The posting-list service verifies both certificates, the common lineage and provider key, the forward epoch relation, and the old-key membership proof before storing the tombstone and updating local lineage state. These checks authenticate revocation independently of the live-posting acceptance predicate. An expired prior lease does not invalidate its historical key-membership evidence. C.3 Migration with Move Hints When an update changes the publication-key set, queries that still probe the old keys need a way to discover the successor. During a dual-publication window Δmig _mig, the provider publishes d′d at its publication keys and leaves a Move hint at each old publication key: Moved→d′=⟨ιd,Cd,Cd′,ed′,tend,d→d′move,d′,Σd′⟩.Move_d→ d = _d,C_d,C_d ,e_d ,t_end, sig_d→ d ^move, Cert_d , _d . (28) Here tend=tupdate+Δmigt_end=t_update+ _mig is an absolute expiration time, and the provider signature covers all preceding fields. The provider chooses a window ending no later than the successor certificate’s lease. Including d′ Cert_d and Σd′ _d makes the successor’s certified state available to the receiving posting-list service. For storage at κ∈Kpub(d)κ∈ K_pub(d), the provider sends the Move hint together with d Cert_d, Σd _d, and πd,κ _d,κ. The posting-list service verifies the old-key membership proof, both committee signatures, and the provider’s Move signature under the certified provider key. It also checks the shared lineage, both commitments, consecutive epochs, d′=Cd prev_d =C_d, d′=live mode_d = live, and tnow<tend≤d′t_now<t_end≤ lease_d . The old certificate supplies historical membership evidence; the old descriptor version need not remain live. The service stores the Move hint through its expiration and returns it on probes of the old key. The old descriptor version does not enter the candidate shortlist. A requester verifies the Move hint and resolves the lineage through the stable anchor key. It fetches the current complete descriptor, checks its commitment and namespace eligibility, and admits the descriptor only after the freshness checks below. Additional updates are resolved by the same process. Anchor and successor-key lookups consume the remaining physical lookup budget LqL_q; a resolution that cannot finish within that budget yields no candidate for that lineage. Appendix E.6 evaluates the window’s effect on discoverability. C.4 Freshness Resolution Let Obsq(ι)Obs_q( ) be the membership certificates whose committee signatures the requester has verified for lineage ι , including certificates learned through prior observations and anchor resolution. The certificate accompanying an incoming posting is included after authentication and before evaluating freshness. The set retains epoch and revocation evidence after leases expire. Writing e⁡()e( Cert) for the epoch field of a membership certificate, the highest observed epoch is eq⋆(ι)=max⁡e⁡():∈Obsq(ι),e_q ( )= \e( Cert): Cert _q( )\, (29) with max∅=⊥ = . This maximum is taken before checking whether the highest epoch is live or its lease is valid. Under the committee state-serialization assumption, a committee signature authenticates a certificate’s lineage and predecessor relation. When combining certificates, the requester checks predecessor links against observed state. A missing link between observed epochs or conflicting certified state identities triggers a stable-anchor lookup for the certificates needed to resolve that lineage. Move hints, tombstones, and a deployment-defined near-expiry threshold also trigger anchor resolution. Every such lookup is charged to LqL_q. Define Consistentq(ι)=1Consistent_q( )=1 when the observed certificates have compatible lineage and predecessor fields, no unresolved same-epoch state conflict, and no successor after a tombstone. Compatible same-epoch renewals have one certified state identity; local state retains the largest verified lease. If required resolution leaves a conflict or a predecessor gap unresolved, Consistentq(ι)=0Consistent_q( )=0. A repeated certificate does not outweigh conflicting certified state. For a descriptor version d with a verified membership certificate, freshness at query time tqt_q is q(d)=1⇔ fresh_q(d)=1 Consistentq(ιd)=1 _q( _d)=1 (30) ∧ed=eq⋆(ιd) \,e_d=e_q ( _d) ∧d=live \, mode_d= live ∧tq<d. \,t_q< lease_d. A posting-list service evaluates ⁡(d,t) FreshAccept(d,t) by the same rule using its local observed certificates and time t. The lease check uses the membership certificate bound to the presented posting body; learning a longer renewal does not change an old body’s signed fields. Membership verification and descriptor reconstruction remain the checks in §4.3. A highest epoch that is expired or a tombstone yields no live candidate. An older version cannot become current again when that highest epoch expires. Participants retain this epoch or revocation information when deleting expired posting bodies. Freshness is relative to observed certified state: a participant learns a new update or revocation through publication, anchor resolution, or read-repair. C.5 Read-Repair A requester that receives stale responses sends the newer membership certificate and committee signature to the corresponding posting-list services. It includes predecessor certificates needed to connect the recipient’s observed epoch to the newer state, or the recipient fetches those certificates from the stable anchor. A certificate hash can identify the update to fetch; installing the update requires the certificate and its verifiable signature. The receiving service verifies the committee signatures and predecessor relations, advances its observed epoch, and marks older live versions superseded. For a compatible renewal at the same epoch, it retains the larger lease. Lower epochs do not replace higher epochs, and conflicts follow the resolution rule in §C.4. An expired certificate can still establish that an older epoch has been superseded; a tombstone continues to establish revocation. A service admits a live posting only after the posting passes Eq. (19). Repair messages disseminate certified state and do not reissue membership certificates. DHT lookups performed by the requester for repair consume LqL_q; direct repair messages and recipient-side background fetches are maintenance traffic accounted for separately. Appendix E.7 reports stale exposure, convergence, and repair-message cost. Appendix D Scalability under Skew and Churn Sections 3–4 and Appendix C define the logical index, certification, and freshness rules. Popular semantic regions can nevertheless concentrate query, storage, and maintenance load. This section separates those logical rules from physical layout: sharding may redistribute the posting list of a logical key, but it must not change the publication-key set or exceed the query’s physical lookup budget. D.1 Why Semantic Regions Hot-Spot A semantic index is more hotspot-prone than a classic exact-object DHT for a structural reason: many unrelated queries and many unrelated providers can legitimately converge on the same handful of coarse cells simply because that region of the embedding space is popular, which a content hash never causes. For any logical key κ at time t, let λκqry(t) _κ^qry(t) and λκmnt(t) _κ^mnt(t) be its query and maintenance (renew/update/move/repair) arrival rates and Nκ(t)N_κ(t) its active posting count. We do not need a physically exact cost model, only one that lets the system tell apart why a key is hot: Λκ(t)=αqλκqry(t)+αmλκmnt(t)+αnNκ(t). _κ(t)= _q _κ^qry(t)+ _m _κ^mnt(t)+ _nN_κ(t). (31) Here αq,αm,αn≥0 _q, _m, _n≥ 0 convert the three measured loads into a common load score. This score separates a posting-heavy logical key (long posting lists inflate bandwidth and narrowing cost even at modest query rates) from a query-heavy logical key (a popular semantic region hit repeatedly regardless of list length) from a maintenance-heavy logical key (high provider churn or capability drift saturates control traffic even when neither of the other two is large). A key enters scaling mode once any of four thresholds trips, Hotκ(t)=1⇔ _κ(t)=1 Λκ(t)>Θload∨Nκ(t)>Θsize _κ(t)> _load\ \ N_κ(t)> _size (32) ∨λκqry(t)>Θqry∨λκmnt(t)>Θmnt, \ _κ^qry(t)> _qry\ \ _κ^mnt(t)> _mnt, where Θload,Θsize,Θqry,Θmnt>0 _load, _size, _qry, _mnt>0 are deployment-configured thresholds for the corresponding quantities. A key is therefore hot when any one threshold is exceeded. Everything below is built to satisfy four constraints simultaneously: change physical layout only, never logical keys or the publication-key set; never bypass the membership-certificate or freshness checks of Section 4 and Appendix C; trigger and recover locally rather than rebalancing the whole overlay; and keep the physical lookup budget LqL_q an explicit, interpretable quantity even after sharding is introduced. D.2 Physical Sharding without Semantic Rewriting The membership certificate of §4.2 fixes which publication keys a descriptor may occupy. Changing those keys during sharding would invalidate the certified descriptor-to-key relation. SemDHT therefore shards only the physical storage of a hot logical key κ and never changes the publication-key set. The physical layout is recorded in the shard manifest Gκ(ξκ)=⟨κ,ξκ,sκ,κ[r]r=1sκ,κ,κsh,Σκsh⟩.G_κ^( _κ)= κ,\ _κ,\ s_κ,\κ^[r]\_r=1^s_κ,\ rule_κ, lease_κ^sh,\ _κ^sh . (33) The manifest assigns κ a layout epoch ξκ _κ and sκs_κ physical shard keys, derived as κ[r]=H(“SHARD”∥κ∥ξκ∥r).κ^[r]=H(``SHARD′\|κ\| _κ\|r). (34) Here κ rule_κ is the deterministic commitment-to-shard assignment rule instantiated below, κsh lease_κ^sh is the manifest-expiration time, and Σκsh _κ^sh is the signature or quorum certificate required by the deployment’s shard-layout policy over all preceding manifest fields. For descriptor d, the service selects a shard using the deterministic assignment rule sidκ⁡(Cd)=1+(H⁡(Cd)modsκ).sid_κ(C_d)=1+(H(C_d) s_κ). (35) It routes the posting to physical key κ[sidκ⁡(Cd)]κ^[sid_κ(C_d)] without recomputing the semantic sketch or requiring the provider to obtain a new membership certificate. The corresponding acceptance predicate is ShardAccept⁡(d,κ[r])=1⇔ (d,κ^[r])=1 Accept⁡(d,κ)=1 (d,κ)=1 (36) ∧VerifyManifest⁡(Gκ(ξκ)) \,VerifyManifest(G_κ^( _κ)) ∧r=sidκ⁡(Cd). \,r=sid_κ(C_d). This predicate is a strict conjunction: a posting must pass every check from §4.3 and land in its assigned physical shard, so sharding narrows how a valid posting is stored without weakening what counts as valid. Here VerifyManifestVerifyManifest checks the manifest’s signature or quorum certificate, expiration time, logical key, and layout epoch. A hot key that stays hot for a sustained split window Δsplit _split is split into sκ′=min⁡(smax,max⁡(2,⌈Λκ(t)Θload⌉))s_κ = \! (s_ , \! (2, _κ(t) _load ) ) (37) shards, where smaxs_ is the deployment shard cap. Merges use strictly lower hysteresis thresholds held for a merge window Δmerge _merge to avoid flapping between layouts. D.3 Two Caches That Are Never Authoritative Sharding by itself does not remove manifest traffic, so SemDHT adds a directory cache for shard layout and a small posting-window cache for recently validated postings. Both are non-authoritative. The directory cache stores entries of the form Xκdir=⟨κ,ξκ,sκ,κ[r]r=1sκ,κdir,H⁡(Gκ(ξκ))⟩.X_κ^dir= κ, _κ,s_κ,\κ^[r]\_r=1^s_κ, ttl_κ^dir,H(G_κ^( _κ)) . (38) Each entry carries the directory-cache expiration time κdir ttl_κ^dir and the shard-manifest digest H⁡(Gκ(ξκ))H(G_κ^( _κ)). It is invalidated on expiration, a newer authenticated shard-manifest digest learned through anti-entropy or a shard response, or an epoch mismatch returned by an attempted shard. A mismatch charges the attempted old shards, an authoritative logical-key lookup, and the current shards. A posting-window hit still re-runs membership-certificate and lineage checks before shortlist admission: caching can shortcut finding a candidate, never trusting it. This rule separates two guarantees that are easy to conflate. Even a stale cache cannot make an invalid posting pass candidate verification. It can, however, miss candidates until a newer shard-manifest digest is observed or the TTL expires. Our simulation assumes that shard or anti-entropy transport surfaces mismatches between authenticated shard-manifest digests; it does not measure that transport’s delay. Without such a channel, TTL only bounds layout staleness and the system cannot claim immediate knowledge of the current shard manifest. D.4 Budget-Aware Probing after Sharding Once a logical key can be sharded, the assumption in §3.4 that one probe key costs one physical lookup breaks: looking up a sharded logical key now means fetching a manifest and then fanning out to some or all of its physical shards. SemDHT makes this explicit rather than silently absorbing it into LqL_q: costq(u,κ)=1,κunsharded,1+sκ,sharded, directory cache miss,sκ,sharded, directory cache hit,cost_q(u,κ)= cases1,&κ\ unsharded,\\ 1+s_κ,&sharded, directory cache miss,\\ s_κ,&sharded, directory cache hit, cases (39) The cost is charged separately for every entry point u; namespace-label expansion has already produced distinct probe keys. The scheduler admits a set of actions Aq(Lq)⊆Eq×set⁡(⁡(q))A_q(L_q) E_q×set(P(q)) only if ∑(u,κ)∈Aq(Lq)costq(u,κ)≤Lq. _(u,κ)∈ A_q(L_q)cost_q(u,κ)≤ L_q. (40) The budgeted probe-key set is the projection Kqry(q;Lq)=κ:∃u,(u,κ)∈Aq(Lq).K_qry(q;L_q)=\κ:∃ u,\ (u,κ)∈ A_q(L_q)\. (41) Thus LqL_q remains the explicit bound promised in §3.4 after namespace-label expansion, path diversity, and sharding. The scheduler preserves probe-stage precedence and repeats each selected key across entry points as defined in §A.7.1. It admits a key only when the combined cost of its actions across EqE_q fits the remaining budget. When physical lookup costs differ, the scheduler can reprioritize eligible keys within a stage using estimated marginal utility per unit cost for each lookup action, q(u,κ)=1costq(u,κ)(CLOSEαgaingain^q(κ)+αscoreΔscore^q(κ)OPEN−αlatlat^q(κ)−αpollpoll^q(κ)). splitU_q(u,κ)= 1cost_q(u,κ) (& _gain\, gain_q(κ)+ _score\, _q(κ)\\ &- _lat\, lat_q(κ)- _poll\, poll_q(κ) ). split (42) Here gain^q gain_q estimates new-candidate yield, Δscore^q _q shortlist-score improvement, lat^q lat_q latency, and poll^q poll_q historical invalid-candidate exposure; the four estimates are normalized before weighting, and αgain,αscore,αlat,αpoll≥0 _gain, _score, _lat, _poll≥ 0 are their utility weights. The scheduler ranks keys by the cost-weighted mean of q(u,κ)U_q(u,κ) across u∈Equ∈ E_q, which equals estimated total utility divided by total physical cost. It completes the selected key’s actions before selecting another key. The requester stops after a completed group when Stopq=1Stop_q=1 iff |⁡(q)|≥kq|C(q)|≥ k_q and the largest score improvement among the most recent probe batch falls below εstop _stop, the configured minimum meaningful score improvement. We validate the routing substrate this cost model sits on top of with a 64-bit full-Kademlia implementation and a separately fit analytic routing backend, blind-tested on Nnet=105N_net=10^5 lookups never used for fitting: across four churn profiles, the largest relative errors we observe are 16.1%16.1\%, 10.0%10.0\%, and 12.8%12.8\% on p50/p95/p99 latency respectively, and all 17 predeclared consistency gates pass. At Lq=32L_q=32 under a shard capacity selected to exercise all three cost branches, a naive accounting that treats LqL_q as a semantic-probe count rather than a physical-lookup budget lets 56.0%56.0\% of queries silently exceed their declared physical budget; billing every probe through costq(u,κ)cost_q(u,κ) instead keeps every single query at or under its declared budget, at a measured cost of roughly 6.56.5 fewer average lookups per query relative to a cold-directory baseline once the directory cache is warm. D.5 Load under Skew We stress the sharding policy with a Zipf query distribution over the 4,096 most frequently probed real keys in our corpus, at skew parameters from uniform up to 1.41.4. At Zipf 1.21.2, sharding drops the single hottest node’s absolute response-work from 17,555.917,555.9 to 6,713.96,713.9, the max/mean response-work ratio from 191.6191.6 to 50.350.3, and the load Gini coefficient from 0.9520.952 to 0.9060.906, at a cost of roughly 5.195.19 additional physical lookups per logical query on average. Sharding does not reduce every component of load: because a query still has to visit every shard of a key it probes, sharding does not divide a key’s query arrival rate by the number of shards—it primarily redistributes posting-list response work and storage, and it strictly adds base lookup work rather than removing it. D.6 Convergence under Churn Layout can go stale independently of descriptor freshness, so a candidate is only admissible once both hold relative to the newest signed state the requester has observed. Define FreshLayoutq(κ)=1FreshLayout_q(κ)=1 exactly when the requester has verified the highest layout epoch for κ among the shard manifests it has observed: Admissibleq(d,κ)=1⇔ _q(d,κ)=1 FreshLayoutq(κ)=1 _q(κ)=1 (43) ∧ q(d)=1, fresh_q(d)=1, separating the newest certified descriptor state observed by the requester, as defined in Appendix C, from the newest signed layout observed for its logical key. Responsible replicas exchange shard-manifest digest messages of the form ⟨κ,ξκ,H⁡(Gκ(ξκ)),κ⟩ κ, _κ,H(G_κ^( _κ)), ts_κ , where κ ts_κ is the message timestamp, and repair on mismatch or epoch lag using the same authenticated shard-manifest mechanism as ordinary layout changes, and a newly responsible node bootstraps state—not semantic truth, which remains defined entirely by Section 4 and Appendix C—from any online replica. In a controlled evaluation with 128 real hot keys and 20 replicas, this read-repair mechanism lowers the stale-layout exposure AUC from 3.5623.562 to 1.4481.448 and the p95 convergence tail from 20.7420.74 to 18.8218.82 time units at a representative turnover rate. Comparing an unsafe cache design that trusts any cached posting against the safe design of §D.3 makes candidate-acceptance safety concrete. Given the simulation’s signal that two authenticated shard-manifest digests mismatch, safe caching accepts no injected invalid candidate (measured correctness 1.0001.000, identical to no caching) against 0.56970.5697 for the unsafe variant, at a 2.1%2.1\% fallback rate to the authoritative logical key κ. This result does not measure the real transport latency of learning the newer shard-manifest digest or claim that a stale layout cannot temporarily reduce recall. Appendix E Supplementary Evaluation and Reproducibility E.1 Network Replay: Inputs and Complete Conditions Placement System Schedule Cache Mean [95% CI] (s) P95 [95% CI] (s) RPC errors Same SemDHT Parallel Cold 3.819 [3.490, 4.156] 10.289 [8.949, 12.742] 1 Same SemDHT Parallel Warm 3.009 [2.725, 3.315] 8.879 [7.339, 10.099] 0 Same SemDHT Barrier Cold 3.977 [3.618, 4.334] 11.407 [9.195, 13.323] 0 Same SemDHT Barrier Warm 2.918 [2.634, 3.215] 8.751 [7.630, 9.779] 0 Same LSH Parallel Cold 13.897 [13.628, 14.157] 19.721 [18.591, 20.157] 0 Same LSH Parallel Warm 13.565 [13.301, 13.843] 18.929 [18.141, 19.786] 0 Same LSH Barrier Cold 13.829 [13.532, 14.126] 19.735 [18.096, 20.764] 1 Same LSH Barrier Warm 13.565 [13.288, 13.839] 18.865 [18.151, 19.943] 4 Cross SemDHT Parallel Cold 7.038 [6.673, 7.419] 14.178 [11.955, 16.882] 0 Cross SemDHT Parallel Warm 6.836 [6.446, 7.230] 15.093 [13.004, 17.329] 2 Cross SemDHT Barrier Cold 9.717 [9.297, 10.168] 18.311 [15.564, 20.135] 0 Cross SemDHT Barrier Warm 9.094 [8.704, 9.524] 15.946 [14.551, 19.378] 0 Cross LSH Parallel Cold 28.938 [28.644, 29.221] 33.318 [32.588, 34.265] 0 Cross LSH Parallel Warm 29.044 [28.770, 29.312] 33.734 [32.462, 34.263] 0 Cross LSH Barrier Cold 32.162 [31.863, 32.452] 36.290 [35.610, 37.314] 1 Cross LSH Barrier Warm 32.130 [31.840, 32.419] 36.569 [35.967, 37.276] 0 Table 8: All network-replay conditions for the archived 299-query sample. Estimates retain frozen sample weights and all error-bearing queries. Each interval resamples complete query clusters; errors count application RPC failures, not failed logical lookups. Frozen inputs. The 500-query input bundle is sampled from the 8,087-query workload before network execution. The SemDHT configuration uses 16 coarse centroids, ρ=2ρ=2, J=4J=4, ℓ=3 =3, rH=0r_H=0, and a probe-key budget of 64. The LSH configuration uses 16 tables with eight-bit signatures, Hamming radius two, and a probe-key budget of 256. Publication sets and probe sequences are materialized from these configurations; the replay does not interpolate between operating points. The materializer freezes the rebuilt coarse codebook used for this input bundle. Over the source workload, rebuilding changes eight candidate incidences, while the median and P95 candidate counts and mean probe count match the original configuration’s saved results. For each overlay, the materialized workload publishes 171,339 SemDHT postings at 8,570 keys and 226,857 LSH postings at 42,749 keys. Setup readback checks 10,970 and 92,575 keys, respectively, including planned keys with empty posting lists. This check compares the returned descriptor commitments with the materialized input before the timed replay begins. Runtime settings. The run uses 200 peers per overlay, replication three, read and write quorums two, page size 64, lookup concurrency 32, and 60-second lookup and RPC timeouts. Replica completion uses the wait-all policy. Certificate caches have 65,536 entries, are isolated between overlays, and are cleared before each condition; warm conditions then execute the same query’s certificate prelude. The timing records separate this prelude from lookup completion. This experiment contains one requester and one deployment for each placement. Measured sample and intervals. The September 15 archive includes sequences 0–4,783: 299 distinct queries, each with one observation in every condition. We retain the positive weights assigned in the frozen sample and normalize them within this prefix. The effective sample size is 298.99. For each bootstrap replicate, we sample 299 query IDs uniformly with replacement and keep each sampled query’s original weight and complete set of conditions. We use 2,000 replicates, seed 20260910, and percentile 95% intervals. Weighted P95 is the left inverse of the weighted empirical CDF. Paired contrasts use the same sampled query IDs for both systems or schedules. For the scheduling contrasts in Table 4, each replicate subtracts the parallel estimate from the stage-barrier estimate. The recorded stage indices and keys agree across all conditions for each query and system: the schedules execute the same budgeted key sequence and reconstruct the expected candidate set. These intervals are exploratory and have no multiple-comparison adjustment or interim stopping rule. Table 8 reports all 16 conditions. A seeded query permutation and a 16-condition balanced Latin square interleave the executions. The 299-query prefix does not end at a complete 16-query block, so it retains some condition-order imbalance. The prefix also need not reproduce every stratum’s final allocation. We preserve its original weights and include every complete query. An earlier execution was interrupted after 37 complete queries; the restarted execution repeats those query IDs. We retain the earlier records separately and do not count them as additional independent queries. Errors and snapshot integrity. The nine RPC errors consist of eight connection resets and one stream-termination (GOAWAY) error, affecting seven query clusters. There are no failed logical lookups, verification rejections, or candidate-set mismatches. Excluding those seven complete query clusters changes any condition’s weighted mean completion time by at most 0.111 s. That calculation is a sensitivity diagnostic; the main results retain the error-bearing queries. All nine requester source-file hashes match the download manifest. The checkpoint ends after query 299, and its detailed logs reconcile to 690,256 logical lookups and 2,070,768 replica attempts. The compressed files contain sealed members for these queries and an unsealed tail from the next query. Analysis excludes this uncheckpointed tail. The archive covers 299 of the 500 planned queries; the original full-schedule and zero-RPC-error criteria were not met. Resource instrumentation. During the latter part of replay, separate samplers read service-cgroup CPU counters once per second on the requester and 16 data hosts. Requester entry and exit probes additionally record CPU counters around the timed lookup path, excluding certificate prewarming. The markers align with 144 conditions from ten queries, including eight complete 16-condition query blocks. The maximum discrepancy between a marker window and its recorded lookup time is 2.61 ms. These CPU windows include service background work and cover a short contiguous portion of the run. Instrumentation may add overhead; the latency analysis retains both instrumented and uninstrumented observations. The samplers did not collect resident memory. Accounting. Application RPC counts include replica requests and continuation pages; a logical lookup can generate several RPCs. Message bytes are the requester’s encoded request and response frames. Accumulated validation time counts concurrent work and cannot be added to a wall-clock time breakdown. The saved runtime CPU-capacity metric and Go heap-allocation metric do not measure actual process CPU use and RSS; neither is used for a resource-saving claim. E.2 Validation Fixture and Record Sizes The microbenchmark uses protocol v2, which binds the provider public key in the membership certificate and admits an initial lineage epoch of zero. This separate archived microbenchmark ran under Go 1.27.0 on Windows/amd64 with 16 logical processors. Measurements use CIRCL’s portable BLS12-381 implementation, with public keys in G1, signatures in G2, and distinct messages for the committee signers. Each reported operation is repeated ten times with independent benchmark invocations. Table 9 gives canonical CBOR sizes for the 16-key, five-of-seven fixture. Each size measures the indicated object independently; nested encodings need not equal the sum of the standalone component encodings. Cache measurements reuse the same verified certificate and committee signature across validations. They do not measure batch verification of distinct certificates. Encoded object Bytes Posting body 253 Provider signature 64 Membership certificate 266 Committee signature 103 Certificate with committee signature 372 Merkle inclusion proof 143 Complete posting 839 Table 9: Protocol-v2 fixture sizes. The complete posting includes the signed body, certificate, committee signature, and inclusion proof. E.3 Retrieval Configurations and Sensitivity Codebook seeds and query uncertainty. Repeating the three representative points in Table 1 on two additional codebook seeds keeps the qualitative ranking intact (recall stable within 0.9020.902–0.9190.919, 0.9500.950–0.9600.960, and 0.9700.970–0.9780.978 respectively), but exposure moves by 3–5 percentage points across seeds, limiting the precision of a single-seed estimate. For the primary seed, query bootstrap 95% confidence intervals for (recall, exposure) at the three rows are respectively (0.8987CLOSE(0.8987–0.9060, 0.62030.9060,\ 0.6203–OPEN0.6311)0.6311), (0.9471CLOSE(0.9471–0.9529, 0.72150.9529,\ 0.7215–OPEN0.7335)0.7335), and (0.9683CLOSE(0.9683–0.9727, 0.79570.9727,\ 0.7957–OPEN0.8055)0.8055). Matched-recall selection. The operating point in Table 1 at recall target 0.950.95 has publication fan-out eight. It is selected directly by exposure among configurations already above that target. Table 10 instead interpolates each configuration’s measured budget curve to recall exactly 0.950.95 before minimizing exposure. The selected SemDHT configuration then has fan-out ten and slightly smaller interpolated exposure. The network replay uses discrete configurations selected before execution, as specified in Section 6.3. SemDHT LSH-on-DHT recall target exposure/probes exposure/probes 0.80 47.5% / 30.6 47.1% / 102.1 0.90 62.1% / 33.7 61.6% / 173.2 0.95 72.7% / 32.9 72.7% / 253.5 0.97 79.0% / 65.2 83.5% / 110.2 Table 10: SemDHT versus the best-tuned LSH-on-DHT configuration at matched recall, interpolated from measured budget curves. “probes” is the mean number of exact-key DHT lookups actually issued. E.4 Multi-View Lookup under Entry-Path Suppression We replay 8,087 queries with a one-entry budget of Lq=128L_q=128. For each query and entry point, the model independently captures the entry path with probability f∈0.05,…,0.50f∈\0.05,…,0.50\. A captured path suppresses a coordinated target set comprising approximately 80%80\% of reachable descriptors and returns the remainder. Here f is an entry-path capture probability; the model does not map it to a fraction of malicious DHT nodes. We compare two probe schedules. The first repeats the complete one-entry probe prefix at every entry, increasing total physical cost. The second divides the original query’s actual probe count across entries and repeats the resulting shorter prefix at each entry. Table 11 reports both schedules at f=0.20f=0.20. Repeating the complete prefix through two entries raises attacked recall from 0.79570.7957 to 0.91910.9191, with twice the lookup cost. Keeping mean cost at 59.159.1 lookups reduces clean recall from 0.95000.9500 to 0.85530.8553, as fewer distinct keys are probed. Schedule Lookups Recall Clean Attacked One entry 59.1 0.9500 0.7957 Two, full prefix 118.3 0.9500 0.9191 Two, fixed cost 59.1 0.8553 0.8273 Table 11: Mean physical lookups and recall at entry-path capture probability f=0.20f=0.20. Both two-entry schedules repeat the same keys across entries; the fixed-cost schedule uses a shorter prefix. For each query, we average q(d) cov_q(d) and q(d) rep_q(d) over returned candidates and use one minus the mean of these two averages as the query-level anomaly score. View coverage uses the configured 3|Eq|3|E_q| denominator in Eq. (22). The simulation assigns two distinct responder observations to each successful key–entry lookup, with saturation b0=20b_0=20; it does not model routes converging on the same authenticated responder. The ROC analysis distinguishes clean queries from queries with at least one captured entry path. At f=0.20f=0.20, two entries repeating the complete prefix yield AUC 0.9280.928 from view coverage, 0.8920.892 from responder coverage, and 0.9200.920 from the combined score, compared with combined AUC 0.4960.496 for one entry. When all entry paths are captured, targeted candidates disappear from every view and the combined AUC returns to approximately 0.50.5. The experiment measures query-level detection and coverage; the candidate-ranking weights in Eq. (23) remain uncalibrated. E.5 Storage under Skew and Layout Changes Sharding’s benefit under query skew is not limited to the single Zipf level reported in §D.5: across the full swept range from uniform traffic to Zipf 1.41.4, the gap between sharded and unsharded hottest-node response-work widens as skew increases, from a 1.5×1.5× reduction under uniform traffic to 3.8×3.8× at Zipf 1.21.2 and 4.9×4.9× at Zipf 1.41.4, the highest skew we tested. Figure 9 presents the full skew sweep. Figure 9: Hottest-node response-work versus query Zipf skew, sharded (balanced policy) versus unsharded (log-scale y-axis). The benefit grows with skew; the arrow marks the 192-to-50 reduction at Zipf 1.21.2. Meanwhile, caching with certificate re-validation keeps measured candidate-acceptance correctness at 1.0001.000, versus 0.56970.5697 for a design that trusts cached postings without re-validation, as reported in Appendix D.6. The safe-cache result additionally assumes that mismatches between authenticated shard-manifest digests reach readers; we do not measure mismatch-transport delay or the temporary recall loss of a reader that has not yet learned the new layout. E.6 Descriptor Migration We construct 512 same-lineage, same-namespace reindexing cases from the augmented corpus, selecting old and new descriptor versions with disjoint publication-key sets. Both sets are reached by real query probes at Lq=128L_q=128. The resulting 20,276 query observations receive controlled switch times from old to new keys within one normalized rollout unit. We use uniform, front-loaded, and back-loaded switch profiles. During an active migration window, a Move hint is modeled as successful resolution of an old-key lookup; the metric measures discoverability under this model and does not charge additional anchor-resolution lookups. We sweep the dual-publication window Δmig _mig over 0,0.1,0.25,0.5,0.75,1,1.5\0,0.1,0.25,0.5,0.75,1,1.5\. Without Move hints, minimum discoverability is 00 at update time: the selected key sets are disjoint and the modeled observations have not yet switched. A window covering the full rollout reaches minimum discoverability 1.0001.000 under all three profiles. This follows the model’s bounded switch times and successful Move resolution. Shorter windows preserve discoverability initially and reduce the subsequent loss. Under uniform rollout, a half-unit window raises minimum discoverability to 0.4960.496 and lowers the integrated discoverability shortfall from 0.5020.502 to 0.1290.129. Figure 10 shows the window sweep. Figure 10: Minimum discoverability in the controlled reindexing model under uniform rollout. Old and new publication-key sets are disjoint; query observations switch within one rollout unit. A one-unit Move window covers that interval. The one-unit window places 4,096 Move hints at old publication keys, with total residence time of 4,096 hint–rollout units. Extending the window to 1.51.5 raises residence time to 6,1446,144 without improving discoverability in this workload. E.7 Freshness and Read-Repair For silent provider loss, we use 512 lineages and 14,019 query-weighted observations with controlled residual lease phases. Stale exposure is the weighted fraction of postings whose leases remain valid after the provider disappears. With a one-unit lease, the stale-exposure integral is 0.4990.499 and the p95 stale window is 0.9510.951 units; exposure reaches zero by one unit. Plain TTL with the same timeout and phases gives the same curve. In a separate replay experiment, lineage checks reject older postings after a verified update or tombstone; plain TTL retains them until expiration. The read-repair experiment starts each of 512 lineages with two of eight responsible replicas holding the new epoch. Each query contacts three distinct replicas, with query rates weighted by corpus query hotness. Both experiment arms retain background anti-entropy at 0.250.25 per stale replica per time unit. Responsibility turnover at rates 00, 0.050.05, 0.100.10, 0.200.20, and 0.400.40 per time unit replaces a replica’s state with a randomly selected peer’s state. We run three seeds over a 40-unit horizon with a 0.05-unit step, using perfect routing. Here stale exposure is the query-weighted fraction of responsible replicas still holding the old epoch. It measures replica state before candidate verification. Convergence time is the first time all eight replicas of a lineage hold the new epoch. For both freshness experiments, the stale-exposure integral is the area under the corresponding exposure curve over the observation horizon and has units of time; the suppression detector’s ROC-AUC is a separate metric. Table 12 reports the representative turnover rate 0.100.10. Read-repair Stale-exposure integral p95 time Messages Off 3.037 17.96 0 On 1.288 8.95 1,538 Table 12: Read-repair at turnover rate 0.100.10. Times are normalized units; messages count direct read-repair messages for the 512-lineage run, averaged over three seeds. Both arms include background anti-entropy. Across all five turnover rates, read-repair lowers the stale-exposure integral from 2.9552.955–3.0893.089 to 1.2461.246–1.3171.317 and the p95 convergence time from 16.0416.04–19.2619.26 to 8.668.66–9.309.30 units, a 1.841.84–2.08×2.08× reduction in the convergence tail. The experiment models propagation of authenticated state; validating the complete control-record transport and recovery paths remains implementation work. CPU (%) RSS (MiB) System Scheduler Cache Baseline Query phase [range] Baseline Query phase [range] SemDHT Parallel Cold 0.399 0.326 [0.323, 0.328] 51.87 52.17 [52.09, 52.25] SemDHT Parallel Warm 0.411 0.291 [0.288, 0.296] 52.25 52.16 [51.76, 52.44] SemDHT Stage-barrier Cold 0.414 0.336 [0.326, 0.354] 52.12 52.50 [52.29, 52.62] SemDHT Stage-barrier Warm 0.416 0.294 [0.284, 0.307] 51.76 51.68 [51.47, 51.87] LSH Parallel Cold 0.409 0.394 [0.382, 0.408] 52.44 52.85 [52.58, 53.11] LSH Parallel Warm 0.401 0.440 [0.431, 0.449] 52.55 53.00 [52.90, 53.19] LSH Stage-barrier Cold 0.407 0.410 [0.394, 0.433] 52.24 52.68 [52.39, 52.93] LSH Stage-barrier Warm 0.398 0.431 [0.421, 0.449] 52.37 52.89 [52.62, 53.10] Table 13: Per-node resource observations in the separate 400-node deployment. Baseline and query-phase values are means of three rounds, each averaging 25 cloud nodes. Brackets give the minimum and maximum of the three query-phase batch means. CPU 100% denotes one logical core. E.8 Node Resource Measurements The resource experiment in Section 6.3 measures 25 colocated cloud node processes in a 400-node overlay. The local server has an Intel Core i9-10980XE with 36 logical CPUs and about 251 GiB of OS-visible memory. The Hong Kong VM has four Intel Xeon Platinum vCPUs and 8 GB RAM. The requester and controller run on the local server. The measured resource values are for the cloud node processes. Publication materializes the selected 50-query workload: 39,631 SemDHT postings at 1,228 keys and 46,503 LSH postings at 6,489 keys. Each system retains its frozen query plans and the replica, quorum, paging, and lookup-concurrency settings from Section 6.3. The eight conditions combine the two systems, parallel and stage-barrier scheduling, and cold and warm requester certificate caches. Each condition runs once in each of three rounds, with the same 50 query IDs and query order. Condition order is randomized within each round. These repetitions provide 24 complete batches. An interrupted 16-query attempt is retained separately and excluded from every resource summary; its replacement supplies the complete batch. Cold and warm refer to the requester certificate cache; operating-system file caches are not reset. The sampler reads cgroup v2 CPU usage and main-process RSS from /proc at nominal 10-second intervals. It tracks process identity and phase transitions. We exclude intervals crossing phase boundaries and use actual elapsed time for CPU rates and weighted RSS means. The complete batches contain 57,325 node samples with no recorded sampling errors, process-identity changes, or CPU-counter resets. Recomputing CPU rates from the raw counters reproduces the recorded rates. Table 13 reports baseline means and variation among the three query-phase batch means. The resource summaries retain all 1,200 executions, including 493 that returned fewer candidates than expected, together with their waiting and recovery work. Time samples and colocated nodes are not independent experimental repetitions. The query phase includes certificate prewarming and gaps between queries, so it does not isolate per-query CPU cost.

Instant research discovery