"Short-Dot": Computing Large Linear Transforms Distributedly Using Coded Short Dot Products
Faced with saturation of Moore's law and increasing size and dimension of data, system designers have increasingly resorted to parallel and distributed computing to reduce computation time of machine-learning algorithms. However, distributed computing is often bottle necked by a small fraction of slow processors called "stragglers" that reduce the speed of computation because the fusion node has to wait for all processors to complete their processing. To combat the effect of stragglers, recent literature proposes introducing redundancy in computations across processors, e.g., using repetition-based strategies or erasure codes. The fusion node can exploit this redundancy by completing the computation using outputs from only a subset of the processors, ignoring the stragglers. In this paper, we propose a novel technique -that we call "Short-Dot" -to introduce redundant computations in a coding theory inspired fashion, for computing linear transforms of long vectors. Instead of computing long dot products as required in the original linear transform, we construct a larger number of redundant and short dot products that can be computed more efficiently at individual processors. Further, only a subset of these short dot products are required at the fusion node to finish the computation successfully. We demonstrate through probabilistic analysis as well as experiments on computing clusters that Short-Dot offers significant speed-up compared to existing techniques. We also derive trade-offs between the length of the dot-products and the resilience to stragglers (number of processors required to finish), for any such strategy and compare it to that achieved by our strategy.
In this paper, the authors introduce a method to compute a matrix-vector product in parallel. The method relies on a key assumption that the number of available processors is larger than the number of columns in the matrix. Under this assumption, they propose a method that distributes the columns of a modified matrix, computes (sparse) vector dot products in parallel and only has to wait for a small number of the processors to finish computing the dot products. This way, they can avoid the problem of waiting for straggler processors to finish. 
The paper is easy to understand, and the concept seems clear. Detailed comments follow (both major and minor, in no particular order):  - My biggest concern about the practicality of the method is the (pretty restrictive) assumption that the number of available processors is larger than the number of columns. Almost all modern applications have a large number of variables to fit, and the number of available processors is almost always smaller (at most in the order of hundreds). So while the math is correct and the results look impressive, i’d like to see this aspect discussed and addressed in detail.   - line 10: a only —> only a  - Figure 2: at this point, with K > M, short dot is not necessarily faster. it depends on the sparsity (s) as well. You address this later, but this has to be made clear before directing one’s attention to fig 2.   - line 142: chosen —> choosing  - The flow of ideas to prove theorem 1 is confusing. It is better to separate lemmas from the main theorem proof.   - Figure 5 does not paint a full picture. For example, what happens when \mu is varied? Why is MDS worse than no coding at all? Are there any values of \mu for which the repetition scheme is good? Why is the expected time  = 1 even when the number of dot products is nearly 0 for MDS and repetition?   - line 233: Could you include a plot akin to fig 5 but taking the encoding and decoding complexity also into account? Although it is a one-time computation, it cannot be ignored.   - How do the performances of the various algorithms compare on real datasets? You mention linear regression, but experiments on real data would be nice to have.