  The design of caching algorithms to maximize hit probability has been
extensively studied. In this paper, we associate each content with a utility,
which is a function of either the corresponding content hit rate or hit
probability. We formulate a cache optimization problem to maximize the sum of
utilities over all contents under stationary and ergodic request processes.
This problem is non-convex in general but we reformulate it as a convex
optimization problem when the inter-request time (irt) distribution has a
non-increasing hazard rate function. We provide explicit optimal solutions for
some irt distributions, and compare the solutions of the hit-rate based (HRB)
and hit-probability based (HPB) problems. We formulate a reverse engineering
based dual implementation of LRU under stationary arrivals. We also propose
decentralized algorithms that can be implemented using limited information and
use a discrete time Lyapunov technique (DTLT) to correctly characterize their
stability. We find that decentralized algorithms that solve HRB are more robust
than decentralized HPB algorithms. Informed by these results, we further
propose lightweight Poisson approximate decentralized and online algorithms
that are accurate and efficient in achieving optimal hit rates and hit
probabilities.
