  Faced with saturation of Moore's law and increasing dimension of data, system
designers have increasingly resorted to parallel and distributed computing.
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 finish. To combat the
effect of stragglers, recent literature introduces 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 faster and more
efficiently at individual processors. In reference to comparable schemes that
introduce redundancy to tackle stragglers, Short-Dot reduces the cost of
computation, storage and communication since shorter portions are stored and
computed at each processor, and also shorter portions of the input is
communicated to each processor. We demonstrate through probabilistic analysis
as well as experiments 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 to wait
for), for any such strategy and compare it to that achieved by our strategy.
