Blind Updates in Coded Caching

Ghosh, Suman and Krishnan, Prasad and Natarajan, Lakshmi Prasad (2021) Blind Updates in Coded Caching. In: 2020 IEEE Information Theory Workshop, ITW 2020, 11 April 2021 - 15 April 2021, Riva del Garda.

Full text not available from this repository. (Request a copy)


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 replacement needs to be communicated to the caches. The server loses the original file when the replacement is done and is unaware of the differences between the two files, whereas 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 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 another simple scheme that is based on MDS codes. We then derive converse bounds on the minimum cost `∗ among all linear strategies. For two well-known families of PDAs – the Maddah-Ali-Niesen scheme and a scheme by Tang & Ramamoorthy and Yan et al. – we show that our new scheme has cost `∗(1 + o(1)) when the updates are sufficiently sparse, while the scheme using MDS codes has order-optimal cost when the updates are dense.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Natarajan, Lakshmi PrasadUNSPECIFIED
Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: aching system; Coded transmission; MDS code; Minimum cost; Optimal costs; Simple schemes Engineering main heading
Subjects: Electrical Engineering
Divisions: Department of Electrical Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 23 Sep 2021 06:23
Last Modified: 23 Sep 2021 06:23
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 8838 Statistics for this ePrint Item