Large-scale decentralized learning frameworks such as federated learning (FL), require both communication efficiency and strong data security, motivating the study of secure aggregation (SA). While information-theoretic SA is well understood in centralized and fully connected networks, its extension to decentralized networks with limited local connectivity remains largely unexplored. This paper introduces \emph{topological secure aggregation} (TSA), which studies one-shot, information-theoretically secure aggregation of neighboring users' inputs over arbitrary network topologies. We develop a unified linear design framework that characterizes TSA achievability through the spectral properties of the communication graph, specifically the kernel of a diagonally modulated adjacency matrix. For several representative classes of $d$-regular graphs including ring, prism and complete topologies, we establish the optimal communication and secret key rate region. In particular, to securely compute one symbol of the neighborhood sum, each user must (i) store at least one key symbol, (ii) broadcast at least one message symbol, and (iii) collectively, all users must hold at least $d$ i.i.d. key symbols. Notably, this total key requirement depends only on the \emph{neighborhood size} $d$, independent of the network size, revealing a fundamental limit of SA in decentralized networks with limited local connectivity.

Coded polynomial aggregation (CPA) enables the master to directly recover a weighted aggregation of polynomial evaluations without individually decoding each term, thereby reducing the number of required worker responses. In this paper, we extend CPA to straggler-aware distributed computing systems and introduce a straggler-aware CPA framework with pre-specified non-straggler patterns, where exact recovery is required only for a given collection of admissible non-straggler sets. Our main result shows that exact recovery of the desired aggregation is achievable with fewer worker responses than required by polynomial coded computing based on individual decoding, and that feasibility is fundamentally characterized by the intersection structure of the non-straggler patterns. In particular, we establish necessary and sufficient conditions for exact recovery in straggler-aware CPA and identify an intersection-size threshold that is sufficient to guarantee exact recovery. We further prove that this threshold becomes both necessary and sufficient when the number of admissible non-straggler sets is sufficiently large. We also provide an explicit construction of feasible CPA schemes whenever the intersection size exceeds the derived threshold. Finally, simulations reveal a sharp feasibility transition at the predicted threshold, providing empirical evidence that the bound is tight in practice.

This paper studies the master-worker distributed linearly separable computation problem, where the considered computation task, referred to as linearly separable function, is a generic linear map. This model includes cooperative distributed gradient coding, real-time rendering, linear transforms, etc. as special cases. The computation task on K datasets can be expressed as Kclinear combinations of K messages, where each message is the output of an individual function on one dataset. In this distributed computing model, the K datasets are assigned to N workers for computation. Due to the possible presence of stragglers, it is required that the master can obtain the desired computation task from the answers of any Nrout of N workers. The computation cost is defined as the number of datasets assigned to each worker, while the communication cost is defined as the number of codewords that should be received. The objective is to characterize the optimal tradeoff between the computation and communication costs. A common way to assign the datasets to the workers is “cyclic assignment”. This has been considered in several theoretical works, as well as gradient coding, etc. Motivated by its theoretical and practical relevance, in this paper we focus on the cyclic assignment and solve the problem by determining the optimal computation/communication cost tradeoff when N = K and order optimal within a factor of 2 otherwise. In particular, this paper proposes a new computing scheme with the cyclic assignment based on the concept of interference alignment, by treating each message which cannot be computed by a worker as an interference from this worker. The decodability of our scheme is proved for the cases Kc[K/N (Nr− m + 1) : K] and N = Nrwith m+u−1 dividing N (where u = [ KcN K ]), and is further numerically verified for N ≤ 60. Beyond the appealing order-optimality result, we also show that the proposed scheme achieves significant gains over the current state of the art in practice. Experimental results over Tencent Cloud show the reduction of whole distributed computing process time of our scheme is up to 72.8% compared to the benchmark scheme which treats the computation on Kclinear combinations as Kcindividual computations.

Secure aggregation is concerned with the task of securely computing the sum of the inputs from multiple users by an aggregation server without letting the server know the inputs beyond their summation. It finds broad applications in distributed machine learning paradigms such as federated learning (FL) where numerous clients, each holding a proprietary dataset, periodically upload their locally trained models (abstracted as inputs) to a parameter server. The server then generates an aggregate model, typically through averaging, which is shared back with clients as the starting point for a new round of local training. To protect data security, secure aggregation protocols leverage cryptographic techniques to ensure the server gains no additional information beyond the input sum, even if it colludes with a subset of users. While the simple star client-server architecture provides insights into the fundamental utility-security trade-off in secure aggregation, it falls short of capturing the impact of network topology in practical systems. Motivated by hierarchical federated learning, we investigate the secure aggregation problem in a three-layer hierarchical network, where clustered users communicate with an aggregation server via an intermediate layer of relays. In addition to conventional server security which ensures the server learns only the input sum, we also impose relay security, requiring that the relays remain oblivious to users’ inputs. For such a hierarchical secure aggregation (HSA) problem, we characterize the optimal multifaceted trade-off between communication efficiency (measured by user-to-relay and relay-to-server communication rates) and key generation efficiency (including individual and source key rates). A core contribution of this work is the derivation of the optimal source key rate as a function of the number of relays, cluster size, and collusion level. We propose an optimal communication scheme alongside a key generation scheme utilizing a novel matrix structure called extended Vandermonde matrix that guarantees both input sum recovery and security. Moreover, we derive a tight information-theoretic converse proof to establish the optimal rate region for the HSA problem.

Coded elastic computing, introduced by Yang et al. in 2018, is a technique designed to mitigate the impact of elasticity in cloud computing systems, where machines can be preempted or be added during computing rounds. This approach utilizes maximum distance separable (MDS) coding for both storage and download in matrix-matrix multiplications. The proposed scheme is unable to tolerate stragglers and has high encoding complexity and upload cost. In 2023, we addressed these limitations by employing uncoded storage and Lagrange-coded download. However, it results in a large storage size. To address the challenges of storage size and upload cost, in this paper, we focus on Lagrange-coded elastic computing based on uncoded download. We propose a new class of elastic computing schemes, using Lagrange-coded storage with uncoded download (LCSUD). Our proposed schemes address both elasticity and straggler challenges while achieving lower storage size, reduced encoding complexity, and upload cost compared to existing methods.

Coded elastic computing enables virtual machines to be preempted for high-priority tasks while allowing new virtual machines to join ongoing computation seamlessly. This paper addresses coded elastic computing for matrix-matrix multiplications with straggler tolerance by encoding both storage and download using Lagrange codes. In 2018, Yang et al. introduced the first coded elastic computing scheme for matrix-matrix multiplications, achieving a lower computational load requirement. However, this scheme lacks straggler tolerance and suffers from high upload cost. Zhong et al. (2023) later tackled these shortcomings by employing uncoded storage and Lagrange-coded download. However, their approach requires each machine to store the entire dataset. This paper introduces a new class of elastic computing schemes that utilize Lagrange codes to encode both storage and download, achieving a reduced storage size. The proposed schemes efficiently mitigate both elasticity and straggler effects, with a storage size reduced to a fraction 1/L of Zhong et al.'s approach, at the expense of doubling the download cost. Moreover, we evaluate the proposed schemes on AWS EC2 by measuring computation time under two different tasks allocations: heterogeneous and cyclic assignments. Both assignments minimize computation redundancy of the system while distributing varying computation loads across machines.

In a typical formulation of the private information retrieval (PIR) problem, a single user wishes to retrieve one out of$ K$files from N servers without revealing the demanded file index to any server. This paper formulates an extended model of PIR, referred to as multi-message private computation (MM-PC), where instead of retrieving a single file, the user wishes to retrieve$P\gt 1$linear combinations of files while preserving the privacy of the demand information. The MM-PC problem is a generalization of the private computation (PC) problem (where the user requests one linear combination of the files), and the multi-message private information retrieval (MM-PIR) problem (where the user requests$P\gt 1$files). A baseline achievable scheme repeats the optimal PC scheme by Sun and Jafar P times, or treats each possible demanded linear combination as an independent file and then uses the near optimal MM-PIR scheme by Banawan and Ulukus. In this paper, we propose a new MM-PC scheme that significantly improves upon the baseline schemes. In doing so, we design the queries inspired by the structure in the cache-aided scalar linear function retrieval scheme by Wan et al., which leverages the dependency between linear functions to reduce the amount of communications. To ensure the decodability of our scheme, we propose a new method to benefit from the existing dependency, referred to as the sign assignment step. In the end, we use Maximum Distance Separable matrices to code the queries, which allows the reduction of download from the servers, while preserving privacy. By the proposed schemes, we characterize the capacity within a multiplicative factor of 2.

Federated learning (FL) is a useful tool that enables the training of machine learning models over distributed data without having to collect data centrally. When deploying FL in constrained wireless environments, however, intermittent connectivity of devices, heterogeneous connection quality, and non-i.i.d. data can severely slow convergence. In this paper, we consider FL with arbitrary device participation probabilities for each round and show that by weighing each device’s update by the reciprocal of their per-round participation probability, we can guarantee convergence to a stationary point. Our bound applies to non-convex loss functions and non-i.i.d. datasets and recovers state-of-the-art convergence rates for both full and uniform partial participation, including linear speedup, with only a single-sided learning rate. Then, using the derived convergence bound, we develop a new online client selection and power allocation algorithm that utilizes the Lyapunov drift-plus-penalty framework to opportunistically minimize a function of the convergence bound and the average communication time under a transmit power constraint. We use optimization over manifold techniques to obtain a solution to the minimization problem. Thanks to the Lyapunov framework, one key feature of the algorithm is that knowledge of the channel distribution is not required and only the instantaneous channel state information needs to be known. Using the CIFAR-10 dataset with varying levels of data heterogeneity, we show through simulations that the communication time can be significantly decreased using our algorithm compared to uniformly random participation, especially for heterogeneous channel conditions.

In 2018, Yang et al. introduced a novel and effective approach, using maximum distance separable (MDS) codes, to mitigate the impact of elasticity in cloud computing systems. This approach is referred to as coded elastic computing. Some limitations of this approach include that it assumes all virtual machines have the same computing speeds and storage capacities, and it cannot tolerate stragglers for matrix-matrix multiplications. In order to resolve these limitations, in this paper, we introduce a new combinatorial optimization framework, named uncoded storage coded transmission elastic computing (USCTEC), for heterogeneous speeds and storage constraints, aiming to minimize the expected computation time for matrix-matrix multiplications, under the consideration of straggler tolerance. Within this framework, we propose optimal solutions with straggler tolerance under relaxed storage constraints. Moreover, we propose a heuristic algorithm that considers heterogeneous storage constraints. Our results demonstrate that the proposed algorithm outperforms baseline solutions utilizing cyclic storage placements, in terms of both expected computation time and storage size.

In federated learning (FL), clients usually have diverse participation statistics that are unknown a priori, which can significantly harm the performance of FL if not handled properly. Existing works aiming at addressing this problem are usually based on global variance reduction, which requires a substantial amount of additional memory in a multiplicative factor equal to the total number of clients. An important open problem is to find a lightweight method for FL in the presence of clients with unknown participation rates. In this paper, we address this problem by adapting the aggregation weights in federated averaging (FedAvg) based on the participation history of each client. We first show that, with heterogeneous participation statistics, FedAvg with non-optimal aggregation weights can diverge from the optimal solution of the original FL objective, indicating the need of finding optimal aggregation weights. However, it is difficult to compute the optimal weights when the participation statistics are unknown. To address this problem, we present a new algorithm called FedAU, which improves FedAvg by adaptively weighting the client updates based on online estimates of the optimal weights without knowing the statistics of client participation. We provide a theoretical convergence analysis of FedAU using a novel methodology to connect the estimation error and convergence. Our theoretical results reveal important and interesting insights, while showing that FedAU converges to an optimal solution of the original objective and has desirable properties such as linear speedup. Our experimental results also verify the advantage of FedAU over baseline methods with various participation patterns.

In federated learning (FL), data heterogeneity is the main reason that existing theoretical analyses are pessimistic about the convergence rate. In particular, for many FL algorithms, the convergence rate grows dramatically when the number of local updates becomes large, especially when the product of the gradient divergence and local Lipschitz constant is large. However, empirical studies can show that more local updates can improve the convergence rate even when these two parameters are large, which is inconsistent with the theoretical findings. This paper aims to bridge this gap between theoretical understanding and practical performance by providing a theoretical analysis from a new perspective on data heterogeneity. In particular, we propose a new and weaker assumption compared to the local Lipschitz gradient assumption, named the heterogeneity-driven pseudo-Lipschitz assumption. We show that this and the gradient divergence assumptions can jointly characterize the effect of data heterogeneity. By deriving a convergence upper bound for FedAvg and its extensions, we show that, compared to the existing works, local Lipschitz constant is replaced by the much smaller heterogeneity-driven pseudo-Lipschitz constant and the corresponding convergence upper bound can be significantly reduced for the same number of local updates, although its order stays the same. In addition, when the local objective function is quadratic, more insights on the impact of data heterogeneity can be obtained using the heterogeneity-driven pseudo-Lipschitz constant. For example, we can identify a region where FedAvg can outperform mini-batch SGD even when the gradient divergence can be arbitrarily large. Our findings are validated using experiments.

