We propose two coded schemes for the distributed computing problem ofmultiplying a matrix by a set of vectors. The first scheme is based onpartitioning the matrix into submatrices and applying maximum distanceseparable (MDS) codes to each submatrix. For this scheme, we prove that up to agiven number of partitions the communication load and the computational delay(not including the encoding and decoding delay) are identical to those of thescheme recently proposed by Li et al., based on a single, long MDS code.However, due to the use of shorter MDS codes, our scheme yields a significantlylower overall computational delay when the delay incurred by encoding anddecoding is also considered. We further propose a second coded scheme based onLuby Transform (LT) codes under inactivation decoding. Interestingly, LT codesmay reduce the delay over the partitioned scheme at the expense of an increasedcommunication load. We also consider distributed computing under a deadline andshow numerically that the proposed schemes outperform other schemes in theliterature, with the LT code-based scheme yielding the best performance.
展开▼
