DRACO Byzantine-Resilient Distributed Training via Redundant Gradients

Theorem 1 and Corollary 6 prove that any gradient allocation, encoding, and decoding mechanism (A, E, D) that exactly recovers the true gradient sum D(Z^{A,E,G} + N) = G * 1_P against any s worst-case Byzantine compute nodes must replicate every data sample at least 2s + 1 times (||A_{.,i}||_0 >= 2s + 1), requiring redundancy ratio r = (1/P)||A||_0 >= 2s + 1 and s <= (P - 1)/2.

DRACO achieves the optimal r = 2s + 1 redundancy bound with O((2s+1)d) per-node encoding and O(P d) server decoding via two schemes: (1) the Fractional Repetition Code (A^Rep, E^Rep, D^Rep), which partitions P nodes into P/r groups of size r = 2s + 1 and sums the P/r groupwise Boyer-Moore streaming majority votes (Theorem 2, Algorithm 2); and (2) the Cyclic Code (A^Cyc, E^Cyc, D^Cyc), which encodes via W = [Q 1_P] C_L using the first P - 2s rows of the P x P IDFT matrix C, locates the adversarial index set V = phi(R^Cyc) with probability 1 by solving an s x s Toeplitz error-locator system from the syndrome projection f R^Cyc C_R^dagger = f N C_R^dagger (Lemma 4), and recovers u^Cyc = R_{.,U} b = G * 1_P (Lemma 3, Theorem 5).

Because DRACO guarantees exact recovery of the adversary-free gradient sum, its computational redundancy r = 2s + 1 grows linearly with the number of Byzantine nodes s and requires the parameter server to redundantly allocate overlapping data batches across compute nodes.