Block-Diagonal and LT Codes for Distributed Computing With Straggling Servers

We propose two coded schemes for the distributed computing problem of\nmultiplying a matrix by a set of vectors. The first scheme is based on\npartitioning the matrix into submatrices and applying maximum distance\nseparable (MDS) codes to each submatrix. For this scheme, we prove that up to a\ngiven number of partitions the communication load and the computational delay\n(not including the encoding and decoding delay) are identical to those of the\nscheme recently proposed by Li et al., based on a single, long MDS code.\nHowever, due to the use of shorter MDS codes, our scheme yields a significantly\nlower overall computational delay when the delay incurred by encoding and\ndecoding is also considered. We further propose a second coded scheme based on\nLuby Transform (LT) codes under inactivation decoding. Interestingly, LT codes\nmay reduce the delay over the partitioned scheme at the expense of an increased\ncommunication load. We also consider distributed computing under a deadline and\nshow numerically that the proposed schemes outperform other schemes in the\nliterature, with the LT code-based scheme yielding the best performance for the\nscenarios considered.\n

Paper

Similar papers

© 2026 NYSGPT2525 LLC