arXiv CSopen access

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

S EM DHT: Certified Semantic Discovery for Peer-to-Peer Agent Networks over Exact-Key DHTs Taotao Wang†

Chonghe Zhao†

Shengli Zhang

Soung Chang Liew

Shenzhen University

Guangzhou University

Shenzhen University

The Chinese University of Hong Kong

arXiv:2609.23539v1 [cs.NI] 20 Sep 2026

Abstract

tant 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. 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 fol-

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 exactkey 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 S EM DHT, a certified semantic index for discovering agentaccessible 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, S EM DHT achieves recall@10 = 0.955 against exact embedding-space neighbors and 0.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.95 with 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, S EM DHT achieves mean completion-time speedups of 3.64× and 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 assis† Equal contribution. Correspondence: [email protected].

1

(a) Shared semantic neighborhood hard constraints match ⇒ n(d) ∈ Nq

cell 17 centroid µ17

cell 42 centroid µ42 query q (zq )

descriptor d (zd ) same cell IDs: Zq ∩ Zd = {17, 42} similar within-cell residual codes

(b) Bounded exact-key overlap descriptor d publication-key set Kpub (d)

κ1

query q budgeted probe-key set Kqry (q; Lq )

κ1

κ3

κ2

(c) Exact-key responsibility routing ···

provider pd certified publish

exact-key overlap {κ1 , κ3 }

publish cap |Kpub (d)| ≤ ρ(1 + J)

κ3

κ7

unchanged DHT responsibility routing

···

shared key κ1

merge shortlist C (q)

requester issues q budgeted lookup lookup budget |Kqry (q; Lq )| ≤ Lq

ordinary DHT routing reaches the posting-list service

Figure 1: S EM DHT compiles semantics before the DHT. (a) Matching hard constraints ensure that the descriptor’s namespace label n(d) belongs to the query’s allowed namespace-label set Nq ; nearby embeddings zq , zd yield overlapping coarse-cell ID sets Zq , Zd and similar residual codes. (b) These codes become exact keys: the publication-key set Kpub (d) and budgeted probekey set Kqry (q; Lq ) overlap on κ1 , κ3 . Publication uses at most ρ(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 Lq . (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. 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, S EM DHT 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× and 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.

lows from its descriptor before accepting it. We present S EM DHT, 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, S EM DHT achieves recall@10 = 0.955 against exact embedding-space neighbors and 0.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 LSHon-DHT sweep at recall 0.95 with 7.7× fewer exact-key lookups and reduces publication fan-out from 16 to 10. We

2 Problem and Overview S EM DHT 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

2

Semantic keys, certified publication, and budgeted lookup d¯ to committee; Certd , Σd to provider

Provider Clinic service assistant agent / API n(d), xd

Semantic sketch coarse cells residual codes Kpub (d)

Anchor committee recompute Kpub (d) issue Certd , Σd

Exact-key DHT route each key to responsible peers

Two cells, two families: six publication keys Every lookup consumes the query’s budget Lq .

provider publishes certified postings

Service requester Personal assistant Eye-clinic query Nq , xq , Lq

Query sketch allowed namespaces coarse cells residual codes

Probe stages P1 , P2 , P3 precision before recall Kqry (q; Lq )

Posting-list service verify and store postings per key

Verify and merge fetch descriptors rank shortlist C (q)

budgeted 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. 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.

with the same namespace label n(d) if they use the same interface contract, admission class, and execution-policy class; their respective texts xd distinguish their specialties. Conversely, an eye clinic offering a different conversational interface requires support for that contract before it can be included through Nq . 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 namespacecompatible population for query q is

2.1 Discovery and Lookup Budget A provider advertises a descriptor version d containing compatibility conditions, semantic text xd , and a retrieval URI for the complete descriptor d.¯ This URI locates the description; it is not, by definition, the service’s invocation endpoint. The namespace label n(d) encodes the compatibility conditions to delimit the compatible search scope. A requester issues q = (Nq , xq , kq , Lq ), specifying allowed namespace labels Nq , task text xq , shortlist size kq , and physical lookup budget Lq . In the appointment example, the clinic publishes a descriptor version d whose semantic text xd describes eye-clinic appointment queries; its complete descriptor d¯ records the interface contract and other compatibility conditions summarized by n(d). Discovery has two parts. First, the assistant chooses Nq 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) ∈ Nq . Second, the assistant expresses “Find a service for querying eye-clinic appointments” in xq ; semantic matching compares this intent with xd 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 xd advertises the query capability; current slots come from the service. An eye clinic and a dental clinic can publish descriptors

Dq = {d ∈ D : n(d) ∈ Nq }.

(1)

S EM DHT retrieves and ranks candidates from Dq using semantic matching. To retrieve candidates, S EM DHT 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 ) hops, where Nnet 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 Lq . 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 Lq ; we measure their communication and processing costs separately. Thus, Lq bounds the number of physical lookups, while kq specifies the desired shortlist size. If the budgeted lookups yield fewer than kq eligible candidates, the requester returns a shorter shortlist.

3

2.2 Publication and Query Workflow

3 Semantic Index

For the clinic service provider introduced above, publication begins by encoding its semantic text xd 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 residualcode families. Following the key construction described in Section 3, it then derives a publication-key set Kpub (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) from the complete descriptor d¯ and issues a membership certificate Certd binding the descriptor to this publicationkey set. It authenticates Certd with a committee signature Σd . At each key, the provider publishes a posting containing a provider-signed posting body, the membership certificate Certd , the committee signature Σd , and a Merkle inclusion proof that the key belongs to the certified set. S EM DHT 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 Nq and expresses its discovery task in xq , such as “Find a service for querying eye-clinic appointments.” It encodes xq 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 P1 , neighboring-code and additional-cell precision keys in P2 , and recall keys in P3 . The keys selected within the physical lookup budget Lq form the budgeted probe-key set Kqry (q; Lq ). It then verifies returned postings, merges them by descriptor commitment, fetches complete descriptors, and ranks eligible candidates to produce the candidate shortlist C (q), following the verification and ranking procedure described in Section 4.

S EM DHT’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¯ be the complete descriptor for version d. It records the provider public key pk pd , a provider-local capability identifier, compatibility fields, semantic text xd , metadata, and a retrieval address ptrd . With cryptographic hash H and deterministic canonicalization Canon, its commitment is ¯ Cd = H(Canon(d)).

(2)