In a typical formulation of the private information retrieval (PIR) problem, a single user wishes to retrieve one out of$K$files from$N$servers without revealing the demanded file index to any server. This paper formulates an extended model of PIR, referred to as multi-message private computation (MMPC), where instead of retrieving a single file, the user wishes to retrieve$P > 1$linear combinations of files while preserving the privacy of the demand information. The MM-PC problem is a generalization of the private computation (PC) problem (where the user requests one linear combination of the files), and the multi-message private information retrieval (MM-PIR) problem (where the user requests$P > 1$files). A baseline achievable scheme repeats the optimal PC scheme by Sun and Jafar$P$times, or treats each possible demanded linear combination as an independent file and then uses the near optimal MM-PIR scheme by Banawan and Ulukus. In this paper, we propose an achievable MM-PC scheme that significantly improves upon the baseline scheme. Doing so, we design the queries inspired from the structure in the cache-aided scalar linear function retrieval scheme, where they leverage the dependency between messages to reduce the amount of communication. To ensure the decodability of our scheme, we propose a new method to benefit from the existing dependency, referred to as the sign assignment step. In the end, we use Maximum Distance Separable matrices to code the queries, which allows the reduction of download from the servers, while preserving privacy.

Elasticity plays an important role in modern cloud computing systems. Elastic computing allows virtual machines (i.e., computing nodes) to be preempted when high-priority jobs arise, and also allows new virtual machines to participate in the computation. This paper consider the elastic computing with heterogeneous speeds under uncoded storage. In 2018, Yang et al. introduced Coded Storage Elastic Computing (CSEC) to address the elasticity using coding technology, with lower storage and computation load requirements. However, CSEC is limited to certain types of computations (e.g., linear) due to the coded data storage based on linear coding. Then Centralized Uncoded Storage Elastic Computing (CUSEC) with heterogeneous computation speeds was proposed, which directly copies parts of data into the virtual machines. In all existing works in elastic computing, the storage assignment is centralized, meaning that the number and identity of all virtual machines possible used in the whole computation process are known during the storage assignment. In this paper, we consider Decentralized Uncoded Storage Elastic Computing (DUSEC) with heterogeneous computation speeds, where any available virtual machine can join the computation which is not predicted and thus coordination among different virtual machines' storage assignments is not allowed. Under a decentralized storage assignment originally proposed in coded caching by Maddah-Ali and Niesen, we propose a computing scheme with closed-form optimal computation time. We also run experiments over MNIST dataset with Softmax regression model through the Tencent cloud platform, and the experiment results demonstrate that the proposed DUSEC system approaches the state-of-art best storage assignment in the CUSEC system in computation time.

This paper considers the secure aggregation problem for federated learning under an information theoretic cryptographic formulation, where distributed training nodes (referred to as users) train models based on their own local data and a server aggregates the trained models without retrieving other information about users' local data. Secure aggregation generally contains two phases, namely key sharing phase and model aggregation phase. Due to the common effect of user dropouts in federated learning, the model aggregation phase should contain two rounds, where in the first round the users transmit masked models and according to the identity of surviving users, the surviving users then transmit some further messages to help the server decrypt the sum of users' trained models. The objective of the considered information theoretic formulation is to characterize the capacity region of the communication rates from the users to the server in the two rounds of the model aggregation phase, by assuming that the key sharing have already been done offline in prior. If the keys shared by the users could be any random variables, the capacity was fully characterized in the literature. Recently, an additional constraint on the keys (referred to as uncoded groupwise keys) was added into the problem, where there are several independent keys in the system and each key is shared by exactly S users, where S is a system parameter. In this paper, we fully characterize the capacity region for this problem by matching new converse and achievable bounds.

Secure aggregation is concerned with the task of securely uploading the inputs associated with multiple users to an aggregation server without revealing the user inputs to the server besides the summation of all inputs. It finds broad applications in distributed machine learning paradigms such as federated learning (FL). Motivated by practical hierarchical FL systems which utilize the client-edge-cloud network architecture to improve delay performance, we study the hierarchical secure aggregation (HSA) problem in a 3-layer hierarchical network where a total of$UV$users are connected to an aggregation server through$U$relay nodes each being associated with a disjoint subset of$V$users. Security requires that the server learn nothing beyond the desired sum of the inputs (server security), and each relay learn nothing about the user inputs (relay security) even if they collude with up to$T$users. We characterize the optimal communication and key rate region by proposing a novel secure aggregation scheme and deriving an information-theoretic converse that matches the achievable scheme. In particular, we show that when$T\geq(U-1)V$, the proposed HSA problem is infeasible. Otherwise when$T < (U-1)V$, to securely compute 1 bit of the desired sum, each user needs to upload at least 1 bit to its associating relay, each relay needs to upload at least 1 bit to the server, each user needs to hold at least 1 key bit, and all users need to collectively hold at least$\max\{V+T, \min\{U+T-1,UV- 1\}\}$(source) key bits. The characterization of the source key rate is a major contribution of this work.

In this work, we present a new federation framework for Union-Labs, an innovative cloud-based resource-sharing infrastructure designed for next-generation (NextG) and Internet of Things (IoT) over-the-air (OTA) experiments. The framework aims to reduce the federation complexity for testbeds developers by automating tedious backend operations, thereby providing scalable federation and remote access to various wireless testbeds. We first describe the key components of the new federation framework, including the Systems Manager Integration Engine (SMIE), the Automated Script Generator (ASG), and the Database Context Manager (DCM). We then prototype and deploy the new Federation Plane on the Amazon Web Services (AWS) public cloud, demonstrating its effectiveness by federating two wireless testbeds: i) UB NeXT, a 5G-and-beyond (5G+) testbed at the University at Buffalo, and ii) UT IoT, an IoT testbed at the University of Utah1.

This paper investigates the privacy problem in coded caching. Recently, it was shown that the seminal MAN coded caching scheme leaks the demand information of each user to the other users in the system. Many works have considered coded caching with demand privacy, while every non-trivial existing coded caching scheme with private demands was built on the fact that the cache information of each user is private to the others. However, most of these schemes leak the users’ cache information. As a consequence, in most realistic settings (e.g., video streaming) where the system is used over time with multiple sequential transmission rounds, these schemes leak demand privacy beyond the first round. This observation motivates our new formulation of coded caching with simultaneously private demands and caches in this paper. For this new model, we first show that an existing coded caching scheme with private demands, referred to as the virtual users scheme, can also preserve the privacy of the users’ caches. However, this scheme suffers from its extremely high subpacketization. The main contribution of this paper is a new construction that generates private coded caching schemes by leveraging two-server private information retrieval (PIR) schemes. We show that if in the PIR scheme the demand is uniform over all files and the queries are independent, the resulting caching scheme is private on both the demands and the caches; otherwise, the resulting scheme is private only on the demands. This first result constructs coded caching schemes from a particular class of PIR schemes, which is a new “structural” result in its own merit. We then construct new two-server PIR schemes with uniform demand and independent queries, such that the resulting caching scheme has a subpacketization level that is significantly reduced compared to the virtual users scheme. Interestingly we propose a new construction of two-server PIR schemes with uniform demand and independent queries by exploiting coded caching schemes. By applying the seminal Maddah-Ali and Niesen coded caching scheme in our construction, the resulting two-server PIR scheme is proved to be order-optimal under the constraint of uniform demand and independent queries. This is a second new “structural” result that somehow closes the loop in the relationship between coded caching and PIR. As a by-product of our new construction, we obtain a new demand private that improves the load of the state-of-the-art demand private caching schemes known so far. Finally, to explore a broader tradeoff between cache privacy and transmission load, we relax the cache privacy constraint and introduce the definition of cache information leakage. Then, again as a by-product of our new construction, we propose new schemes with perfect demand privacy and imperfect cache privacy that achieve an order-gain in load with respect to the scheme with perfect privacy on both demands and caches. This also establishes a first non-trivial achievability result in the tradeoff between load and cache privacy, for demand-private caching schemes.

This paper considers the secure aggregation problem for federated learning under an information theoretic cryptographic formulation, where distributed training nodes (referred to as users) train models based on their own local data and a curious-but-honest server aggregates the trained models without retrieving other information about users’ local data. Secure aggregation generally contains two phases, namely key sharing phase and model aggregation phase. Due to the common effect of user dropouts in federated learning, the model aggregation phase should contain two rounds, where in the first round the users transmit masked models and, in the second round, according to the identity of surviving users after the first round, these surviving users transmit some further messages to help the server decrypt the sum of users’ trained models. The objective of the considered information theoretic formulation is to characterize the capacity region of the communication rates from the users to the server in the two rounds of the model aggregation phase, assuming that key sharing has already been performed offline in prior. In this context, Zhao and Sun completely characterized the capacity region under the assumption that the keys can be arbitrary random variables. More recently, an additional constraint, known as “uncoded groupwise keys,” has been introduced. This constraint entails the presence of multiple independent keys within the system, with each key being shared by precisely S users, where S is a defined system parameter. The capacity region for the information theoretic secure aggregation problem with uncoded groupwise keys was established in our recent work subject to the condition S > K - U, where K is the number of total users and U is the designed minimum number of surviving users (which is another system parameter). In this paper we fully characterize the capacity region for this problem by matching a new converse bound and an achievable scheme. Experimental results over the Tencent Cloud show the improvement on the model aggregation time compared to the original secure aggregation scheme.

Secure aggregation, which is a core component of federated learning, aggregates locally trained models from distributed users at a central server. The “secure” nature of such aggregation consists of the fact that no information about the local users’ data must be leaked to the server except the aggregated local models. In order to guarantee security, some keys may be shared among the users (this is referred to as the key sharing phase). After the key sharing phase, each user masks its trained model which is then sent to the server (this is referred to as the model aggregation phase). This paper follows the information theoretic secure aggregation problem originally formulated by Zhao and Sun, with the objective to characterize the minimum communication cost from the$\mathsf K$users in the model aggregation phase. Due to user dropouts, which are common in real systems, the server may not receive all messages from the users. A secure aggregation scheme should tolerate the dropouts of at most${\mathsf K}-{\mathsf U}$users, where$\mathsf U$is a system parameter. The optimal communication cost is characterized by Zhao and Sun, but with the assumption that the keys stored by the users could be any random variables with arbitrary dependency. On the motivation that uncoded groupwise keys are more convenient to be shared and could be used in large range of applications besides federated learning, in this paper we add one constraint into the above problem, namely, that the key variables are mutually independent and each key is shared by a group of$\mathsf S$users, where$\mathsf S$is another system parameter. To the best of our knowledge, all existing secure aggregation schemes (with information theoretic security or computational security) assign coded keys to the users. We show that if${\mathsf S}\gt {\mathsf K}-{\mathsf U}$, a new secure aggregation scheme with uncoded groupwise keys can achieve the same optimal communication cost as the best scheme with coded keys; if${\mathsf S}\leq {\mathsf K}-{\mathsf U}$, uncoded groupwise key sharing is strictly sub-optimal. Finally, we also implement our proposed secure aggregation scheme into Amazon EC2, which are then compared with the existing secure aggregation schemes with offline key sharing.

Secure aggregation, which is a core component of federated learning, aggregates locally trained models from distributed users at a central server, without revealing any other information about the local users' data. This paper follows a recent information theoretic secure aggregation problem with user dropouts, where the objective is to characterize the minimum communication cost from the$\mathrm{K}$users to the server during the model aggregation. All existing secure aggregation protocols let the users share and store coded keys to guarantee security. On the motivation that uncoded groupwise keys are more convenient to be shared and could be used in large range of practical applications, this paper is the first to consider uncoded groupwise keys, where the keys are mutually independent and each key is shared by a group of$\mathrm{S}$users. We show that if$\mathrm{S}$is beyond a threshold, a new secure aggregation protocol with uncoded groupwise keys, referred to as GroupSecAgg, can achieve the same optimal communication cost as the best protocol with coded keys. The experiments on Amazon EC2 show the considerable improvements on the key sharing and model aggregation times compared to the state-of-the art.

In cloud computing systems, elastic events and stragglers increase the uncertainty of the system, leading to computation delays. Coded elastic computing (CEC) introduced by Yang et al. in 2018 is a framework which mitigates the impact of elastic events using Maximum Distance Separable (MDS) coded storage. It proposed a CEC scheme for both matrix-vector multiplication and general matrix-matrix multiplication applications. However, in these applications, the proposed CEC scheme cannot tolerate stragglers due to the limitations imposed by MDS codes. In this paper we propose a new elastic computing scheme using uncoded storage and Lagrange coded computing approaches. The proposed scheme can effectively mitigate the effects of both elasticity and stragglers. Moreover, it produces a lower complexity and smaller recovery threshold compared to existing coded storage based schemes.

Federated learning (FL) enables distributed model training from local data collected by users. In distributed systems with constrained resources and potentially high dynamics, e.g., mobile edge networks, the efficiency of FL is an important problem. Existing works have separately considered different configurations to make FL more efficient, such as infrequent transmission of model updates, client subsampling, and compression of update vectors. However, an important open problem is how to jointly apply and tune these control knobs in a single FL algorithm, to achieve the best performance by allowing a high degree of freedom in control decisions. In this paper, we address this problem and propose FlexFL – an FL algorithm with multiple options that can be adjusted flexibly. Our FlexFL algorithm allows both arbitrary rates of local computation at clients and arbitrary amounts of communication between clients and the server, making both the computation and communication resource consumption adjustable. We prove a convergence upper bound of this algorithm. Based on this result, we further propose a stochastic optimization formulation and algorithm to determine the control decisions that (approximately) minimize the convergence bound, while conforming to constraints related to resource consumption. The advantage of our approach is also verified using experiments.

