Byzantine Fault Tolerance (BFT) Aggregation

Defines the maximum proportion of malicious nodes a system can tolerate before the global model is compromised. BFT algorithms are characterized by their theoretical breakpoint ratio (f/n) .

• Optimal bounds: Deterministic algorithms typically tolerate up to f < n/3 Byzantine nodes.
• Stochastic bounds: Randomized algorithms can sometimes push this tolerance higher.
• Krum guarantees convergence if the number of Byzantine workers is less than half the number of selected neighbors minus one.

The ability to defend against attackers who manipulate specific high-magnitude coordinates of a gradient vector. A single corrupted dimension can poison the entire update.

• Coordinate-wise defenses: Trimmed Mean and Median aggregation operate independently on each parameter dimension to isolate corrupted coordinates.
• Vector-wise defenses: Krum and Multi-Krum evaluate the entire update vector, selecting the most centrally located gradient based on Euclidean distance.

The additional server-side computation required to filter malicious updates, which can become a bottleneck in high-dimensional deep learning models.

• Distance matrix computation: Algorithms like Krum require O(n²d) operations to compute pairwise distances between all n updates of dimension d.
• Sorting overhead: Trimmed Mean requires sorting each coordinate across all clients, scaling as O(d * n log n).
• Trade-off: Simpler statistical methods offer speed but less robustness against sophisticated attacks.

The formal nature of the safety proof underpinning the aggregation rule, which dictates deployment confidence in life-critical medical applications.

• Worst-case robustness: Krum and Multi-Krum provide deterministic convergence proofs under the assumption of f malicious nodes, offering absolute guarantees.
• Statistical robustness: Methods like Robust Federated Averaging (RFA) use geometric medians to provide high-probability guarantees that are resilient to outliers but not fully Byzantine adversaries.
• Medical context: Worst-case guarantees are preferred for diagnostic model training where patient safety is paramount.

BFT aggregation rules are often designed to counter specific adversarial strategies. Understanding the threat model is critical for selecting the correct defense.

• Gaussian noise attacks: Random perturbations designed to degrade convergence; countered by simple averaging or median-based methods.
• Sign-flipping attacks: Malicious gradients are the exact negative of the true gradient; countered by Trimmed Mean or Multi-Krum.
• A Little Is Enough attack: Subtle perturbations designed to stay within the variance of honest updates; requires sophisticated distance-based defenses like Krum.

The degree to which the robust aggregation rule slows down the asymptotic convergence speed compared to standard Federated Averaging in a non-adversarial setting.

• Statistical efficiency: Median and Trimmed Mean can suffer from reduced statistical efficiency, requiring more communication rounds to reach the same accuracy.
• Adaptive switching: Advanced systems use a validation-loss-based trigger to switch from standard FedAvg to a BFT rule only when an attack is detected.
• Momentum integration: Modern BFT optimizers integrate momentum buffers on the server side to recover convergence speed lost due to aggressive filtering.

A foundational Byzantine-resilient aggregation rule that selects a single local update vector with the minimal sum of squared Euclidean distances to its closest neighbors. Krum operates on the principle that honest gradients cluster together in vector space, while malicious updates appear as outliers. The algorithm computes pairwise distances between all submitted updates, sums the distances to the n - b - 2 nearest neighbors for each vector, and selects the update with the smallest cumulative distance as the global model. This effectively filters out arbitrary adversarial perturbations without requiring prior knowledge of attack strategies.

• Complexity: O(n²) distance computations per round
• Assumption: Requires 2b + 2 < n, where b is the maximum number of Byzantine nodes
• Limitation: Discards information from all but one client, reducing statistical efficiency

A robust aggregation technique that operates independently on each model parameter coordinate. For each weight dimension, the server sorts the values submitted by all clients, discards the b largest and b smallest values, and computes the arithmetic mean of the remaining entries. This coordinate-wise approach assumes that Byzantine attacks manifest as extreme outliers in specific parameter dimensions. Trimmed Mean is computationally efficient and effective against sign-flipping attacks and additive Gaussian noise, but can be vulnerable to more sophisticated, coordinated poisoning strategies that manipulate the median.

• Strength: Simple to implement and computationally lightweight
• Weakness: Fails under the 'A Little Is Enough' attack where perturbations are small but coordinated
• Variant: Median aggregation discards all but the median value per coordinate

An extension of the Krum algorithm that selects multiple candidate updates instead of a single vector. Multi-Krum iteratively applies the Krum scoring function to select the m most centrally located updates, then averages them to produce the global model. This approach retains more statistical information from honest clients while still filtering out Byzantine outliers. The selection process uses a greedy iterative strategy: after each selection, the chosen update is removed from the candidate pool to ensure diversity among the selected representatives.

• Parameter m: Controls the trade-off between resilience and statistical efficiency
• Advantage: Reduces variance compared to single-selection Krum
• Use Case: Healthcare networks with moderate adversarial risk and sufficient honest client diversity

A two-phase Byzantine-resilient aggregation protocol that combines the strengths of iterative selection and coordinate-wise trimming. In the first phase, Bulyan applies a variant of Multi-Krum to select a subset of θ candidate updates that are likely honest. In the second phase, it performs a variant of Trimmed Mean on this pre-filtered set, discarding the extreme values per coordinate before averaging. This hybrid approach provides strong theoretical guarantees against a wide range of attacks, including the 'A Little Is Enough' perturbation strategy that defeats standalone Trimmed Mean.

• Phase 1: Selects θ = n - 2b candidates using iterative distance-based scoring
• Phase 2: Applies coordinate-wise trimming on the selected subset
• Guarantee: Resilient against up to b < n/4 Byzantine nodes with high probability

A lightweight defensive pre-processing step that constrains the L2 norm (Euclidean length) of each local model update to a predefined maximum threshold C before aggregation. If a client's update vector g has a norm exceeding C, it is scaled down to C * (g / ||g||). This prevents Byzantine nodes from submitting arbitrarily large gradient values designed to dominate the aggregation and poison the global model. While not a complete BFT solution on its own, gradient clipping is a critical first line of defense that limits the damage any single malicious update can inflict.

• Threshold Selection: Typically set based on the expected distribution of honest gradient norms
• Synergy: Often combined with Krum, Trimmed Mean, or differential privacy mechanisms
• Limitation: Does not defend against direction-based attacks within the allowed norm

A robust aggregation framework that optimizes the global model for the worst-case mixture of client data distributions, including those from potentially adversarial nodes. Unlike Krum or Trimmed Mean, which focus on filtering individual malicious updates, AFL reformulates the learning objective as a minimax optimization problem: minimize the maximum empirical risk over any mixture of client distributions. This provides performance guarantees even when Byzantine nodes collude to create a damaging data distribution mixture.

• Objective: min_w max_λ Σ λ_i * L_i(w), where λ is a probability simplex
• Guarantee: Model performance is bounded for the worst-case client mixture
• Computational Cost: Requires solving a more complex saddle-point optimization per round