Search

We consider a mobile edge computing scenario, in which mobile users (e.g., smartphones) offload their computation requests to the computing nodes distributed at the network edge (e.g., base stations). The edge nodes process the offloaded requests in the “computation phase”, and return the results to the users in the “communication phase” through wireless links. With emphasis on the role of coding in both computation and communication phases, we introduce new architectures for mobile edge computing to exploit the best of both and achieve three salient features: 1) Optimality: We show that coded computations can induce collaboration among the nodes in communication phase, and thus achieves minimum possible load of communication, without requiring extra computation, therefore achieves the minimum possible load of computation simultaneously. 2) Universality: The code design in the coded computation does not require channel state information in communication phase, and therefore it is universality optimum for any channel coefficient. 3) Mobility tolerance: The computation results can be delivered from any subset of the edge nodes with slightly more computations, thus mobility of the users can be dealt with effectively.

We propose a framework for edge-facilitated wireless distributed computing, in which several mobile users connected to an access point collaborate for a distributed computing task. We characterize the minimum communication load, both in uplink (from users to the access point) and downlink (from access point to the users), required for distributed computing. In particular, we develop a communication scheme and a dataset placement strategy that induces a particular overlap of computations at the users, which can then be exploited for coding at both users and the access point to significantly reduce the communication load. We demonstrate that the reduction in communication load (compared to uncoded solutions) can scale linearly with the size of the network (i.e., the number of users), hence our proposed scheme can result in a "scalable" design for edge- facilitated wireless distributed computing (i.e., accommodating any number of users without incurring extra communication load). Furthermore, we establish the optimality of the proposed scheme by developing a tight information theoretic outer- bound, and demonstrate that the proposed scheme achieves the minimum uplink and downlink communication load simultaneously. We also generalize the results to a decentralized setting, in which a random and a priori unknown subset of users may participate in distributed computing at each time, and characterize the minimum communication load for uniformly random dataset placement at users.

In this paper, we demonstrate a coded computing framework, named Coded Distributed Computing (CDC), which optimally trades extra computation resources for communication bandwidth in a MapReduce-type distributed computing environment. We also empirically illustrate the practical impact of CDC by analyzing the performance of a distributed sorting algorithm, named CodedTeraSort, which was developed by integrating the coding principle of CDC into the Hadoop benchmark TeraSort. Experiment results illustrate 1.97×–3.39 × speedup using CodedTeraSort, compared with TeraSort, for typical settings of interest. In the end, we review some of the open problems and future directions.

In this paper, we first review the Coded Distributed Computing (CDC) framework, recently proposed to significantly slash the data shuffling load of distributed computing via coding, and then discuss the extension of the CDC techniques to cope with two major challenges in general distributed computing problems, namely the straggling servers and multistage computations. When faced with straggling servers in a distributed computing cluster, we describe a unified coding scheme that superimposes CDC with the Maximum-Distance-Separable (MDS) coding on computation tasks, which allows a flexible tradeoff between computation latency and communication load. On the other hand, for a general multistage computation task expressed as a directed acyclic graph (DAG), we propose a coded framework that given the load of computation on each vertex of the DAG, applies the generalized CDC scheme individually on each vertex to minimize the communication load.

We introduce a general distributed computing framework, motivated by commonly used structures like MapReduce, and formulate an information-theoretic tradeoff between computation and communication in such a framework. We characterize the optimal tradeoff to within a constant factor, for all system parameters. In particular, we propose a coded scheme, namely “Coded MapReduce” (CMR), which creates and exploits coding opportunities in data shuffling for distributed computing, reducing the communication load by a factor that is linearly proportional to the computation load. We then prove a lower bound on the minimum communication load, and demonstrate that CMR achieves this lower bound to within a constant factor. This result reveals a fundamental connection between computation and communication in distributed computing - the two are inverse-linearly proportional to each other.

In this paper, a new coding scheme for the multiple access channel (MAC) with noisy cooperative links is proposed. The cooperation cost is modelled by powers spent on exchanging common information at transmitters. The optimal power allocation policy is derived to explore the tradeoff between cooperation and transmission. For some important cases, optimal power allocation that maximizes weighted sum rate, is found analytically. The sufficient and necessary condition for which the sum and the individual rates are simultaneously maximized, is identified. Analytical and numerical results suggest that the transmitter, whose power budget is dominated by that of the other, acts purely as a relay. The cooperation gain becomes more significant when the difference between the power budgets is smaller.

We consider a spectrum sharing protocol wherein the primary and secondary transmitters cooperatively relay each other's message. Transmission is done in two phases, with each transmitter attempting to decode messages from the other system transmission in a first phase. The second phase transmission consists of the decoded message superposed onto its own message. Priority is given to the primary system transmissions by having the primary message always transmitted over the two phases, while the secondary message is transmitted depending on successful decoding. We consider the scenario where the primary and secondary receivers are co-located, forming a virtual two-antenna receiver. We assess the performance of the system in terms of outage probability and characterize performance corresponding to each state of the Markov chain that governs the proposed transmission protocol. We show that joint decoding offers a 20 dB performance improvement over separate decoding for the primary user and 1.8 dB for the secondary user.

A new transmission protocol for joint cooperation between a primary and secondary user in a cognitive radio system is proposed. If successful decoding is achieved, the primary/secondary transmitters behave as relays for the other system. With more efficient use of the communication resource, performance is enhanced. The proposed scheme builds on the work in [1] and offers improved outage probabilities for both the primary and secondary systems. The paper provides a full characterization of the Markov Chain describing the protocol behavior and a closed form expression for the stationary distribution of the chain. Furthermore, exact computation or tight approximations for the outage probabilities for all states of the chain are derived. Simulation results exhibit a performance improvement between 22 and 48 percent for primary system and an uniform decrease of outage probability for secondary system.