In distributed computing systems slow working nodes, known as stragglers, can greatly extend finishing times. Coded computing is a technique that enables straggler-resistant computation. Most coded computing techniques presented to date provide robustness by ensuring that the time to finish depends only on a set of the fastest nodes. However, while stragglers do compute less work than non-stragglers, in real-world commercial cloud computing systems (e.g., Amazon’s Elastic Compute Cloud (EC2)) the distinction is often a soft one. In this paper, we develophierarchicalcoded computing that exploits the work completed by all nodes, both fast and slow, automatically integrating the potential contribution of each. We first present a conceptual framework to represent the division of work amongst nodes in coded matrix multiplication as a cuboid partitioning problem. This framework allows us to unify existing methods and motivates new techniques. We then develop three methods of hierarchical coded computing that we termbit-interleavedcoded computation (BICC),multilevelcoded computation (MLCC), andhybridhierarchical coded computation (HHCC). In this paradigm, each worker is tasked with completing a sequence (a hierarchy) of ordered subtasks. The sequence of subtasks, and the complexity of each, is designed so that partial work completed by stragglers can be used, rather than ignored. We note that our methods can be used in conjunction with any coded computing method. We illustrate this by showing how we can use our methods to accelerate all previously developed coded computing techniques by enabling them to exploit stragglers. Under a widely studied statistical model of completion time, our approach realizes a 66% improvement in the expected finishing time. On Amazon EC2, the gain was 27% when stragglers are simulated.

Coded computation is a method to mitigate “stragglers” in distributed computing systems through the use of error correction coding that has lately received significant attention. First used in vector-matrix multiplication, the range of application was later extended to include matrix-matrix multiplication, heterogeneous networks, convolution, and approximate computing. A drawback to previous results is they completely ignore work completed by stragglers. While stragglers are slower compute nodes, in many settings the amount of work completed by stragglers can be non-negligible. Thus, in this work, we propose a hierarchical coded computation method that exploits the work completed by all compute nodes. We partition each node's computation into layers of sub-computations such that each layer can be treated as (distinct) erasure channel. We then design different erasure codes for each layer so that all layers have the same failure exponent. We propose design guidelines to optimize parameters of such codes. Numerical results show the proposed scheme has an improvement of a factor of 1.5 in the expected finishing time compared to previous work.

In cloud computing systems slow processing nodes, often referred to as “stragglers”, can significantly extend the computation time. Recent results have shown that error correction coding can be used to reduce the effect of stragglers. In this work we introduce a scheme that, in addition to using error correction to distribute mixed jobs across nodes, is also able to exploit the work completed by all nodes, including stragglers. We first consider vector-matrix multiplication and apply maximum distance separable (MDS) codes to small blocks of sub-matrices. The worker nodes process blocks sequentially, working block-by-block, transmitting partial per-block results to the master as they are completed. Sub-blocking allows a more continuous completion process, which thereby allows us to exploit the work of a much broader spectrum of processors and reduces computation time. We then apply this technique to matrix-matrix multiplication using product code. In this case, we show that the order of computing sub-tasks is a new degree of design freedom that can be exploited to reduce computation time further. We propose a novel approach to analyze the finishing time, which is different from typical order statistics. Simulation results show that the expected computation time decreases by a factor of at least two in compared to previous methods.

In this paper we propose an approach to parallelizing synchronous stochastic gradient descent (SGD) that we term “Anytime-Gradients”. The Anytime-Gradients is designed to exploit the work completed by slow compute nodes or “stragglers”. In many approaches work completed by these nodes, while only partial, is discarded completely. To maintain synchronization in our approach, each computational epoch is of fixed duration, and at the end of each epoch, workers send updated parameter vectors to a master mode for combination. The master weights each update by the amount of work done. The Anytime-Gradients scheme is robust to both persistent and non-persistent stragglers and requires no prior knowledge about processor abilities. We show that the scheme effectively exploits stragglers and outperforms existing methods.

This paper proposes a low-complexity scheme to construct Voronoi constellations for the shaping of high-dimensional lattice codes. The Voronoi region of a low-dimensional lattice is used as a prototype for the shaping region for a high-dimensional lattice codebook. The proposed scheme retains the shaping and coding gains of the respective lattices. Further, the proposed scheme provides a general approach for shaping popular high-dimensional lattices, including LDA lattices, for which no practical shaping algorithm exists to our knowledge. Finally, the proposed scheme preserves the algebraic properties of nested lattice codes, making it suitable for compute-and-forward applications. Using E8and BW16as prototype shaping lattices, we numerically show that the proposed scheme results in 0:65 dB and 0:86 dB shaping gains.

