New coding scheme for straggler mitigation in distributed matrix-vector multiplication

Coded distributed computing (CDC) has been recognized as a classic method to mitigate stragglers via erasure codes. Nevertheless, previous studies ignored the work completed by stragglers and incurred additional coding overheads. Thus, two coded computation methods based on hierarchical bundle matrix codes (HBMC) were proposed, fixed-rate hierarchical bundle coded distributed computing (F-HB) and rateless hierarchical bundle coded distributed computing (R-HB). F-HB was designed to solve the straggler problem and reduce coding latency. Based on this, R-HB further exploited the work completed by stragglers. The effectiveness of the proposed schemes was verified through theoretical analysis and experimental simulation. Numerical results show that F-HB and R-HB reduce task time by approximately 68% and 74% respectively, compared to uncoded distributed computing (UDC) methods. F-HB and R-HB based on HBMC reduce the task time of distributed matrix-vector multiplication computing systems significantly by lowering the latency of coding and exploiting the work completed by stragglers. The proposed schemes provide an efficient and feasible new approach to solving the straggler problem in distributed computing systems.