We consider a distributed computing system in which a master node coordinates $N$ workers to evaluate a function over $n$ input files, where this function accepts general decomposition. In particular, we focus on the general case where the requested function admits a $d$-uniform decomposition, meaning that it can be decomposed into a set of subfunctions that each depends on a unique $d$-tuple of the $n$ files. Our objective is to design file and task allocations that minimize the worst-case communication from the master to any worker and the worst-case computational load across workers. We first show that the optimal file and task allocation with minimum communication and computation costs admits a natural characterization within combinatorial design theory: it corresponds to a Steiner system $S(t, k, v)$ with $t=d$, $v=n$, and $k \approx \frac{n}{N^{1/d}}$. However, Steiner systems are known to exist only for very restricted parameter regimes. To overcome this limitation, we propose the information-theoretic-inspired \emph{Interweaved Clique (IC) design}, a universal and deterministic allocation framework that relaxes the strict structure of Steiner systems by allowing slight variations in worker file loads. Although slightly suboptimal, the IC design achieves a communication cost within a constant factor $4e$ from our converse, while also maintaining an order-optimal computation cost, thus allowing this work to derive the fundamental scaling laws of this general distributed computing problem for a large range of parameters.

This work establishes the fundamental limits of the classical problem of multi-user distributed computing of linearly separable functions. In particular, we consider a distributed computing setting involving $L$ users, each requesting a linearly separable function over $K$ basis subfunctions from a master node, who is assisted by $N$ distributed servers. At the core of this problem lies a fundamental tradeoff between communication and computation: each server can compute up to $M$ subfunctions, and each server can communicate linear combinations of their locally computed subfunctions outputs to at most $Δ$ users. The objective is to design a distributed computing scheme that reduces the communication cost (total amount of data from servers to users), and towards this, for any given $K$, $L$, $M$, and $Δ$, we propose a distributed computing scheme that jointly designs the task assignment and transmissions, and shows that the scheme achieves optimal performance in the real field under various conditions using a novel converse. We also characterize the performance of the scheme in the finite field using another converse based on counting arguments.

This work explores a multiple transmit antenna setting in a multi-access coded caching (MACC) network where each user accesses more than one cache. A MACC network has K users and K caches, and each user has access to$r \lt K$consecutive caches in a cyclic wrap-around manner. There are L antennas at the server, and each cache has a normalized size$M/N \leq 1$. The cyclic wrap-around MACC network with a single antenna at the server has been well-investigated, and several coded caching schemes and improved lower bounds on the performance are derived for the same. However, this MACC network has not yet been studied under multi-antenna settings in the coded caching literature. We study the multi-antenna MACC problem and propose a solution for the same by constructing a pair of arrays called caching and delivery arrays. We present four constructions of caching and delivery arrays for different scenarios and obtain corresponding multi-antenna MACC schemes. Three of the above schemes achieve optimal performance under uncoded placement and one-shot delivery. The optimality is shown by matching the performance of the multi-antenna MACC scheme to the optimal performance in a dedicated cache network having K users and normalized cache size$rM/N$. Further, as a special case, one of the proposed schemes subsumes an existing optimal MACC scheme for the single-antenna setting.

This work introduces a multi-antenna coded caching problem in a two-dimensional multi-access network, where a server with$L$transmit antennas and$N$files communicates to$K_{1}K_{2}$users, each with a single receive antenna, through a wireless broadcast link. The network consists of$K_{1}K_{2}$cache nodes and$K_{1}K_{2}$users. The cache nodes, each with capacity$M$, are placed on a rectangular grid with$K_{1}$rows and$K_{2}$columns, and the users are placed regularly on the square grid such that a user can access$r^{2}$neighbouring caches in a cyclic wrap-around fashion. For a given cache memory$M$, the goal of the coded caching problem is to serve the user demands with a minimum delivery time. We propose a solution for the aforementioned coded caching problem by designing two arrays: a caching array and a delivery array. Further, we present two classes of caching and delivery arrays and obtain corresponding multi-access coded caching schemes. The first scheme achieves a normalized delivery time (NDT)$\frac{K_{1}K_{3}(1-r^{2}\frac{M}{N})}{L+K_{1}K_{2}\frac{M}{N}}$. The second scheme achieves an NDT$\frac{K_{1}K_{3}(1-r^{2}\frac{M}{N})}{L+K_{1}K_{2}r^{2}\frac{M}{N}}$when$M/N=1/K_{1}K_{2}$and$L=K_{1}K_{2}-r^{2}$, which is optimal under uncoded placement and one-shot delivery.