The requester verifies a fetched descriptor against Cd . Whereas Cd identifies one descriptor version, a stable lineage handle ιd , derived from the provider key and capability identifier, identifies the same capability across versions. The anchor committee assigns a lineage epoch ed 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.¯ We collect the descriptor’s hard compatibility requirements in a namespace label, defined as n(d) = (τd , σd , ψd ),

(3)

where τd is an admission class, σd identifies a compatible input/output contract, and ψd is an execution-policy class. For the appointment-query interface introduced in §2.1, an illustrative label uses τd = generic, which adds no admission distinction, σd = appointment-query-v1 identifies the department/date request and appointmentrecord response contract, and ψd = web-enabled permits external network access. These values specify the compatibility scope; the eye-clinic specialization remains in xd . 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 xd ; adding a capability under an existing contract requires no new label. A resolver maps the query’s explicit hard requirements to Nq ⊆ Rν , retaining the task wording in xq . Providers, anchor committees, and requesters share a signed, contentaddressed 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

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.

4

that identical inputs yield identical labels, cell IDs, and residual codes across participants. Queries and descriptors are encoded separately.

µ9 cell 17 (local, zoomed) µ42

3.2 Coarse Cells and Residual Codes

b = 01

b = 00 rd,17

µ17

To support semantic matching within the compatibility scope defined by namespace labels, the provider converts xd 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 ), which the two layers discretize:

µ17 Zd = Topρ (zd ;Uν ) = {17, 42}, ρ = 2

b = 11

b = 10

(1)

bd,17 = 00

Figure 3: Left: zd selects top-ρ=2 coarse-cell IDs Zd = {17, 42} (blue/orange), while a farther centroid µ9 (gray) is not selected. Right: inside cell 17, the residual rd,17 = zd − µ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 layer: The shared codebook is Uν = Mcode {µc }c=1 , where Mcode is the number of centroid vectors and µc is the centroid of coarse cell c. Sorting the cell IDs c by cosine distance from zd to µc gives the descriptor’s coarse-cell ranking. We write Zd = Topρ (zd ;Uν ) for the set of the top-ρ cell IDs, where ρ is the descriptor’s coarse-cell depth. Retaining more than one cell (ρ = 2 or 3 in practice) covers descriptors near a cell boundary. For each selected cell ID c ∈ Zd , the residual vector rd,c = zd − µc represents the descriptor’s position relative to centroid µc .

P κν, j (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 ( j) n(d) and bd,c to obtain  [ ( j) J P Kpub (d) = {κνR (n(d), c)} ∪ {κν, j (n(d), c, bd,c )} j=1 .

• Residual-code layer: Each of J independently seeded residual-code families maps rd,c to an ℓ-bit residual ( j) ( j) code bd,c = Codeν (rd,c ), j = 1, . . . , J. Our concrete instantiation uses sign projection: family j contains projection vectors a j,r , r = 1, . . . , ℓ, and packs the signs ( j) of ⟨a j,r , rd,c ⟩ into bd,c .

c∈Zd

(6) Each selected cell contributes at most 1 + J keys, yielding

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, 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 − µ17 has sign pattern 00 under residual-code fam(1) ily j = 1, giving bd,17 = 00. A query that also selects cell 17 and obtains code 00 under this family later derives the corresponding probe key that matches d’s publication key. Coarse-cell overlap provides coverage, while residualcode agreement provides discrimination within a shared cell. Multiple residual-code families mitigate projectionboundary 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.

|Kpub (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 ) and a ranked cell sequence Zqord ; its first ρq IDs form the primary-cell set Zq . For each cell, it computes residual codes using the provider’s construction and substitutes n ∈ Nq into the key constructors. Probes follow three stages. P1 (q) contains exact precision keys for primary cells. P2 (q) probes codes at Hamming distances one through rH from the query’s residual codes in Zq , then exact precision keys for secondary cells ranked ρq + 1 through ρext . Here rH = 0 disables neighboring-code probes, and ρext bounds the considered cell ranks. P3 (q) contains recall keys for Zq in cell-rank order. Within each stage, the requester interleaves allowed namespace labels. The logical sequence is
P(q) = Dedup P1 (q)∥P2 (q)∥P3 (q) , (8)

3.3 Exact Keys and Bounded Publication For each c ∈ Zd , 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),

zd

where ∥ concatenates sequences and D EDUP retains each key’s first occurrence. Appendix A.3 gives the deterministic ordering rules.

(4) 5

With one entry point, unsharded keys, and no lineageresolution lookups, each probe costs one lookup, giving the budgeted key set

transition. It recomputes the namespace, embedding, and publication-key set under ν, then commits to the sorted keys with a Merkle tree [24]:

Kqry (q; Lq ) = set(PrefLq (P(q))),

rootd = MerkleRoot(sorted(Kpub (d))).

(9)

(10)

The membership certificate Certd binds this root to Cd , the provider key, namespace, configuration, lineage, epoch, predecessor, live or tombstone state, and lease. The committee signs it as Σd . For each target key κ, the provider constructs a posting body md,κ that binds κ, descriptor commitment Cd , retrieval address, lease, and certificate hash. The body includes the provider’s signature. It publishes

where PrefL 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 Lq 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

Posting(d, κ) = ⟨md,κ , Certd , Σd , πd,κ ⟩,

(11)

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.

where πd,κ proves the key’s inclusion under rootd . The signed certificate supplies the provider key, so verification does not require fetching the complete descriptor. Appendix A.5 specifies the record fields.

4.1 Threats and Certification Assumptions

4.3 Posting and Candidate Verification

An adversary may control providers, routing peers, and up to fA 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 nA -member committee with signing threshold tA . With unforgeable signatures and collision-resistant hashes, fA < tA ensures that a valid committee signature includes an honest member that recomputes the publication keys. Availability also requires nA − fA ≥ tA 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.

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 Certd . 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). Keeping one active posting per (Cd , κ) 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 Lq is exhausted; unresolved lineages supply no candidates. The requester verifies returned postings using its own time and observations. It merges accepted postings by Cd , fetches each complete descriptor once, and checks its commitment, provider key, namespace, and lineage against the certificate. After checking n(d) ∈ Nq and resolving versions, it computes zd = Encν (xd ) from the verified descriptor and ranks by the base score:

4.2 Certified Publication The provider submits the complete descriptor and a signed registration request to the committee assigned to lineage ιd . The stable anchor key κA (ιd ) = H(“A”∥ιd ) locates that lineage’s certified state. The committee verifies the provider signature, descriptor commitment, and requested lineage

sbase (d | q) = sim(zq , zd ).

