Blind Updates in Coded Caching

We consider the centralized coded caching system where a library of files is available at the server and their subfiles are cached at the clients as prescribed by a placement delivery array (PDA). We are interested in the problem where a specific file in the library is replaced with a new file at the server, the contents of which are correlated with the file being replaced, and this change needs to be communicated to the caches. Upon replacement, the server has access only to the updated file and is unaware of its differences with the original, while each cache has access to specific subfiles of the original file as dictated by the PDA. We model the correlation between the two files by assuming that they differ in at the most $\epsilon$ subfiles, and aim to reduce the number of bits broadcast by the server to update the caches. We design a new elegant coded transmission strategy for the server to update the caches blindly, and also identify a simple scheme that is based on MDS codes. We then derive converse bounds on the minimum communication cost $\ell^*$ among all linear strategies. For two well-known families of PDAs -- Maddah-Ali & Niesen's caching scheme and a PDA by Tang & Ramamoorthy and Yan et al. -- our new scheme has cost $\ell^*(1 + o(1))$ when the updates are sufficiently sparse, while the scheme using MDS codes has order-optimal cost when the updates are dense.
Comment: Shorter version was accepted and presented in ITW 2020, Riva del Garda, Italy. Changes with respect to arXiv:2010.10464v1 -- improved presentation and corrected minor errors. Keywords: blind update, broadcast channel, coded caching, communication cost, placement delivery array