Distributed Linearly Separable Computation problem under the cyclic assignment is studied in this paper. It is a problem widely existing in cooperated distributed gradient coding, real-time rendering, linear transformers, etc. In a distributed computing system, a master asks N distributed workers to compute a linearly separable function from K datasets. The task function can be expressed as Kclinear combinations of K messages, where each message is the output of one individual function of one dataset. Straggler effect is also considered, such that from the answers of each Nrworker, the master should recover the task. The computation cost is defined as the number of datasets assigned to each worker, while the communication cost is defined as the number of (coded) messages which should be received. The objective is to characterize the optimal tradeoff between the computation and communication costs. Various distributed computing scheme were proposed in the literature with a well-known cyclic data assignment, but the (order) optimality of this problem remains open, even under the cyclic assignment. This paper proposes a new computing scheme with the cyclic assignment based on interference alignment, which is near optimal under the cyclic assignment.

We propose a flexible low complexity design (FLCD) of coded distributed computing (CDC) with empirical evaluation on Amazon Elastic Compute Cloud (Amazon EC2). CDC can expedite MapReduce like computation by trading increased map computations to reduce communication load and shuffle time. A main novelty of FLCD is to utilize the design freedom in defining map and reduce functions to develop asymptotic homogeneous systems to support varying intermediate values (IV) sizes under a general MapReduce framework. Compared to existing designs with constant IV sizes, FLCD offers greater flexibility in adapting to network parameters and significantly reduces the implementation complexity by requiring fewer input files and shuffle groups. The FLCD scheme is the first proposed low-complexity CDC design that can operate on a network with an arbitrary number of nodes and computation load. We perform empirical evaluations of the FLCD by executing the TeraSort algorithm on an Amazon EC2 cluster. This is the first time that theoretical predictions of the CDC shuffle time are validated by empirical evaluations. The evaluations demonstrate a 2.0 to 4.24× speedup compared to conventional uncoded MapReduce, a 12 to 52 percent reduction in total time, and a wider range of operating network parameters compared to existing CDC schemes.

This paper studies the fundamental limits of the shared-link coded caching problem with correlated files, where a server with a library of${\mathsf N}$files communicates with${\mathsf K}$users who can locally cache${\mathsf M}$files. Given an integer${\mathsf r}\in [{\mathsf N}]$, correlation is modelled as follows: each${\mathsf r}$-subset of files contains a unique common block. The tradeoff between the cache size and the average transmitted load over the uniform demand distribution is studied. First, a converse bound under the constraint of uncoded cache placement (i.e., each user directly stores a subset of the library bits) is derived. Then, a caching scheme for the case where every user demands a distinct file (possible for${\mathsf N}\geq {\mathsf K}$) is shown to be optimal under the constraint of uncoded cache placement. This caching scheme is further proved to be decodable and optimal under the constraint of uncoded cache placement when (i)${\mathsf K} {\mathsf r} {\mathsf M}\leq 2 {\mathsf N}$or${\mathsf K} {\mathsf r} {\mathsf M}\geq ({\mathsf K}-1) {\mathsf N}$or${\mathsf r}\in \{1,2, {\mathsf N}-1, {\mathsf N}\}$, and (ii) when the number of distinct demanded files is no larger than four. Finally, a new delivery scheme based on interference alignment which jointly serves the users’ demands is shown to be order optimal to within a factor of 2 under the constraint of uncoded cache placement. As an extension, the above exact and order optimal results can be extended to the worst-case load. As by-products, an extension of the proposed scheme for${\mathsf M}= {\mathsf N}/ {\mathsf K}$is shown to reduce the load of state-of-the-art schemes for the coded caching problem where the users can request multiple files; the proposed scheme for distinct demands can be extended to the coded distributed computing problem with a central server, which achieves the optimal transmission load over the binary field.

Federated learning (FL) is a key enabler for efficient communication and computing, leveraging devices’ distributed computing capabilities. However, applying FL in practice is challenging due to the local devices’ heterogeneous energy, wireless channel conditions, and non-independently and identically distributed (non-IID) data distributions. To cope with these issues, this paper proposes a novel learning framework by integrating FL and width-adjustable slimmable neural networks (SNN). Integrating FL with SNNs is challenging due to time-varying channel conditions and data distributions. In addition, existing multi-width SNN training algorithms are sensitive to the data distributions across devices, which makes SNN ill-suited for FL. Motivated by this, we propose a communication and energy-efficient SNN-based FL (namedSlimFL) that jointly utilizessuperposition coding (SC)for global model aggregation andsuperposition training (ST)for updating local models. By applying SC, SlimFL exchanges the superposition of multiple-width configurations decoded as many times as possible for a given communication throughput. Leveraging ST, SlimFL aligns the forward propagation of different width configurations while avoiding inter-width interference during backpropagation. We formally prove the convergence of SlimFL. The result reveals that SlimFL is not only communication-efficient but also deals with non-IID data distributions and poor channel conditions, which is also corroborated by data-intensive simulations.

Hierarchical SGD (H-SGD) has emerged as a new distributed SGD algorithm for multi-level communication networks. In H-SGD, before each global aggregation, workers send their updated local models to local servers for aggregations. Despite recent research efforts, the effect of local aggregation on global convergence still lacks theoretical understanding. In this work, we first introduce a new notion of "upward" and "downward" divergences. We then use it to conduct a novel analysis to obtain a worst-case convergence upper bound for two-level H-SGD with non-IID data, non-convex objective function, and stochastic gradient. By extending this result to the case with random grouping, we observe that this convergence upper bound of H-SGD is between the upper bounds of two single-level local SGD settings, with the number of local iterations equal to the local and global update periods in H-SGD, respectively. We refer to this as the "sandwich behavior". Furthermore, we extend our analytical approach based on "upward" and "downward" divergences to study the convergence for the general case of H-SGD with more than two levels, where the "sandwich behavior" still holds. Our theoretical results provide key insights of why local aggregation can be beneficial in improving the convergence of H-SGD.

This paper aims to integrate two synergetic technologies, federated learning (FL) and width-adjustable slimmable neural network (SNN) architectures. FL preserves data privacy by exchanging the locally trained models of mobile devices. By adopting SNNs as local models, FL can flexibly cope with the time-varying energy capacities of mobile devices. Combining FL and SNNs is however non-trivial, particularly under wireless connections with time-varying channel conditions. Furthermore, existing multi-width SNN training algorithms are sensitive to the data distributions across devices, so are ill-suited to FL. Motivated by this, we propose a communication and energy efficient SNN-based FL (named SlimFL) that jointly utilizes superposition coding (SC) for global model aggregation and superposition training (ST) for updating local models. By applying SC, SlimFL exchanges the superposition of multiple width configurations that are decoded as many as possible for a given communication throughput. Leveraging ST, SlimFL aligns the forward propagation of different width configurations, while avoiding the inter-width interference during back propagation. We formally prove the convergence of SlimFL. The result reveals that SlimFL is not only communication-efficient but also can counteract non-IID data distributions and poor channel conditions, which is also corroborated by simulations.

Federated learning (FL) is a useful tool in distributed machine learning that utilizes users’ local datasets in a privacy-preserving manner. When deploying FL in a constrained wireless environment; however, training models in a time-efficient manner can be a challenging task due to intermittent connectivity of devices, heterogeneous connection quality, and non-i.i.d. data. In this paper, we provide a novel convergence analysis of non-convex loss functions using FL on both i.i.d. and non-i.i.d. datasets with arbitrary device selection probabilities for each round. Then, using the derived convergence bound, we use stochastic optimization to develop a new client selection and power allocation algorithm that minimizes a function of the convergence bound and the average communication time under a transmit power constraint. We find an analytical solution to the minimization problem. One key feature of the algorithm is that knowledge of the channel statistics is not required and only the instantaneous channel state information needs to be known. Using the FEMNIST and CIFAR-10 datasets, we show through simulations that the communication time can be significantly decreased using our algorithm, compared to uniformly random participation.

In the coded caching literature, the notion of privacy is considered only against demands. On the motivation that multi-round transmissions almost appear everywhere in real communication systems, this paper formulates the coded caching problem with private demands and caches. Only one existing private caching scheme, which is based on introducing virtual users, can preserve the privacy of demands and caches simultaneously, but at the cost of an extremely large subpacketization exponential in the product of the number of users (K) and files (N) in the system. In order to reduce the subpacketization while satisfying the privacy constraints, we propose a novel approach which constructs private coded caching schemes through private information retrieval (PIR). Based on this approach, we propose novel schemes with private demands and caches which have a subpacketization level in the order exponential with K instead of NK in the virtual user scheme. As a by-product, for the coded caching problem with private demands, a private coded caching scheme could be obtained from the proposed approach, which generally improves the memory-load tradeoff of the private coded caching scheme by Yan and Tuninetti.

We consider the cache-aided multiuser private information retrieval (MuPIR) problem with a focus on the special case of two messages, two users and arbitrary number of databases where the users have distinct demands of the messages. We characterize the optimal memory-load trade-off for the considered MuPIR problem by proposing a novel achievable scheme and a tight converse. The proposed achievable scheme uses the idea of cache-aided interference alignment (CIA) developed in the literature by the same authors. The proposed converse uses a tree-like decoding structure to incorporate both the decodability and privacy requirements of the users. While the optimal characterization of the cache-aided MuPIR problem is challenging in general, this work provides insight into understanding the general structure of the cache-aided MuPIR problem.

Federated learning (FL) faces challenges of intermittent client availability and computation/communication efficiency. As a result, only a small subset of clients can participate in FL at a given time. It is important to understand how partial client participation affects convergence, but most existing works have either considered idealized participation patterns or obtained results with non-zero optimality error for generic patterns. In this paper, we provide a unified convergence analysis for FL with arbitrary client participation. We first introduce a generalized version of federated averaging (FedAvg) that amplifies parameter updates at an interval of multiple FL rounds. Then, we present a novel analysis that captures the effect of client participation in a single term. By analyzing this term, we obtain convergence upper bounds for a wide range of participation patterns, including both non-stochastic and stochastic cases, which match either the lower bound of stochastic gradient descent (SGD) or the state-of-the-art results in specific settings. We also discuss various insights, recommendations, and experimental results.

Elasticity is one important feature in modern cloud computing systems and can result in computation failure or significantly increase computing time. Such elasticity means that virtual machines over the cloud can be preempted under a short notice (e.g., hours or minutes) if a high-priority job appears; on the other hand, new virtual machines may become available over time to compensate the computing resources. Coded Storage Elastic Computing (CSEC) introduced by Yang et al. in 2018 is an effective and efficient approach to overcome the elasticity and it costs relatively less storage and computation load. However, one of the limitations of the CSEC is that it may only be applied to certain types of computations (e.g., linear) and may be challenging to be applied to more involved computations because the coded data storage and approximation are often needed. Hence, it may be preferred to use uncoded storage by directly copying data into the virtual machines. In addition, based on our own measurement, virtual machines on Amazon EC2 clusters often have heterogeneous computation speed even if they have exactly the same configurations (e.g., CPU, RAM, I/O cost). In this paper, we introduce a new optimization framework on Uncoded Storage Elastic Computing (USEC) systems with heterogeneous computing speed to minimize the overall computation time. Under this framework, we propose optimal solutions of USEC systems with or without straggler tolerance using different storage placements. Our proposed algorithms are evaluated using power iteration applications on Amazon EC2.

This paper formulates a distributed computation problem, where a master asks${\mathsf N}$distributed workers to compute a linearly separable function. The task function can be expressed as${\mathsf K}_{\mathrm{ c}}$linear combinations of${\mathsf K}$messages, where each message is a function of one dataset. Our objective is to find the optimal tradeoff between the computation cost (number of uncoded datasets assigned to each worker) and the communication cost (number of symbols the master must download), such that from the answers of any${\mathsf N}_{\mathrm{ r}}$out of${\mathsf N}$workers the master can recover the task function with high probability, where the coefficients of the${\mathsf K}_{\mathrm{ c}}$linear combinations are uniformly i.i.d. over some large enough finite field. The formulated problem can be seen as a generalized version of some existing problems, such as distributed gradient coding and distributed linear transform. In this paper, we consider the specific case where the computation cost is minimum, and propose novel achievability schemes and converse bounds for the optimal communication cost. Achievability and converse bounds coincide for some system parameters; when they do not match, we prove that the achievable distributed computing scheme is optimal under the constraint of a widely used ‘cyclic assignment’ scheme on the datasets. Our results also show that when${\mathsf K}= {\mathsf N}$, with the same communication cost as the optimal distributed gradient coding scheme proposed by Tandonet al. from which the master recovers one linear combination of${\mathsf K}$messages, our proposed scheme can let the master recover any additional${\mathsf N}_{\mathrm{ r}}-1$independent linear combinations of messages with high probability.

Coded caching is a promising technique to smooth out network traffic by storing part of the library content at the users’ local caches. The seminal work on coded caching for single file retrieval by Maddah-Ali and Niesen (MAN) showed the existence of a global caching gain that scales with the total memory in the system, in addition to the known local caching gain in uncoded systems. This paper formulates a novel cache-aided matrix multiplication retrieval problem, relevant for data analytics and machine learning applications. In the considered problem, each cache-aided user requests the product of two matrices from the library. A structure-agnostic solution is to treat each possible matrix product as an independent file and use the MAN coded caching scheme for single file retrieval. This paper proposes two structure-aware schemes, which partition each matrix in the library by either rows or columns and let a subset of users cache some sub-matrices, that improve on the structure-agnostic scheme. For the case where the library matrices are “fat” matrices, the structure-aware row-partition scheme is shown to be order optimal under some constraint.