(12)

Here sim denotes cosine similarity, and C (q) contains up to kq highest-scoring eligible candidates. Certificate consistency and freshness determine eligibility before ranking. A 6

rejected posting alone does not attribute misconduct to its provider: a peer can alter proofs or replay old postings.

gest 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.

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 postinglist 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 Lq ; 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 Lq , 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.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 postingspecific 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, completedescriptor 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 shardlayout mechanisms are evaluated separately, as detailed in Appendices C and D.

5 Implementation We implement S EM DHT’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.

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.

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 di7

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 ). 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 384dimensional 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 = 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.

recall target

(ρ, J, ℓ, rH , Lq )

recall

exposure

fan-out

0.90 0.95 0.97

(3, 4, 3, 1, 32) (2, 3, 3, 1, 128) (3, 2, 3, 2, 64)

0.902 0.950 0.970

62.6% 72.8% 80.1%

15 8 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.

recall@10

1.00 0.75

0.97 0.90

0.95

0.50 0.25

432 budgeted operating points 276 four-objective Pareto points recall-exposure frontier

0.00

0.0 0.2 0.4 0.6 0.8 1.0 exposure (fraction of reachable candidates)

Figure 4: Recall versus exposure for 432 budgeted operating points from 48 (ρ, J, rH ) configurations on the combined corpus. Blue points are the 276 operating points retained by the four-objective Pareto filter; the curve traces the twodimensional recall–exposure frontier. The three marked operating points correspond to Table 1. erating 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 rH at fixed Lq 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.90, the smallest observed exposure is 62.6% of the reachable population. Raising recall to the sweep’s maximum of 0.9976 requires 95.0% exposure. Two additional codebook seeds preserve the ordering of the three representative points: their recall ranges are 0.902–0.919, 0.950–0.960, and 0.970–0.978, respectively. Exposure varies by 3–5 percentage points across seeds. Appendix E.3 reports the query-bootstrap intervals and the baseline selection details.

6.2 Retrieval Effectiveness and Index Efficiency On the real-only corpus, before density augmentation, one calibrated configuration reaches recall@10 = 0.955 against exact cosine neighbors at physical lookup budget Lq = 32, and 0.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 = ρ, 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} (48 configurations, with ℓ and ρ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. We apply the four-objective Pareto filter to all 432 op-

Publication and lookup cost. We compare S EM DHT with LSH-on-DHT over the same namespaces and corpus, selecting configurations at matched recall. The LSH sweep combines signature widths wLSH ∈ {4, 6, 8}, table counts T ∈ {1, 2, 4, 8, 16}, and Hamming radii rH ∈ {0, 1, 2}: 45 configurations at nine budgets, yielding 405 operating points. For each system, we linearly interpolate each con-

8

200 100 0

254

102 31

0.80

34

33

residual-code model pℓ r (θ) measured (marker area ∝ observations) , H

precision-stage hit probability

mean exact-key DHT lookups issued

LSH-on-DHT (tuned) SemDHT 173

110 65

0.90 0.95 0.97 recall@10 target

1.0 0.8 0.6 0.4

sparse tail (n=2, n=4)

40 60 80 100 residual angle θ (degrees)

Figure 5: Mean exact-key DHT lookups issued to reach a given recall target, S EM DHT versus the best-tuned LSH-onDHT configuration at that target, using the data presented in Table 10. S EM DHT is cheaper at all four targets; the gap is largest at recall 0.95 and narrows at 0.97 because the matched LSH optimum switches from the hash-width/radius pair (wLSH , rH ) = (8, 2) to (6, 1).

Figure 6: Measured single-family hit probability versus residual angle θ at a representative calibrated configuration (ρ=2, ℓ=3, rH =1), against the closed-form pℓ,rH (θ ) 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 wellpopulated 30◦ –100◦ range and only visibly departs in the sparsely observed tails.

figuration’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, 32} and search breadth efSearch ∈ {8, . . . , 256}. We also evaluate exact-key hashing of capability names and an inverted BM25 index [32] within the same namespaces. At recall 0.90, S EM DHT and LSH expose 62.1% and 61.6% of the reachable candidate population, while issuing 33.7 and 173.2 exact-key lookups on average. At recall 0.95, both expose 72.7%, with 32.9 versus 253.5 lookups. The corresponding lookup reductions are 5.1× and 7.7×; publication fan-out at recall 0.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.97, where the selected LSH signature width and probe radius change. HNSW reaches recall 0.985 at MHNSW = 16 and efSearch = 16, while exact FlatIP reaches 1.0. Their reported times measure local batch CPU work. With verbatim API-name matching, exact-key hashing reaches recall 0.065. BM25’s top-10 ranking reaches about 0.398 recall with mean publication fan-out 26.2 (p95 = 39); its candidate population contains enough relevant items for oracle recall 0.953. This difference separates candidate coverage from ranking quality. Two LSH seeds give recall 0.94–0.96 and preserve the lookup-cost ordering at the tested targets.

for a precision-key hit, as described in Section 3.2. We test how well the angle-based prediction and approximateindependence 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,858 namespace-correct nearest pairs and 80,830 random reachable negative pairs. Figure 6 compares measured and predicted single-family hit probabilities. For the residual-code component with J = 4, the observation-weighted mean absolute error is 0.0022. The maximum normalized conditional covariance between residual-code families is 0.0131, below the prespecified 0.05 threshold for approximate independence. At a different configuration (ρ = 4, ℓ = 4, rH = 1, J = 4), the sparse 100◦ –110◦ residual-angle bin shows a measured hit rate of 0.581 against a predicted 0.627, an error of −0.0461. This bin covers 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

Residual-code hit model. Multiple residual-code families give a query–descriptor pair additional opportunities

9

Same-region Frankfurt Cross-region Eight regions Requester Frankfurt

SemDHT

VMs Peers/VM vCPU RAM 8 8 1

25 25 –

4 8 GB 4 8 GB 8 16 GB

Lookup completion (s)

Deployment Region

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.

Same region

LSH

Cross region

30 20 10 0

Mean

P95

Mean

P95

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.

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 S EM DHT and LSH use the same certified posting format, replica policy, and posting-list service. 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 S EM DHT 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.

Placement

System

Lookups

RPCs

MiB

Same Same Cross Cross

S EM DHT LSH S EM DHT LSH

32.59 256.00 32.59 256.00

130.91 777.85 130.91 777.85

