Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOptimal Demand Private Coded Caching for Users with Small Buffers
80
0
0.0
(
0
)
Added by
B.Sundar Rajan
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Coded Caching is an efficient technique to reduce peak hour network traffic. One limitation of known coded caching schemes is that the demands of all users are revealed to their peers in the delivery phase. Schemes that assure privacy for user demands are studied in recent past. Assuming that the users are equipped with caches of small memory sizes, the achievable rate under demand privacy constraints is investigated in this work. We present an MDS code based demand private coded caching scheme with $K$ users and $N$ files that achieves a memory rate pair $left(frac{1}{K(N-1)+1},Nleft(1-frac{1}{K(N-1)+1}right)right)$. The presented memory-rate pair meets the lower bound under demand-privacy requirements, proposed by Yan textit{et al.} in the recent work cite{c13}. By memory sharing this characterizes the exact rate-memory trade-off for the demand private coded caching scheme for cache memory $Min left[0,frac{1}{K(N-1)+1}right]$.
rate research
Read More
We consider the coded caching problem with an additional privacy constraint that a user should not get any information about the demands of the other users. We first show that a demand-private scheme for $N$ files and $K$ users can be obtained from a non-private scheme that serves only a subset of the demands for the $N$ files and $NK$ users problem. We further use this fact to construct a demand-private scheme for $N$ files and $K$ users from a particular known non-private scheme for $N$ files and $NK-K+1$ users. It is then demonstrated that, the memory-rate pair $(M,min {N,K}(1-M/N))$, which is achievable for non-private schemes with uncoded transmissions, is also achievable under demand privacy. We further propose a scheme that improves on these ideas by removing some redundant transmissions. The memory-rate trade-off achieved using our schemes is shown to be within a multiplicative factor of 3 from the optimal when $K < N$ and of 8 when $Nleq K$. Finally, we give the exact memory-rate trade-off for demand-private coded caching problems with $Ngeq K=2$.
Recently Hachem et al. formulated a multiaccess coded caching model which consists of a central server connected to $K$ users via an error-free shared link, and $K$ cache-nodes. Each cache-node is equipped with a local cache and each user can access $L$ neighbouring cache-nodes with a cyclic wrap-around fashion. In this paper, we take the privacy of the users demands into consideration, i.e., each user can only get its required file and can not get any information about the demands of other users. By storing some private keys at the cache-nodes, we propose a novel transformation approach to transform a non-private multiaccess coded caching scheme into a private multiaccess coded caching scheme.
The demand private coded caching problem in a multi-access network with $K$ users and $K$ caches, where each user has access to $L$ neighbouring caches in a cyclic wrap-around manner, is studied. The additional constraint imposed is that one user should not get any information regarding the demands of the remaining users. A lifting construction of demand private multi-access coded caching scheme from conventional, non-private multi-access scheme is introduced. The demand-privacy for a user is ensured by placing some additional textit{keys} in a set of caches called the textit{private set} of that user. For a given $K$ and $L$, a technique is also devised to find the private sets of the users.
This work investigates the problem of demand privacy against colluding users for shared-link coded caching systems, where no subset of users can learn any information about the demands of the remaining users. The notion of privacy used here is stronger than similar notions adopted in past work and is motivated by the practical need to insure privacy regardless of the file distribution. Two scenarios are considered: Single File Retrieval (SFR) and Linear Function Retrieval (LFR), where in the latter case each user demands an arbitrary linear combination of the files at the server. The main contributions of this paper are a novel achievable scheme for LFR, referred as privacy key scheme, and a new information theoretic converse bound for SFR. Clearly, being SFR a special case of LFR, an achievable scheme for LFR works for SFR as well, and a converse for SFR is a valid converse for LFR as well. By comparing the performance of the achievable scheme with the converse bound derived in this paper (for the small cache size regime) and existing converse bounds without privacy constraints (in the remaining memory regime), the communication load of the privacy key scheme turns out to be optimal to within a constant multiplicative gap in all parameter regimes. Numerical results show that the new privacy key scheme outperforms in some regime known schemes based on the idea of virtual users, which also satisfy the stronger notion of user privacy against colluding users adopted here. Moreover, the privacy key scheme enjoys much lower subpacketization than known schemes based on virtual users.
Classical coded caching setting avails each user to have one dedicated cache. This is generalized to a more general shared cache scheme and the exact expression for the worst case rate was derived in [E. Parrinello, A. Unsal, P. Elia, Fundamental Limits of Caching in Heterogeneous Networks with Uncoded Prefetching, available on arXiv:1811.06247 [cs.IT], Nov. 2018]. For this case, an optimal linear error correcting delivery scheme is proposed and an expression for the peak rate is established for the same. Furthermore, a new delivery scheme is proposed, which gives an improved rate for the case when the demands are not distinct.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