In the coded caching problem, as originally formulated by Maddah-Ali and Niesen, a server communicates via a noiseless shared broadcast link to multiple users that have local storage capability. In order for a user to decode its demanded file from the coded multicast transmission, the demands of all the users must be globally known, which may violate the privacy of the users. To overcome this privacy problem, Wan and Caire recently proposed several schemes that attain coded multicasting gain while simultaneously guarantee information theoretic privacy of the users’ demands. In Device-to-Device (D2D) networks, the demand privacy problem is further exacerbated by the fact that each user is also a transmitter, which appears to be needing the knowledge of the files demanded by the remaining users in order to form its coded multicast transmission. This paper shows how to solve this seemingly infeasible problem. The main contribution of this paper is the development of new achievable and converse bounds for D2D coded caching that are to within a constant factor of one another when privacy of the users’ demands must be guaranteed even in the presence of colluding users (i.e., when some users share cached contents and demanded file indices). First, a D2D private caching scheme is proposed, whose key feature is the addition of virtual users in the system in order to “hide” the demands of the real users. By comparing the achievable D2D private load with an existing converse bound for the shared-link model without demand privacy constraint, the proposed scheme is shown to be order optimal, except for the very low memory size regime with more files than users. Second, in order to shed light into the open parameter regime, a new achievable scheme and a new converse bound under the constraint of uncoded cache placement (i.e., when each user stores directly a subset of the bits of the library) are developed for the case of two users, and shown to be to within a constant factor of one another for all system parameters. Finally, the two-user converse bound is extended to any number of users by a cut-set type argument. With this new converse bound, the virtual users scheme is shown to be order optimal in all parameter regimes under the constraint of uncoded cache placement and user collusion.

Caching is an efficient way to reduce network traffic congestion during peak hours by storing some content at the users’ local caches. For the shared-link network with end-user-caches, Maddah-Ali and Niesen proposed a two-phase coded caching strategy. In practice, users may communicate with the server through intermediate relays. This paper studies the tradeoff between the memory size M and the network load R for the networks where a server with N files is connected to H relays (without caches), which in turn are connected to K users equipped with caches of M files. When each user is connected to a different subset of r relays, i.e., K = (Hr), the system is referred to as a combination network with end-user-caches. In this work, converse bounds are derived for the practically motivated case of uncoded cache contents, that is, bits of the various files are directly pushed into the user caches without any coding. In this case, once the cache contents and the users’ demands are known, the problem reduces to a general index coding problem. This paper shows that relying on a well-known “acyclic index coding converse bound” results in converse bounds that are not tight for combination networks with end-user-caches. A novel converse bound that leverages the network topology is proposed, which is the tightest converse bound known to date. As a result of independent interest, an inequality that generalizes the well-known sub-modularity of entropy is derived. Several novel caching schemes are proposed, based on the Maddah-Ali and Niesen cache placement. These schemes leverage the structure of the combination network or/and perform interference elimination at the end-users. The proposed schemes are proved: (i) to be (order) optimal for some (N, M, H, r) parameters regimes under the constraint of uncoded cache placement, and (ii) to outperform the state-of-the-art schemes in numerical evaluations.

Throughput-Outage scaling laws for single-hop cache-aided device-to-device (D2D) communications have been extensively investigated under the assumption of the protocol model. However, the corresponding performance under physical models has not been explored; in particular it remains unclear whether link-level power control and scheduling can improve the asymptotic performance. This paper thus investigates the throughput-outage scaling laws of cache-aided single-hop D2D networks considering a general physical channel model. By considering the networks with and without the equal-throughput assumption, we analyze the corresponding outer bounds and provide the achievable performance analysis. Results show that when the equal-throughput assumption is considered, using link-level power control and scheduling cannot improve the scaling laws. On the other hand, when the equal-throughput assumption is not considered, we show that the proposed double time-slot framework with appropriate link-level power control and scheduling can significantly improve the throughput-outage scaling laws, where the fundamental concept is to first distinguish links according to their communication distances, and then enhance the throughput for links with small communication distances.

We propose using Carrier Sensing (CS) for distributed interference management in millimeter-wave (mmWave) cellular networks where spectrum is shared by multiple operators that do not coordinate among themselves. In addition, even the base station sites can be shared by the operators. We describe important challenges in using traditional CS in this setting and propose enhanced CS protocols to address these challenges. Using stochastic geometry, we develop a general framework for downlink coverage probability analysis of our shared mmWave network in the presence of CS and derive the downlink coverage probability expressions for several CS protocols. Our work is the first to investigate and analyze (using stochastic geometry) CS for mmWave networks with spectrum and BS sites shared among non-coordinating operators. We evaluate the downlink coverage probability of our shared mmWave network using simulations as well as numerical examples based on our analysis. Our evaluations show that our proposed approach leads to an improvement in coverage probability, compared to the coverage probability with no CS, for higher values of signal-to-interference and noise ratio (SINR). Interestingly, our evaluations also reveal that for lower values of SINR, not using any CS is the best strategy in terms of the downlink coverage probability.

This paper studies the problem of distributed beam scheduling for 5G millimeter-Wave (mm-Wave) cellular networks where base stations (BSs) belonging to different operators share the same spectrum without centralized coordination among them. Our goal is to design efficient distributed scheduling algorithms to maximize the network utility, which is a function of the achieved throughput by the user equipment (UEs), subject to the average and instantaneous power consumption constraints of the BSs. We propose a Media Access Control (MAC) and a power allocation/adaptation mechanism utilizing the Lyapunov stochastic optimization framework and non-cooperative games. In particular, we first decompose the original utility maximization problem into two sub-optimization problems for each time frame, which are a convex optimization problem and a non-convex optimization problem, respectively. By formulating the distributed scheduling problem as a non-cooperative game where each BS is a player attempting to optimize its own utility, we provide a distributed solution to the non-convex sub-optimization problem via finding the Nash Equilibrium (NE) of the game whose weights are determined optimally by the Lyapunov optimization framework. Finally, we conduct simulation under various network settings to show the effectiveness of the proposed game-based beam scheduling algorithm in comparison to that of several reference schemes.

Our extensive real measurements over Amazon EC2 show that the virtual instances often have different computing speeds even if they share the same configurations. This motivates us to study heterogeneous Coded Storage Elastic Computing (CSEC) systems where machines, with different computing speeds, join and leave the network arbitrarily over different computing steps. In CSEC systems, a Maximum Distance Separable (MDS) code is used for coded storage such that the file placement does not have to be re-defined with each elastic event. Computation assignment algorithms are used to minimize the computation time given computation speeds of different machines. While previous studies of heterogeneous CSEC do not include stragglers - the slow machines during the computation, we develop a new framework in heterogeneous CSEC that introduces straggler tolerance. Based on this framework, we design a novel algorithm using our previously proposed approach for heterogeneous CSEC such that the system can handle any subset of stragglers of a specified size while minimizing the computation time. Furthermore, we establish a trade-off in computation time and straggler tolerance. Another major limitation of existing CSEC designs is the lack of practical evaluations using real applications. In this paper, we evaluate the performance of our designs on Amazon EC2 for applications of the power iteration and linear regression. Evaluation results show that the proposed heterogeneous CSEC algorithms outperform the state-of-the-art designs by more than 30%.

Throughput-Outage scaling laws for single-hop cache-aided device-to-device (D2D) communications have been extensively investigated under the assumption of the protocol model. However, the corresponding performance under physical models has not been explored; in particular it remains unclear whether link-level power control and scheduling can improve the asymptotic performance. This paper thus investigates the asymptotic throughput-outage tradeoff and derives its outer bound for cache-aided D2D networks under two common physical models. The results show that the asymptotic performance of the network under physical models is identical to that under the protocol model when requests are served with equal quality. This indicates that the throughput-outage performance cannot be improved asymptotically by using link-level power control and scheduling.

Distributed linearly separable computation, where a user asks some distributed servers to compute a linearly separable function, was recently formulated by the same authors and aims to alleviate the bottlenecks of stragglers and communication cost in distributed computation. For this purpose, the data center assigns a subset of input datasets to each server, and each server computes some coded packets on the assigned datasets, which are then sent to the user. The user should recover the task function from the answers of a subset of servers, such that the effect of stragglers could be tolerated. In this paper, we formulate a novel secure framework for this distributed linearly separable computation, where we aim to let the user only retrieve the desired function without obtaining any other information about the input datasets, even if it receives the answers of all servers. In order to preserve the security of the input datasets, some common randomness variable independent of the datasets should be introduced into the transmission. We show that any non-secure linear-coding based computing scheme for the original distributed linearly separable computation problem, can be made secure without increasing the communication cost (number of symbols the user should receive). Then we focus on the case where the computation cost of each server (number of datasets assigned to each server) is minimum and aim to minimize the size of the randomness variable (i.e., randomness size) introduced in the system while achieving the optimal communication cost. Novel information theoretic converse bound on the randomness size and some achievable schemes are proposed, where they coincide in some cases.

This paper formulates the shared-link cache-aided matrix multiplication retrieval problem. Matrix multiplication is an essential building block for distributed computing applications. Different from the original coded caching single file retrieval model, in the considered problem each cache-aided user requests the product of two matrices from a library that contains N matrices. A trivial solution, agnostic to the structure of matrix multiplication, is to treat each of the N2possible matrix products as a file in the original single file retrieval coded caching problem. Such a solution can be improved by leveraging the correlation among the entries in the matrix product. In this paper, two structure-aware schemes are proposed, which partition each library matrix either by rows or by columns, and let a subset of users cache some sub-matrices; in the delivery, coded multicast messages are created to leverage the cached content and the correlation among the entries in the requested matrix products. These schemes outperform two baseline schemes, where one sends packets without coding and the other lets each user directly recover the two input matrices. Order optimality results are derived in some parameter regimes.

In the problem of cache-aided multiuser private information retrieval (MuPIR), a set of$K_{\mathrm{u}}$cache-equipped users wish to privately download a set of messages from$N$distributed databases each holding a library of$K$messages. The system works in two phases: the cache placement (prefetching) phase in which the users fill up their cache memory, and the private delivery phase in which the users' demands are revealed and they download an answer from each database so that the their desired messages can be recovered while each individual database learns nothing about the identities of the requested messages. The goal is to design the placement and the private delivery phases such that the load, which is defined as the total number of downloaded bits normalized by the message size, is minimized given any user memory size. This paper considers the MuPIR problem with two messages, arbitrary number of users and databases where uncoded prefetching is assumed, i.e., the users directly copy some bits from the library as their cached contents. We propose a novel MuPIR scheme inspired by the Maddah-Ali and Niesen (MAN) coded caching scheme. The proposed scheme achieves lower load than any existing schemes, especially the product design (PD), and is shown to be optimal within a factor of 8 in general and exactly optimal at very high or very low memory regimes.

Improved routing algorithms are needed for the rapid proliferation of inexpensive, wireless network devices. In certain scenarios, decentralized wireless networks are either necessary or preferred over centralized ones. The barrage relay network (BRN) is an emerging ad hoc, decentralized wireless network designed to address issues of network reliability and routing overhead. In BRNs, the routing of unicast transmissions is controlled by the cooperative formation of controlled-barrage regions (CBRs), based on a simple set of rules. In this paper, we simulate CBR formation to study the routing reliability and node utilization, with the goal of predicting BRN utility in future scenarios. We have three specific aims which have not been addressed in other BRN studies: 1) we study the impact of channel effects on BRN routing, 2) we study the impact of node density significantly above the theoretical minimum density required to guarantee a fully connected network, and 3) we employ large ensembles of random networks to account for the wide variability that ad hoc networks may encounter. We find that CBRs tend to grow spatially as network density increases, leading to significant network utilization. Furthermore, we find with the most realistic fading model employed, a random channel model, requires the most network resources in high density networks. Then, we investigate a trade-off in network resources and reliability. Understanding these effects will lead to the design of more efficient and robust routing algorithms for high density decentralized networks for use in disaster relief, military, vehicle-to-vehicle and wireless sensor network applications.

Cache-aided wireless device-to-device (D2D) networks have demonstrated more promising performance improvement for video distribution than conventional distribution methods; thus, understanding the fundamental scaling behavior of such networks is highly important. However, the existing scaling laws for multi-hop networks are not optimal even in the case of Zipf popularity distributions (gaps between upper and lower bounds are not constants); furthermore, there are no scaling law results for such networks for the more practical case of a Mandelbrot-Zipf (MZipf) popularity distribution. We thus in this work investigate the throughput-outage performance for cache-aided wireless D2D networks adopting multi-hop communications, with the MZipf popularity distribution for file requests and users distributed according to Poisson point process. We propose an achievable content caching and delivery scheme, and then analyze its performance. We obtain the optimal scaling law by showing that the achievable performance is tight to the proposed outer bound. Since the Zipf distribution is a special case of the MZipf distribution, the optimal scaling law for the networks considering the Zipf popularity distribution is also obtained, which closes the gap in literature.