2.913 2.945 2.913 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. Completion time and lookup work. Figure 7 presents completion times with parallel scheduling and a cold certificate cache. S EM DHT 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× and 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. Table 3 reports per-query work. The probe-key budgets are upper bounds; S EM DHT 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 S EM DHT 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.

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.

Scheduling and completion. Table 4 compares scheduling policies while holding each query’s keys fixed, for both

10

Placement System

Cache Mean difference [95% CI] (s) P95 difference [95% CI] (s)

Same Same Same Same Cross Cross Cross Cross

Cold Warm Cold Warm Cold Warm Cold Warm

S EM DHT S EM DHT LSH LSH S EM DHT S EM DHT LSH LSH

0.157 [0.075, 0.235] -0.091 [-0.139, -0.045] -0.067 [-0.175, 0.044] 0.000 [-0.118, 0.116] 2.679 [2.540, 2.834] 2.259 [2.114, 2.409] 3.224 [2.947, 3.517] 3.085 [2.833, 3.339]

1.118 [-0.948, 2.124] -0.127 [-0.246, 0.291] 0.014 [-0.618, 0.742] -0.064 [-0.521, 0.809] 4.133 [2.315, 5.101] 0.854 [-0.478, 3.830] 2.973 [1.794, 4.392] 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. 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 S EM DHT 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 S EM DHT. 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 S EM DHT’s lookup-count advantage. With cold caches and stage barriers, S EM DHT achieves mean completion speedups over LSH of 3.48× within a region and 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.

Validation path Cold certificate Verified certificate cached

Mean (ms)

95% CI (ms)

10.6496 0.0487

[10.5570, 10.7422] [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 S EM DHT with parallel scheduling, warm-cache mean completion is 3.009 s within a region and 6.836 s across regions, compared with coldcache 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.

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 µs, a 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.

11

Scheduler

Cache S EM DHT

Parallel Cold Parallel Warm Stage-barrier Cold Stage-barrier Warm

LSH S EM DHT

0.326 0.394 0.291 0.440 0.336 0.410 0.294 0.431

2.73× without membership verification with membership verification

RSS (MiB) LSH

exposure amplification

CPU (%)

52.17 52.85 52.16 53.00 52.50 52.68 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.

2.5 2.0 1.5 1.0

0%

1% 5% 10% 20% 50% malicious provider fraction

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× across the sweep.

The query phase includes certificate prewarming, waiting, and background DHT activity. Across these conditions, S EM DHT 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 S EM DHT and 52.68–53.00 MiB for LSH. Baseline CPU means are similar, at 0.398–0.416%.

Provider quotas. At Qns = 128, admission-layer quota accounting retains 99.42% of honest descriptors and reduces honest recall by 0.0023. Under a fixed attack budget, stuffing amplification rises from 1.137× with one attacking provider per namespace to 2.081× with 16 attacking providers. The quota limits one admitted provider’s publication volume, while additional identities supply additional quota slots.

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.

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.10 per normalized time unit, read-repair lowers the p95 time for all eight replicas to hold the new epoch from 17.96 to 8.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.

Implementation checks. Before network replay, a fourpeer 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.

Multi-view lookup and storage. Appendix E.4 evaluates entry-path suppression. At capture probability f = 0.20, repeating the complete probe prefix through two entries raises attacked recall from 0.7957 to 0.9191 with twice the lookup cost. At fixed cost, the shorter repeated prefix reduces clean recall from 0.9500 to 0.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.

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% to 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% malicious providers, skipping membership verification produces 1.692× query-weighted exposure; verification retains the honest recall of 0.9500. Figure 8 shows the full sweep: amplification reaches 2.73× without membership verification and remains 1.000× with it. 12

7 Related Work

for skewed lookup demand [29]. Load-balancing schemes redistribute key ranges or items across peers [18]. These mechanisms complement S EM DHT’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.

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]. S EM DHT 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]. S EM DHT connects task matching to exact-key responsibility and posting-list retrieval, with a budget for network lookups.

8 Discussion and Conclusion 8.1 Limitations and Future Work S EM DHT 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.

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]. S EM DHT 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 multiattribute resource constraints, and Mercury supports range queries with overlay load balancing [2, 27, 4]. S EM DHT 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; S EM DHT 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

13

8.2 Conclusion

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.

We presented S EM DHT, 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-tokey 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. S EM DHT thus connects semantic retrieval quality to enforceable publication rules and explicit network budgets within a decentralized discovery protocol.

