Krum

Krum operates by computing a local sum of squared Euclidean distances for each client's gradient vector to its n - f - 2 closest neighbors, where n is the total number of clients and f is the maximum number of Byzantine workers. The algorithm selects the single vector with the minimum cumulative distance score as the global update. This geometric approach assumes that honest gradients cluster together in vector space, while malicious updates appear as outliers. The selection rule is deterministic and computationally efficient, requiring only pairwise distance calculations.

Krum provides a provable convergence guarantee under the assumption that the number of Byzantine workers f satisfies 2f + 2 < n. This means Krum tolerates up to (n-3)/2 malicious clients. The theoretical proof demonstrates that the selected gradient lies within a bounded distance of the true average of honest gradients, even when adversaries collude to send arbitrary vectors. This resilience holds under the standard assumption of bounded variance among honest gradients and a Lipschitz-smooth objective function, making Krum suitable for non-convex deep learning optimization.

The original Krum selects only a single vector per round, discarding information from other honest clients. Multi-Krum extends the algorithm by selecting the m vectors with the smallest distance scores and averaging them to form the global update. This variant improves statistical efficiency by incorporating more honest gradients while maintaining Byzantine resilience. The selection parameter m is typically set to n - f, ensuring that all likely-honest updates contribute. Multi-Krum achieves faster convergence in practice while preserving the same theoretical fault tolerance bounds as the single-vector version.

Krum is vulnerable to sophisticated attacks where Byzantine clients craft gradients that appear close to a targeted subset of honest vectors while pulling the selected update toward a malicious objective. The little is enough attack exploits Krum's reliance on local neighborhoods by sending gradients with amplified magnitudes in directions orthogonal to the honest variance, gradually steering convergence. Additionally, Krum's assumption of independent and identically distributed (IID) data across clients weakens in heterogeneous federated settings, where honest gradients naturally diverge, reducing the clustering assumption's validity.

Unlike coordinate-wise robust aggregators such as median or trimmed mean, Krum operates in the full vector space using Euclidean distances. This makes Krum resistant to omniscient Byzantine attacks that corrupt specific coordinates while leaving others intact. Coordinate-wise methods can be defeated by adversaries who inject large values into a minority of dimensions across many clients. Krum's vector-level selection avoids this vulnerability but at the cost of higher computational complexity: O(n²d) for pairwise distance calculations, where d is the gradient dimensionality, compared to O(nd) for coordinate-wise methods.

Krum is implemented in major federated learning frameworks and is often combined with gradient clipping and differential privacy mechanisms for defense-in-depth. In production, the n - f - 2 neighborhood size parameter must be carefully tuned: setting it too small increases sensitivity to outliers, while setting it too large risks including Byzantine vectors in the distance calculation. Krum is most effective when Byzantine clients constitute a minority of the total population and when honest data distributions are reasonably homogeneous. For highly non-IID settings, variants like Bulyan combine Krum with trimmed mean for stronger guarantees.

The distributed systems property that Krum is designed to achieve. A system is Byzantine Fault Tolerant if it can reach correct consensus despite an arbitrary subset of nodes exhibiting malicious or arbitrary failures. In the context of federated learning, a Byzantine client may send arbitrary, crafted gradient updates to corrupt the global model. Krum provides BFT by selecting a single update that is geometrically closest to a majority of its neighbors, effectively ignoring outliers that deviate from the consensus.

A complementary defense that identifies malicious clients by analyzing the diversity of their historical gradient updates. FoolsGold operates on the insight that sybil attackers—a single adversary controlling multiple fake clients—often produce highly similar, low-diversity gradient contributions. By assigning lower learning rates to clients with mutually similar update histories, FoolsGold neutralizes sybil-based poisoning. While Krum focuses on geometric consensus, FoolsGold targets the behavioral fingerprint of the attacker.

A fundamental defensive technique that caps the L2-norm of individual per-example gradients during training. By enforcing a maximum magnitude, clipping bounds the influence any single data point or client can exert on the model update. This is a prerequisite for Differential Privacy SGD (DP-SGD) and provides a lightweight first line of defense against poisoning. While Krum operates at the server-aggregation level, gradient clipping is applied locally at each client before updates are shared.

A direct extension of the original Krum algorithm that selects multiple updates instead of a single one to improve convergence speed. While Krum picks the single most central update, Multi-Krum iteratively selects the m updates closest to their neighbors and averages them. This trades a slight reduction in Byzantine resilience for significantly faster convergence, as more client information is retained in each round. The selection criterion remains the same: minimizing the sum of squared distances to the nearest n - f - 2 neighbors.