This paper studies the distributed linearly separable computation problem, which is a generalization of many existing distributed computing problems such as distributed gradient coding and distributed linear transform. A master asks${\mathsf {N}}$distributed workers to compute a linearly separable function of${\mathsf {K}}$datasets, which is a set of${\mathsf {K}}_{\mathrm{ c}}$linear combinations of${\mathsf {K}}$equal-length messages (each message is a function of one dataset). We assign some datasets to each worker in an uncoded manner, who then computes the corresponding messages and returns some function of these messages, such that from the answers of any${\mathsf {N}}_{\mathrm{ r}}$out of${\mathsf {N}}$workers the master can recover the task function with high probability. In the literature, the specific case where${\mathsf {K}}_{\mathrm{ c}}=1$or where the computation cost is minimum has been considered. In this paper, we focus on the general case (i.e., general${\mathsf {K}}_{\mathrm{ c}} $and general computation cost) and aim to find the minimum communication cost. We first propose a novel converse bound on the communication cost under the constraint of the popularcyclic assignment(widely considered in the literature), which assigns the datasets to the workers in a cyclic way. Motivated by the observation that existing strategies for distributed computing fall short of achieving the converse bound, we propose a novel distributed computing scheme for some system parameters. The proposed computing scheme is optimal for any assignment when${\mathsf {K}}_{\mathrm{ c}}$is large and is optimal under the cyclic assignment when the numbers of workers and datasets are equal or${\mathsf {K}}_{\mathrm{ c}}$is small. In addition, it is order optimal within a factor of 2 under the cyclic assignment for the remaining cases.

We study the optimal design of heterogeneous Coded Elastic Computing (CEC) where machines have varying computation speeds and storage. CEC introduced by Yang et al. in 2018 is a framework that mitigates the impact of elastic events, where machines can join and leave at arbitrary times. In CEC, data is distributed among machines using a Maximum Distance Separable (MDS) code such that subsets of machines can perform the desired computations. However, state-of-the-art CEC designs only operate on homogeneous networks where machines have the same speeds and storage. This may not be practical. In this work, based on an MDS storage assignment, we develop a novel computation assignment approach for heterogeneous CEC networks to minimize the overall computation time. We first consider the scenario where machines have heterogeneous computing speeds but same storage and then the scenario where both heterogeneities are present. We propose a novel combinatorial optimization formulation and solve it exactly by decomposing it into a convex optimization problem to find the optimal computation load and a filling problem to find the exact computation assignment. A low-complexity filling algorithm is adapted and can be completed within a number of iterations equal to at most the number of available machines.

Coded Distributed Computing (CDC) introduced by Li et al. in 2015 offers an efficient approach to trade computing power to reduce the communication load in general distributed computing frameworks such as MapReduce and Spark. In particular, increasing the computation load in the Map phase by a factor of r can create coded multicasting opportunities to reduce the communication load in the Shuffle phase by the same factor. However, the CDC scheme is designed for the homogeneous settings, where each node maps the same number of files and is assigned the same number of reduce functions. It requires an exponentially large number of input files (data batches), reduce functions and multicasting groups relative to the number of nodes to achieve the promised gain. We address the CDC limitations by proposing a novel CDC approach based on a combinatorial design, which accommodates heterogeneous networks and maintains a multiplicative computation-communication trade-off. In addition, the proposed approach requires an exponentially less number of input files compared to the original CDC scheme proposed by Li et al. Finally, we derive a new information theoretic converse for general heterogeneous CDC and show that the communication load of the proposed design is optimal within a constant factor.

Coding theoretic approaches have been developed to significantly reduce the communication load in modern distributed computing system. In particular, coded distributed computing (CDC) introduced by Li et al. can efficiently trade computation resources to reduce the communication load in MapReduce like computing systems. For the more general cascaded CDC, Map computations are repeated at r nodes to significantly reduce the communication load among nodes tasked with computing Q Reduce functions s times. In this paper, we propose a novel low-complexity combinatorial design for cascaded CDC which 1) determines both input file and output function assignments, 2) requires significantly less number of input files and output functions, and 3) operates on heterogeneous networks where nodes have varying storage and computing capabilities. We provide an analytical characterization of the computation-communication tradeoff, from which we show the proposed scheme can outperform the state-of-the-art scheme proposed by Li et al. for the homogeneous networks. Further, when the network is heterogeneous, we show that the performance of the proposed scheme can be better than its homogeneous counterpart. In addition, the proposed scheme is optimal within a constant factor of the information theoretic converse bound while fixing the input file and the output function assignments.

We consider the problem of cache-aided Multiuser Private Information Retrieval (MuPIR) which is an extension of the single-user cache-aided PIR problem to the case of multiple users. In cache-aided MuPIR, each of the$K_{\mathrm{ u}}$cache-equipped users wishes to privately retrieve a message out of$K$messages from$N$databases each having access to the entire message library. Demand privacy requires that any individual database learns nothing about the demands of all users. The users are connected to each database via an error-free shared-link. In this paper, we aim to characterize the optimal trade-off between user cache memory and communication load for such systems. First, we propose a novel approach ofcache-aided interference alignment (CIA), for the MuPIR problem with$K=2$messages,$K_{\mathrm{ u}}=2$users and$N\ge 2$databases. The CIA approach is optimal when the cache placement is uncoded. For general cache placement, the CIA approach is optimal when$N=2$and 3 verified by the computer-aided converse approach. Second, for the general case, we propose aproduct design(PD) which incorporates the PIR code into the linear caching code. The product design is shown to be order optimal within a multiplicative factor of 8 and is exactly optimal in the high memory regime.

Coded caching has the potential to greatly reduce network traffic by leveraging the cheap and abundant storage available in end-user devices so as to create multicast opportunities in the delivery phase. In the seminal work by Maddah-Ali and Niesen (MAN), the shared-link coded caching problem was formulated, where each user demands one file (i.e., single file retrieval). This article generalizes the MAN caching problem formulation from single file retrieval on the binary filed to general scalar linear function retrieval on an arbitrary finite field. The proposed novel scheme is linear, based on MAN uncoded cache placement, and leverages ideas from interference alignment. Quite surprisingly, the worst-case load of the proposed scheme among all possible demands is the same as the one of the scheme by Yu, Maddah-Ali, and Avestimehr (YMA) for single file retrieval. The proposed scheme has thus the same optimality guarantees as YMA, namely, it is optimal under the constraint of uncoded cache placement, and is optimal to within a factor 2 otherwise. Some extensions of the proposed scheme are then discussed. It is shown that the proposed scheme works not only on arbitrary finite field, but also on any commutative ring. The key idea of this article can be also extended to all scenarios to which the original MAN scheme has been extended, including but not limited to demand-private retrieval and Device-to-Device networks.

Maddah-Ali and Niesen (MAN) in 2014 showed that coded caching in single bottleneck-link broadcast networks allows serving an arbitrarily large number of cache-equipped users with a total link load (bits per unit time) that does not scale with the number of users. Since then, the general topic of coded caching has generated enormous interest both from the information theoretic and (network) coding theoretic viewpoint, and from the viewpoint of applications. Building on the MAN work, this paper considers a particular network topology referred to as cache-aided Fog Radio Access Network (Fog-RAN), that includes a Macro-cell Base Station (MBS) co-located with the content server, several cache-equipped Small-cell Base Stations (SBSs), and many users without caches. Some users are served directly by the MBS broadcast downlink, while other users are served by the SBSs. The SBSs can also exchange data via rounds of direct communication via a side channel, referred to as “sidelink”. For this novel Fog-RAN model, the fundamental tradeoff among (a) the amount of cache memory at the SBSs, (b) the load on the downlink (from MBS to directly served users and SBSs), and (c) the aggregate load on the sidelink is studied, under the standard worst-case demand scenario. We propose a converse bound whose key novelty is to jointly bound the downlink load an the sidelink load. For the achievability, by leveraging the network topology, we propose two classes of memory-loads point, where the SBS sidelink load is minimum and the MBS downlink load is minimum, respectively. By memory-sharing between these two classes of memory-loads points, some exact or order optimality results are obtained. Several existing models (e.g., Device-to-Device coded caching, single bottleneck-link coded caching with shared caches, single bottleneck-link caching coded caching with cache-less users) are recovered as special cases of this network model and by-product results of independent interest are given. Finally, the role of topology-aware versus topology-agnostic caching is discussed.

We consider a cache-aided interference network which consists of a library of N files, KTtransmitters and KRreceivers (users), each equipped with a local cache of size MTand MRfiles respectively, and connected via a discrete-time additive white Gaussian noise (AWGN) channel. Each receiver requests an arbitrary file from the library. The objective is to design a cache placement without knowing the receivers' requests and a communication scheme such that the sum Degrees of Freedom (sum-DoF) of the delivery is maximized. This network model with one-shot transmission was firstly investigated by Naderializadeh et al., who proposed a scheme achieving an order-optimal one-shot sum-DoF of min {MTKT+KRMR/N, KR}. One of the biggest limitations of this scheme is the requirement of high subpacketizations. This paper attempts to design new algorithms to reduce the file subpacketization in such a network without hurting the sum-DoF. In particular, we propose a new approach for both prefetching and linearly coded delivery based on a combinatorial design called hypercube. The proposed approach reduces the subpacketization exponentially in terms of KRM/N ( M=MTor MRrepresents the transmitter/receiver cache size) and achieves the identical one-shot sum DoF when MTKT+KRMR/N ≤ KR.

Coded caching is an information theoretic scheme to reduce high peak hours traffic by partially prefetching files in the users local storage during low peak hours. This paper considers heterogeneous decentralized caching systems where users' caches and content library files may have distinct sizes. The server communicates with the users through a Gaussian broadcast channel. The main contribution of this paper is a novel joint coded caching and modulation strategy to map the multicast messages generated in the coded caching delivery phase to the symbols of a signal constellation, such that users can leverage their cached content to demodulate the desired symbols with higher reliability and for the sake of simplicity, in this paper we focus only on “uncoded” modulation and symbol-by-symbol error probability. However, our scheme in conjunction with multilevel coded modulation can be extended to channel coding over a larger block lengths.

Cache-aided wireless device-to-device (D2D) networks have demonstrated promising performance improvement for video distribution compared to conventional distribution methods. Understanding the fundamental scaling behavior of such networks is thus importance. Recently, based on real-world data, it has been observed that the popularity distribution should be modeled by a Mandelbrot-Zipf (MZipf) distribution, instead of the common Zipf distribution. We thus in this work investigate the throughput-outage performance for cache-aided wireless D2D network adopting multi-hop communications, with the MZipf popularity distribution for file requests and Poisson point process for user distribution. Considering the case that Zipf factor is larger than one, we first propose an achievable content caching and delivery scheme and analyze its performance. Then, by showing that the achievable performance is tight to the proposed outer bound, we show that an optimal scaling law for cache-aided wireless multi-hop D2D networks is obtained.

This paper considers the MapReduce-like coded distributed computing framework originally proposed by Li et al., which uses coding techniques when distributed computing servers exchange their computed intermediate values, in order to reduce the overall traffic load. In their original model, servers are connected via an error-free common communication bus allowing broadcast transmissions. However, this assumption is one of the major limitations for practical implementations since real-world data centers may have network topologies far more involved than a single broadcast bus. We formulate a topological coded distributed computing problem, where the computing servers communicate with each other through some switch network. By using a special instance of fat-tree topologies, referred to as t-ary fat-tree proposed by Al-Fares et al. which can be built by some inexpensive switches, we propose a coded distributed computing scheme to achieve the optimal max-link communication load (defined as the maximum load over all links) over any network topology.

In order to preserve the privacy of the users demands from other users, in this paper we formulate a novel information theoretic Device-to-Device (D2D) private caching model by adding a trusted server. In the delivery phase, the trusted server collects the users demands and sends a query to each user, who then broadcasts packets according to this query. Two D2D private caching schemes (uncoded and coded) are proposed in this paper, which are shown to be order optimal.

Coded distributed computing (CDC) introduced by Li et. at. is an effective technique to trade computation load for communication load in a MapReduce framework. CDC achieves an optimal trade-off by duplicating map computations at r computing nodes to yield multicasting opportunities such that r nodes are served simultaneously in the Shuffle phase. However, in general, the state-of-the-art CDC scheme is mainly designed only for homogeneous networks, where the computing nodes are assumed to have the same storage, computation and communication capabilities. In this work, we explore two approaches of heterogeneous CDC design. First, we study CDC schemes which operate on multiple, collaborating homogeneous computing networks. Second, we allow heterogeneous function assignment in the CDC design, where nodes are assigned a varying number of reduce functions. We propose an expandable heterogeneous CDC scheme where r-1 nodes are served simultaneously in the Shuffle phase. In comparison to the state-of-the-art homogeneous CDC scheme with an equivalent computation load, we find our newly proposed heterogeneous CDC scheme has a smaller communication load in some cases.

This paper considers cache-aided device-to-device (D2D) networks where a trusted server helps to preserve the privacy of the users' demands. Specifically, the trusted server collects the users' demands before the delivery phase and sends a query to each user, who then broadcasts multicast packets according to this query. Recently the Authors proposed a D2D private caching scheme that was shown to be order optimal except for the very low memory size regime, where the optimality was proved by comparing to a converse bound without privacy constraint. The main contribution of this paper is a novel converse bound for the studied model where users may collude (i.e., some users share cache contents and demanded files, and yet cannot infer what files the remaining users have demanded) and under the placement phase is uncoded. To the best of the Author's knowledge, such a general bound is the first that genuinely accounts for the demand privacy constraint. The novel converse bound not only allows to show that the known achievable scheme is order optimal in all cache size regimes (while the existing converse bounds cannot show it), but also has the potential to be used in other variants of demand private caching.

