Coded distributed computing (CDC) is a new technique proposed with the purpose of decreasing the intense data exchange required for parallelizing distributed computing systems. Under the famous MapReduce paradigm, this coded approach has been shown to decrease this communication overhead by a factor that is linearly proportional to the overall computation load during the mapping phase. In this paper, we propose multi-access distributed computing (MADC) as a generalization of the original CDC model, where now mappers (nodes in charge of the map functions) and reducers (nodes in charge of the reduce functions) are distinct computing nodes that are connected through a multi-access network topology. Focusing on the MADC setting with combinatorial topology, which implies$\Lambda $mappers and$K$reducers such that there is a unique reducer connected to any$\alpha $mappers, we propose a coded scheme and an information-theoretic converse, which jointly identify the optimal inter-reducer communication load, as a function of the computation load, to within a constant gap of 1.5. Additionally, a modified coded scheme and converse identify the optimal max-link communication load across all existing links to within a gap of 4.

Coded distributed computing (CDC), originally proposed by Li et al., leverages coded multicast messages to exchange computed intermediate values among the distributed computing nodes, such that the overall communication load could be reduced by a factor of r, the number of input files assigned to each node. However, in the original CDC framework, each output function/task is composed of intermediate values from all input files. In this paper, we propose a new CDC problem for sparse functions with structured support, where each output function depends on a subset of the input files. For a symmetric structured support for which the input files are divided into G equal-length batches and each output function depends on the same number of G′batches, we propose a novel CDC scheme that is strictly better by a factor G/G′than directly employing the original CDC scheme in the considered problem. Furthermore, by proposing a new converse bound, we prove that the communication load of the proposed CDC scheme is order optimal within a constant multiplicative factor of 6.

This work identifies the fundamental limits of multi-access coded caching (MACC) where each user is connected to multiple caches in a manner that follows a generalized combinatorial topology. This topology stands out as it allows for unprecedented coding gains, even with very modest cache resources. First, we extend the setting and the scheme presented by Muralidhar et al. to a much more general topology that supports both a much denser range of users and the coexistence of users connected to different numbers of caches, all while maintaining the astounding coding gains — here proven to be exactly optimal — associated with the combinatorial topology. This is achieved, for this generalized topology, with a novel information-theoretic converse that we present here, which establishes, together with the scheme, the exact optimal performance under the assumption of uncoded placement. We subsequently consider different connectivity ensembles, including the very general scenario of the entire ensemble of all possible network connectivities/topologies, where any subset of caches can serve any arbitrary number of users. For these settings, we develop novel converse bounds on the optimal performance averaged over the ensemble’s different connectivities. This novel analysis of topological ensembles leaves open the possibility that currently-unknown topologies may yield even higher gains, a hypothesis that is part of the bigger question of which network topology yields the most caching gains.

In typical coded caching scenarios, the content of a central library is assumed to be of interest to all receiving users. However, in a realistic scenario the users may have diverging interests which may intersect to various degrees. What happens for example if each file is of potential interest to, say, 40% of the users and each user has potential interest in 40% of the library? What if then each user caches selfishly only from content of potential interest? In this work, we formulate the symmetric selfish coded caching problem, where each user naturally makes requests from a subset of the library, which defines its own file demand set (FDS), and caches selfishly only contents from its own FDS. For the scenario where the different FDSs symmetrically overlap to some extent, we propose a novel information-theoretic converse that reveals, for such general setting of symmetric FDS structures, that selfish coded caching yields a load performance which is strictly worse — in the non-trivial memory regime — than that in standard coded caching.

Recently, Muralidhar et al. proposed a novel multi-access system model where each user is connected to multiple caches in a manner that follows the well-known combinatorial topology of combination networks. For such multi-access topology, the same authors proposed an achievable scheme, which stands out for the unprecedented coding gains even with very modest cache resources. In this paper, we identify the fundamental limits of such multi-access setting with exceptional potential, providing an information-theoretic converse which establishes, together with the inner bound by Muralidhar et al., the exact optimal performance under uncoded prefetching.

In this paper, we consider a coded caching scenario where users have heterogeneous interests. Taking into consideration the system model originally proposed by Wang and Peleato, for which the end-receiving users are divided into groups according to their file preferences, we develop a novel information-theoretic converse on the worst-case communication load under uncoded cache placement. Interestingly, the developed converse bound, jointly with one of the coded schemes proposed by Wang and Peleato, allows us to characterize the optimal worst-case communication load under uncoded prefetching within a constant multiplicative gap of 2. Although we restrict the caching policy to be uncoded, our work improves the previously known order optimality results for the considered caching problem.

The original coded caching scenario assumes a content library that is of interest to all receiving users. In a realistic scenario though, the users may have diverging interests which may intersect to various degrees. What happens for example if each file is of potential interest to, say, 40% of the users and each user has potential interest in 40% of the library? In this work, we investigate the so- called symmetrically selfish coded caching scenario, where each user only makes requests from a subset of the library that defines its own file demand set (FDS), each user caches selfishly only contents from its own FDS, and where the different FDSs symmetrically overlap to some extent. In the context of various traditional prefetching scenarios (prior to the emergence of coded caching), selfish approaches were known to be potentially very effective. On the other hand — with the exception of some notable works — little is known about selfish coded caching. We here present a new information-theoretic converse that proves, in a general setting of symmetric FDS structures, that selfish coded caching, despite enjoying a much larger local caching gain and a much smaller set of possible demands, introduces an unbounded load increase compared to the unselfish case. In particular, in the $K$ -user broadcast channel where each user stores a fraction $\gamma $ of the library, where each file (class) is of interest to $\alpha $ users, and where any one specific file is of interest to a fraction $\delta $ of users, the optimal coding gain of symmetrically selfish caching is at least $(K - \alpha)\gamma + 1$ times smaller than in the unselfish scenario. This allows us to draw the powerful conclusion that the optimal selfish coding gain is upper bounded by $1/(1 - \delta)$ , and thus does not scale with $K$ . These derived limits are shown to be exact for different types of demands. In the end, this work provides, in a unified manner, the strong conclusion that selfish caching can cause unbounded performance deterioration in coded caching systems.

This paper considers the problem of code design for a channel where communications and radar systems coexist, modeled as having both Additive White Gaussian Noise (AWGN) and Additive Radar Interference (ARI). The issue of how to adapt or re-design convolutional codes (decoded by the Viterbi algorithm) and LDPC codes (decoded by the sum-product algorithm and optimized by using the EXIT chart method) to effectively handle the overall non-Gaussian ARI noise is investigated. A decoding metric is derived from the non-Gaussian ARI channel transition probability as a function of the Signal-to-Noise Ratio (SNR) and Interference-to-Noise Ratio (INR). Two design methodologies are benchmarked against a baseline "unaltered legacy system", where a code designed for AWGN-only noise, but used on the non-Gaussian ARI channel, is decoded by using the AWGN-only metric (i.e., as if INR is zero). The methodologies are: M1) codes designed for AWGN-only noise, but decoded with the new metric that accounts for both SNR and INR; and M2) codes optimized for the overall non-Gaussian ARI channel. Both methodologies give better average Bit Error Rate (BER) in the high INR regime compared to the baseline. In the low INR regime, both methodologies perform as the baseline since in this case the radar interference is weak. Interestingly, the performance improvement of M2 over M1 is minimal. In practice, this implies that specifications in terms of channel error correcting codes for commercially available wireless systems need not be changed, and that it suffices to use an appropriate INR-based decoding metric in order to effectively cope with the ARI.