Search

Caching at the wireless edge nodes is a promising way to boost the spatial and spectral efficiency, for the sake of alleviating networks from content-related traffic. Coded caching originally introduced by Maddah-Ali and Niesen significantly speeds up communication efficiency by transmitting multicast messages simultaneously useful to multiple users. Most prior works on coded caching are based on the assumption that each user may request all content in the library. However, in many applications the users are interested only in a limited set of content that depends on their location. For example, assisted self-driving vehicles may access super High-Definition maps of the area through which they are travelling. Motivated by these considerations, this paper formulates the coded caching problem for location-based content with edge cache nodes. The considered problem includes a content server with access to ${\mathsf N}$ location-based files (e.g., High-Definition maps), ${\mathsf K}$ edge cache nodes located at different regions, and ${\mathsf K}$ users (i.e., vehicles) each of which is in the serving region of one cache node and can retrieve the cached content of this cache node with negligible cost. Depending on the location, each user only requests a file from a location-dependent subset of the library. The objective is to minimize the worst-case load (i.e., the worst-case number of broadcasted bits from the content server among all possible demands). For this novel coded caching problem, we propose a highly non-trivial converse bound under uncoded cache placement (i.e., each cache node directly copies some library bits in its cache), which shows that a simple achievable scheme is optimal under uncoded cache placement. In addition, this achievable scheme is also proved to be generally order optimal within a factor of 3. Finally, we extend the coded caching problem for location-based content to the multiaccess coded caching topology originally proposed by Hachem et al., where each user is connected to ${\mathsf L}$ nearest cache nodes. When ${\mathsf L}\geq 2$ , we characterize the exact optimality on the worst-case load. [ABSTRACT FROM AUTHOR]

This paper studies the distributed linearly separable computation problem, which is a generalization of many existing distributed computing problems such as distributed gradient coding and distributed linear transform. A master asks ${\mathsf {N}}$ distributed workers to compute a linearly separable function of ${\mathsf {K}}$ datasets, which is a set of ${\mathsf {K}}_{\mathrm{ c}}$ linear combinations of ${\mathsf {K}}$ equal-length messages (each message is a function of one dataset). We assign some datasets to each worker in an uncoded manner, who then computes the corresponding messages and returns some function of these messages, such that from the answers of any ${\mathsf {N}}_{\mathrm{ r}}$ out of ${\mathsf {N}}$ workers the master can recover the task function with high probability. In the literature, the specific case where ${\mathsf {K}}_{\mathrm{ c}}=1$ or where the computation cost is minimum has been considered. In this paper, we focus on the general case (i.e., general ${\mathsf {K}}_{\mathrm{ c}} $ and general computation cost) and aim to find the minimum communication cost. We first propose a novel converse bound on the communication cost under the constraint of the popular cyclic assignment (widely considered in the literature), which assigns the datasets to the workers in a cyclic way. Motivated by the observation that existing strategies for distributed computing fall short of achieving the converse bound, we propose a novel distributed computing scheme for some system parameters. The proposed computing scheme is optimal for any assignment when ${\mathsf {K}}_{\mathrm{ c}}$ is large and is optimal under the cyclic assignment when the numbers of workers and datasets are equal or ${\mathsf {K}}_{\mathrm{ c}}$ is small. In addition, it is order optimal within a factor of 2 under the cyclic assignment for the remaining cases. [ABSTRACT FROM AUTHOR]

