Coded Distributed Computing for Inverse Problems
Computationally intensive distributed and parallel computing is often bottlenecked by a small set of slow workers known as stragglers. In this paper, we utilize the emerging idea of "coded computation" to design a novel error-correcting-code inspired technique for solving linear inverse problems under specific iterative methods in a parallelized implementation affected by stragglers. Example machinelearning applications include inverse problems such as personalized PageRank and sampling on graphs. We provably show that our coded-computation technique can reduce the mean-squared error under a computational deadline constraint. In fact, the ratio of mean-squared error of replication-based and coded techniques diverges to infinity as the deadline increases. Our experiments for personalized PageRank performed on real systems and real social networks show that this ratio can be as large as 10 4 . Further, unlike coded-computation techniques proposed thus far, our strategy combines outputs of all workers, including the stragglers, to produce more accurate estimates at the computational deadline. This also ensures that the accuracy degrades "gracefully" in the event that the number of stragglers is large.
The paper considers a distributed computing scenario where a bunch of processors have different delays in computing. A job (here finding a solution of a system of linear equations) is distributed among the processors. After a certain deadline the output of the processors are combined and the result is produced.
Previous literature mainly neglect the slower processors and work with the best k out of n processors' outputs. Usually an MDS code is used to distribute the task among the processors. I understand the main contribution is to include the stragglers computations and not treat them as mere erasures.
I have few critical comments regarding the work.
1. Correctness of results:  I think there are serious problems in the assumptions (see line 116-117). If x_i s are all iid, it is not necessary that r_i s are all iid as well. This only happens when M is square invertible matrix. For example, if a row of M is zero then the corresponding entry of r_i is going to be always zero. The main results all depend on this assumption, which makes me doubtful about the veracity of results.
2. Assumptions without justification: From the introduction it seems like the main result is contained in Theorem 4.4. This theorem is true under two very specific assumptions.  One, the solutions of a systems of linear equations are all iid variables, and the number of iterations of each processor within a deadline are all iid random variables. These two seem like very stringent condition and I see no reason for these to be true in real systems. The authors also do not provide any motivation for these assumptions to be true either. Given this, I am unable to judge whether the theoretical results are of any value here.
Another key condition for the results to be true is n-k = o(\sqrt(n). Again it was not explained why this should be the case even asymptotically. 
Also, I do not understand the implication of the random variable C(l) satisfying the ratio of variance and mean-square to be large. Why would this assumption make any sense?
Overall lack of motivations for these assumptions seem concerning.
3. Unfair comparison:  The replication scheme, that the paper compare their coding scheme with, has several problems. And I do not think that it is a good comparison. The assumption is that n -k is very small, i.e., o(\sqrt{n}). So computation of only o(\sqrt{n}) elements are computed twice. The rest of the processors are uncoded. This is a very specific coding scheme, and it is obvious that the Fourier matrix based scheme (which is an MDS code) will beat this scheme.
In the introduction it was claimed that: “To compare with the existing coding technique in [6], ..” But the theoretical comparison to the method of [6] is missing. 
4. Novelty: I do not think the presented scheme is new. It is the same MDS code based scheme that was proposed by Lee et al (in ref [6]). 
Overall the same encoding method has been used in both [6] and in this paper. The only difference is that the results of the stragglers are also used in this paper while decoding - so it is expected to get a better error rate. But in general, the claim of introduction, the prevention of ill-conditioning of MDS matrices in the erasure channel, remains unmitigated. It is just that a particular problem is considered in the paper.
5. Experiments: 9. The figures are not properly labeled. In the third plot of fig 2, ref [12] is mentioned, which should be [6] (I think). This is quite confusing.
I am further skeptical about this plot. At certain value of the T_deadline, the method of [6], should result in absolute 0 error. But this is not observed in the plot. It is also not clear why in the extension of the coded method the mean square error would increase.
6. More minor comments:
 The authors say “iterative methods for linear inverse problem” as if it is a very standard problem: however it is not to me. A more understandable term would be `finding solutions of a linear system'. So for quite long time I could not figure out what the exact problem they are trying to solve. This create difficulty reading the entirety of the introduction/abstract.
\rho has been used as spectral radius, and also in the heavy tail distributions.
=============
After the rebuttal:
I am able to clarify my confusion about independence of the random variables. So I do not have about the concern with correctness anymore. The point that I am still worried about is the unfair comparison with repetition codes! I do not think n-k =o(n) is the correct regime to use repetition code.
It seems to me from the rebuttal is, if T_deadline is large enough, then coding does not help (which makes sense). Is it clear what is the crossover point of T_deadline?  
I am satisfied with the rebuttal in other points.