  In this paper, we consider a cache aided network in which each user is
assumed to have individual caches, while upon users' requests, an update
message is sent though a common link to all users. First, we formulate a
general information theoretic setting that represents the database as a
discrete memoryless source, and the users' requests as side information that is
available everywhere except at the cache encoder. The decoders' objective is to
recover a function of the source and the side information. By viewing cache
aided networks in terms of a general distributed source coding problem and
through information theoretic arguments, we present inner and outer bounds on
the fundamental tradeoff of cache memory size and update rate. Then, we
specialize our general inner and outer bounds to a specific model of content
delivery networks: File selection networks, in which the database is a
collection of independent equal-size files and each user requests one of the
files independently. For file selection networks, we provide an outer bound and
two inner bounds (for centralized and decentralized caching strategies). For
the case when the user request information is uniformly distributed, we
characterize the rate vs. cache size tradeoff to within a multiplicative gap of
4. By further extending our arguments to the framework of Maddah-Ali and
Niesen, we also establish a new outer bound and two new inner bounds in which
it is shown to recover the centralized and decentralized strategies, previously
established by Maddah-Ali and Niesen. Finally, in terms of rate vs. cache size
tradeoff, we improve the previous multiplicative gap of 72 to 4.7 for the
average case with uniform requests.
