Information-Theoretic Caching

Motivated by the caching problem introduced by Maddah-Ali and Niesen, a problem of distributed source coding with side information is formulated, which captures a distinct interesting aspect of caching. For the single-user case, a single-letter characterization of the optimal rate region is presented. For the cases where the source is composed of either independent or nested components, the exact optimal rate regions are found and some intuitive caching strategies are confirmed to be optimal. When the components are arbitrarily correlated with uniform requests, the optimal caching strategy is found to be closely related to total correlation and Wyner's common information. For the two-user case, some subproblems are solved which draw connections to the Gray--Wyner system and distributed successive refinement. Finally, inner and outer bounds are given for the case of two private caches with a common update.