In this paper, we propose a multi-access coded caching system under decentralized setting tailored for Content Delivery Networks (CDNs). In this system, a central server hosts N files, each of size F bits, and serves K≤N users through a shared link. The network is equipped with c caches, each with a capacity of MF bits, distributed across the network, where each of the K users is connected to a random set of r≤c caches. Initially, we consider a model where each cache subset is accessed by an equal number of users. We introduce a novel content delivery algorithm for the central server, which allows us to derive a closed-form expression for the per user transmission rate. Using techniques from index coding, we prove the optimality of the proposed delivery scheme. Additionally, we extend the model to propose a more general and novel framework by allowing each subset of caches to serve an arbitrary number of users, thereby greatly enhancing the system’s flexibility and applicability. We also propose a new delivery algorithm tailored to this generalized setting and demonstrate its optimality under specific user-to-cache association scenarios. Numerical results demonstrate that, in a specific scenario where the user-to-cache associations do not satisfy the optimality conditions, the proposed generalized scheme shows improvement over the order-optimal state-of-the-art decentralized multi-access coded caching scheme for small cache sizes. Specifically, when approximately 25% of the content is stored at every cache, the proposed scheme achieves up to a 20% reduction in the per user transmission rate. Considering that both schemes serve an equal number of users, the observed improvements indicate a potential reduction in server bandwidth requirements, lower latency, and enhanced energy efficiency during content delivery.

There are two major problems while training large machine learning models using distributed gradient descent. The first is the problem of straggling workers, and the second is the communication delays in transmitting the computed gradient. In Tree Gradient Coding (TGC) architecture, the workers are arranged in a tree topology, and the data partitions are redundantly assigned to these workers, providing us resilience to straggling workers. In TGC the effect of the communication delays and the partial straggling behavior of the workers are not considered while distributing the computation load. In this paper, an expression for computation load in TGC considering the communication delays and the partial stragglers is derived. Moreover, the proposed technique is implemented on cloud-based VMs and experimental results are obtained. A speedup of up to 23.95% is observed compared to the traditional TGC scheme.

The growing privacy concerns and the communication costs associated with transmitting raw data have resulted in techniques like federated learning, where the machine learning models are trained at the edge nodes, and the parameter updates are shared with a central server. Because communications from the edge nodes are often unreliable, a hierarchical setup involving intermediate helper nodes is considered. The communication links between the edges and the helper nodes are error-prone and are modeled as straggling/failing links. To overcome the issue of link failures, coding techniques are proposed. The edge nodes communicate encoded versions of the model updates to the helper nodes, which pass them on to the master after suitable aggregation. The primary work in this area uses repetition codes and Maximum Distance Separable (MDS) codes at the edge nodes to arrive at the Aligned Repetition Coding (ARC) and Aligned MDS Coding (AMC) schemes, respectively. We propose using vector codes, specifically a family of layered MDS codes parameterized by a variable ν, at the edge nodes. For the proposed family of codes, suitable aggregation strategies at the helper nodes are also developed. At the extreme values of ν, our scheme matches the communication costs incurred by the ARC and AMC schemes, resulting in a graceful transition between these schemes.

Caching has emerged as a potential way to reduce the latency of content delivery and decrease network traffic during peak hours. In this paper, decentralized caching is considered where caches are filled with random contents of the files. The shared caching problem is considered in which more than one user can access a cache. A precoding technique using erasure codes is employed on the files before the caching. It is shown that the precoding technique implemented improves the delivery rate as compared to the rate when no erasure precoding is employed. Moreover, it is established that the rate corresponding to the proposed decentralized scheme matches with that of the optimal centralized scheme for certain cache sizes. Hence for certain specific cache sizes, the proposed scheme is optimal.

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.

The scaling-up process of distributed machine learning systems faces two major bottlenecks – delays due to stragglers and limited communication bandwidth. Gradient Coding (GC) was proposed for mitigating stragglers in distributed learning. A major drawback of the master-worker architecture in GC for distributed learning is the bandwidth contention at the master, which increases as the cluster size increases. Tree Gradient Coding (TGC), in which the workers are arranged in a regular tree topology leads to a reduction in bandwidth contention at the master. In TGC, each node is allocated the same amount of data for computation and the nodes communicate only with its immediate parent. In this paper, an improvement in the completion time of the TGC is achieved by allocating different computation loads to the nodes at different levels. This approach takes into account the communication delay from the nodes in the lower layers to the upper layers. The computation load at each node has been derived taking the communication delay into account. The computation load, thus calculated, is also proven to be optimal. Furthermore, the improvement in completion time is shown by implementing the proposed scheme on Amazon EC2 servers.

