Addressing Fluctuating Stragglers in Distributed Matrix Multiplication via Fountain Codes
Siyuan Wang, Jianping Wang, Linqi Song · 2024
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.