Information-Theoretic Caching: Sequential Coding for Computing

Abstract

Under the paradigm of caching, partial data is delivered before the actual requests of users are known. In this paper, this problem is modeled as a canonical distributed source coding problem with side information, where the side information represents the users' requests. For the single-user case, a single-letter characterization of the optimal rate region is established, and for several important special cases, closed-form solutions are given, including the scenario of uniformly distributed user requests. In this case, it is shown that the optimal caching strategy is closely related to total correlation and Wyner's common information. Using the insight gained from the single-user case, three two-user scenarios admitting single-letter characterization are considered, which draw connections to existing source coding problems in the literature: the Gray--Wyner system and distributed successive refinement. Finally, the model studied by Maddah-Ali and Niesen is rephrased to make a comparison with the considered information-theoretic model. Although the two caching models have a similar behavior for the single-user case, it is shown through a two-user example that the two caching models behave differently in general.

submitted to IEEE Trans. Inf. Theory and presented in part at ISIT 2015

References in corpus (6)

• The information bottleneck method
• Wireless Device-to-Device Caching Networks: Basic Principles and System Performance
• Fundamental Limits of Caching with Secure Delivery
• Order-Optimal Rate of Caching and Coded Multicasting with Random Demands
• Coded Caching for Delay-Sensitive Content
• Rate-Distortion with Side-Information at Many Decoders

Cited by in corpus (11)

• The Exact Rate-Memory Tradeoff for Caching with Uncoded Prefetching
• Noisy Broadcast Networks with Receiver Caching
• Information Theoretic Caching: The Multi-User Case
• Fundamental Limits of Cache-Aided Wireless BC: Interplay of Coded-Caching and CSIT Feedback
• A Rate-Distortion Approach to Caching
• The Synergistic Gains of Coded Caching and Delayed Feedback
• Coordination Through Shared Randomness
• Feedback-Aided Coded Caching for the MISO BC with Small Caches
• On Wyner's Common Information in the Gaussian Case
• Lower bound on Wyner's Common Information
• A Multiway Relay Channel with Balanced Sources