We propose two low-complexity lattice code constructions that have competitive coding and shaping gains. The first construction, named systematic Voronoi shaping, maps short blocks of integers to the dithered Voronoi integers, which are dithered integers that are uniformly distributed over the Voronoi region of a low-dimensional shaping lattice. Then, these dithered Voronoi integers are encoded using a high-dimensional lattice retaining the same shaping and coding gains of lowand high-dimensional lattices. A drawback to this construction is that there is no isomorphism between the underlying message and the lattice code, preventing its use in applications such as compute-and-forward. Therefore, we propose a second construction, called mixed nested lattice codes, in which a high-dimensional coding lattice is nested inside a concatenation of low-dimensional shaping lattices. This construction not only retains the same shaping/coding gains as first construction but also provides the desired algebraic structure. We numerically study these methods, for point-to-point channels as well as compute-and-forward using low-density lattice codes as coding lattices and E8 and Barnes-Wall as shaping lattices. Numerical results indicate a shaping gain of up to 0.86 dB, compared with the state-ofthe-art of 0.4 dB; furthermore, the proposed method has lower complexity than the state-of-the-art approaches.

We propose a class of practical efficient lattice codes for real-valued full-duplex one- and two-way relay channels. First, we investigate the problem from a theoretical perspective, proposing lattice-coding instantiations of superposition block Markov encoding. Our encoding/decoding strategies recover the well-known decode-and-foward rates for the one-way relay channel and a previously-proven rate region for the two-way relay channel. Then, we construct practical, low-complexity implementations of these schemes using low-density lattice codes. Simulations show that our schemes achieve performance as close as 2.5 dB away from theoretical limits. Finally, we show that, due to features inherent to full-duplex relaying and practical codes, the gap to theoretical limits depends on the channel gains and transmit power of the relay relative to the source(s). We characterize this gap analytically, providing insight into the design of practical full-duplex relay systems.

A lattice code construction that employs two separate lattices, a high dimension lattice for coding gain and a low-dimension lattice for shaping gain, is described. Systematic lattice encoding is a method to encode an integer sequence to a lattice point that is nearby that integer sequence. We describe the “Voronoi integers” ℤm/Λs, the set of integers inside the fundamental Voronoi region of a shaping lattice Λs, and a concrete scheme to label these integers. By first shaping the information using the Voronoi integers in low dimension, and then performing systematic lattice encoding using a high-dimension lattice, good shaping and coding gains can be simultaneously obtained. We concentrate on the case of using the E8lattice for shaping and low-density lattice codes (LDLC) with dimension ~ 10,000 for coding. While optimal shaping provides a well-known 1.53 dB gain, previously reported shaping gains with LDLC lattices are on the order of 0.4 dB. The proposed method preserves the shaping gain of the E8lattice, that is, as much as 0.65 dB. This shaping operation can be implemented with lower complexity than previous LDLC approaches.

We study practical, efficient codes for the Gaussian relay channel. It has been demonstrated that low-density lattice codes (LDLCs) can provide near-capacity performance for point-to-point Gaussian channels. We present an LDLC formulation that provides performance near the decode-and-forward inner bound of the relay channel capacity. We employ a superposition block Markov strategy tailored to LDLCs and design an appropriate iterative decoder. We characterize the error performance via simulations, showing that our scheme achieves performance only 2dB away from the decode-and-forward bound.

Antenna correlation is usually viewed as a detrimental effect in a multiple input multiple output (MIMO) system. This paper investigates how this affects the performance of an amplify-and-forward (AF) relay network. We consider multiple antennas at all nodes with a general correlation matrix structure having an arbitrary eigenvalue distribution. We derive exact closed form expression for the ergodic capacity and simplify to special case of distinct eigenvalues. Further, we investigate the system in high signal-to-noise ratio (SNR) and derive a simple asymptotic expression. Our results provide a comprehensive analysis and useful insight about the ergodic capacity of the system.

This paper investigates the secrecy performance of multiple-input single-output (MISO) wiretap channels with transmit antenna selection (TAS) and subject to an interference-limited eavesdropper. By considering NAantennas at the transmitter, a single antenna at the legitimate receiver and eavesdropper, and multiple arbitrary co-channel interferers M at the eavesdropper, an exact closed-form expression for the secrecy outage probability is derived. The exact expression is simplified for two, yet novel, special cases. Based on these analytical expressions, an asymptotic secrecy outage analysis is carried out and it shows that the diversity order of the considered system equals to min(NA, M). The proposed analysis is corroborated through Monte Carlo simulation results. Illustrative numerical examples are depicted and insightful discussions are drawn. It is shown that the secrecy outage performance is largely limited by the number of interference channels and the number of transmit antennas due to diversity gain.

