Source-linked AI summary
DRACO: Byzantine-resilient Distributed Training via Redundant Gradients
Lingjiao Chen, Hongyi Wang, Zachary Charles, Dimitris Papailiopoulos
TL;DR
Adversarial nodes can corrupt distributed training, while median-based defenses may be computationally expensive and require restrictive convergence assumptions. DRACO uses coding-theoretic gradient redundancy and decoding to recover the correct update, preserving the adversary-free model and delivering substantially faster training in experiments.
Problem
Distributed training needs a scalable way to compute gradient sums robustly because adversarial nodes can corrupt updates, while median-based convergence may require assumptions such as convexity.
Method
DRACO assigns redundant gradients to compute nodes, encodes their updates, and decodes the received vectors at the parameter server to remove adversarial effects.
Results
DRACO returns the same model as adversary-free training, tolerates up to (r −1)/2 adversaries, and is orders of magnitude faster than state-of-the-art robust distributed systems.
Takeaways & Limitations
Adversary-free convergence guarantees transfer to adversarial training because DRACO preserves each model update exactly.
Takeaways & Limitations
DRACO’s exact-recovery design may tolerate fewer worst-case adversaries than median-based techniques and may impose computational redundancy.
Abstract
from arXiv · showhide
Distributed model training is vulnerable to byzantine system failures and adversarial compute nodes, i.e., nodes that use malicious updates to corrupt the global model stored at a parameter server (PS). To guarantee some form of robustness, recent work suggests using variants of the geometric median as an aggregation rule, in place of gradient averaging. Unfortunately, median-based rules can incur a prohibitive computational overhead in large-scale settings, and their convergence guarantees often require strong assumptions. In this work, we present DRACO, a scalable framework for robust distributed training that uses ideas from coding theory. In DRACO, each compute node evaluates redundant gradients that are used by the parameter server to eliminate the effects of adversarial updates. DRACO comes with problem-independent robustness guarantees, and the model that it trains is identical to the one trained in the adversary-free setup. We provide extensive experiments on real datasets and distributed setups across a variety of large-scale models, where we show that DRACO is several times, to orders of magnitude faster than median-based approaches.
1 Introduction
Distributed training is vulnerable to adversarial nodes, while median-based defenses can be costly and rely on strong assumptions. DRACO uses coding-theoretic redundancy to recover correct gradient sums efficiently and preserve adversary-free training behavior.
- A single adversarial node can introduce arbitrary bias and inaccuracies into the final distributed model.
- Median-based aggregation can tolerate adversaries but may incur prohibitive computation in large-data settings.
- DRACO uses redundant gradients, encoded updates, and parameter-server decoding to eliminate adversarial effects.
- DRACO tolerates up to (r −1)/2 worst-case adversaries with redundancy ratio r, matching an information-theoretic bound.
- DRACO uses efficient majority-vote and Fourier decoding techniques rather than median aggregation.
- Its worst-case adversary bound may be smaller than the approximately constant-fraction tolerance of median-based techniques, although it is faster when only a constant number of nodes are malicious.
- DRACO is up to orders of magnitude faster than geometric-median approaches and always converges to the correct adversary-free model in the reported experiments.
2 Preliminaries
Distributed mini-batch SGD partitions gradient computation across nodes and aggregates their sums at a parameter server. DRACO formulates robust computation of the batch gradient sum under adversaries and applies broadly to first-order distributed algorithms.
- Empirical risk minimization trains a model w by minimizing loss over data points x_i.
- Mini-batch SGD updates the model using gradients from a randomly selected subset of data.
- Distributed mini-batch SGD partitions assigned gradients across compute nodes, whose sums are aggregated by the parameter server.
- DRACO addresses computing the batch gradient sum in a distributed, adversary-resistant manner.
- The framework applies to first-order methods including gradient descent, SVRG, coordinate descent, and projected or accelerated variants.
- The adversarial model allows s nodes to send arbitrary updates instead of their prescribed gradients.
3 DRACO: Robust Distributed Training via Algorithmic Redundancy
DRACO defines robust distributed training through gradient allocation, redundant local encoding, and parameter-server decoding that recovers the true gradient sum despite adversarial nodes. Its coding schemes achieve information-theoretic redundancy and linear-time processing while preserving adversary-free updates.
- DRACO framework: DRACO assigns gradients through A, locally encodes each node’s assigned gradients through E, and decodes received vectors through D at the parameter server.The received matrix is modeled as R = ZA,E,G + N, and the decoder produces the update gradient vector u = D(R).
- Robustness guarantee: The decoder must recover the true gradient sum despite any s adversarial nodes, ensuring each model update matches the adversary-free setup.This identity transfers convergence guarantees proved for adversary-free training to the adversarial setting.
- Redundancy bound: Theorem 1 requires redundancy ratio r ≥ 2s + 1, meaning each data sample must be replicated at least 2s + 1 times against s adversaries.The bound is information-theoretic and applies regardless of the encoding and decoding mechanisms.
- Optimal coding schemes: DRACO can achieve the optimal redundancy bound with O((2s + 1)d) compute-node work and O(Pd) parameter-server work.The stated decoder cost is significantly less than that of the median approach in the cited prior work.
- Repetition code: The repetition code tolerates any s adversaries when 2s + 1 divides P, using majority vote with linear-time encoding and decoding.It partitions compute nodes into r = 2s + 1 groups that compute the same gradient sum.
- Cyclic code: The cyclic code also achieves the redundancy lower bound and tolerates any s adversaries with probability 1, with linear-time encoding and decoding when d ≫ P.Its adversarial-node detection and recovery procedures are tailored to the adversarial setting.
4 Experiments
Across adversarial training experiments, DRACO converged reliably and generally faster than geometric-median training across datasets, models, and attack types. Its overhead was concentrated in redundancy-related computation, while geometric-median decoding could dominate runtime.
- End-to-end Convergence Performance: DRACO converged faster than GM under reverse-gradient attacks, with both repetition and cyclic codes reaching more than an order-of-magnitude speedup.The comparison used matched testing accuracy.
- End-to-end Convergence Performance: Under constant adversaries, GM sometimes failed to converge, whereas DRACO converged in all reported experiments.The experiments covered MNIST, CIFAR10, and MR tasks with multiple neural-network models.
- Per iteration cost: On ResNet-152, VGG-19, and AlexNet, DRACO remained several times faster than GM despite encoding and decoding costs exceeding ordinary SGD computation.These measurements used 46 AWS EC2 instances and 11.1% adversarial nodes.
- Per iteration cost: GM’s geometric-median update at the parameter server was prohibitively expensive, while DRACO’s encoding and decoding overhead was relatively negligible.The component costs were reported for ResNet-152, VGG-19, and AlexNet.
- Effects of number of adversaries: DRACO’s runtime did not increase significantly as the number of adversaries increased from 1 to 7 in the ResNet-18 experiments.The study used CIFAR10, 15 compute nodes, and a constant-adversary model.
5 Conclusion and Open Problems
DRACO provides robust distributed training through algorithmic redundancy while preserving the adversary-free model, and it is reported to be orders of magnitude faster than state-of-the-art robust systems. The authors identify approximate recovery, straggler tolerance, and more efficient coding methods as open directions.
- Conclusion: DRACO is robust to arbitrarily malicious compute nodes and achieves orders-of-magnitude speedups over state-of-the-art robust distributed systems.The framework also achieves the information-theoretic redundancy lower bound while maintaining the correct update rule.
- Conclusion: DRACO is designed to output the same model with or without adversaries.The authors contrast this exact-recovery design with the possibility that slightly inexact updates might preserve performance.
- Open Problems: Future work could seek greater straggler tolerance or lower computational cost by approximately recovering the desired gradient summation.The authors also note that more efficient encoding and decoding methods may exist.
A.1 Proof of Theorem 1
Theorem 1 establishes that exact recovery against s adversaries requires each gradient to be replicated at least 2s + 1 times, yielding a total redundancy lower bound. This also limits the number of tolerable adversaries to at most (P − 1)/2, so a majority of compute nodes must remain non-adversarial.
- Definitions: An s-attack is valid when at most s compute nodes contribute nonzero adversarial noise vectors.The proof analyzes arbitrary attacks satisfying this support-size constraint.
- Proof Strategy: The proof assumes a gradient appears on fewer than 2s + 1 nodes and constructs two gradient assignments with valid attacks that produce the same decoder input.Because unaffected encoders do not depend on the changed gradient, adversarial noise can make the received matrices indistinguishable.
- Redundancy Lower Bound: Each gradient must be replicated at least 2s + 1 times, implying total assignment sparsity ∥A∥0 ≥ (2s + 1)P.This is obtained by contradiction from the indistinguishable received inputs.
- Adversary Bound: Since 2s + 1 ≤ P, the framework can resist at most (P − 1)/2 adversaries.Equivalently, at least a majority of compute nodes must be non-adversarial.
A.2 Proof of Theorem 2
The repetition-code proof uses majority voting within each group to recover the correct gradient despite s adversaries. Its encoding and decoding costs are linear in the group size and gradient dimension.
- Correctness: Each group contains 2s + 1 compute nodes, so at least s + 1 are non-adversarial when there are at most s adversaries.Majority voting therefore returns the correct gradient for every group.
- Complexity: Each compute node processes and sums (2s + 1) d-dimensional gradients, giving complexity O((2s + 1)d).The passage likewise states linear-time decoder complexity within each group.
A.3 Proof of Lemma 3
The lemma’s proof establishes structural properties of the coding matrix using zero-pattern implications and Vandermonde-matrix rank. It then shows that sufficiently large column subsets span the all-ones vector.
- Column Span: Any column subset U with |U| ≥ P − (2s + 1) has a span containing the all-ones vector.Equivalently, there exists a vector b such that W·,U b = 1.
- Vandermonde Construction: The span result follows by selecting P − 2s columns from U, using their linear independence in the full-rank Vandermonde matrix CL, and setting remaining coefficients to zero.The proof concludes after constructing the coefficient vector and verifying the resulting product.
- Zero Pattern: A zero entry Aj,k = 0 implies the corresponding coding-matrix entry Wj,k = 0.The proof derives this implication through the relevant row-vector and coding-matrix product.
A.4 Proof of Lemma 4
The proof shows that a random projection identifies exactly the adversarial coordinates with probability 1, enabling Fourier-based recovery of the relevant support and proving Lemma 4.
- A random Gaussian projection produces a nonzero coordinate exactly when the corresponding column of N is nonzero, with probability 1.The proof uses the continuous normal distribution to show that nonzero columns do not project to zero almost surely.
- At most s adversaries imply that the projected vector γ has at most s nonzero elements.The support of γ is bounded by the number of nonzero columns in N.
- Applying the inverse transform yields t = γ, so the returned index set equals the support of N with probability 1.Thus the detection procedure identifies precisely the compute-node coordinates affected by adversarial noise.
A.5 Proof of Theorem 5
The cyclic code recovers the desired gradient despite any s adversaries with probability 1, while using redundancy at the information-theoretic lower bound and an explicit decoding procedure.
- The cyclic decoder recovers the desired gradient and resists any ≤s adversaries with probability 1.The proof combines correct identification of non-adversarial nodes with the decoding relation uCyc = G1P.
- The cyclic code uses redundancy ratio 2s + 1, which reaches the lower bound.Each compute node evaluates a linear combination requiring O((2s + 1)d) computations.
- The parameter-server decoder includes detection, solving a Toeplitz system, DFT computation, and gradient recovery.The stated detection complexity is O(dP + Ps + P log P), while finding b is given as O(P^3) and recovery as O(dP).
B Streaming Majority Vote Algorithm
The streaming majority vote algorithm processes a sequence using linear computation and returns the majority item whenever one exists.
- The algorithm maintains a candidate element and counter while scanning the input sequence.It initializes Ma to the first item and updates the counter as subsequent items are processed.
- The streaming majority vote algorithm runs in linear time in the sequence size.This avoids the quadratic scaling of a naive majority-vote implementation.
- If a majority item exists, the algorithm eventually returns that item.This property supports efficient majority decoding when repeated compute-node outputs contain a strict majority of correct values.