[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.

References

[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.

[1] A2A Project. Agent2Agent Protocol Specification. https://a2a-protocol.org/v0.3.0/ specification/. Version 0.3.0. Accessed September 20, 2026.

[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.

[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.

[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.

[3] Juan Benet. IPFS—content addressed, versioned, P2P file system. arXiv preprint arXiv:1407.3561, 2014.

[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.

[4] Ashwin R. Bharambe, Mukesh Agrawal, and Srinivasan Seshan. Mercury: Supporting scalable multiattribute range queries. In Proceedings of ACM SIGCOMM, pages 353–366, 2004.

[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.

[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.

[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.

[6] Dan Boneh, Ben Lynn, and Hovav Shacham. Short signatures from the Weil pairing. Journal of Cryptology, 17(4):297–319, 2004.

[17] Simon Josefsson and Ilari Liusvaara. Edwards-curve digital signature algorithm (EdDSA). RFC 8032, RFC Editor, 2017.

[7] Carsten Bormann and Paul Hoffman. Concise binary object representation (CBOR). RFC 8949, RFC Editor, 2020.

[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.

[8] Miguel Castro, Peter Druschel, Ayalvadi Ganesh, Antony Rowstron, and Dan S. Wallach. Secure routing 14

[19] Naama Kraus, David Carmel, Idit Keidar, and Meni Orenbach. NearBucket-LSH: Efficient similarity search in P2P networks. arXiv preprint arXiv:1511.07148, 2015.

[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.

[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.

[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.

[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.

[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.

[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.

[32] Stephen Robertson and Hugo Zaragoza. The probabilistic relevance framework: BM25 and beyond. Foundations and Trends in Information Retrieval, 3(4):333– 389, 2009.

[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.

[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.

[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.

[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.

[25] Model Context Protocol. MCP Registry. https: //github.com/modelcontextprotocol/ registry. Accessed September 20, 2026.

[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.

[26] Model Context Protocol. Tools. https: //modelcontextprotocol.io/ specification/2025-06-18/server/ tools. Specification dated June 18, 2025. Accessed September 20, 2026.

[36] Liang Wang and Jussi Kangasharju. Measuring largescale distributed systems: Case of BitTorrent Mainline DHT. In Proceedings of the IEEE International Conference on Peer-to-Peer Computing (P2P), pages 1–10, 2013.

[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.

[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.

[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+ realworld APIs. In The Twelfth International Conference on Learning Representations, 2024.

[38] Yuntao Wang, Shaolong Guo, Yanghe Pan, Zhou Su, Fahao Chen, Tom H. Luan, Peng Li, Jiawen Kang, and

15

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.

16

A Protocol Details

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 ), 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 Nq ⊆ Rν ; the original task wording remains in xq . A descriptor is eligible exactly when n(d) ∈ Nq . 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 xq . A client supporting multiple registered contracts may include their labels in Nq ; 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), and probe-key construction includes only labels in Nq . 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) ∈ Nq after fetching the complete descriptor. The anchor committee validates the registered descriptor fields and recomputes the namespace label before certifying

A.1 Complete Descriptor and Canonicalization We use d to denote a particular version of a capability descriptor and d¯ to denote the complete descriptor for that version. We write the complete descriptor as the tuple d¯ = (idd , pk pd , τd , σd , ψd , xd , metad , ptrd ),

(13)

where pd is the provider that owns and publishes d. A provider is an authenticated principal identified by its public key pk pd . The field idd is a provider-local capability identifier that remains fixed across versions of the same capability; τd is a protocol-level admission class, with a common generic value when no additional admission distinction is required; σd identifies a canonical interfacecompatibility family, which groups descriptors with compatible input/output requirements (e.g., accepting a department and date and returning appointment records); and ψd is a coarse execution-policy class, such as no-network or web-enabled. The field xd 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 metad carries freshness and version hints (e.g., the declared software version, model revision, and last-update time), while ptrd 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(·) fixes field order and strips noise. Let H denote the protocol’s cryptographic hash function. The descriptor commitment is ¯ as defined in Equation (2). After fetchCd = H(Canon(d)), ing the complete descriptor through ptrd , the requester applies the same canonicalization and hash functions and compares the result with Cd to verify that the retrieved content matches the referenced descriptor version. Here, Cd 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”∥pk pd ∥idd )

(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 ed , assigned by its anchor committee. The requester deduplicates postings by descriptor commitment Cd and resolves updates and revocations by lineage handle ι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, 17

for i = 1, . . . , T , where H is a cryptographic hash function. A requester computes zq = Encν (xq ) 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 neighboringcode 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 S EM DHT at matched recall. Section 3 develops the two-layer semantic sketch used by S EM DHT to allocate coverage and discrimination to separate keys.

the publication-key set, as described in Section 4.2. When Nq contains multiple labels, the requester constructs a probe sequence for each label and interleaves these sequences under one physical lookup budget Lq , following the schedule in Section 3.4. A.3 Deterministic Probe Ordering The requester computes zq = Encν (xq ) and orders the coarsecell IDs by distance to obtain Zqord . Its primary coarse-cell set Zq contains the first ρq IDs. For each considered coarse cell c, the requester computes rq,c = zq − µc and residual codes ( j) bq,c using the same construction as the provider. Substituting ( j) n ∈ Nq , c, and bq,c 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) for top-cell precision probe keys, P2 (q) for neighboring-code and secondary-cell precision probe keys, and P3 (q) for recall probe keys. P1 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 rH (rH = 0 disables this step), P2 recovers projectionboundary cases by substituting into Equation 5 codes at ( j) Hamming distances 1 through rH from bq,c , ordered by distance, cell rank, family index, and residual-code bytes; it then adds exact precision probe keys for cells ranked ρq + 1, . . . , ρext , where ρext is the largest coarse-cell rank admitted for secondary-cell probing. P3 orders recall probe keys by cell rank. Within each stage, the per-label probekey 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 D EDUP 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) 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 Lq . A descriptor can be retrieved through a shared logical key when Kpub (d) ∩ Kqry (q; Lq ) ̸= 0. /

A.5 Registration and Certified Records For lineage ιd , the stable anchor key is κA (ιd ) = H(“A”∥ιd ). The anchor committee assigned to this key, H (ιd ), certifies successive descriptor versions without changing its assignment when descriptor content changes. The provider submits ¯ d , ν, ed , leased , sigreg RegisterAnchor(d) = ⟨ιd , d,C pd ⟩, (16) reg

where leased is the requested expiration time and sig pd signs all preceding fields. The anchor committee verifies the signature using the provider public key in d,¯ checks ¯ derives ιd from pk p and idd (Eq. (14)), Cd = H(Canon(d)), d and validates the requested transition against its lineage state. The anchor committee then recomputes n(d), zd , and Kpub (d) under configuration ν. It constructs a Merkle tree over the sorted publication-key set and issues the membership certificate Certd = ⟨ιd ,Cd ,pk pd ,ν,n(d),ed ,leased ,rootd ,prevd ,moded ⟩, rootd = MerkleRoot(sorted(Kpub (d))), (17) with committee signature Σd over Certd . The provider public key is copied from the verified complete descriptor. Carrying this key in Certd lets a posting-list service verify a posting without first fetching d.¯ The predecessor commitment prevd and state moded ∈ {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 = 0, prevd = ⊥, and moded = live. For each target logical key κ, the provider creates a posting body

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 ) and applies T independently seeded LSH functions h1 , . . . , hT . Descriptor d is published at the keys κiLSH (d) = H(“LSH”∥ν∥n(d)∥i∥hi (zd )),

md,κ = ⟨κ,Cd , pk pd , n(d), ptrd , ιd , ed , leased ,

(18)

post

H(Certd ), sigd,κ ⟩, post

where ptrd locates the complete descriptor and sigd,κ signs all preceding fields. The posting sent to the posting-list service is the envelope in Equation (11), where πd,κ proves κ’s

(15) 18

inclusion under rootd . Ordinary DHT routing locates the responsible peers; their posting-list services perform acceptance and storage.

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 P(q), preserving the stage order in §3.4. Every action consumes physical lookup budget. In the unsharded case, |Eq | entries can repeat at most ⌊Lq /|Eq |⌋ keys within budget Lq . 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

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,κ , Certd , κ) 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(Certd ). Acceptance requires five checks:

Πd,κ,u = ⟨(u, Pi ), κ, Bd,κ,u , ts, H(Certd )⟩,

Accept(d, κ) = 1 ⇐⇒ Bind(md,κ , Certd , κ)

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 Bd,κ,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.

∧ VerifySigpk p (md,κ ) d

∧ VerifyThresh(Certd , Σd ) ∧ VerifyMerkle(rootd , κ, πd,κ ) ∧ FreshAccept(d,tnow ). (19) The provider-signature check uses the key in Certd . 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 , κ), 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 Qns 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.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 Cd 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 Certd , and requires n(d) ∈ Nq . Descriptor versions are then resolved by lineage using §C.4. This resolution distinguishes lease renewal from conflicting state. Define the certified state identity hstate (Certd ) = H(ιd ∥Cd ∥pk pd ∥ν∥n(d)∥ed ∥rootd ∥prevd ∥moded ).

A.7 Multi-View Lookup and Ranking A.7.1

(20)

(21)

A monotonic lease renewal preserves this identity; the full H(Certd ) 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 Vq (d) ⊆ Vq contain the views that returned an accepted posting, and let Bq (d) =

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 | } drawn from distinct routing zones or bootstrap neighborhoods. A view is an entry-point and probe-stage pair (u, Pi ), giving the configured view set Vq = Eq × {P1 , P2 , P3 }. A lookup action (u, κ) probes logical key κ through entry point u. For each 19

κ,u Bd,κ,u contain its distinct authenticated responders. De-

S

independent after conditioning on that geometry, then

fine

J Pr[BJ | q, d, A] ≈ 1 − 1 − p(q, d) .

  |Bq (d)| |Vq (d)| , repq (d) = min 1, , covq (d) = 3|Eq | b0 (22) where b0 > 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. Entrypath comparisons use matched (Pi , κ) actions across entry points; disjoint keys would confound path effects with semantic selection. Among verified, namespace-eligible, current descriptor versions, the requester ranks by

(24)

Averaging over residual geometries and applying the probability product rule gives the precision-key hit-probability model Phit (δ ) = Pr[A ∩ BJ | δ ] = Pr[A | δ ] Pr[BJ | A, δ ] i h
J ≈ gρ,ρq (δ ) · E 1 − 1 − p(q, d) A, δ .

(25)

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 residualcode families as conditionally independent. The expectation remains outside the nonlinear union because, in general, E[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 ) be the angle between the query and descriptor residuals. Under sign projection, one bit agrees with probability pbit (θ ) = 1 − θ /π. With ℓ independent projection bits, the probability that the two residual codes differ in at most rH positions is rH  
i ℓ 1 − pbit (θ ) pbit (θ )ℓ−i . (26) pℓ,rH (θ ) = ∑ i i=0

score(d | q) = λsem sim(zq , zd ) + λcov covq (d) + λrep repq (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 C (q). Appendix E.4 evaluates the coverage signal and the recall–cost trade-off of repeated probes.

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 ∩ Zd 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 Lq truncates the logical probe sequence. The model excludes schedule-dependent secondary-cell and P3 recall paths. For a namespace-eligible query–descriptor pair, let δ (q, d) = 1 − sim(zq , zd ). In this subsection, conditioning on δ abbreviates conditioning on δ (q, d) = δ . Define the coarse-overlap event A = {Zq ∩ Zd ̸= 0}, / and let BJ 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 ∩ BJ occurs. The coarse-cell overlap probability is gρ,ρq (δ ) = Pr[A | δ ]. Conditioned on a realized pair satisfying A, let 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

This is exactly the probability that the descriptor’s code lies within the query’s Hamming-rH precision probes for that cell; rH = 0 reduces it to the exact-code probability pbit (θ )ℓ . The pair-level p(q, d) combines these cell-level opportunities over all cells in Zq ∩ Zd . 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.

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.

20

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.

new lease and H(Certd ). 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.

Table 7: Lineage transitions. Supersession is derived locally from an observed successor.

Version update. A change to the complete descriptor requires a new epoch. The anchor committee checks ιd ′ = ιd , ed ′ = ed + 1, and prevd ′ = Cd , then recomputes the successor’s namespace label, semantic sketch, and publication-key set. The provider publishes the resulting postings at Kpub (d ′ ). Participants that observe Certd ′ mark lower live epochs superseded. If the publication-key set changes, the provider also installs the Move hints defined in §C.3.

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 ′ its successor. The versions share ιd ′ = ιd , while the anchor committee assigns ed ′ = ed + 1 and sets prevd ′ = Cd in Certd ′ , 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 ) 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.

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 Cd , 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 ). 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.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.

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 , the provider publishes d ′ at its publication keys and leaves a Move hint at each old publication key:

Lease renewal. The anchor committee renews only its current live epoch. At approval time tapprove , it requires tapprove < leaseold ,

(27)

Moved→d ′ = ⟨ιd ,Cd ,Cd ′ , ed ′ ,tend , sigmove d→d ′ , Certd ′ , Σd ′ ⟩. (28)

where ∆max is the maximum lease duration. All fields in hstate (Certd ) (Eq. (21)) remain unchanged. The provider obtains the renewed membership certificate and committee signature, then signs replacement posting bodies containing the

Here tend = tupdate + ∆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 Certd ′ and Σd ′ makes

leaseold < leasenew ≤ tapprove + ∆max ,

21

gap unresolved, Consistentq (ι) = 0. A repeated certificate does not outweigh conflicting certified state. For a descriptor version d with a verified membership certificate, freshness at query time tq is

the successor’s certified state available to the receiving posting-list service. For storage at κ ∈ Kpub (d), the provider sends the Move hint together with Certd , Σd , and π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, prevd ′ = Cd , moded ′ = live, and tnow < tend ≤ leased ′ . 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 Lq ; a resolution that cannot finish within that budget yields no candidate for that lineage. Appendix E.6 evaluates the window’s effect on discoverability.

freshq (d) = 1 ⇐⇒ Consistentq (ιd ) = 1 ∧ ed = e⋆q (ιd ) ∧ moded = live ∧ tq < leased . A posting-list service evaluates 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

C.4 Freshness Resolution

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 Lq ; 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.

Let Obsq (ι) 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(Cert) for the epoch field of a membership certificate, the highest observed epoch is e⋆q (ι) = max{e(Cert) : Cert ∈ Obsq (ι)},

(30)

(29)

with max 0/ = ⊥. 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 Lq . Define Consistentq (ι) = 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

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 22

Here ruleκ is the deterministic commitment-to-shard assignment rule instantiated below, leasesh κ is the manifestexpiration time, and Σsh is the signature or quorum certifiκ cate 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

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 qry t, let λκ (t) and λκmnt (t) be its query and maintenance (renew/update/move/repair) arrival rates and 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: qry Λκ (t) = αq λκ (t) + αm λκmnt (t) + αn Nκ (t).

sidκ (Cd ) = 1 + (H(Cd ) mod sκ ).

(35)

It routes the posting to physical key κ [sidκ (Cd )] without recomputing the semantic sketch or requiring the provider to obtain a new membership certificate. The corresponding acceptance predicate is ShardAccept(d, κ [r] ) = 1 ⇐⇒ Accept(d, κ) = 1 (ξ )

∧ VerifyManifest(Gκ κ )

(31)

∧ r = sidκ (Cd ). (36) 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 VerifyManifest 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 is split into     Λκ (t) ′ (37) sκ = min smax , max 2, Θload

Here α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) > Θload ∨ Nκ (t) > Θsize qry

∨ λκ (t) > Θqry ∨ λκmnt (t) > Θmnt , (32) where Θ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 Lq an explicit, interpretable quantity even after sharding is introduced.

shards, where smax is the deployment shard cap. Merges use strictly lower hysteresis thresholds held for a merge window ∆merge to avoid flapping between layouts. D.3 Two Caches That Are Never Authoritative Sharding by itself does not remove manifest traffic, so S EM DHT 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] }sr=1 , ttldir κ , H(Gκ ) .

D.2 Physical Sharding without Semantic Rewriting

Each entry carries the directory-cache expiration time ttldir κ (ξ ) and the shard-manifest digest 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 postingwindow 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

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. S EM DHT 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 (ξ )

sh κ Gκ κ = κ, ξκ , sκ , {κ [r] }sr=1 , ruleκ , leasesh κ , Σκ .

(33)

The manifest assigns κ a layout epoch ξκ and sκ physical shard keys, derived as κ [r] = H(“SHARD”∥κ∥ξκ ∥r).

(38)

(34) 23

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 shardmanifest 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.

selected key’s actions before selecting another key. The requester stops after a completed group when Stopq = 1 iff |C (q)| ≥ kq and the largest score improvement among the most recent probe batch falls below ε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 = 105 lookups never used for fitting: across four churn profiles, the largest relative errors we observe are 16.1%, 10.0%, and 12.8% on p50/p95/p99 latency respectively, and all 17 predeclared consistency gates pass. At Lq = 32 under a shard capacity selected to exercise all three cost branches, a naive accounting that treats Lq as a semantic-probe count rather than a physical-lookup budget lets 56.0% of queries silently exceed their declared physical budget; billing every probe through costq (u, κ) instead keeps every single query at or under its declared budget, at a measured cost of roughly 6.5 fewer average lookups per query relative to a cold-directory baseline once the directory cache is warm.

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. S EM DHT makes this explicit rather than silently absorbing it into Lq :   κ unsharded, 1, costq (u, κ) = 1 + sκ , sharded, directory cache miss,   sκ , sharded, directory cache hit, (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(P(q)) only if

∑

costq (u, κ) ≤ Lq .

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.4. At Zipf 1.2, sharding drops the single hottest node’s absolute response-work from 17,555.9 to 6,713.9, the max/mean response-work ratio from 191.6 to 50.3, and the load Gini coefficient from 0.952 to 0.906, at a cost of roughly 5.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.

(40)

(u,κ)∈Aq (Lq )

The budgeted probe-key set is the projection Kqry (q; Lq ) = {κ : ∃u, (u, κ) ∈ Aq (Lq )}.

(41)

Thus Lq 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 Eq 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, Uq (u, κ) =

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 (κ) = 1 exactly when the requester has verified the highest layout epoch for κ among the shard manifests it has observed:

1 d (κ) + αscore ∆score \ q (κ) αgain gain q costq (u, κ)
b q (κ) − αpoll poll d (κ) . − αlat lat q

Admissibleq (d, κ) = 1 ⇐⇒ FreshLayoutq (κ) = 1

(42)

∧ freshq (d) = 1,

d estimates new-candidate yield, ∆score \ q shortlistHere gain q b d score improvement, latq latency, and pollq historical invalidcandidate exposure; the four estimates are normalized before weighting, and αgain , αscore , αlat , αpoll ≥ 0 are their utility weights. The scheduler ranks keys by the cost-weighted mean of Uq (u, κ) across u ∈ Eq , which equals estimated total utility divided by total physical cost. It completes the

(43)

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κ κ ), tsκ ⟩, where tsκ is the message timestamp, and repair on mismatch or epoch lag using the same authenticated shard-manifest mechanism as ordinary layout 24

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.

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.562 to 1.448 and the p95 convergence tail from 20.74 to 18.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 candidateacceptance safety concrete. Given the simulation’s signal that two authenticated shard-manifest digests mismatch, safe caching accepts no injected invalid candidate (measured correctness 1.000, identical to no caching) against 0.5697 for the unsafe variant, at a 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.

E Supplementary ducibility

Evaluation

and

Repro-

E.1 Network Replay: Inputs and Complete Conditions Frozen inputs. The 500-query input bundle is sampled from the 8,087-query workload before network execution. The S EM DHT configuration uses 16 coarse centroids, ρ = 2, J = 4, ℓ = 3, rH = 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 S EM DHT 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.

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.

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.

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 pre25

Placement

System

Schedule

Cache

Mean [95% CI] (s)

P95 [95% CI] (s)

RPC errors

Same Same Same Same Same Same Same Same Cross Cross Cross Cross Cross Cross Cross Cross

S EM DHT S EM DHT S EM DHT S EM DHT LSH LSH LSH LSH S EM DHT S EM DHT S EM DHT S EM DHT LSH LSH LSH LSH

Parallel Parallel Barrier Barrier Parallel Parallel Barrier Barrier Parallel Parallel Barrier Barrier Parallel Parallel Barrier Barrier

Cold Warm Cold Warm Cold Warm Cold Warm Cold Warm Cold Warm Cold Warm Cold Warm

3.819 [3.490, 4.156] 3.009 [2.725, 3.315] 3.977 [3.618, 4.334] 2.918 [2.634, 3.215] 13.897 [13.628, 14.157] 13.565 [13.301, 13.843] 13.829 [13.532, 14.126] 13.565 [13.288, 13.839] 7.038 [6.673, 7.419] 6.836 [6.446, 7.230] 9.717 [9.297, 10.168] 9.094 [8.704, 9.524] 28.938 [28.644, 29.221] 29.044 [28.770, 29.312] 32.162 [31.863, 32.452] 32.130 [31.840, 32.419]

10.289 [8.949, 12.742] 8.879 [7.339, 10.099] 11.407 [9.195, 13.323] 8.751 [7.630, 9.779] 19.721 [18.591, 20.157] 18.929 [18.141, 19.786] 19.735 [18.096, 20.764] 18.865 [18.151, 19.943] 14.178 [11.955, 16.882] 15.093 [13.004, 17.329] 18.311 [15.564, 20.135] 15.946 [14.551, 19.378] 33.318 [32.588, 34.265] 33.734 [32.462, 34.263] 36.290 [35.610, 37.314] 36.569 [35.967, 37.276]

1 0 0 0 0 0 1 4 0 2 0 0 0 0 1 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. reuse the same verified certificate and committee signature across validations. They do not measure batch verification of distinct certificates.

warming. 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.

Encoded object Posting body Provider signature Membership certificate Committee signature Certificate with committee signature Merkle inclusion proof Complete posting

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.

Bytes 253 64 266 103 372 143 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.902–0.919, 0.950–0.960, and 0.970– 0.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.8987–0.9060, 0.6203–0.6311), (0.9471– 0.9529, 0.7215–0.7335), and (0.9683–0.9727, 0.7957– 0.8055).

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, fiveof-seven fixture. Each size measures the indicated object independently; nested encodings need not equal the sum of the standalone component encodings. Cache measurements

Matched-recall selection. The operating point in Table 1 at recall target 0.95 has publication fan-out eight. It is selected directly by exposure among configurations already

26

S EM DHT exposure/probes

LSH-on-DHT exposure/probes

0.80 0.90 0.95 0.97

47.5% / 30.6 62.1% / 33.7 72.7% / 32.9 79.0% / 65.2

47.1% / 102.1 61.6% / 173.2 72.7% / 253.5 83.5% / 110.2

hottest-node response-work (log)

recall target

Table 10: S EM DHT 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. Schedule One entry Two, full prefix Two, fixed cost

Lookups 59.1 118.3 59.1

sharded (balanced)

at skew 1.2

10

192

0.0

→ 50 (3.8× lower)

0.5 1.0 query Zipf skew exponent

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.2.

Recall Clean Attacked 0.9500 0.9500 0.8553

unsharded

100

0.7957 0.9191 0.8273

ulation assigns two distinct responder observations to each successful key–entry lookup, with saturation b0 = 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.20, two entries repeating the complete prefix yield AUC 0.928 from view coverage, 0.892 from responder coverage, and 0.920 from the combined score, compared with combined AUC 0.496 for one entry. When all entry paths are captured, targeted candidates disappear from every view and the combined AUC returns to approximately 0.5. The experiment measures query-level detection and coverage; the candidate-ranking weights in Eq. (23) remain uncalibrated.

Table 11: Mean physical lookups and recall at entry-path capture probability f = 0.20. Both two-entry schedules repeat the same keys across entries; the fixed-cost schedule uses a shorter prefix. above that target. Table 10 instead interpolates each configuration’s measured budget curve to recall exactly 0.95 before minimizing exposure. The selected S EM DHT 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. E.4 Multi-View Lookup under Entry-Path Suppression

E.5 Storage under Skew and Layout Changes

We replay 8,087 queries with a one-entry budget of Lq = 128. For each query and entry point, the model independently captures the entry path with probability f ∈ {0.05, . . . , 0.50}. A captured path suppresses a coordinated target set comprising approximately 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.20. Repeating the complete prefix through two entries raises attacked recall from 0.7957 to 0.9191, with twice the lookup cost. Keeping mean cost at 59.1 lookups reduces clean recall from 0.9500 to 0.8553, as fewer distinct keys are probed. For each query, we average covq (d) and repq (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 | denominator in Eq. (22). The sim-

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.4, the gap between sharded and unsharded hottest-node response-work widens as skew increases, from a 1.5× reduction under uniform traffic to 3.8× at Zipf 1.2 and 4.9× at Zipf 1.4, the highest skew we tested. Figure 9 presents the full skew sweep. Meanwhile, caching with certificate re-validation keeps measured candidate-acceptance correctness at 1.000, versus 0.5697 for a design that trusts cached postings without revalidation, 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 = 128. The re-

27

minimum discoverability during reindexing

1.0 0.99 gate Δmig = 1

0.5 0.0

Read-repair Off On

smallest window meeting the gate

0.0

Stale-exposure integral

p95 time

Messages

3.037 1.288

17.96 8.95

0 1,538

Table 12: Read-repair at turnover rate 0.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.

0.5 1.0 1.5 dual-publication window Δmig (rollout units)

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.

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.25 per stale replica per time unit. Responsibility turnover at rates 0, 0.05, 0.10, 0.20, and 0.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.10. Across all five turnover rates, read-repair lowers the staleexposure integral from 2.955–3.089 to 1.246–1.317 and the p95 convergence time from 16.04–19.26 to 8.66–9.30 units, a 1.84–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.

sulting 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 over {0, 0.1, 0.25, 0.5, 0.75, 1, 1.5}. Without Move hints, minimum discoverability is 0 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.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.496 and lowers the integrated discoverability shortfall from 0.502 to 0.129. Figure 10 shows the window sweep. 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.5 raises residence time to 6,144 without improving discoverability in this workload.

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 S EM DHT 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 rep-

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.499 and the p95 stale window is 0.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

28

CPU (%)

RSS (MiB)

System

Scheduler

Cache Baseline Query phase [range] Baseline Query phase [range]

S EM DHT S EM DHT S EM DHT S EM DHT

Parallel Parallel Stage-barrier Stage-barrier

Cold Warm Cold Warm

0.399 0.411 0.414 0.416

0.326 [0.323, 0.328] 0.291 [0.288, 0.296] 0.336 [0.326, 0.354] 0.294 [0.284, 0.307]

51.87 52.25 52.12 51.76

52.17 [52.09, 52.25] 52.16 [51.76, 52.44] 52.50 [52.29, 52.62] 51.68 [51.47, 51.87]

LSH LSH LSH LSH

Parallel Parallel Stage-barrier Stage-barrier

Cold Warm Cold Warm

0.409 0.401 0.407 0.398

0.394 [0.382, 0.408] 0.440 [0.431, 0.449] 0.410 [0.394, 0.433] 0.431 [0.421, 0.449]

52.44 52.55 52.24 52.37

52.85 [52.58, 53.11] 53.00 [52.90, 53.19] 52.68 [52.39, 52.93] 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. etitions provide 24 complete batches. An interrupted 16query 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 mainprocess 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.

29