Optimal Factored LT codes for Distributed Matrix Multiplication
Lei Zhang, Jie Liu · 2023
Due to the presence of slow or failed worker computers (called stragglers), distributed matrix multiplication over large clusters may encounter delays. To tackle this issue, Factored Luby Transform (FLT) codes have been proposed for edge computing scenarios involving distributed matrix multiplication of the form C = A * B. However, the decoding time of FLT codes becomes a bottleneck in coded distributed matrix multiplication, primarily due to the high computational complexity associated with peeling decoding. To overcome this limitation, this paper introduces the modified generalized degree distribution algorithm (MGDDA) for designing an optimal degree distribution in FLT codes with BP decoding. The MGDDA algorithm minimizes overhead and maximizes performance efficiency in coded distributed matrix multiplication scenarios. Additionally, we propose an optimal encoding algorithm that achieves a balanced probability of connecting input symbols from matrices A and B to encoded symbols. This algorithm further enhances the performance of FLT codes. Simulation results consistently demonstrate that our proposed Optimal FLT (OFTL) method outperforms other existing approaches in terms of average overhead, block error rate (BER) and computational delay.