AEGIS: A Byzantine-Resilient Federated Learning Protocol for Highly Non-IID Environments

Federated Learning (FL) is vulnerable to Byzantine attacks, where compromised clients submit poisoned updates to degrade the global model. Existing robust aggregators force a harsh trade-off: distance-based methods incur an O(k2d) bottleneck and penalize honest statistical drift, while efficient O(kd) coordinate-wise median filters remain blind to directional poisoning. We introduce Aegis, an O(kd) aggregation protocol for high data-skew environments that replaces distance-based filtering with a two-pass dual-metric anomaly detector using adaptive Median Absolute Deviation (MAD) thresholding and cross-round reputation tracking. On CIFAR-10 under a 30% Byzantine threat, Aegis holds accuracy within 10% of the clean baseline across Sign-Flipping, Label-Flipping, and Volume Spam while preserving linear scalability. We also document where statistical filtering breaks down: variance-envelope attacks (ALIE) collapse the protocol to chance-level accuracy, while Sybil collusion degrades it progressively, failing only once cloned identities grow numerous enough to capture the median majority