  Distributed caching systems such as content distribution networks often
advertise their content via lightweight approximate indicators (e.g., Bloom
filters) to efficiently inform clients where each datum is likely cached. While
false-positive indications are necessary and well understood, most existing
works assume no false-negative indications. Our work illustrates practical
scenarios where false-negatives are unavoidable and ignoring them significantly
impacts system performance. Specifically, we focus on false-negatives induced
by indicator staleness, which arises whenever the system advertises the
indicator only periodically, rather than immediately reporting every change in
the cache. Such scenarios naturally occur, e.g., in bandwidth-constraint
environments or when latency impedes each client's ability to obtain an updated
indicator. Our work introduces novel false-negative aware access policies that
continuously estimate the false-negative ratio and sometimes access caches
despite negative indications. We present optimal policies for homogeneous
settings and provide approximation guarantees for our algorithms in
heterogeneous environments. We further perform an extensive simulation study
with multiple real system traces. We show that our false-negative aware
algorithms incur a significantly lower access cost than existing approaches or
match the cost of these approaches while requiring an order of magnitude fewer
resources (e.g., caching capacity or bandwidth).

Networking and Internet Architecture