In the shared-link coded caching problem, formulated by Maddah-Ali and Niesen (MAN), each cache-aided user demands one file (i.e., single file retrieval). This paper generalizes the MAN problem so as to allow users to request scalar linear functions (aka, linear combinations with scalar coefficients) of the files. We propose a novel coded delivery scheme, based on MAN uncoded cache placement, that allows for the decoding of arbitrary scalar linear functions of the files on arbitrary finite fields. Surprisingly, it is shown that the load for cache-aided scalar linear function retrieval depends on the number of linearly independent functions that are demanded, akin to the cache-aided single-file retrieval problem where the load depends on the number of distinct file requests. The proposed scheme is proved to be optimal under the constraint of uncoded cache placement, in terms of worst-case load, and within a factor 2 otherwise.

We study the optimal design of a heterogeneous coded elastic computing (CEC) network where machines have varying relative computation speeds. CEC introduced by Yang et al. is a framework which mitigates the impact of elastic events, where machines join and leave the network. A set of data is distributed among storage constrained machines using a Maximum Distance Separable (MDS) code such that any subset of machines of a specific size can perform the desired computations. This design eliminates the need to re-distribute the data after each elastic event. In this work, we develop a process for an arbitrary heterogeneous computing network to minimize the overall computation time by defining an optimal computation load, or number of computations assigned to each machine. We then present an algorithm to define a specific computation assignment among the machines that makes use of the MDS code and meets the optimal computation load.

This paper formulates the cache-aided multi-user Private Information Retrieval (MuPIR) problem, including Kucache-equipped users, each of which wishes to retrieve a desired message efficiently from N distributed databases with access to K independent messages. Privacy of the users’ demands requires that any individual database can not learn anything about the demands of the users. The load of this problem is defined as the average number of downloaded bits per desired message bit. The goal is to find the optimal memory-load trade-off while preserving the demand privacy. Besides the formulation of the MuPIR problem, the contribution of this paper is two-fold. First, we characterize the optimal memory-load trade-off for a system with N = 2 databases, K = 2 messages and Ku= 2 users demanding distinct messages; Second, a product design with order optimality guarantee is proposed. In addition, the product design can achieve the optimal load when the cache memory is large enough. The product design embeds the well-known Sun-Jafar PIR scheme into coded caching, in order to benefit from the coded caching gain while preserving the privacy of the users’ demands.

In this paper, we propose a new design framework on Device-to-Device (D2D) coded caching networks with optimal communication load (rate) but significantly less file subpacketizations compared to that of the well-known D2D coded caching scheme proposed by Ji, Caire and Molisch (JCM). The proposed design framework is referred to as the Packet Type-based (PTB) design, where each file is partitioned into packets according to their pre-defined types while the cache placement and user multicast grouping are based on the packet types. This leads to the so-called raw packet saving gain for the subpacketization levels. By a careful selection of transmitters within each multicasting group, a so-called further splitting ratio gain of the subpacketizatios can also be achieved. By the joint effect of the raw packet saving gain and the further splitting ratio gain, an order-wise subpacketization reduction can be achieved compared to the JCM scheme while preserving the optimal rate. In addition, as the first time presented in the literature according to our knowledge, we find that unequal subpacketizaton is a key to achieve subpacketization reductions when the number of users is odd. As a by-product, instead of directly translating shared link caching schemes to D2D caching schemes, at least for the sake of subpackeitzation, a new design framework is indeed needed.

We consider wireless device-to-device (D2D) caching networks with single-hop transmissions. Previous work has demonstrated that caching and coded multicasting can significantly increase per user throughput. However, the state-of-the-art coded caching schemes for D2D networks are generally impractical because content files are partitioned into an exponential number of packets with respect to the number of users if both library and memory sizes are fixed. In this paper, we present two combinatorial approaches of D2D coded caching network design with reduced packetizations and desired throughput gain compared to the conventional uncoded unicasting. The first approach uses a “hypercube” design, where each user caches a “hyperplane” in this hypercube and the intersections of “hyperplanes” represent coded multicasting codewords. In addition, we extend the hypercube approach to a decentralized design. The second approach uses the Ruzsa-Szeméredi graph to define the cache placement. Disjoint matchings on this graph represent coded multicasting codewords. Both approaches yield an exponential reduction of packetizations while providing a per-user throughput that is comparable to the state-of-the-art designs in the literature. Furthermore, we apply spatial reuse to the new D2D network designs to further reduce the required packetizations and significantly improve per user throughput for some parameter regimes.

We propose capacity-achieving schemes for private information retrieval (PIR) from uncoded databases (DBs) with both homogeneous and heterogeneous storage constraints. In the PIR setting, a user queries a set of DBs to privately download a message, where privacy implies that no one DB can infer which message the user desires. In general, a PIR scheme is comprised of storage placement and delivery designs. Previous works have derived the capacity, or infimum download cost, of PIR with uncoded storage placement and sufficient conditions of storage placement to meet capacity. However, the currently proposed storage placement designs require splitting each message into an exponential number of sub-messages with respect to the number of DBs. In this work, when DBs have the same storage constraint, we propose two simple storage placement designs that satisfy the capacity conditions. Then, for more general heterogeneous storage constraints, we translate the storage placement design process into a “filling problem”. We design an iterative algorithm to solve the filling problem where, in each iteration, messages are partitioned into sub-messages and stored at subsets of DBs. All of our proposed storage placement designs require a number of sub-messages per message at most equal to the number of DBs.

Data shuffling of training data among different computing nodes (workers) has been identified as a core element to improve the statistical performance of modern large-scale machine learning algorithms. Data shuffling is often considered as one of the most significant bottlenecks in such systems due to the heavy communication load. Under a master-worker architecture (where a master has access to the entire dataset and only communication between the master and the workers is allowed) coding has been recently proved to considerably reduce the communication load. This work considers a different communication paradigm referred to as decentralized data shuffling, where workers are allowed to communicate with one another via a shared link. The decentralized data shuffling problem has two phases: workers communicate with each other during the data shuffling phase, and then workers update their stored content during the storage phase. The main challenge is to derive novel converse bounds and achievable schemes for decentralized data shuffling by considering the asymmetry of the workers' storages (i.e., workers are constrained to store different files in their storages based on the problem setting), in order to characterize the fundamental limits of this problem. For the case of uncoded storage (i.e., each worker directly stores a subset of bits of the dataset), this paper proposes converse and achievable bounds (based on distributed interference alignment and distributed clique-covering strategies) that are within a factor of 3/2 of one another. The proposed schemes are also exactly optimal under the constraint of uncoded storage for either large storage size or at most four workers in the system.

On-demand video accounts for the majority of wireless data traffic. Video distribution schemes based on caching combined with device-to-device (D2D) communications promise order-of-magnitude greater spectral efficiency for video delivery, but hinge on the principle of concentrated demand distributions. This paper presents, for the first time, the analysis and evaluations of the throughput-outage tradeoff of such schemes based on measured cellular demand distributions. In particular, we use a dataset with more than 100 million requests from the BBC iPlayer, a popular video streaming service in the U.K., as the foundation of the analysis and evaluations. We present an achievable scaling law based on the practical popularity distribution, and show that such scaling law is identical to those reported in the literature. We find that also for the numerical evaluations based on a realistic setup, order-of-magnitude improvements can be achieved. Our results indicate that the benefits promised by the caching-based D2D in the literature could be retained for cellular networks in practice.

We propose a capacity-achieving scheme for private information retrieval (PIR) from databases (DBs) with heterogeneous storage constraints. In the PIR setting, a user queries a set of DBs to privately download a message, where privacy implies that no one DB can infer which message the user desires. Our PIR scheme uses an uncoded storage placement and we derive sufficient conditions to meet capacity in this design architecture. We translate the storage placement design to a "filling problem" where messages are partitioned into sub- messages and stored at subsets of DBs. We prove a set of necessary and sufficient conditions for the existence of the filling problem solution and design an iterative algorithm to find a filling problem solution. Our proposed algorithm requires at most a number of iterations equal to the number of DBs. Furthermore, we significantly reduce the number of sub-messages compared to the state-of- the-art PIR scheme, as our proposed PIR scheme requires that each message is split into a polynomial number of sub-messages with respect to the number of DBs.

We consider a cache-aided interference network which consists of a library of N files, KTtransmitters and KRreceivers (users), each equipped with a local cache of size MTand MRfiles respectively, and connected via a discrete-time additive white Gaussian noise channel. Each receiver requests an arbitrary file from the library. The objective is to design a cache placement without knowing the receivers' requests and a communication scheme such that the sum Degrees of Freedom (sum-DoF) of the delivery is maximized. This network model has been investigated by Naderializadeh et al., who proposed a prefetching and a delivery scheme that achieve a sum-DoF of min{MTKT+ KRMR/N, KR}. One of the biggest limitations of this scheme is the requirement of high subpacketization level. This paper attempts to design new algorithms to reduce the file subpacketization in such a network. In particular, we propose a new approach for both prefetching and linear delivery based on a combinatorial design called hypercube. We show that the required number of packets per file can be exponentially reduced compared to the state-of-the-art scheme proposed by Naderializadeh et al., or the NMA scheme. When MTKT+ KRMR≤ KR, the achievable one-shot sum-DoF using this approach is MTKT+ KRMR/N, which shows that 1) the one-shot sum-DoF scales linearly with the aggregate cache size in the network and 2) it is within a factor of 2 to the information-theoretic optimum. Surprisingly, the identical and near optimal sum-DoF performance can be achieved using the hypercube approach with a much less file subpacketization.

This paper studies the fundamental limits of the shared-link caching problem with correlated files, where a server with a library of N files communicates with K users who can store M files. Given an integer r G ∈ [N], correlation is modelled as follows: each r-subset of files contains one and one only common block. The tradeoff between the cache size and the average transmitted load is considered. First, a converse bound under the constraint of uncoded cache placement (i.e., each user directly caches a subset of the library bits) is derived. Then, an interference alignment scheme is proposed. The proposed scheme achieves the optimal average load under uncoded cache placement to within a factor of 2 in general, and it is exactly optimal for (i) users demand distinct files, (ii) large or small cache size, namely KrM/N ≤ 2 or KrM/N ≥ K - 1, and (iii) large or small correlation, namely r ∈{1, 2, N - 1, N}. As a by-product, the proposed scheme reduces the (worst-case or average) load of existing schemes for the caching problem with multi-requests.

This paper considers a novel cache-aided Fog Radio Access Network (Fog-RAN) architecture including a Macro-cell Base Station (MBS), several Small-cell Base Stations (SBSs), and users. Some users, not in the reach of any SBS, are directly served by the MBS, while the other users are "offloaded" and receive information only from the SBSs through high throughput links. In order to alleviate the load in the wireless front-haul links between the MBS and the SBSs, caching is employed at the SBSs. The MBS sends coded packets to the SBSs and to the directly served users via wireless multicast transmission on a common downlink channel, modeled as an error-free shared link of fixed capacity. Subsequently, the SBSs communicate among one another in a Device-to-Device (D2D) fashion so as each SBS obtains enough information to decode the files demanded by its connected users. The access links between SBSs and users are assumed to operate at a sufficiently high rate such that they are not the system bottleneck. For this novel Fog-RAN model, the memory-loads tradeoff for the worst-case demands is investigated. The main contributions of this paper are: (i) a novel symmetric inter-file coded cache placement scheme, (ii) a novel D2D delivery scheme to handle the inter-SBS communication phase, that is order optimal when each SBS serves the same number of users, and (iii) a novel asymmetric cache placement with file subpacketization dependent on the network structure, which is exactly optimal in some memory size regimes.

Private information retrieval (PIR) allows a user to download one of K messages from N databases without revealing to any database which of the K messages is being downloaded. In general, the databases can be storage constrained where each database can only store up to μKL bits where 1/N ≤ μ ≤ 1 and L is the size of each message in bits. Let t = μN, a recent work showed that the capacity of Storage Constrained PIR (SC-PIR) is (1 + 1/t + 1/t2 + ··· +1)-1, which is achieved by a storage placement scheme inspired by the content placement scheme in the literature of coded caching and the original PIR scheme. Not surprisingly, this achievable scheme requires that each message is L = (Nt)tKbits in length, which can be impractical. In this t paper, without trying to make the connection between SC-PIR and coded caching problems, based on a general connection between the Full Storage PIR (FS-PIR) problem (μ = 1) and SCPIR problem, we propose a new SC-PIR design idea using novel storage placement schemes. The proposed schemes significantly reduce the message size requirement while still meeting the capacity of SC-PIR. In particular, the proposed SC-PIR schemes require the size of each file to be only L = NtK-1compared to the state-of-the-art L = (Nt)tK.

Coded distributed computing (CDC) introduced by Li et al. in 2015 offers an efficient approach to trade computing power to reduce the communication load in general distributed computing frameworks such as MapReduce. For the more general cascaded CDC, Map computations are repeated at r nodes to significantly reduce the communication load among nodes tasked with computing Q Reduce functions s times. While an achievable cascaded CDC scheme was proposed, it only operates on homogeneous networks, where the storage, computation load and communication load of each computing node is the same. In this paper, we address this limitation by proposing a novel combinatorial design which operates on heterogeneous networks where nodes have varying storage and computing capabilities. We provide an analytical characterization of the computation-communication trade-off and show that it is optimal within a constant factor and could outperform the state-of-the-art homogeneous schemes.

