Abstract
Standard Federated Learning (FL) frameworks rely on the assumption of an honest majority to ensure model convergence and security. However, in the presence of large-scale Byzantine attacks, such as Sybil attacks, malicious participants can easily constitute a majority, causing traditional robust aggregators to fail. We present LiD-FL, a novel framework that leverages list-decoding techniques to maintain a set of candidate models. By incorporating a client-side voting mechanism, LiD-FL guarantees that at least one candidate model remains uncorrupted and continues to converge, even when up to 80% of the network is malicious. Our evaluations on FEMNIST and CIFAR-10 datasets demonstrate that LiD-FL maintains high accuracy in scenarios where conventional methods collapse.
Introduction
Federated Learning (FL) enables multiple clients to collaboratively train a model without sharing raw data. A critical challenge in FL is its vulnerability to Byzantine attacks, where malicious clients send poisoned updates to the server. While robust aggregators like Coordinate-wise Median or Trimmed Mean can mitigate these attacks, they typically have a "breaking point" at 50% malice. If attackers control the majority, they can steer the global model toward failure or install backdoors.
LiD-FL addresses this "malicious majority" problem without requiring the server to hold a verified dataset. By shifting from a single-model aggregation approach to a list-decoding selection strategy, LiD-FL breaks the 50% honest majority barrier.
Methods: List-Decodable Federated Learning
The core of LiD-FL is inspired by list-decoding from coding theory. When noise levels are too high to identify a single correct message, the system produces a list of possibilities guaranteed to contain the correct one.
The LiD-FL Workflow
- List Maintenance: The server maintains a list of $q$ candidate models.
- Random Sampling and Local Updates: In each round, the server samples a model and a client. The client performs local training and returns an update.
- List Expansion: The server applies the update to create a new candidate model, adding it to the list.
- Local Voting and Pruning: The server broadcasts the candidate list to all clients. Honest clients evaluate the models on local validation data and vote for the most accurate one. The server then prunes the list to maintain a constant size $q$ by discarding models with the fewest votes.
Theoretically, if the list size $q \ge \lfloor 1/\gamma \rfloor$ (where $\gamma$ is the fraction of honest clients), at least one model is highly likely to remain on the optimal trajectory.
Experimental Results
We evaluated LiD-FL against standard baselines (FedAvg, CWM, GM, Norm) using FEMNIST and CIFAR-10 datasets under various attack scenarios, including Label Flipping (LF), Little Is Enough (LIE), and Omniscient (OMN) attacks.
Resilience to Malicious Majorities
In settings with 60% malicious clients, traditional methods failed completely. For instance, on the FEMNIST Logistic Regression (LR) task, baselines dropped to approximately 2% accuracy. In contrast, LiD-FL maintained a stable accuracy of approximately 56%.
On more complex CNN models, LiD-FL achieved 72% accuracy under 60% malice, whereas baselines remained below 6%. The framework also demonstrated robustness against "voting attacks," where malicious clients attempted to subvert the pruning process by voting for poor-performing models.
Conclusion
LiD-FL provides a robust alternative for Federated Learning in adversarial environments where honest participants are in the minority. By maintaining a list of candidate models and leveraging minority-consistent voting, it overcomes the fundamental limits of traditional aggregation. Future work will focus on reducing communication overhead associated with list broadcasting and extending the framework to handle highly non-IID data distributions.
Summary updated