Byzantine Resilience

The foundational property enabling a distributed system to reach consensus despite the presence of Byzantine nodes—clients that may send arbitrary, conflicting, or malicious updates. In federated learning, BFT aggregation rules ensure that a minority of adversarial participants cannot derail global model convergence. The system must tolerate faults that include omission failures, crash faults, and arbitrary deviations from the prescribed algorithm.

The ability of an aggregation rule to produce a correct global update that is close to the true mean of honest client updates, even when contaminated by outliers. Robust estimators achieve this through techniques like:

• Dimensionality reduction before aggregation
• Median-based operations instead of weighted averaging
• Iterative filtering to exclude suspicious updates This property is measured by the breakdown point—the fraction of Byzantine inputs an estimator can tolerate before producing arbitrarily erroneous results.

A mathematical constraint ensuring that small changes in honest client inputs produce bounded changes in the aggregated output. This property prevents Byzantine nodes from exploiting discontinuities to amplify the impact of poisoned updates. In practice, Lipschitz-bounded aggregation rules like Krum and Trimmed Mean guarantee that the gradient update remains stable and predictable, which is essential for convergence guarantees in non-convex optimization landscapes.

A detection mechanism that identifies malicious updates by measuring the cosine similarity between each client's gradient vector and the median or principal direction of all updates. Byzantine gradients often exhibit high angular deviation from the honest majority. Aggregation rules like Multi-Krum and Bulyan exploit this property by selecting updates that cluster tightly in vector space, effectively isolating adversaries that submit random or inverse gradients.

The practical requirement that Byzantine-resilient aggregation must operate with low overhead relative to standard Federated Averaging. High-dimensional models with millions of parameters demand algorithms that avoid pairwise distance computations between all client updates. Techniques like sign-based aggregation and coordinate-wise median achieve sub-linear complexity while maintaining robustness. This property is critical for cross-device federated learning where the central server must process updates from thousands of edge clients.

The formal property that a Byzantine-resilient aggregation rule will drive the global model to a stationary point of the loss function, even under attack. This requires the aggregation output to be an unbiased estimator of the true gradient direction with bounded variance. Frameworks like Byzantine SGD provide theoretical proofs that convergence rates degrade gracefully—typically by a factor proportional to the fraction of Byzantine nodes—rather than diverging entirely.