In this paper, we present information theoretic inner and outer bounds on the fundamental tradeoff between cache memory size and update rate in a multi-user cache network. Each user is assumed to have individual caches, while upon users’ requests, an update message is sent though a common link to all users. The database is represented as a discrete memoryless source and the user request information is represented as side information that is available at the decoders and the update encoder, but oblivious to the cache encoder. We establish two inner bounds, the first based on a centralized caching strategy and the second based on a decentralized caching strategy. For the case when the user requests are i.i.d. with the uniform distribution, we show that the performance of the decentralized inner bound is within a multiplicative gap of 4 from the optimal cache–rate tradeoff. For general request distributions, we numerically compare the bounds and the baseline uncoded strategy, caching the most popular files.