The increasing amount of data generated at the edge/client nodes and the privacy concerns have resulted in learning at the edge, in which the computations are performed at edge devices and are communicated to a central node for updating the model. The edge nodes have low bandwidth and may be available only intermittently. There are helper nodes present in the network that aid the edge nodes in the communication to the server. The edge nodes communicate the local gradient to helper nodes which relay these messages to the central node after possible aggregation. Recently, schemes using repetition codes and maximum-distance-separable (MDS) codes were proposed. It was observed that in MDS scheme the communication between edge nodes and helper nodes is optimal but with an increased cost of communication between helper and master. An upper bound on the communication cost between helpers and master was obtained. In this paper, a tradeoff between communication costs at edge nodes and helper nodes is established with the help of pyramid codes, a well-known class of locally repairable codes. The communication costs at both the helper nodes and edge nodes are exactly characterized. Using the developed technique, the exact communication cost at helper nodes can be computed for the scheme using MDS codes.

Data traffic in a client-server framework exhibits a temporal variability leading to congestion of resources at peak hours. One prevalent technique to overcome this problem is to load popular content/data into cache memories distributed across the end users. In this paper, the multi-access coded caching problem is considered in which each client is connected to multiple consecutive caches in a cyclic wrap around fashion and the cache memories are arbitrarily loaded in a decentralized manner. A new delivery scheme is proposed for the decentralized multi-access coded caching problem. A lower bound on the delivery rate is also obtained for the decentralized multi-access coded caching problem using techniques from index coding. The delivery scheme is shown to be optimal among all linear schemes when the number of caches associated with each user satisfies certain constraints.

Coded caching is a technique which enables the server to reduce the peak traffic rate by making use of the caches available at each user. In the classical coded caching problem, a centralized server is connected to many users through an error free link. Each user have a dedicated cache memory. This paper considers the shared caching problem which is an extension of the coded caching problem in which each cache memory could be shared by more than one user. An existing prefetching and delivery scheme for the shared caching problem with better rate-memory tradeoff than the rest is studied and the optimality of the scheme is proved by using techniques from index coding. The worst case rate of the coded caching problem is also obtained by using cut-set bound techniques. An optimal linear error correcting delivery scheme is obtained for the shared caching problem satisfying certain conditions.

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.

In coded caching, a single server is connected to a set of users through a shared bottleneck link, which is assumed to be error free. During non-peak hours, all the users fill their local cache with portions of the files available. During the delivery phase, each user requests a file and the server delivers coded transmissions to meet the demands. In this paper, the links between the server and the users are assumed to be error prone. Prefetching errors are also considered. A new delivery scheme is required to meet the demands of each user even after receiving a finite number of transmissions in error in the presence of erroneous portions of files in the cache. The minimum average rate and minimum peak rate for this problem are characterized. Closed form expressions for average and peak rates for a particular caching scheme, namely, symmetric batch prefetching are established when there are no prefetching errors. An optimal linear error correcting delivery scheme is proposed for coded caching problems with symmetric batch prefetching in the absence of prefetching errors. In addition to this, lower bounds are established for the optimal rate required when there are prefetching errors in symmetric batch prefetching.

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.

Optimal delivery scheme for coded caching problems with small buffer sizes and the number of users no less than the amount of files in the server was proposed by Chen, Fan and Letaief [“Fundamental limits of caching: improved bounds for users with small buffers,” IET Communications, 2016]. This scheme is referred to as the CFL scheme. In this paper, an extension to the coded caching scheme where the link between the server and the users is error prone, is considered. The delivery phase is error prone and the placement phase is considered to be error free. The closed form expressions for average rate and peak rate of error correcting delivery scheme are found for CFL prefetching scheme using techniques from index coding. For a given demand, the delivery phase of a coded caching problem becomes an index coding problem. Using results from error correcting index coding, an optimal linear error correcting delivery scheme for caching problems employing CFL prefetching is proposed.

Coded caching is used to reduce network congestion during peak hours. A single server is connected to a set of users through a shared bottleneck link, which generally is assumed to be error-free. During non-peak hours, all the users have full access to the files and they fill their local cache with portions of the files available. During delivery phase, each user requests a file and the server delivers coded transmissions to meet the demands taking into consideration their cache contents. In this paper we assume that the link between the server and the users is error prone. A new delivery scheme is required to meet the demands of each user even after receiving finite number of transmissions in error. We characterize the average rate and peak rate for this problem. We find closed form expressions of these rates for a particular caching scheme namelysymmetric batch prefetching. We also propose an optimal linear error correcting delivery scheme for coded caching problems with symmetric batch prefetching.

