Codes are widely used in many engineering applications to offer some form of reliability and fault tolerance. The high-level idea of coding is to exploit resource redundancy to deliver higher robustness against system noise. In large-scale systems there are several types of "noise " that can affect the performance of distributed machine learning algorithms : straggler nodes, system failures, or communication bottlenecks . Moreover, redundancy is abundant: a plethora of nodes, a lot of spare storage, etc . In this work, scratching the surface of "codes for distributed computation," we provide theoretical insights on how coded solutions can achieve significant gains compared to uncoded ones. We focus on two of the most basic building blocks of distributed learning algorithms: matrix multiplication and data shuffling. For matrix multiplication, we use codes to leverage the plethora of nodes and alleviate the effects of stragglers. We show that if the number of  workers is n, and the runtime of each subtask has an exponential tail, the optimal coded matrix multiplication is \Theta(\log n) times faster than the uncoded matrix multiplication. In data shuffling, we use codes to exploit the excess in storage and reduce communication bottlenecks . We show that when \alpha is the fraction of the data matrix that can be cached at each worker, and n is the number of workers, coded shuffling \emph{ reduces the communication cost by a factor \Theta(\alpha \gamma(n) ) compared to uncoded shuffling, where \gamma(n) is the ratio of the cost of unicasting n messages to n users to broadcasting a common message (of the same size) to n users. Our synthetic and Open MPI experiments on Amazon EC2 show that coded distributed algorithms can achieve significant speedups of up to 40\% compared to uncoded distributed algorithms.
Codes are widely used in many engineering applications to offer robustness against noise. In large-scale systems there are several types of noise that can affect the performance of distributed machine learning algorithms -- straggler nodes, system failures, or communication bottlenecks -- but there has been little interaction cutting across codes, machine learning, and distributed systems . In this work, we provide theoretical insights on how coded solutions can achieve significant gains compared to uncoded ones. We focus on two of the most basic building blocks of distributed learning algorithms: matrix multiplication and data shuffling. For matrix multiplication, we use codes to alleviate the effect of stragglers, and show that if the number of homogeneous workers is n, and the runtime of each subtask has an exponential tail, coded computation can speed up distributed matrix multiplication by a factor of \log n. For data shuffling, we use codes to reduce communication bottlenecks, exploiting the excess in storage . We show that when a constant fraction \alpha of the data matrix can be cached at each worker, and n is the number of workers, \emph{coded shuffling reduces the communication cost by a factor of (\alpha + \frac{1 \gamma(n) compared to uncoded shuffling, where \gamma(n) is the ratio of the cost of unicasting n messages to n users to multicasting a common message (of the same size) to n users. For instance, \gamma(n) \simeq n if multicasting a message to n users is as cheap as unicasting a message to one user. We also provide experiment results, corroborating our theoretical gains of the coded algorithms.
R
some form of reliability and fault tolerance. The high-level idea of coding is to exploit resource redundancy to deliver higher robustness against system
robustness against
R
"noise "
noise
R
:
--
R
. Moreover, redundancy is abundant: a plethora of nodes, a lot of spare storage, etc
-- but there has been little interaction cutting across codes, machine learning, and distributed systems
D
scratching the surface of "codes for distributed computation,"
R
leverage the plethora of nodes and alleviate the effects of stragglers. We
alleviate the effect of stragglers, and
A
homogeneous
R
the optimal coded matrix multiplication is \Theta(\log n) times faster than the uncoded matrix multiplication. In
coded computation can speed up distributed matrix multiplication by a factor of \log n. For
R
exploit
reduce communication bottlenecks, exploiting
D
and reduce communication bottlenecks
R
\alpha is the fraction
a constant fraction \alpha
D
that
D
coded shuffling
A
coded shuffling
R
\Theta(\alpha
of (\alpha + \frac{1
D
)
R
broadcasting
multicasting
R
Our synthetic and Open MPI experiments on Amazon EC2 show that coded distributed algorithms can achieve significant speedups of up to 40\% compared to uncoded distributed
For instance, \gamma(n) \simeq n if multicasting a message to n users is as cheap as unicasting a message to one user. We also provide experiment results, corroborating our theoretical gains of the coded