Coding for distributed computing

Distributed computing has emerged as an effective way of tackling increasingly complex computational problems.However, distributed computing systems bring significant challenges.Among them, the problems of straggling servers and bandwidth scarcity have recently received significant attention.The straggler problem is a synchronization problem characterized by the fact that a distributed computing task must wait for the slowest server to complete its computation.On the other hand, distributed computing tasks typically require that data is moved between servers during the computation, the so-called data shuffling, which is a challenge in bandwidth-constrained networks.We consider the distributed computing task of multiplying a set of vectors with a matrix.This operation is a key component of machine learning and several other data-intensive applications.For this scenario, coding theoretical solutions have been proposed for both the straggler and data shuffling problem by Lee et al. and Li et al. respectively.Furthermore, Li et al. recently unified these ideas in a common framework and showed a fundamental tradeoff between computational delay and communication load.This coding framework is based on maximum distance separable (MDS) codes of code length proportional to the number of rows of the matrix, which can be very large.We propose a block-diagonal coding scheme consisting of partitioning the matrix into submatrices and encoding each submatrix using a shorter MDS code.We show that the assignment of coded matrix rows to servers to minimize the communication load can be formulated as an integer program with a nonlinear cost function, and propose an algorithm to solve it.We further prove that, up to a level of partitioning, the proposed scheme does not incur any loss in terms of computational delay (as defined by Li et al.) and communication load compared to the scheme by Li et al..We also show numerically that, when the decoding time is also taken into account, the proposed scheme significantly lowers the overall computational delay with respect to the scheme by Li et al..For heavy partitioning, this is achieved at the expense of a slight increase in the communication load.