This paper considers the multiaccess coded caching systems formulated by Hachem et al., including a central server containing $N$ files connected to $K$ cache-less users through an error-free shared link, and $K$ cache-nodes, each equipped with a cache memory size of $M$ files. Each user has access to $L$ neighbouring cache-nodes with a cyclic wrap-around topology. The coded caching scheme proposed by Hachem et al. suffers from the case that $L$ does not divide $K$ , where the needed number of transmissions (a.k.a. load) is at most four times the load expression for the case where $L$ divides $K$. Our main contribution is to propose a novel transformation approach to smartly extend the schemes satisfying some conditions for the well known shared-link caching systems to the multiaccess caching systems. Then we can get many coded caching schemes with different subpacketizations for multiaccess coded caching system. These resulting schemes have the maximum local caching gain (i.e., the cached contents stored at any $L$ neighbouring cache-nodes are different such that the number of retrieval packets by each user from the connected cache-nodes is maximal) and the same coded caching gain as the original schemes. Applying the transformation approach to the well-known shared-link coded caching scheme proposed by Maddah-Ali and Niesen, we obtain a new multiaccess coded caching scheme that achieves the same load as the scheme of Hachem et al. but for any system parameters. Under the constraint of the cache placement used in this new multiaccess coded caching scheme, our delivery strategy is approximately optimal when $K$ is sufficiently large. Finally, we also show that the transmission load of the proposed scheme can be further reduced by compressing the multicast message. [ABSTRACT FROM AUTHOR]

We consider the problem of cache-aided Multiuser Private Information Retrieval (MuPIR) which is an extension of the single-user cache-aided PIR problem to the case of multiple users. In cache-aided MuPIR, each of the $K_{\mathrm{ u}}$ cache-equipped users wishes to privately retrieve a message out of $K$ messages from $N$ databases each having access to the entire message library. Demand privacy requires that any individual database learns nothing about the demands of all users. The users are connected to each database via an error-free shared-link. In this paper, we aim to characterize the optimal trade-off between user cache memory and communication load for such systems. First, we propose a novel approach of cache-aided interference alignment (CIA), for the MuPIR problem with $K=2$ messages, $K_{\mathrm{ u}}=2$ users and $N\ge 2$ databases. The CIA approach is optimal when the cache placement is uncoded. For general cache placement, the CIA approach is optimal when $N=2$ and 3 verified by the computer-aided converse approach. Second, for the general case, we propose a product design (PD) which incorporates the PIR code into the linear caching code. The product design is shown to be order optimal within a multiplicative factor of 8 and is exactly optimal in the high memory regime. [ABSTRACT FROM AUTHOR]

The coded caching scheme originally proposed by Maddah-Ali and Niesen (MAN) transmits coded multicast messages from a server to users equipped with caches via a capacitated shared-link and was shown to be information theoretically optimal within a constant multiplicative factor. This work extends the MAN scheme to a class of two-hop wired-wireless networks including one server connected via fronthaul links to a layer of H helper nodes (access points/base stations), which in turn communicate via a wireless access network to K users, each equipped with its own cache. Two variants are considered, which differ in the modeling of the access segment. Both models should be regarded as abstractions at the “network layer” for physical scenarios such as local area networks and cellular networks, spatially distributed over a certain coverage area. The key of our approach consists of routing MAN-type multicast messages through the network and formulating the optimal routing scheme as an optimization problem that can be solved exactly or for which we give powerful heuristic algorithms. Our approach addresses at once many of the open practical problems identified as stumbling blocks for the application of coded caching in practical scenarios, namely: asynchronous streaming sessions, finite file size, scalability of the scheme to large and spatially distributed networks, user mobility and random activity (users joining and leaving the system at arbitrary times), decentralized prefetching of the cache contents, end-to-end encryption of HTTPS requests, which renders the helper nodes oblivious of the users’ demands. [ABSTRACT FROM AUTHOR]

We consider a cache-aided wireless device-to-device (D2D) network of the type introduced by Ji et al., where the placement phase is orchestrated by a central server. We assume that the devices’ caches are filled with uncoded data, and the whole content database is contained in the collection of caches. After the cache placement phase, the files requested by the users are serviced by inter-device multicast communication. For such a system setting, we provide the exact characterization of the optimal load-memory trade-off under the assumptions of uncoded placement and one-shot delivery. In particular, we derive both the minimum average (under uniformly distributed demands) and the minimum worst-case sum-load of the D2D transmissions, for given individual cache memory size at disposal of each user. Furthermore, we show that the performance of the proposed scheme is within factor 4 of the information-theoretic optimum. Capitalizing on the one-shot delivery property, we also propose an extension of the presented scheme that provides robustness against random user inactivity. [ABSTRACT FROM AUTHOR]