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.

Published in:
Proceedings of the 2015 IEEE International Symposium on Information Theory
Presented at:
2015 IEEE International Symposium on Information Theory, Hong Kong, China, June 14-19, 2015

 Record created 2015-06-24, last modified 2018-03-17

Rate this document:

Rate this document:
(Not yet reviewed)