2020/01/10 by Kai Wan, Sun Hua, Wan, Kai +7
Computer Science · #Advanced Data Storage Technologies #Caching and Content Delivery #Cooperative Communication and Network Coding #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2001.03577
openalex publication_date 2020/01/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Coded caching has the potential to greatly reduce network traffic by\nleveraging the cheap and abundant storage available in end-user devices so as\nto create multicast opportunities in the delivery phase. In the seminal work by\nMaddah-Ali and Niesen (MAN), the shared-link coded caching problem was\nformulated, where each user demands one file (i.e., single file retrieval).\nThis paper generalizes the MAN problem so as to allow users to request scalar\nlinear functions of the files. This paper proposes a novel coded delivery\nscheme that, based on MAN uncoded cache placement, is shown to allow for the\ndecoding of arbitrary scalar linear functions of the files (on arbitrary finite\nfields). Interestingly, and quite surprisingly, it is shown that the load for\ncache-aided scalar linear function retrieval depends on the number of linearly\nindependent functions that are demanded, akin to the cache-aided single-file\nretrieval problem where the load depends on the number of distinct file\nrequests. The proposed scheme is optimal under the constraint of uncoded cache\nplacement, in terms of worst-case load, and within a factor 2 otherwise. The\nkey idea of this paper can be extended to all scenarios which the original MAN\nscheme has been extended to, including demand-private and/or device-to-device\nsettings.\n