FVCC: Enabling Fast and Verifiable Coded Computation for Robust Distributed Learning

Abstract

Distributed Learning (DL) is a fundamental paradigm for large-scale model training in mobile and edge computing. However, its practical adoption is often plagued by performance degradation due to straggler and Byzantine nodes, compromising overall robustness and efficiency. Although coded computing provides theoretical solutions to these challenges, existing implementations are constrained by two critical limitations: inefficient decoding and expensive verification. To address these two issues, we propose FVCC, a fast and verifiable coded computation framework that enables robust DL. Specifically, we employ two-dimensional Shift-and-Add (SA) encoding and ZigZag Decoding (ZD) strategies for large-scale matrix-matrix multiplications prevalent in DL. To improve decoding efficiency, we propose a bidirectional two-dimensional ZD (4D-ZD) algorithm that enables parallel processing, significantly reducing recovery latency. Moreover, we introduce a lightweight verification mechanism based on Freivalds’ algorithm to defend against Byzantine attacks with low overhead. Finally, we conduct a comprehensive theoretical analysis and experimental evaluation. Empirical results demonstrate that 4D-ZD achieves approximately $2\times $ faster decoding compared to the state-of-the-art scheme. Moreover, FVCC maintains model accuracy while reducing the training time by approximately 38.55% for small-scale and 42.87% for large-scale DL tasks compared to state-of-the-art baselines.