The demands of the clients in the client-server framework exhibit temporal variance leading to congestion in the network at random intervals. To alleviate this problem, popular data is loaded in cache memories scattered across the network. In the conventional cache framework, each user has an associated cache and cache loading is centrally coordinated. For large networks, a more practical approach is to make the loading of the caches decentralized. This letter considers the shared caching problem in which each cache can serve multiple clients. A new and optimal delivery scheme is proposed for the decentralized shared caching problem. The delivery scheme is shown to be optimal among all linear schemes, using techniques from index coding. It is shown that the rate achieved by the proposed scheme is comparable to the existing scheme which uses centralized prefetching.
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.
19 January 2022 in IEEE Journal on Selected Areas in Communications
Increasing amount of data generated at edge nodes and quest for privacy have resulted in learning at the edge. Computations are performed at edge devices and outputs are communicated to a central node for updating the model. The edge nodes are available intermittently and are connected via low-bandwidth links. The edge nodes communicate local gradients to helper nodes, and these helpers forward messages to the central node after possible aggregation. Recently, schemes using repetition codes and maximum-distance-separable (MDS) codes, respectively known as aligned repetition coding (ARC) and aligned MDS coding (AMC) schemes, were proposed. It was observed that the communication cost at edge nodes becomes optimal in the AMC scheme, at the expense of an increased cost of communication incurred by helpers. An upper bound on the communication cost at helpers for the AMC scheme was known in literature. In this paper, a tradeoff between communication costs at edge nodes and at helper nodes is established with the help of newly proposed pyramid scheme. The scheme makes use of well-known class of pyramid codes, thus expanding the realm of application of locally repairable codes to distributed learning. The communication costs both at helper nodes and at edge nodes are exactly characterized. Using the developed technique, the exact communication cost at helper nodes can be computed for the AMC scheme as well. Next, we come up with a technique to improve the aggregation strategy of both pyramid and AMC schemes, that yields significant reduction in communication cost at helpers without changing parameters of the code used by edges. Finally, we present a greedy algorithm to improve the aggregation strategy of the ARC scheme, achieving significantly reduced communication cost at helpers.
11 April 2019 in IEEE Transactions on Communications
In the conventional index coding problem, the messages transmitted by the source to satisfy the demands of the receivers are error-free. However, in practice, the messages may be error prone which led to the introduction of error-correcting index codes. An error-correcting index code is an encoding scheme which enables every receiver to decode its demanded message even in the presence of certain number of transmission errors. Formally, an index code capable of correcting at most δ errors at all its receivers is defined as a δ-error-correcting index code. In this paper, we explore the connections between vector linear error-correcting index codes and discrete polymatroids. This is motivated from the connections between linear network error-correcting codes and matroids. It is shown that a vector linear error-correcting index code exists if and only if there exists a representable discrete polymatroid satisfying certain conditions. Differential error-correcting index codes which allow different receivers to have different error-correcting capabilities are also studied. Note that the δ-error-correcting code is a special case of a differential error-correcting index code. Error correction at a subset of receivers is another special case which is discussed.
The connections between index coding and matroid theory have been well studied in the recent past. Index coding solutions were first connected to multi linear representation of matroids. For vector linear index codes, discrete polymatroids, which can be viewed as a generalization of the matroids, were used. The index coding problem has been generalized recently to accommodate receivers that demand functions of messages and possess functions of messages. In this work we explore the connections between generalized index coding and discrete polymatroids. The conditions that need to be satisfied by a representable discrete polymatroid for a generalized index coding problem to have a vector linear solution is established. From a discrete polymatroid, an index coding problem with coded side information is constructed and it is shown that if the index coding problem has a certain optimal length solution then the discrete polymatroid is representable. If the generalized index coding problem is constructed from a matroid, it is shown that the index coding problem has a binary scalar linear solution of optimal length if and only if the matroid is binary representable.