Bulyan

Bulyan operates in two distinct phases to filter malicious updates. First, it applies a primary robust aggregation rule (like Krum or Trimmed Mean) not once, but repeatedly to select a set of 'candidate' updates deemed trustworthy. Second, it computes a coordinate-wise trimmed mean across this filtered candidate set to produce the final global update. This layered approach provides stronger theoretical guarantees than using either stage alone.

Unlike simpler defenses, Bulyan is specifically designed to withstand adaptive Byzantine adversaries. These are attackers that can observe the aggregation mechanism and craft malicious updates designed to bypass it. By using the trimmed mean in its second stage—which is robust to arbitrary values in any single coordinate—Bulyan limits the influence an adversary can have on any individual model parameter, even if their update passes the first-stage filter.

Bulyan provides formal convergence guarantees under Byzantine faults. Research demonstrates that when the fraction of malicious clients is bounded (specifically, less than a quarter of the total clients in the original formulation), Bulyan ensures the global model converges to a point close to the optimum achievable without any attackers. This guarantee holds even when the benign clients' data is non-IID (not independently and identically distributed).

The algorithm's robustness is controlled by two key hyperparameters:

• n: The number of candidate updates selected in the first stage.
• m: The number of extreme values to trim from each side per coordinate in the second-stage trimmed mean. These parameters are set based on the estimated maximum fraction of Byzantine clients. Choosing n too small reduces the utility of the candidate set, while setting m incorrectly can either leave the system vulnerable or discard too many benign updates. Proper configuration is critical for balancing robustness and model performance.

Bulyan was proposed to address limitations of its constituent algorithms:

• Krum: Selects only one update, discarding all other information from benign clients, which is inefficient and can slow convergence.
• Trimmed Mean: Effective per-coordinate but vulnerable if adversaries concentrate their attack on a single parameter dimension. Bulyan mitigates these weaknesses: its first stage uses Krum's neighbor-scoring to filter out blatant outliers, while its second stage uses trimmed mean's coordinate-wise robustness to handle residual attacks, creating a more comprehensive defense.

The primary trade-off for Bulyan's robustness is increased computational cost on the aggregation server. The first stage requires calculating pairwise Euclidean distances between all client updates, an O(N²) operation where N is the number of clients per round. The second stage involves sorting values for each model parameter. While this overhead is manageable for moderate-sized models and client batches, it can become significant for very large models (e.g., LLMs) or massive federations, necessitating optimized implementations or approximations.

The overarching class of algorithms to which Bulyan belongs. These methods are designed to produce a correct global model update even when a fraction of participating clients are malicious or faulty, sending arbitrary or adversarial updates. The core challenge is achieving statistical resilience without assuming honest majority.

• Goal: Tolerate Byzantine failures (arbitrary behavior).
• Key Insight: Use robust statistics (e.g., median, trimmed mean) or geometric consensus (e.g., Krum) to filter outliers.
• Trade-off: Resilience often comes at the cost of statistical efficiency, especially under heavy attack.

A foundational Byzantine-robust aggregation rule that Bulyan uses in its first selection phase. Krum selects a single client's model update as the global update by choosing the one whose parameter vector is closest, in Euclidean distance, to its nearest neighbors.

• Mechanism: For each candidate update, sum the distances to its n - f - 2 nearest neighbors (where f is the max faulty clients). The update with the smallest sum is selected.
• Property: Provides theoretical guarantees against a bounded number of Byzantine clients.
• Limitation: Uses only one update per round, wasting information from other honest clients. Bulyan addresses this by using Krum to select a subset of candidates.

A robust statistical method central to Bulyan's second aggregation phase. For each model parameter (coordinate), a fixed fraction β of the highest and lowest values from the candidate updates are discarded. The mean of the remaining values is computed to form the final global update for that coordinate.

• Process: Applied coordinate-wise across the model's parameter vector.
• Robustness: Highly effective against value corruption attacks where adversaries submit updates with extreme parameter values.
• Bulyan's Use: Applies trimmed mean to the set of updates pre-filtered by Krum, creating a meta-aggregation that is resilient to both directional and magnitude-based attacks.

A simpler Byzantine-robust baseline where the server computes the coordinate-wise median of all received client updates. It is highly resilient to extreme outlier values but can have high variance.

• Comparison to Bulyan: Median is a single-step aggregation. Bulyan's two-step process (select then trim) often achieves lower variance and better convergence because it first removes likely malicious updates geometrically (via Krum) before applying a robust statistic.
• Use Case: Effective when a large proportion of clients are honest, as the median is a breakdown point statistic.

The broader defensive category against attacks where malicious clients manipulate their local training data to corrupt the global model. Bulyan is a primary defense against the model update poisoning that results from data poisoning.

• Attack Vector: Adversaries corrupt local datasets to produce malicious gradients/updates.
• Bulyan's Role: Mitigates the effect of poisoned updates by robust aggregation, acting as a server-side shield. It does not prevent local poisoning but prevents the poisoned updates from significantly altering the global model.
• Complementary Techniques: Often paired with client-side validation or trust scoring for a layered defense.

A classical distributed systems property that federated learning borrows from. A BFT system can reach correct consensus despite a subset of participants behaving arbitrarily (Byzantine).

• Relation to FL: In federated learning, "consensus" is on the global model parameters. Bulyan provides a form of BFT for this consensus problem.
• Difference: Traditional BFT (e.g., PBFT) uses cryptographic voting and replication. FL BFT (like Bulyan) uses statistical and geometric methods on high-dimensional vectors, as model updates are large and voting is impractical.
• Guarantee: Bulyan provides statistical BFT, ensuring convergence to a good model under bounded adversarial influence.