Krum

Krum operates on a simple geometric intuition: a benign gradient update will be close to many other benign updates, while a malicious one will be an outlier. The algorithm computes the sum of squared Euclidean distances from each local update to its n - f - 2 closest neighbors, where n is the total number of nodes and f is the maximum number of tolerated Byzantine nodes. The update with the smallest cumulative distance score is selected as the global model update for that round, effectively ignoring poisoned or erratic vectors.

Krum provides a formal resilience guarantee against Byzantine failures in synchronous distributed systems. The algorithm is proven to converge under the assumption that the number of malicious nodes f satisfies 2f + 2 < n. This means Krum can tolerate up to (n-3)/2 adversarial nodes. Unlike median-based aggregation, Krum's selection of a single, complete update vector prevents an attacker from shifting the aggregate even slightly by injecting a carefully crafted malicious gradient.

The time complexity of Krum is O(n² * d), where n is the number of workers and d is the dimensionality of the gradient vector. This quadratic scaling with the number of nodes arises from the need to compute pairwise distances between all submitted updates. While this is computationally heavier than simple averaging, it is a necessary trade-off for the strong Byzantine resilience. For very large d, the distance computation dominates, making Krum most practical in cross-silo settings with a moderate number of high-value nodes.

A key limitation of the original Krum is that it discards all but one update, wasting the computational work of benign nodes. Multi-Krum addresses this by iteratively applying the Krum selection rule. After the first vector is selected, it is removed from the candidate pool, and the process repeats to select m vectors. The final global update is the arithmetic mean of these m selected vectors. This variant improves statistical efficiency and convergence speed while retaining strong Byzantine resilience.

Krum's Euclidean distance metric becomes less discriminative in high-dimensional spaces, a phenomenon known as the curse of dimensionality. In very deep neural networks with millions of parameters, the distance between any two gradient vectors can become nearly uniform, making it harder to distinguish outliers. Furthermore, a sophisticated adversary can craft omniscient attacks that generate a malicious gradient appearing closer to the benign cluster than some legitimate updates, potentially subverting the selection process in extreme high-dimensional regimes.

Krum is particularly suited for cross-silo federated learning scenarios with a small, known number of institutional participants (e.g., hospitals or banks) where the trust model is adversarial. In these settings, the O(n² * d) complexity is manageable, and the strong Byzantine guarantee is critical. It is less suited for cross-device settings with thousands of mobile devices due to the quadratic scaling and the assumption that the server can identify and enumerate all potential nodes to compute the n - f - 2 neighborhood size.

Non-Independently and Identically Distributed data is a fundamental challenge in federated learning that complicates Byzantine detection. When local datasets are statistically heterogeneous, honest client updates naturally diverge from each other. This increases the variance of benign gradients, making it harder for distance-based rules like Krum to distinguish between a malicious outlier and a client with genuinely unique local data, potentially leading to false positives.