Failure-Resilient and Verifiable Distributed Approximate Nearest-Neighbor Retrieval

• TrustANN addresses the gap between authentic stored state and trustworthy distributed results, where workers may omit candidates, return stale results, or manipulate rankings.The paper frames this as query-level retrieval trust: whether participants provide sufficient independent evidence to accept a result.Source: §1 · p. 1
• CoordShift builds reusable, failure-domain-aware retrieval epochs asynchronously, avoiding coordination on the latency-critical query path.Queries consume cached coordination state; that state is not the query-level safety boundary.Source: §1 · p. 2
• TrustANN operates above existing ANN indexes, separating retrieval execution from retrieval trust and background coordination from query-level safety.Its three components are TrustBind, CoordShift, and AvailGuard.Source: §1 · p. 2
• AvailGuard seeks additional independent evidence under failures without weakening the trust threshold, and returns UNVERIFIED if sufficient evidence cannot be established.This preserves the distinction between having an answer and having enough evidence to trust it.Source: §1 · p. 2
• The system evaluates retrieval attacks, evidence ablations, failures, fan-out, recovery, and asynchronous coordination using distributed HNSW on Deep10M in a multi-node AWS deployment.TrustANN is implemented over an existing ANN substrate without changing the underlying search algorithm.Source: §1 · p. 2
• R-ASR drops from 1.000 to 0.000 under the tested Byzantine-retrieval attack; clean p95 overhead is 9.36%, with trusted retrieval through 33% replica crashes.TrustANN returns UNVERIFIED when sufficient evidence is unavailable.Source: §1 · p. 2

• Each shard has r replicas, and fewer than half may be corrupted; Byzantine workers may return arbitrary, incomplete, stale, or conflicting candidates or selectively respond.Crash and Byzantine failures may coexist within a shard.Source: §2 · p. 2
• For each reached shard, selected evidence must meet support, consistency, and failure-domain independence thresholds; evidence from different shards cannot be pooled.The thresholds are |Sq,j| ≥ θ, C(Sq,j) ≥ γ, and D(Sq,j) ≥ dmin.Source: §2 · p. 2
• Distinct worker identities do not by themselves establish independent evidence; independence is determined using configured failure-domain metadata.If sufficient evidence is unavailable, TrustANN returns UNVERIFIED rather than weakening the criteria.Source: §2 · p. 3
• TrustANN assumes secure cryptographic primitives, authenticated worker identities, and an uncompromised ANN implementation; guarantees are bounded by its per-shard corruption and failure-domain assumptions.It does not provide a formal ANN-recall guarantee when those assumptions are violated.Source: §2 · p. 3

3 System Design

• TrustANN operates above existing distributed ANN deployments, leaving the underlying index and search algorithm unchanged while addressing unavailable, stale, or adversarial workers.Source: §3 · p. 3

3.1 System Model

• Each shard has replicated ANN indexes, and contacted workers return candidate sets with authenticated metadata identifying the worker, shard, replica, index state, and retrieval epoch.Source: §3.1 · p. 3

3.2 Architecture Overview

• Queries use ordinary ANN retrieval, then TrustBind evaluates authenticated, consistent, failure-domain-independent evidence per shard; AvailGuard seeks additional evidence within a bounded budget and returns UNVERIFIED if trust remains unestablished.Source: §3.2 · p. 4

3.3 Consistency-Aware Query-Level Trust

• TrustBind selects per-shard evidence meeting support, consistency, and failure-domain-diversity thresholds; trust requires every relevant shard to satisfy the condition.Source: §3.3 · p. 5

3.4 Diversity-Aware Asynchronous Coordination

• CoordShift asynchronously creates reusable coordination epochs using randomized, diversity-aware worker selection, but its authenticated reference is not a Byzantine-safe certificate or the query-time safety boundary.Source: §3.4 · p. 6

3.5 Independence-Aware Evidence Recovery

• AvailGuard seeks replicas in new failure domains for an affected shard, keeps the trust thresholds unchanged, and returns UNVERIFIED if sufficient independent evidence cannot be found within Kmax rounds.Source: §3.5 · pp. 6–7

3.6 Correctness and Safety Properties

• Coordination does not determine query trust, which is established independently per shard from consistent, failure-domain-diverse evidence; bounded recovery never weakens those requirements.Source: §3.6 · p. 7

3.7 Communication and Performance Model

• The communication model separates retrieval, evidence verification, and background coordination; its recovery fan-out expressions are worst-case bounds, while selective recovery is normally used.Source: §3.7 · p. 7

4 Implementation

