In distributed matrix multiplication, stragglers present a significant challenge. Coding techniques are often employed to mitigate this issue; however, their effectiveness is typically limited to handling a fixed number of stragglers. To address the issue of a fluctuating number of stragglers, we propose a novel approach that leverages a variant of Luby transform (LT) codes for distributed matrix multiplication, augmented with a feedback mechanism. This enables the system to tolerate a variable number of stragglers, potentially reducing the redundant computation to complete the task compared with existing coding methods dealing with a fixed number of strangers. Furthermore, we comprehensively analyze the computational complexity associated with the proposed algorithm.

Matrix factorization is an important representation learning algorithm, e.g., recommender systems, where a large matrix can be factorized into the product of two low dimensional matrices termed as latent representations. This paper investigates the problem of matrix factorization in distributed computing systems with stragglers, those computing nodes that are slow to return computation results. A computation procedure, called coded Alternative Least Square (ALS), is proposed for mitigating the effect of stragglers in such systems. The coded ALS algorithm iteratively computes two low dimensional latent matrices by solving various linear equations, with the Entangled Polynomial Code (EPC) as a building block. We theoretically characterize the maximum number of stragglers that the algorithm can tolerate (or the recovery threshold) in relation to the redundancy of coding (or the code rate). In addition, we theoretically show the computation complexity for the coded ALS algorithm and conduct numerical experiments to validate our design.