This paper proposes a video delivery strategy for dynamic streaming services which maximizes time-average streaming quality under a playback delay constraint in wireless caching networks. The network where popular videos encoded by scalable video coding are already stored in randomly distributed caching nodes is considered under adaptive video streaming concepts, and distance-based interference management is investigated in this paper. In this network model, a streaming user makes delay-constrained decisions depending on stochastic network states: 1) caching node for video delivery, 2) video quality, and 3) the quantity of video chunks to receive. Since wireless link activation for video delivery may introduce delays, different timescales for updating caching node association, video quality adaptation, and chunk amounts are considered. After associating with a caching node for video delivery, the streaming user chooses combinations of quality and chunk amounts in the small timescale. The dynamic decision making process for video quality and chunk amounts at each slot is modeled using Markov decision process, and the caching node decision is made based on the framework of Lyapunov optimization. Our intensive simulations verify that the proposed video delivery algorithm works reliably and also can control the tradeoff between video quality and playback latency.

Orthogonal Time Frequency Space (OTFS) is a novel modulation scheme designed in the Doppler-delay domain to fully exploit time and frequency diversity of general time-varying channels. In this paper, we present a novel discrete-time analysis of OFDM-based OTFS transceiver with a concise and vectorized input-output relationship that clearly characterizes the contribution of each underlying signal processing block in such systems. When adopting cyclic prefix in the time domain, our analysis reveals that the proposed MIMO OTFS and OFDM systems have the same ergodic capacity despite the well-known fact that the former has great advantages in low-complexity receiver design for high Doppler channels. The proposed discrete-time vectorized formulation is applicable to general fast fading channels with arbitrary window functions. It also enables practical low-complexity receiver design for which such a concise formulation of the input-output relationship is of great benefits.

Maddah-Ali and Niesen's original coded caching scheme for shared-link broadcast networks is now known to be optimal to within a factor two, and has been applied to other types of networks. For practical reasons, this paper considers that a server communicates to cache-aided users through H intermediate relays. In particular, it focuses on combination networks where each of the K = (rH) users is connected to a r distinct r-subsets of relays. By leveraging the symmetric topology of the network, this paper proposes a novel method to generate multicast messages such that each multicast message sent to each relay is useful for the largest possible subset of users connected to this relay. By numerical evaluations, the proposed scheme is shown to reduce the download time compared to the schemes available in the literature. The idea is then extended to decentralized combination networks, more general relay networks, and combination networks with cache-aided relays and users. Also in these cases the proposed scheme outperforms known ones.

We consider a wireless distributed computing network, where all computing nodes (workers) are connected via wireless medium obeying the seminal protocol channel model. In particular, we focus on the MapReduce-type platform, where each worker is assigned to compute some arbitrary output functions from F input files, which are distributively cached in all workers. The overall computation is decomposed into computing a set of “Map” and “Reduce” functions across all workers. The goal is to characterize the minimum computing latency as a function of the computation load. Unlike other related works, which consider either wireline settings or restrict the communication among workers to single-hop, here we focus on the wireless scenario and do not constrain any communication schemes. We propose a data set cache strategy based on a deterministic assignment of Maximum Distance Separable (MDS)-coded date sets over all input files, and a coded multicast transmission strategy where the workers send linearly coded computing results to each other in order to collectively satisfy their assigned tasks. We show that our approach can achieve a scalable communication latency, outperform the state of the art schemes in the order sense, and achieve the information theoretic outer bound within a multiplicative constant factor in practical parameter regimes.

This paper investigates the fundamental tradeoff between cache size and download time in the (H, r, M, N) combination network, where a server with N files is connected to H relays (without caches) and each of the K: = Hr users (with caches of size M files) is connected to a different subset of r relays. Existing schemes fall within two categories: either use the uncoded symmetric cache placement originally proposed for the shared-link model and design delivery phase dependent on the network topology, or effectively divide the combination network into H uncoordinated shared-link networks each serving K':= H-1r-1 users; in either case, the placement phase leverages effectively the connectivity of relay s/users. In this paper, a novel strategy is proposed where the coded cache placement is dependent on network topology. The proposed scheme is shown to be information theoretically optimal for large cache size. In addition, when not exactly optimal, the proposed scheme can also outperform existing schemes.

Coded distributed computing introduced by Li et al. in 2015 is an efficient approach to trade computing power to reduce the communication load in general distributed computing frameworks such as MapReduce. In particular, Li et al. show that increasing the computation load in the Map phase by a factor of r can create coded multicasting opportunities to reduce the communication load in the Reduce phase by the same factor. However, there are two major limitations in practice. First, it requires an exponentially large number of input files (data batches) when the number of computing nodes gets large. Second, it forces every s computing nodes to compute one Map function, which leads to a large number of Map functions required to achieve the promised gain. In this paper, we make an attempt to overcome these two limitations by proposing a novel coded distributed computing approach based on a combinatorial design. We demonstrate that when the number of computing nodes becomes large, 1) the proposed approach requires an exponentially less number of input files; 2) the required number of Map functions is also reduced exponentially. Meanwhile, the resulting computation-communication trade-off maintains the multiplicative gain compared to conventional uncoded unicast and achieves the information theoretic lower bound asymmetrically for some system parameters.

We consider wireless device-to-device (D2D) caching networks with single-hop transmissions. Previous work in the literature has shown that caching and coded multicasting can be strategically used to significantly increase the per user throughput. However, these schemes require partitioning files into a large number of packets which grows exponentially as the number of users increases. This makes these schemes impractical to implement. In this paper, we address this issue by designing cache placement, coded multicasting and scheduling schemes based on disjoint matchings in Ruzsa-Szeméredi Graphs, which has been applied to design a coded caching scheme in the shared link caching networks. We demonstrate that by using the proposed approach, the per user throughput is not much worse than that proposed in the literature with the requirement of exponential file subpacketization in terms of the number of users. Nevertheless, by using the proposed scheme, the requirement of file subpacketization is at most sub-quadratic in terms of the number of users if no spatial reuse is allowed. In addition, both per user throughput and file subpacketization can be improved significantly when spatial reuse is allowed.

We consider a wireless Device-to-Device (D2D) caching network, where users make arbitrary requests from a library of files and have pre-fetched (cached) information on their devices, subject to a per-node storage capacity constraint. The network is assumed to obey the “protocol model”, widely considered in the wireless network literature. Unlike other related works, which either restrict the communication to single-hop, or assume entire file caching, here we consider both multi-hop transmission and fully general caching strategies, including file subpacketization. We propose a caching strategy based on deterministic assignment of MDS-coded packets of the library files, and a coded multicast delivery strategy where the users send linearly coded messages to each other in order to collectively satisfy their demands. We show that our approach can achieve the information theoretic outer bound within a multiplicative constant factor in practical parameter regimes.

This paper studies the tradeoff between the memory size M and the download time / rate R* for networks where a server with N files is connected to H relays (without caches), which in turns are connected to K users equipped with caches of size M files. When each user is connected to a different subset of r relays, i.e., K = (Hr), the system is referred to as a combination network with end-user-caches. In this work, outer bounds are derived for the practically motivated case of uncoded cache contents, that is, bits of the various files are directly copied in the user caches without any coding. In this case, once the cache contents and the user demands are known, the problem reduces to a general index coding problem. This paper shows that relying on a well known “acyclic index coding outer bound” results in bounds that are not tight for combination networks with enduser-caches (as opposed to the case without relays) and provides two novel ways to derive the tightest known outer bounds to date. As a result of independent interest, an inequality that generalizes the well-known sub-modularity of entropy is derived.

We study the delay-outage tradeoff in a shared link caching network formed by one source node and n users over a wireless slow fading channel. Each user requests an arbitrary file from a library of m files, each of entropy F bits. The users can locally cache up to MF information bits. Under a single-input single-output (SISO) multi-user system, we present a closed form expression of the delay-outage tradeoff under any i.i.d. channel distributions by using the classical caching and coded multicasting scheme presented by Maddah-Ali and Niesen in [1], where outage probability is regarded as the probability that a user cannot decode the requested file. In addition, when the channel gains follow a Gaussian distribution, we show that for a large range of vanishing outage probability p, the average delay scales as Ω (min {n2-ε1, n1-ε2/p}), where ε1, ε2> 0 are some arbitrarily small constants. This means that the multiplicative caching gain introduced by Maddah-Ali and Niesen is lost. To overcome this problem, we modify the network to a single-input multiple-output system (SIMO) system and find the required number of receive antennas per user such that the promised multiplicative caching gain can be preserved.

We consider a wireless device-to-device network, where n nodes are uniformly distributed at random over the network area. We let each node caches M files from a library of size m ≥ M. Each node in the network requests a file from the library independently at random, according to a popularity distribution, and is served by other nodes having the requested file in their local cache via (possibly) multihop transmissions. Under the classical “protocol model” of wireless networks, we characterize the optimal per-node capacity scaling law for a broad class of heavy-tailed popularity distributions, including Zipf distributions with exponent less than one. In the parameter regime of interest, i.e., m=o(nM), we show that a decentralized random caching strategy with uniform probability over the library yields the optimal per-node capacity scaling of Θ(√M/m) for heavy-tailed popularity distributions. This scaling is constant with n , thus yielding throughput scalability with the network size. Furthermore, the multihop capacity scaling can be significantly better than for the case of single-hop caching networks, for which the per-node capacity is Θ (M/m). The multihop capacity scaling law can be further improved for a Zipf distribution with exponent larger than some threshold > 1, by using a decentralized random caching uniformly across a subset of most popular files in the library. Namely, ignoring a subset of less popular files (i.e., effectively reducing the size of the library) can significantly improve the throughput scaling while guaranteeing that all nodes will be served with high probability as n increases.

We consider the canonical shared link caching network formed by a source node, hosting a library of m information messages (files), connected via a noiseless multicast link to n user nodes, each equipped with a cache of size M files. Users request files independently at random according to an a-priori known demand distribution q. A coding scheme for this network consists of two phases: cache placement and delivery. The cache placement is a mapping of the library files onto the user caches that can be optimized as a function of the demand statistics, but is agnostic of the actual demand realization. After the user demands are revealed, during the delivery phase the source sends a codeword (function of the library files, cache placement, and demands) to the users, such that each user retrieves its requested file with arbitrarily high probability. The goal is to minimize the average transmission length of the delivery phase, referred to as rate (expressed in channel symbols per file). In the case of deterministic demands, the optimal min-max rate has been characterized within a constant multiplicative factor, independent of the network parameters. The case of random demands was previously addressed by applying the order-optimal min-max scheme separately within groups of files requested with similar probability. However, no complete characterization of order-optimality was previously provided for random demands under the average rate performance criterion. In this paper, we consider the random demand setting and, for the special yet relevant case of a Zipf demand distribution, we provide a comprehensive characterization of the order-optimal rate for all regimes of the system parameters, as well as an explicit placement and delivery scheme achieving order-optimal rates. We present also numerical results that confirm the superiority of our scheme with respect to previously proposed schemes for the same setting.

One of the main challenges for continued wireless capacity growth is the difficulty in exploiting the multicast nature of the wireless medium: wireless end points rarely experience the same channel conditions or access the same content at the same time. In this paper, we present and analyze a novel wireless video delivery paradigm based on the combined use of channel-aware caching and coded multicasting that allows simultaneously serving multiple cache-enabled access points that may be requesting different content and experiencing different channel conditions. To this end, we reformulate the caching-aided coded multicast problem as a joint source-channel coding problem and design an achievable scheme that preserves the cache-enabled multiplicative throughput gains of the error-free scenario, by guaranteeing per-receiver (access point) rates unaffected by the presence of receivers with worse channel conditions.

Future Internet usage will be dominated by the consumption of a rich variety of online multimedia services accessed from an exponentially growing number of multimedia capable mobile devices. As such, future Internet designs will be challenged to provide solutions that can deliver bandwidth-intensive delay-sensitive on-demand video-based services over increasingly crowded and bandwidth-limited wireless access networks. One of the main reasons for the bandwidth stress facing wireless network operators is the difficulty to exploit the multicast nature of the wireless medium when wireless users or access points rarely experience the same channel conditions or access the same content at the same time. In this paper, we present and analyze a novel wireless video delivery paradigm based on the combined use of channel-aware caching and coded multicasting that allows simultaneously serving multiple cache-enabled receivers that may be requesting different content and experiencing different channel conditions. To this end, we reformulate the caching-aided coded multicast problem as a joint source-channel coding problem and design an achievable scheme that preserves the cache-enabled multiplicative throughput gains of the error-free scenario, by guaranteeing per-receiver rates unaffected by the presence of receivers with worse channel conditions.

As wireless video is the fastest growing form of data traffic, methods for spectrally efficient on-demand wireless video streaming are essential to both service providers and users. A key property of video on-demand is the asynchronous content reuse, such that a few popular files account for a large part of the traffic but are viewed by users at different times. Caching of content on wireless devices in conjunction with device-to-device (D2D) communications allows to exploit this property, and provide a network throughput that is significantly in excess of both the conventional approach of unicasting from cellular base stations and the traditional D2D networks for “regular” data traffic. This paper presents in a tutorial and concise form some recent results on the throughput scaling laws of wireless networks with caching and asynchronous content reuse, contrasting the D2D approach with other alternative approaches such as conventional unicasting, harmonic broadcasting, and a novel coded multicasting approach based on caching in the user devices and network-coded transmission from the cellular base station only. Somehow surprisingly, the D2D scheme with spatial reuse and simple decentralized random caching achieves the same near-optimal throughput scaling law as coded multicasting. Both schemes achieve an unbounded throughput gain (in terms of scaling law) with respect to conventional unicasting and harmonic broadcasting, in the relevant regime where the number of video files in the library is smaller than the total size of the distributed cache capacity in the network. To better understand the relative merits of these competing approaches, we consider a holistic D2D system design incorporating traditional microwave (2 GHz) and millimeter-wave (mm-wave) D2D links; the direct connections to the base station can be used to provide those rare video requests that cannot be found in local caches. We provide extensive simulation results under a variety of system settings and compare our scheme with the systems that exploit transmission from the base station only. We show that, also in realistic conditions and nonasymptotic regimes, the proposed D2D approach offers very significant throughput gains.

