Pareto Optimal Schemes in Coded Caching

Maddah-Ali and Niesen, in a seminal work, initiated the study of rate memory tradeoff for a canonical cache network which operates via a placement phase and a delivery phase. While considering the case of placement phase being uncoded, Yu et al. proved the surprising result of the existence of a uni...

Full description

Saved in:
Bibliographic Details
Main Authors: K.P., Vijith Kumar, Rai, Brijesh Kumar, Jacob, Tony
Format: Conference Proceeding
Language:English
Subjects:
Cache memory
Cache network
coded caching
coded placement
demand types
Encoding
Indexes
Jacobian matrices
Pareto optimization
Servers
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Maddah-Ali and Niesen, in a seminal work, initiated the study of rate memory tradeoff for a canonical cache network which operates via a placement phase and a delivery phase. While considering the case of placement phase being uncoded, Yu et al. proved the surprising result of the existence of a universal code, a code which is simultaneously optimal for all demand types. In this paper, we prove that universal codes do not exist when coding is permitted in the placement phase. As part of our proof, we introduce new kinds of lower bounds. In these lower bounds, instead of considering one demand type at a time, we consider several demand types simultaneously. These bounds give us better insight into how the performance for one demand type affects the performance for the other demand types. The non-existence of a universal scheme motivates us to introduce the notion of Pareto optimal schemes, and we prove that Chen's scheme is Pareto optimal.
ISSN:2157-8117
DOI:10.1109/ISIT.2019.8849680