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.

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%.

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.

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 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 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.

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.

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.

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.

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.

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.