We consider a wireless device-to-device (D2D) network where communication is restricted to be single-hop. Users make arbitrary requests from a finite library of files and have pre-cached information on their devices, subject to a per-node storage capacity constraint. A similar problem has already been considered in an infrastructure setting, where all users receive a common multicast (coded) message from a single omniscient server (e.g., a base station having all the files in the library) through a shared bottleneck link. In this paper, we consider a D2D infrastructureless version of the problem. We propose a caching strategy based on deterministic assignment of subpackets of the library files, and a coded delivery strategy where the users send linearly coded messages to each other in order to collectively satisfy their demands. We also consider a random caching strategy, which is more suitable to a fully decentralized implementation. Under certain conditions, both approaches can achieve the information theoretic outer bound within a constant multiplicative factor. In our previous work, we showed that a caching D2D wireless network with one-hop communication, random caching, and uncoded delivery (direct file transmissions) achieves the same throughput scaling law of the infrastructure-based coded multicasting scheme, in the regime of large number of users and files in the library. This shows that the spatial reuse gain of the D2D network is order-equivalent to the coded multicasting gain of single base station transmission. It is, therefore, natural to ask whether these two gains are cumulative, i.e., if a D2D network with both local communication (spatial reuse) and coded multicasting can provide an improved scaling law. Somewhat counterintuitively, we show that these gains do not cumulate (in terms of throughput scaling law). This fact can be explained by noticing that the coded delivery scheme creates messages that are useful to multiple nodes, such that it benefits from broadcasting to as many nodes as possible, while spatial reuse capitalizes on the fact that the communication is local, such that the same time slot can be reused in space across the network. Unfortunately, these two issues are in contrast with each other.

We study a noiseless broadcast link serving K users whose requests arise from a library of N files. Every user is equipped with a cache of size M files each. It has been shown that by splitting all the files into packets and placing individual packets in a random independent manner across all the caches prior to any transmission, at most N/M file transmissions are required for any set of demands from the library. The achievable delivery scheme involves linearly combining packets of different files following a greedy clique cover solution to the underlying index coding problem. This remarkable multiplicative gain of random placement and coded delivery has been established in the asymptotic regime when the number of packets per file F scales to infinity. The asymptotic coding gain obtained is roughly t = K M/N. In this paper, we initiate the finite-length analysis of random caching schemes when the number of packets F is a function of the system parameters M, N, and K. Specifically, we show that the existing random placement and clique cover delivery schemes that achieve optimality in the asymptotic regime can have at most a multiplicative gain of 2 even if the number of packets is exponential in the asymptotic gain t = K(M/N). Furthermore, for any clique cover-based coded delivery and a large class of random placement schemes that include the existing ones, we show that the number of packets required to get a multiplicative gain of (4/3)g is at least O((g/K)(N/M)g-1). We design a new random placement and an efficient clique cover-based delivery scheme that achieves this lower bound approximately. We also provide tight concentration results that show that the average (over the random placement involved) number of transmissions concentrates very well requiring only a polynomial number of packets in the rest of the system parameters.

We consider a wireless device-to-device (D2D) network in which the nodes are uniformly distributed at random over the network area and can cache information from a library of possible messages (files). Each node requests a file in the library independently at random, according to a given popularity distribution, and downloads from other nodes having the requested file in their local cache via multihop transmission. Under the classical “protocol model” of wireless ad hoc networks, we characterize the optimal throughput scaling law by presenting a feasible scheme formed by a decentralized caching policy for the parameter regimes of interest and a local multihop transmission protocol. The scaling law optimality of the proposed strategy is shown by deriving a new throughput upper bound. Surprisingly, we show that decentralized uniform random caching yields optimal scaling in most of the system interesting regimes. We also observe that caching improves the throughput scaling law of classical ad hoc networks, and that multihop improves the previously derived scaling law of caching wireless networks under one-hop transmission.

Coded multicasting has been shown to improve the caching performance of content delivery networks with multiple caches downstream of a common multicast link. However, the schemes that have been shown to achieve order-optimal performance require content items to be partitioned into a number of packets that grows exponentially with the number of users [1]. In this paper, we first extend the analysis of the order-optimal multiple-groupcast coded multicasting scheme in [2] to the case of heterogeneous cache sizes and demand distributions, providing an achievable scheme and an upper bound on the optimal performance when the number of packets goes to infinity. We then show that the scheme achieving this upper bound can very quickly loose its promising multiplicative caching gain for finite content packetization. To overcome this limitation, we design a novel polynomial-time algorithm based on greedy local graph-coloring that, while keeping the same content packetization, recovers a significant part of the multiplicative caching gain. Our results show that the achievable schemes proposed to date to quantify the fundamental limiting performance, must be properly designed for practical regimes of finite content packetization.

We consider a wireless device-to-device (D2D) network where n nodes are uniformly distributed at random over the network area. We let each node with storage capacity M cache files from a library of size m. Each node in the network requests a file from the library independently at random, according to a popularity distribution, and is served by other nodes having the requested file in their local cache via (possibly) multihop transmissions. Under the classical “protocol model” of wireless networks, we characterize the optimal per-node capacity scaling law for a broad class of heavy-tailed popularity distributions including the Zipf distribution with Zipf exponent less than one. Surprisingly, in the parameter regimes of interest, we show that decentralized random caching uniformly across the library yields optimal per-node capacity scaling of Θ(√M/m), which outperforms the single-hop caching networks whose capacity scales as Θ (M/m) [1], [2].

The capacity of caching networks has received considerable attention in the past few years. A particularly studied setting is the shared link caching network, in which a single source with access to a file library communicates with multiple users, each having the capability to store segments (packets) of the library files, over a shared multicast link. Each user requests one file from the library according to a common demand distribution and the server sends a coded multicast message to satisfy all users at once. The problem consists of finding the smallest possible average codeword length to satisfy such requests. In this paper, we consider the generalization to the case where each user places L ≥ 1 independent requests according to the same common demand distribution. We propose an achievable scheme based on random vector (packetized) caching placement and multiple groupcast index coding, shown to be order-optimal in the asymptotic regime in which the number of packets per file B goes to infinity. We then show that the scalar (B = 1) version of the proposed scheme can still preserve order-optimality when the number of per-user requests L is large enough. Our results provide the first order-optimal characterization of the shared link caching network with multiple random requests, revealing the key effects of L on the performance of caching-aided coded multicast schemes.

We consider a wireless device-to-device (D2D) network where the nodes have precached information from a library of available files. Nodes request files at random. If the requested file is not in the on-board cache, then it is downloaded from some neighboring node via one-hop local communication. An outage event occurs when a requested file is not found in the neighborhood of the requesting node, or if the network admission control policy decides not to serve the request. We characterize the optimal throughput-outage tradeoff in terms of tight scaling laws for various regimes of the system parameters, when both the number of nodes and the number of files in the library grow to infinity. Our analysis is based on Gupta and Kumar protocol model for the underlying D2D wireless network, widely used in the literature on capacity scaling laws of wireless networks without caching. Our results show that the combination of D2D spectrum reuse and caching at the user nodes yields a per-user throughput independent of the number of users, for any fixed outage probability in (0, 1). This implies that the D2D caching network is scalable: even though the number of users increases, each user achieves constant throughput. This behavior is very different from the classical Gupta and Kumar result on ad hoc wireless networks, for which the per-user throughput vanishes as the number of users increases. Furthermore, we show that the user throughput is directly proportional to the fraction of cached information over the whole file library size. Therefore, we can conclude that D2D caching networks can turn memory into bandwidth (i.e., doubling the on-board cache memory on the user devices yields a 100% increase of the user throughout).

We consider a wireless device-to-device (D2D) network where the nodes have cached information from a library of possible files. Inspired by the current trend in the standardization of the D2D mode for 4th generation wireless networks, we restrict to one-hop communication: each node places a request to a file in the library, and downloads from some other node which has the requested file in its cache through a direct communication link, without going through a base station. We describe the physical layer communication through a simple “protocol-model”, based on interference avoidance (independent set scheduling). For this network we define the outage-throughput tradeoff problem and characterize the optimal scaling laws for various regimes where both the number of nodes and the files in the library grow to infinity.

We consider a wireless Device-to-Device (D2D) network where communication is restricted to be single-hop, users make arbitrary requests from a finite library of possible files and user devices cache information in the form of carefully designed sets of packets from all files in the library. We consider the combined effect of coding in the delivery phase, achieving “coded multicast gain”, and of spatial reuse due to local short-range D2D communication. Somewhat counterintuitively, we show that the coded multicast gain and the spatial reuse gain do not cumulate, in terms of the throughput scaling laws. In particular, the spatial reuse gain shown in our previous work on uncoded random caching and the coded multicast gain shown in this paper yield the same scaling laws behavior, but no further scaling law gain can be achieved by using both coded caching and D2D spatial reuse.

Previous work has shown that distributed cooperative MIMO systems (e.g., the hierarchical MIMO cooperation scheme) can provide large gains in capacity if the size of the MIMO systems is a function of the total number of nodes in the network (n). However, no results have been reported on the scaling laws of distributed cooperative MIMO systems when the number of transmit and receive antennas are of finite size, which is the case in real networks. This paper uses the extended network model to demonstrate that, if the size of distributed MIMO systems is restricted to a finite size, then there is at most a constant gain compared to point-to-point communications. Opportunistic interference management (OIM) is introduced as an alternative to distributed MIMO, and it is shown that it provides higher order gains than distributed cooperative MIMO systems under the same assumption of having a finite number of transmit and receive antennas. More specifically, OIM achieves a throughput capacity of C1(n) = Θ (D log log 2/θ log n/√n log n) in fading channels when the transmission range T(n) is Ω (√2/θ n), where θ is a constant parameter close to zero. This constitutes an order gain of Θ(log log 2/Θ log n) compared to point-to-point communications and distributed MIMO systems! Given that it is much easier to implement OIM schemes than distributed cooperative MIMO systems, these results indicate that OIM is a far better choice to making wireless ad hoc networks scale than distributed cooperative MIMO systems.

We study the scaling laws for wireless ad hoc networks in which the distribution of n nodes in the network is homogeneous but the traffic they carry is heterogeneous. More specifically, we consider the case in which a given node is the data-gathering sink for k sources sending different information to it, while the rest of the s = n - k nodes participate in unicast sessions with random destinations chosen uniformly. We present a separation theorem for heterogeneous traffic showing that the optimum order throughput capacity can be attained in a wireless network in which traffic classes are distributed uniformly by endowing each node with multiple radios, each operating in a separate orthogonal channel, and by allocating a radio per node to each traffic class. Based on this theorem, we show how this order capacity can be attained for the unicast and data-gathering traffic classes by extending cooperative communication schemes that have been proposed previously.

We introduce a new multiuser diversity concept with which multiple transmitters can communicate without causing significant interference to each other. The new scheme, called Opportunistic Interference Management (OIM), significantly reduces the feedback required in distributed Multiple-Input Multiple-Output (MIMO) systems, and requires an encoding and decoding complexity that is similar to that of point-to-point communications. We show that our proposed OIM scheme achieves a per-node throughput capacity of Θ (log(T(n))/√nT(n)) in a wireless network of n nodes and communication range of T(n) = Ω(√log n). This represents a gain of Θ (log(T(n))) compared to simple point-to-point communication. As such, OIM represents a practical alternative to attaining capacity gains similar to those attainable in theory with distributed MIMO systems, and opens up a new area of research for the development of medium access control protocols aimed at managing interference.

We study the scaling laws for wireless ad hoc network in which the distribution of nodes in the network is homogeneous but the traffic is heterogeneous. More specifically, we consider the case in which a node is the sink to k sources sending different information, while the rest of the nodes are part of unicast communications with a uniform assignment of source-destination pairs. We prove that the capacity of these heterogeneous networks is ¿(n/Tmax), where Tmaxand n denote the maximum traffic for a cell and the number of nodes in the network, respectively. Equivalently, our derivations reveal that, when n - k ¿ constant, the network capacity is equal to ¿(¿(n/(log n))) for k = O(¿(n log n)) and equal to ¿ (n/k) for k = ¿(¿(n log n)). Furthermore, the network capacity is ¿(1) when n - k = constant. These results demonstrate that the capacity of a heterogeneous network is dominated by the maximum congestion in any area of the network.

We introduce a new multiuser diversity scheme for interference management in cellular networks. A base station with K antennas communicates with at most K out of M mobile stations. It is proven that, if K ¿ M, then K independent data streams can be transmitted to K mobile stations with no need for cooperative joint decoding by such stations. This result is based on a new multiuser diversity concept that allows parallel communication in the network without any cooperation among mobile stations. If the network does not have enough mobile stations, then some of the users need to jointly decode their corresponding data streams. The result suggests the existence of a tradeoff between multiuser diversity and cooperation in the downlink of cellular networks. Our interference management approach is based on a new multiuser diversity concept that achieves the capacity of dirty paper coding (DPC) asymptotically. Surprisingly, this gain is achieved without requiring full channel state information (CSI) and only K integers related to CSI are fed back from mobile stations to the base station. An additional advantage of this scheme is the fact that the encoding and decoding of signals for this distributed MIMO system is based on simple point-to-point communications.