Straggler Mitigation in Edge Computing with Coded Compressed Sensing

In edge computing the performance of distributed edge computation tasks are adversely impacted by stragglers (i.e., slowest devices). Previous research addresses this problem using coding techniques to bypass the dependence on stragglers. In stead of completely discarding partially unfinished coded computations on stragglers, recent research incorporates those computations contributed by stragglers before the deadline. A faster computation recovery is achieved. One problem with this approach, however, is the recovery accuracy because it is based on lossy quantization over coded data. In this paper, we treat the partially unfinished coded computation as erroneous computations and formulate the computation recovery problem as a compressed sensing (CS) problem. With this rateless approximate code approach, we can recover the erroneous computations with a high accuracy rate when the ratio of stragglers is relatively low. Experimental results show that we reduce the error rate by average of 32% under various straggler ratios compare with the state of the art.