Krum Algorithm

Krum operates by selecting a single client's model update as the new global model. For each client's parameter vector v_i, it calculates the sum of squared Euclidean distances to its n - f - 2 nearest neighbors, where n is the total number of clients and f is the assumed maximum number of Byzantine adversaries. The client whose vector has the smallest sum is chosen. This mechanism inherently assumes that honest updates form a cluster in parameter space, while malicious updates are outliers.

The algorithm provides a formal guarantee: if the number of malicious clients f satisfies 2f + 2 < n, Krum's output is resilient to their influence. This means the aggregated update is close to the true average of the honest clients' updates in expectation, preventing a minority of adversaries from arbitrarily distorting the global model. This Byzantine fault tolerance (BFT) property is critical for security in open participation federated systems.

• Communication: Only the selected client's full model vector is used, making the communication cost for the aggregated result equivalent to one model update.
• Computation: The server must compute pairwise Euclidean distances between all n client updates, resulting in an O(n²d) computational complexity, where d is the model dimension. This quadratic scaling can be a bottleneck for large federations.
• No Iterative Refinement: It is a single-shot selection rule, unlike iterative methods like coordinate-wise median.

• Single-Update Selection: Discards information from all non-selected honest clients, which can slow convergence and increase sample complexity.
• Sensitivity to Hyperparameter f: Performance degrades if the actual number of adversaries exceeds the assumed f.
• Non-IID Data Impact: The geometric clustering assumption of honest updates can be violated under highly heterogeneous (non-IID) client data, potentially causing Krum to select a suboptimal, but non-malicious, update.
• High-Dimensional Distance Curse: Euclidean distance measures become less reliable in very high-dimensional spaces (large d).

Krum is often extended or used as a component in more advanced defenses:

• Multi-Krum: Selects a subset of m clients with the best (smallest) scores and averages their updates, improving statistical efficiency.
• Bulyan: A meta-aggregation defense that first uses Krum (or trimmed mean) to select a candidate set of updates, then applies a coordinate-wise trimmed mean to this set to produce the final robust update. This adds a second layer of filtering.

Krum is deployed in cross-silo or open participation federated learning scenarios where the central server cannot trust all clients. It is a foundational algorithm in the Federated Learning Attack Mitigation toolkit, specifically for countering data poisoning and model update poisoning attacks. It is often compared and benchmarked against other robust aggregators like median and trimmed mean.

A class of server-side algorithms designed to produce a correct global model update even when a fraction of participating clients are malicious or faulty, sending arbitrary or adversarial updates. These algorithms do not rely on identifying the attacker but on constructing an update resilient to their influence.

• Core Principle: Tolerates a bounded fraction f of Byzantine clients.
• Mechanisms: Includes geometric methods (like Krum), coordinate-wise statistical aggregation (Median, Trimmed Mean), and meta-aggregation (Bulyan).
• Goal: Ensure convergence to a useful model despite sabotage, backdoors, or model corruption attempts.

A robust statistical aggregation rule where, for each model parameter dimension, the server discards a fraction β of the highest and lowest values from the received client updates. The mean of the remaining values is then computed to form the global update for that parameter.

• Process: Applied coordinate-wise across the update vector.
• Robustness: Effective against value-corruption attacks where malicious clients send extreme scalar values for specific parameters.
• Contrast with Krum: While Krum selects a single client's vector, Trimmed Mean aggregates a subset of values per dimension, often providing smoother convergence.

A meta-aggregation Byzantine defense that combines a robust aggregator with a second filtering step. First, it uses a base robust rule (e.g., Krum or Multi-Krum) to select a set of n - 2f candidate updates from n clients, where f is the tolerance limit. Then, it computes the coordinate-wise trimmed mean of these candidates to produce the final robust global update.

• Design: Mitigates the limitations of single-step aggregators; designed to be a strong Byzantine resilient aggregator.
• Advantage: Can defend against more sophisticated colluding attacks that might bypass Krum alone.
• Relation: Often cited alongside Krum as part of the evolution of geometric defense mechanisms.

A server-side defense technique that analyzes the statistics, distribution, or geometry of submitted client model updates (gradients) to detect anomalies indicative of malicious behavior or poor data quality. This is a broader category that includes methods like norm bounding and PCA-based outlier detection.

• Common Techniques:
  • Norm Clipping: Bounding the L2-norm of each update to limit the influence of any single client.
  • Cosine Similarity: Measuring the directional alignment of an update with a reference (e.g., the update median).
  • PCA/Clustering: Identifying updates that fall outside dense clusters in the high-dimensional gradient space.
• Role: Often used as a pre-filtering step before applying an aggregation rule like Krum.

A dynamic defense mechanism that assigns and updates a credibility score to each federated client based on the historical quality and consistency of their updates. The server uses these scores to weight client contributions during aggregation, diminishing the influence of unreliable or malicious participants over time.

• Scoring Basis: Can be based on update similarity to a robust aggregate, data quality metrics, or contribution to model improvement.
• Contrast with Krum: Krum makes a binary selection/deselection per round based on spatial proximity. Trust scoring employs a continuous, historical weighting system.
• Synergy: Trust scores can be used to pre-select clients for Krum's distance calculations, making it more efficient.

A property of a distributed system, inherited from classical distributed computing, to correctly reach consensus on a global state despite a subset of participants behaving arbitrarily or maliciously. In federated learning, the "state" is the global model parameters.

• Formal Guarantee: Provides a theoretical framework for algorithms like Krum, specifying the maximum fraction of faulty clients (f) that can be tolerated.
• Consensus vs. Aggregation: Traditional BFT (e.g., PBFT) aims for exact replica agreement. Federated BFT aims for a statistically robust aggregate of high-dimensional vectors.
• Foundation: Krum and related algorithms are Byzantine-robust aggregation rules that provide BFT for the specific consensus problem of model averaging.