In this paper, a novel transmit antenna selection scheme for multiple input multiple output (MIMO) wiretap channels is proposed. This new scheme achieves higher secrecy performance by exploiting eavesdropper's channel state information. The key idea behind our proposal is to perform the antenna selection aiming to maximize the overall secrecy rate instead of maximizing the instantaneous signal-to-noise ratio of the main channel. In our analysis, we assume that the legitimate receiver and the eavesdropper employ a maximal-ratio combining technique to combine the received signals from the transmitter. Considering Nakagami-m fading channels, a closed-form expression for the secrecy outage probability is derived, which can be used as a quality of service metric. Further, an asymptotic analysis is carried out and the diversity/array gains are obtained. The ergodic secrecy rate is also investigated for the case of multiple input single output wiretap channels. Representative numerical examples are plotted and validated through Monte Carlo simulations. Insightful discussions are drawn from the proposed analysis.

This paper studies the effect of feedback delay on the performance of amplify-and-forward (AF) relay selection over Nakagami-m fading environment. Spatial diversity can be improved by employing multiple relays with selection, however, this diversity gain cannot be fully realized when the feedback delay is present in the decision metric. Hence, we try to quantify this detrimental effect by deriving the exact closed form solution to outage probability and ergodic capacity for channel state information (CSI)-assisted relay. Further, we derive simple asymptotic results for outage to provide insight of the system performance and diversity. Monte Carlo simulation is used to verify the analytical work.

This paper investigates the performance of amplify-and-forward (AF) two-way relay system with antenna correlation. Overall outage probability (OOP), average symbol error rate (SER) and ergodic capacity are analyzed. By considering general correlation structure with arbitrary eigenvalue distribution, we derive a tight lower bound for OOP and use it to evaluate average SER and ergodic capacity. Moreover, the system is studied in high signal-to-noise ratio (SNR) to obtain the insightful behavior of the performance and diversity gain. Finally Monte Carlo simulations are conducted to verify the accuracy of the results.

We present a unified performance analysis of beamforming, for the system in which the source and the destination are both equipped with multiple antennas while the relay is equipped with a single antenna. By assuming general correlation structures with arbitrary eigenvalue multiplicities at the source and the destination, the exact outage probability for fixed gain relaying is derived. As a result, our new results unify all previously reported cases as well as new additional ones. Furthermore we derive the exact outage probability for TAS(Transmitter Antenna Selection)/MRC system and provide a performance comparison of the two systems. To gain insights, we have also presented high signal-to-noise ratio expressions which clearly show the impact of number of transmit/receive antennas and correlation on the outage probability. Finally, Monte Carlo simulations are presented to verify the correctness of the analytical results.

This paper presents the performance analysis of multi-user scheduling for channel state information (CSI)-assisted and fixed gain AF relaying with antenna correlation. We consider a source equipped with multiple correlated antennas communicating with multiple users via a relay which has dual correlated antennas. The system performance degrades with the spatial correlation. Hence we derive the exact closed form solutions to outage probability, average symbol error rate (SER) and generalized higher moment of the signal-to-noise ratio (SNR) to quantify this detrimental effect. The ergodic capacity is also analyzed. To understand the insight system performance behavior and the diversity gain, we present a high SNR analysis. The analytical results are verified with the Monte Carlo simulations at the end.

We present a unified performance analysis of a system in which the source and the destination are equipped with multiple antennas and communicating via a single antenna relay. Our studies can be divided into two parts. First we consider a system with maximal ratio transmission (MRT) at the source and maximal ratio combining (MRC) at the destination by assuming general correlation structures with arbitrary eigenvalue multiplicities at the source and the destination. Then a system with transmit antenna selection (TAS) at the source with uncorrelated antennas and MRC at the destination with correlated antennas is investigated. The exact closed form expressions for outage probability, average symbol error rate (SER), generalized higher moments of SNR for both channel state information (CSI)-assisted and fixed gain relaying are derived and an analysis of the ergodic capacity is provided. Hence, our new results cover several previously reported cases as well as new additional ones. Further, we present the asymptotic analysis which gives an insight of the system performance and the diversity gain in each case. To verify the analytical results we provide Monte Carlo simulations at the end.