We consider a coded caching network consisting of a server with a library of$N$files connected to$K$users, where each user is equipped with a dedicated cache of size$M_{p}$units. In addition to that, the network consists of$\Lambda\leq K$helper caches, each with a size$M_{h}$units. Each helper cache can serve an arbitrary number of users; however, each user can access only a single helper cache. Also, we assume that the server knows the user-to-helper cache association, defined as the sets of users connected to each helper cache, during the cache placement phase. We propose a solution for the aforementioned coded caching problem by introducing a combinatorial structure called a Shared and Private Placement Delivery Array (SP-PDA). These SP-PDAs describe the helper cache placement, private cache placement, and the server transmissions in a single array. Further, we propose a novel construction of SP-PDAs using two Placement Delivery Arrays (PDAs). Interestingly, we observe that the permutations of the columns of the two chosen PDAs result in SP-PDAs with different performances. Moreover, we characterize the conditions for selecting the best column permutations of the chosen PDAs. Furthermore, the coded caching schemes resulting from SP-PDAs subsume two existing coded caching schemes as special cases. Additionally, SP-PDAs enable the construction of coded caching schemes with much smaller subpacketization numbers-subpacketization number is defined as the number of subfiles to which a file is divided-compared to the existing schemes, without paying much in terms of rate (the size of the transmission in the delivery phase).

We study the wireless MapReduce distributed computing system in [5], which operates in three phases: Map, Shuffle, and Reduce. The system consists of a set of distributed nodes assigned to compute arbitrary output functions depending on a file library. The computation of the output functions is decomposed into Map and Reduce functions, and the Shuffle phase, which involves the data exchange, links the two. In our model, the Shuffle phase communication happens over a full-duplex wireless interference channel. For this setting, a coded wireless MapReduce distributed computing scheme exists in the literature, achieving optimal performance under one-shot linear schemes. However, the scheme requires the number of input files to be very large, growing exponentially with the number of nodes. We present schemes that require the number of files to be in the order of the number of nodes and achieve the same performance as the existing scheme. The schemes are obtained by designing a structure called wireless MapReduce array that succinctly represents all three phases in a single array. The wireless MapReduce arrays can also be obtained from the extended placement delivery arrays known for multi-antenna coded caching schemes.

This work explores a multiple transmit antenna setting in a multi-access coded caching (MACC) network where each user accesses more than one cache. A MACC network has$K$users and$K$caches, and each user has access to$r < K$consecutive caches in a cyclic wrap-around manner. There are$L$antennas at the server, and each cache has a normalized size of$M/N\leq 1$. The cyclic wrap-around MACC network with a single antenna at the server has been a well-investigated topic, and several coded caching schemes and improved lower bounds on the performance are known for the same. However, this MACC network has not yet been studied under multi-antenna settings in the coded caching literature. We study the multi-antenna MACC problem and propose a solution for the same by constructing a pair of arrays called caching and delivery arrays. We present three constructions of caching and delivery arrays for different scenarios and obtain corresponding multi-antenna MACC schemes for the same. Two schemes resulting from the above constructions achieve optimal performance under uncoded placement and one-shot delivery. The optimality is shown by matching the performance of the multi-antenna MACC scheme to that of an optimal multi-antenna scheme for a dedicated cache network having an identical number of users, and each user having a normalized cache size of$rM/N$. Further, as a special case, one of the proposed schemes subsumes an existing optimal MACC scheme for the single-antenna setting.

This work studies the coded caching problem in a setting where users can access a private cache of their own along with a shared cache. The setting consists of a server connected to a set of users, assisted by a smaller number of helper nodes that are equipped with their own storage. In addition to the helper caches, each user possesses a dedicated cache which is also used to prefetch file contents. Each helper cache can serve an arbitrary number of users, but each user gets served by only one helper cache. We consider two scenarios: (a) the server has no prior information about the user-to-helper cache association, and (b) the server knows the user-to-helper cache association at the placement phase itself. We design centralized coded caching schemes under uncoded placement for the above two settings. For case (b), we propose four schemes, and establish the optimality of certain schemes in specific memory regimes by deriving matching lower bounds. The fourth scheme, called as the composite scheme, appropriately partitions the file library and the cache memories between two other schemes in case (b) to minimize the rate by leveraging the advantages of both.