A source coding problem in which a central source has to satisfy the demands of several receivers, with each receiver having some subset of the messages (side-information) held by the source is considered. The source has knowledge of only the cardinality of the side-information at each receiver. The encoding scheme used by the source to transmit at a higher throughput is referred to as an informed source code. A technique to obtain informed source codes by using ℓ-th Near Maximum Distance Separable (Near-MDS) Codes is presented. The advantage of using ℓ-th Near-MDS codes is the reduction in field size required. For certain informed source coding problems, the code obtained from ℓ-th Near-MDS codes is shown to be of the minimum length under certain field size restrictions. The same technique can be used for a given index coding problem to obtain index codes. The index codes obtained through this technique are optimal for, but not limited to, special cases of index coding problems discussed in the paper. Finding an optimal solution to a general index coding problem is NP hard and this technique helps in finding binary suboptimal solutions. Using the Gilbert-Varshamov bound, an upper bound on the lengths of optimal binary informed source codes is obtained.

In this work an extension of the index coding problem referred to as index coding with restricted information (ICRI) problem is considered. The source has to develop encoding schemes which not only deliver the demanded messages but also prevent receivers from decoding certain specified messages. The problem finds applications in content delivery where a content provider has to restrict the user to obtain only subscribed data. A necessary condition for the ICRI problem to have a linear index coding solution is obtained. Using this condition it is shown that for a certain class of index coding problems, the source is unable to restrict the receiver from decoding unwanted messages. We also show that an ICRI problem has a linear solution if a contraction of the index coding problem can be constructed by contraction of a finite sequence of certain alignment edges. A solution to the ICRI problem is obtained by extending the solution of the contracted index coding problem.

A procedure to obtain index codes for a given index coding problem by using l-th Near Maximum Distance Separable Codes (NMDS) codes is presented. The advantage of using l-th NMDS codes is the reduction in field size required. A trade off between field size and length of index codes is observed. Using appropriate l-th NMDS codes binary index codes for the index coding problem can be constructed. The index codes obtained through this technique make use of only the minimum value of cardinality of the side-information available at the receivers and do not use messages in their side-information. The index codes obtained through this technique are optimal for, but not limited to, special cases of index coding problems discussed in the paper. Finding an optimal solution of a general index coding problem is NP Hard and this technique helps in finding binary suboptimal solutions. Using the Gilbert-Varshamov bound, an upper bound on the length of optimal binary index codes is obtained. Specifically we obtain a length for which a binary index code is guaranteed to exist.

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.

The connection between index coding and matroid theory have been well studied in the recent past. El Rouayheb et al. established a connection between multi linear representation of matroids and wireless index coding. Muralidharan and Rajan showed that a vector linear solution to an index coding problem exists if and only if there exists a representable discrete polymatroid satisfying certain conditions. Recently index coding with erroneous transmission was considered by Dau et al.. Error correcting index codes in which all receivers are able to correct a fixed number of errors was studied. In this paper we consider a more general scenario in which each receiver is able to correct a desired number of errors, calling such index codes differential error correcting index codes. A link between differential error correcting index codes and certain matroids is established. We define matroidal differential error correcting index codes and we show that a scalar linear differential error correcting index code exists if and only if it is matroidal differential error correcting index code associated with a representable matroid.

The connection between index coding and matroid theory have been well studied in the recent past. El Rouayheb et al. established a connection between multi linear representation of matroids and wireless index coding. Muralidharan and Rajan showed that a vector linear solution to an index coding problem exists if and only if there exists a representable discrete polymatroid satisfying certain conditions. Recently index coding with erroneous transmission was considered by Dau et al.. Error correcting index codes in which all receivers are able to correct a fixed number of errors was studied. In this paper we show that vector linear δ-error correcting index code exists if and only if there exists a representable discrete polymatroid satisfying certain conditions.

An index coding scheme in which the source (transmitter) transmits symbols over a wireless fading channel is considered. Index codes with the transmitter using minimum number of transmissions are known as optimal index codes. Different optimal index codes give different performances in terms of probability of error in a fading environment and this also varies from receiver to receiver. In this paper we deal with optimal index codes which minimizes the maximum probability of error among all the receivers. We identify a criterion for optimal index codes that minimizes the maximum probability of error among all the receivers. For a special class of index coding problems, we give an algorithm to identify optimal index codes which minimize the maximum error probability. We illustrate our techniques and claims with simulation results leading to conclude that a careful choice among the optimal index codes will give a considerable gain in fading channels.