• TrustBind checks signatures and epochs, then selects consistent replica evidence subject to support, consistency, and failure-domain coverage thresholds.It builds an evidence consistency graph using candidate-set overlap and ranking consistency, with greedy evidence selection rather than maximum-clique solving.Source: §4 · p. 8
• The prototype leaves the ANN algorithm unchanged and runs a coordinator with distributed HNSW workers that return compact authenticated retrieval evidence.Workers independently search their shard replicas; the coordinator handles query routing and the TrustBind, AvailGuard, and CoordShift services.Source: §4 · p. 8
• CoordShift asynchronously selects a failure-domain-aware coordination quorum and caches each accepted epoch for reuse by later queries.A failed coordination round leaves the previously accepted epoch active.Source: §4 · p. 8
• AvailGuard seeks additional independent evidence without lowering the TrustBind threshold, stops after bounded attempts, and returns Unverified if evidence remains insufficient.Recovery evidence is evaluated within its own shard and cannot be pooled across shards; the AWS prototype also supports fault injection for availability and integrity faults.Source: §4 · p. 8

5.1 Experimental Setup

• The Deep10M evaluation uses a 100K-vector AWS subset, distributed FAISS HNSW shards, and an apples-to-apples unverified distributed-ANN baseline.The default setup uses three shards with three replicas each, θ=2, and fallback budget Kmax=1.Source: §5.1 · pp. 8–9

5.2 Trustworthy Retrieval

• With θ=1, one Byzantine response is accepted, while θ=2 rejects it and still trusts clean retrieval and retrieval with a Byzantine minority; threshold-only and threshold-plus-consistency ablations also accept attacks.Cross-shard tests report zero R-ASR across fallback budgets, and additional candidate-suppression and ranking-manipulation tests report zero measured R-ASR.Source: §5.2 · pp. 9–10
• R-ASR falls from 1.000 for the Unverified ANN baseline to zero with TrustANN at θ=2 under a single-Byzantine-survivor attack.The clean configuration remains fully trusted; measured p95 latency rises from approximately 0.52 ms to 1.88 ms in this attack experiment.Source: §5.2 · p. 9, Table 4 · p. 10

5.3 Off-Path Coordination

• No query waits for epoch construction as offered load rises from 50 to 400 QPS; query p95 remains between 7.77 and 10.70 ms.CoordShift commits 24 epochs in each load configuration at a fixed 200-ms interval.Source: §5.3 · p. 10

5.4 Failure-Resilient Retrieval

• Trusted-query rate remains 1.000 through 33% crashed replicas, then falls to zero at 49% when remaining replicas cannot provide sufficient evidence.AvailGuard activates fallback at nonzero failure levels while retaining θ=2.Source: §5.4 · p. 10

5.5 Distributed-System Cost

• Fan-out from one to three shards raises p95 latency from 1.51 to 7.46 ms, while clean-path p95 latency increases 9.36% with TrustANN versus the unverified baseline.In a separate weak-scaling deployment, throughput rises from 908.6 to 1176.5 QPS across 18 to 144 workers, while parallel efficiency falls from 1.000 to 0.162.Source: §5.5 · pp. 10–11

5.6 Recovery and Reconfiguration

• Queries continue during replica failure, replica replacement, and shard migration with zero query errors; p95 remains 4.38–4.65 ms while reconfiguration takes about 5 s.The measurements indicate convergence latency is decoupled from query-path availability, not instantaneous.Source: §5.6 · p. 11

5.7 CoordShift Resilience

• For k=9 and p=0.10, diversity-aware selection raises failure-domain coverage from 6.845 to 9.000, but does not universally reduce adversary-influenced rounds.For k=15 and k=21, it reaches the maximum configured coverage of 12 domains.Source: §5.7 · p. 11

Distributed ANN and verifiable retrieval

• Distributed ANN systems optimize scalability and resource management, while verifiable systems authenticate search or index state but generally do not establish replica-evidence sufficiency for trusting retrieval.Source: §6 · p. 12

Federated and Byzantine-robust protection

• Federated retrieval, malicious-content defenses, and robust aggregation address complementary security dimensions, not evidence sufficiency under replica failures, stale state, or retrieval-time manipulation.Source: §6 · p. 12

Byzantine coordination and fault tolerance

• BFT agreement offers strong replicated guarantees but incurs communication and synchronization costs; TrustANN keeps coordination off the query path while maintaining retrieval-level evidence requirements.Source: §6 · p. 12

7 Conclusion and Future Work

• 9.36% increase in clean p95 latency accompanies rejection of the tested Byzantine retrieval attack and trusted retrieval under evaluated replica failures.Source: §7 · p. 12
• TrustANN works as middleware above existing ANN indexes without modifying the search algorithm, using TrustBind, CoordShift, and AvailGuard for trust, coordination, and recovery.Source: §7 · p. 12
• Future work will investigate adaptive adversaries, larger-scale and more dynamic failure and reconfiguration scenarios, and stronger retrieval-level guarantees.Source: §7 · p. 12