This work considers the combinatorial multi-access coded caching problem introduced in the recent work by Muralidhar et al. (2021). The problem setting consists of a central server having a library of$N$files and$C$caches each with capacity$M$. Each user in the system can access a unique set of$r < C$caches, and there exist users corresponding to every distinct set of$r$caches. Therefore, the number of users in the system is$\binom {C}{r}$. For the aforementioned combinatorial multi-access setting, we propose a coded caching scheme with an MDS code-based coded placement. This novel placement technique helps to achieve a better rate in the delivery phase compared to the optimal scheme under uncoded placement when$M> N/C$. For a lower memory regime, we present another scheme with coded placement, which outperforms the optimal scheme under uncoded placement if the number of files is no more than the number of users. Further, we derive an information-theoretic lower bound on the optimal rate-memory trade-off of the combinatorial multi-access coded caching scheme. In addition, using the derived lower bound, we show that the first scheme is optimal in the higher memory regime, and the second scheme is optimal if$N\leq \binom {C}{r}$. Finally, we show that the performance of the first scheme is within a constant factor of the optimal performance, when$r=2$.

This work considers the combinatorial multi-access coded caching problem introduced in the recent work by Muralidhar et al. [P. N. Muralidhar, D. Katyal, and B. S. Rajan, "MaddahAli-Niesen scheme for multi-access coded caching," in IEEE Inf. Theory Workshop (ITW), 2021] The problem setting consists of a central server having a library of N files and C caches each of capacity M. Each user in the system can access a unique set of rN/C. For a lower memory regime, we present another scheme with coded placement, which outperforms the optimal scheme under uncoded placement if the number of files is no more than the number of users. Further, we derive an information-theoretic lower bound on the optimal rate-memory trade-off of the combinatorial multi-access coded caching scheme. Finally, using the derived lower bound, we show that the first scheme is optimal in the higher memory regime, and the second scheme is optimal if $N \leq \binom C r $.

We consider the coded caching problem where users are simultaneously endowed with a private and shared cache. The problem setting consists of a server having a library of files connected to a set of users via a smaller number of helper nodes having its own storage facility. Each user possesses a dedicated cache which is also used to prefetch file contents. Each helper cache serves an arbitrary number of users. We assume that the server knows the set of users served by each helper cache at the content placement itself. For this setting, we design two centralized coded caching schemes based on uncoded placement. The proposed schemes are shown to be optimal in specific memory regimes.

This work addresses the multi-antenna coded caching problem where a server with$L$transmit antennas communicates to$K$users through a wireless broadcast link. In the problem setting, the server has a library of$N$files, and each user is equipped with a dedicated cache of capacity$M$. A novel solution for the multi-antenna coded caching problem is obtained by designing a combinatorial structure called an extended placement delivery array (EPDA). It is shown that the placement delivery arrays known for the centralized coded caching scheme are a special class of EPDAs with$L=1$. Furthermore, three constructions of EPDAs are proposed for the settings: a)$K = t+L$, b)$K = nt+ (n-1)L;L\geq t, n\geq 2$, and c)$K,L,t$such that$t + L\leq K$, where$t = KM/N$is an integer. The multi-antenna schemes resulting from the first two constructions achieve the optimal degrees of freedom (DoF)$t+L$with a subpacketization number -the number of subfiles into which a file is divided-$K/\text {gcd}(K,t,L)$, which is lower than the subpacketization number of the existing schemes. The scheme obtained from the third construction also achieves the optimal DoF with a subpacketization number$\binom {K/{\gamma }}{(t+L)/{\gamma }}\left ({{t+L}}\right)/{\gamma }$, where$\gamma =\text {gcd}(K,t,L)$.

The multi-antenna coded caching problem, where the server having L transmit antennas communicating to K users through a wireless broadcast link, is addressed. In the problem setting, the server has a library of N files, and each user is equipped with a dedicated cache of capacity M. The idea of extended placement delivery array (EPDA), an array which consists of a special symbol ⋆ and integers in a set {1, 2, …, S}, is proposed to obtain a novel solution for the aforementioned multiantenna coded caching problem. From a (K, L, F, Z, S) EPDA, a multi-antenna coded caching scheme with K users, and the server with L transmit antennas, can be obtained in which the normalized memory $\frac{M}{N} = \frac{Z}{F}$, and the delivery time $T = \frac{S}{F}$. The placement delivery array (for single-antenna coded caching scheme) is a special class of EPDAs with L = 1. For the multiantenna coded caching schemes constructed from EPDAs, it is shown that the maximum possible Degree of Freedom (DoF) that can be achieved is t + L, where $t = \frac{{KM}}{N}$ is an integer. Furthermore, two constructions of EPDAs are proposed: a) K = t + L, and b) K = nt + (n − 1)L, L ≥ t, where n ≥ 2 is an integer. In the resulting multi-antenna schemes from those EPDAs achieve the full DoF, while requiring a subpacketization number $\frac{K}{{\gcd (K,t,L)}}$. This subpacketization number is less than that required by previously known schemes in the literature.

