In this paper, we propose a new coded computing technique called "substitute decoding" for general iterative distributed computation tasks. In the first part of the paper, we use PageRank as a simple example to show that substitute decoding can make the computation of power iterations solving PageRank on sparse matrices robust to erasures in distributed systems. For these sparse matrices, codes with dense generator matrices can significantly increase storage costs and codes with low-density generator matrices (LDGM) are preferred. Surprisingly, we show through both theoretical analysis and simulations that when substitute decoding is used, coded iterative computing with extremely low-density codes (2 or 3 non-zeros in each row of the generator matrix) can achieve almost the same convergence rate as noiseless techniques, despite the poor error-correction ability of LDGM codes. In the second part of the paper, we discuss applications of substitute decoding beyond solving linear systems and PageRank. These applications include (1) computing eigenvectors, (2) computing the truncated singular value decomposition (SVD), and (3) gradient descent. These examples show that the substitute decoding algorithm is useful in a wide range of applications.
 In large scale distributed linear transform problems, coded computation plays an important role to effectively deal with "stragglers" (distributed computations that may get delayed due to few slow or faulty processors). We propose a coded computation strategy, referred to as diagonal code, that achieves the optimum recovery threshold and the optimum computation load. This is the first code that simultaneously achieves two-fold optimality in coded distributed linear transforms. Furthermore, by leveraging the idea from random proposal graph theory, we design two random codes that can guarantee optimum recovery threshold with high probability but with much less computation load. These codes provide order-wise improvement over the state-of-the-art. Moreover, the experimental results show significant improvement compared to both uncoded and existing coding schemes.  Large-scale machine learning and data mining applications require computer systems to perform massive computations that need to be parallelized across multiple nodes, for example, massive matrix-vector and matrix-matrix multiplication. The presence of straggling nodes -- computing nodes that unpredictably slowdown or fail -- is a major bottleneck in such distributed computations. We propose a strategy to alleviate the problem of stragglers in distributed matrix-vector multiplication. Our algorithm creates a stream of linear combinations of the @math rows of the matrix, and assigns them to different worker nodes, which then perform row-vector products with the encoded rows. The original matrix-vector product can be decoded as soon as slightly more than @math row-vector products are collectively finished by the nodes. This strategy enables fast nodes to steal work from slow nodes, without requiring the master to perform any dynamic load-balancing. Compared to recently proposed fixed-rate erasure coding strategies which ignore partial work done by straggling nodes, rateless coding achieves significantly lower overall delay, as well as small computational and decoding overhead. Distributed Stochastic Gradient Descent (SGD) when run in a synchronous manner, suffers from delays in waiting for the slowest learners (stragglers). Asynchronous methods can alleviate stragglers, but cause gradient staleness that can adversely affect convergence. In this work we present a novel theoretical characterization of the speed-up offered by asynchronous methods by analyzing the trade-off between the error in the trained model and the actual training runtime (wallclock time). The novelty in our work is that our runtime analysis considers random straggler delays, which helps us design and compare distributed SGD algorithms that strike a balance between stragglers and staleness. We also present a new convergence analysis of asynchronous SGD variants without bounded or exponential delay assumptions, and a novel learning rate schedule to compensate for gradient staleness. Slow running or straggler tasks can significantly reduce computation speed in distributed computation. Recently, coding-theory-inspired approaches have been applied to mitigate the effect of straggling, through embedding redundancy in certain linear computational steps of the optimization algorithm, thus completing the computation without waiting for the stragglers. In this paper, we propose an alternate approach where we embed the redundancy directly in the data itself, and allow the computation to proceed completely oblivious to encoding. We propose several encoding schemes, and demonstrate that popular batch algorithms, such as gradient descent and L-BFGS, applied in a coding-oblivious manner, deterministically achieve sample path linear convergence to an approximate solution of the original problem, using an arbitrarily varying subset of the nodes at each iteration. Moreover, this approximation can be controlled by the amount of redundancy and the number of nodes used in each iteration. We provide experimental results demonstrating the advantage of the approach over uncoded and data replication strategies. In a large-scale and distributed matrix multiplication problem @math , where @math , the coded computation plays an important role to effectively deal with "stragglers" (distributed computations that may get delayed due to few slow or faulty processors). However, existing coded schemes could destroy the significant sparsity that exists in large-scale machine learning problems, and could result in much higher computation overhead, i.e., @math decoding time. In this paper, we develop a new coded computation strategy, we call , which achieves near , , and @math . We implement our scheme and demonstrate the advantage of the approach over both uncoded and current fastest coded strategies.