Decode-and-Compare: An Efficient Verification Scheme for Coded Distributed Edge Computing

Recently, edge computing has demonstrated increasing potential to provide low-latency computing services. Coded edge computing can not only make full use of the resources of heterogeneous edge computing servers, but also significantly reduce the negative effects of slow computing devices on computing time. Nevertheless, since edge servers may be unreliable or untrustworthy, the user will decode and get incorrect computation results even if it uses one incorrect sub-computation result returned by faulty edge servers. In this article, for the existing coded edge computing schemes, we focus on the distributed matrix-matrix multiplication and design a general and efficient Decode-and-Compare Verification (DCV) scheme to verify the correctness of computation results and identify faulty edge servers by utilizing the properties of coded computing itself. The DCV scheme contains two components: (1) computation result verification, i.e., obtain the computation result and verify its correctness, and (2) faulty edge server identification, i.e., identify the faulty edge servers by verifying the correctness of returned sub-computation results. For both the independent and collusion faulty edge server models, we conduct solid theoretical analyses on the required decoding rounds, the coding redundancy and the successful verification probability to demonstrate that the correct computation result can be efficiently verified. We also conduct a lot of experiments on the DCV scheme from different aspects and the results show that it achieves much less computation time to get the correct computation result compared with other potential schemes, including homomorphic encryption and local computation.

Automated summary

This article discusses the potential, issues, and solutions of coded edge computing. By designing a general and efficient Decode-and-Compare Verification (DCV) scheme, computation results can be verified for correctness and faulty edge servers can be identified. Experimental results show that the DCV scheme outperforms other potential schemes in terms of computation time and accuracy.