The multi-access variant of the coded caching problem with N files, K users and K caches, where each user has access to L neighbouring caches in a cyclic wrap-around manner, is considered. A cut-set based lower bound on the optimal rate-memory trade-off of the multi-access coded caching (MACC) scheme is derived. Furthermore, an improved lower bound on the optimal rate-memory trade-off of the MACC scheme is derived using non-cut-set arguments. The improved lower bound is tighter than the previously known lower bounds for the same setting.

This paper considers the secretive coded caching problem with shared caches in which no user must have access to the files that it did not demand. In a shared cache network, the users are served by a smaller number of helper caches, and each user is connected to exactly one helper cache. To ensure the secrecy constraint in shared cache networks, each user is required to have an individual cache of at least unit file size. The existing secretive coded caching scheme for shared caches requires a subpacketization level, which is exponential in the number of helper caches. In this work, we propose a procedure to obtain new secretive coded caching schemes for shared caches with reduced subpacketization levels by utilizing the placement delivery array constructions. We also show that the existing secretive coded caching scheme for shared caches can be recovered using our procedure. In addition, a lower bound based on cut-set based arguments is derived for the shared cache networks under secrecy constraint and characterized the performance of the obtained scheme.

This work considers the coded caching problem with shared caches, where users share the caches, and each user gets access only to one cache. The number of users connected to each cache is assumed to be known at the server during the placement phase. We focus on the schemes derived using placement delivery arrays (PDAs). The PDAs were originally designed to address the sub-packetization bottleneck of coded caching in a dedicated cache setup. We observe that in the setup of this paper, permuting the columns of the PDA results in schemes with different performances for the same problem, but the sub-packetization level remains the same. This is contrary to what was observed for dedicated cache networks. We propose a procedure to identify the ordering of columns that gives the best performance possible from the PDA employed in the given problem. Further, the performance gain achieved by reordering the columns of the PDA is illustrated using certain classes of PDAs.

The multi-access variant of the coded caching problem with K users, K caches and N files, where each user has access to L neighbouring caches in a cyclic wrap-around manner, is studied. Coded placement technique is introduced in the multi-access coded caching set-up for the first time. Furthermore, it is shown that the rate of transmission can be significantly lowered using coded placement, especially when the number of files is no more than the number of users. For cache memory $M \leq \frac{{N - (K - L)}}{K}$, a multi-access coded caching scheme with coded placement is introduced. The scheme presented is optimal when N ≤ K. Also, for some specific values of K,L,N and M, achievable schemes and matching converses are presented.

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 wraparound 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 keys in a set of caches called the private set of that user. For a given K and L, a technique is also devised to find the private sets of the users.

The multi-access variant of the coded caching problem with$N$files,$K$users and$K$caches, where each user has access to$L$neighbouring caches in a cyclic wrap-around manner, is considered. A cut-set based lower bound on the optimal rate-memory trade-off of the multi-access coded caching (MACC) scheme is derived. Furthermore, an improved lower bound on the optimal rate-memory trade-off of the MACC scheme is derived using non-cut-set arguments. The improved lower bound is tighter than the previously known lower bounds for the same setting. Further, for cache memory$M\leq {(N-K+L)}/{K}$, an achievable scheme makes use of coded placement is presented. By matching with the improved lower bound, the scheme is shown to be optimal when$N\leq K$. Also, lower bounds on the optimal rate-memory trade-off of the MACC scheme incorporating secure delivery and secrecy conditions are derived.

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 the 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}, N\, \left(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 and Tuninetti in the recent work “Fundamental Limits of Caching for Demand Privacy against Colluding Users”. By memory sharing, the achievable memory-rate pair characterizes the exact rate-memory trade-off for the demand private coded caching scheme for cache memory$M\in\left[0,\frac{1}{K(N-1)+1}\right]$.

The multi-access variant of the coded caching problem in the presence of external wiretappers is investigated. A multiaccess coded caching scheme with K users, K caches and N files, where each user has access to L neighbouring caches in a cyclic wrap-around manner, is proposed, which is secure against the wiretappers. Each transmission in the conventional insecure scheme will be now encrypted by a random key. The proposed scheme uses a novel technique for the key placement in the caches. It is also shown that the proposed secure multi-access coded caching scheme is within a constant multiplicative factor from the information-theoretic optimal rate for $L\displaystyle \geq\frac{K}{2}$ and $N\geq 2K$.