Byzantine Attack Identification in Distributed Matrix Multiplication via locally testable codes
Sangwoo Hong, Heecheol Yang, Jungwoo Lee · 2022 IEEE International Symposium on Information Theory (ISIT) · 2022
Coded computing has proved its efficiency in handling a straggler issue in distributed computing framework. However, in a coded distributed computing framework, there may exist Byzantine workers who send the wrong computation results to a master to contaminate the overall computation output. Therefore, it is essential to identify Byzantine workers from their computation results in coded computing. In this paper, we consider Byzantine attack identification problem in coded computing for distributed matrix multiplication tasks. We propose locally testable codes which facilitate the efficient Byzantine attack identification, and suggest a hierarchical group testing method for Byzantine attack identification. We show that our scheme requires smaller number of tests than the conventional group testing methods for the existing coded computing schemes.