Source-linked AI summary
SAFA: a Semi-Asynchronous Protocol for Fast Federated Learning with Low Overhead
Wentai Wu, Ligang He, Weiwei Lin, Rui Mao, Carsten Maple, Stephen Jarvis
TL;DR
Federated learning must remain efficient despite unreliable end devices and non-negligible device-server communication costs. SAFA addresses this with semi-asynchronous model distribution, client selection, and aggregation designs, and experiments report faster rounds, less wasted local work, and improved global-model accuracy at acceptable communication cost.
Problem
FL must handle unreliable end devices and costly communication while maintaining efficient training and convergence.
Method
SAFA is a semi-asynchronous FL protocol using lag-tolerant model distribution, post-training client selection, and cache-based discriminative aggregation.
Results
Across regression and classification tasks, SAFA improves global-model accuracy and convergence, shortens rounds, and reduces wasted straggler progress at relatively low communication cost.
Takeaways & Limitations
SAFA effectively improves round efficiency, global-model quality, and local resource use for FL with unreliable clients.
Takeaways & Limitations
The benefit of involving more clients can be limited, while larger client fractions can be impractical because communication is expensive.
Abstract
from arXiv · showhide
Federated learning (FL) has attracted increasing attention as a promising approach to driving a vast number of end devices with artificial intelligence. However, it is very challenging to guarantee the efficiency of FL considering the unreliable nature of end devices while the cost of device-server communication cannot be neglected. In this paper, we propose SAFA, a semi-asynchronous FL protocol, to address the problems in federated learning such as low round efficiency and poor convergence rate in extreme conditions (e.g., clients dropping offline frequently). We introduce novel designs in the steps of model distribution, client selection and global aggregation to mitigate the impacts of stragglers, crashes and model staleness in order to boost efficiency and improve the quality of the global model. We have conducted extensive experiments with typical machine learning tasks. The results demonstrate that the proposed protocol is effective in terms of shortening federated round duration, reducing local resource wastage, and improving the accuracy of the global model at an acceptable communication cost.
I. INTRODUCTION
Federated learning avoids moving data from end devices but must operate despite unreliable clients, heterogeneous data, and costly communication. SAFA addresses these constraints with semi-asynchronous training designed to improve efficiency, convergence, and use of stragglers’ progress.
- End-device data is difficult to centralize because collection creates privacy and data-leakage risks.
- Unreliable devices and connections can drop offline intermittently, while cellular data transfer can make communication prohibitive.
- Synchronous FL can leave capable clients idle and waste unfinished local progress when selected clients must overwrite their models.
- SAFA combines semi-asynchronous training, a refined pace-steering mechanism, and cache-based aggregation to mitigate stragglers and stale models.
- The protocol introduces lag tolerance as a hyper-parameter and evaluates accuracy, round efficiency, and communication cost across multiple FL settings.
III. THE SAFA PROTOCOL
SAFA organizes federated training around lag-tolerant model distribution, post-training client selection, and discriminative aggregation. Clients are classified by model freshness, while selected and unselected updates are handled differently to preserve useful progress and control synchronization.
- III. THE SAFA PROTOCOL: SAFA defines three operations: lag-tolerant model distribution, post-training client selection, and discriminative aggregation.
- Lag-tolerant Model Distribution: The protocol classifies clients as up-to-date, deprecated, or tolerable according to the freshness of their local model versions.
- Lag-tolerant Model Distribution: Only up-to-date and deprecated clients synchronize with the server, while tolerable clients continue asynchronously within the allowed lag.
- Client Selection: After local training, SAFA labels clients picked, undrafted, or crashed; undrafted updates are cached for possible use in future aggregation.
- Client Selection: Each round produces a new global model, and cached undrafted updates can enter later aggregation through the bypass structure.
- Lag-tolerant Model Distribution: Lag tolerance controls the tradeoff between communication overhead and convergence rate by determining when clients must adopt the latest global model.
B. Client Selection
SAFA replaces fixed pre-training client selection with post-training selection that uses arrived updates, prioritizes underused clients, and improves effective update utilization despite crashes.
- SAFA stops selecting once the quota is met, but otherwise accepts additional updates until the round deadline and uses them to fill the quota.Arrivals from previously undrafted clients are ordered by arrival time when needed.
- SAFA defines Effective Update Ratio (EUR) as the fraction of local-client updates effectively reaching the cloud.EUR differs from the selection fraction because selected clients may crash or fail to upload their models.
- The server accepts updates until a C-fraction is available, rather than waiting for randomly designated clients selected before training.This selection-after-training scheme decouples aggregation from initially selected clients.
- SAFA’s EUR improves by involving committed clients, although extremely high crash ratios still constrain it.The theoretical upper bound is the fraction of clients with successfully committed updates.
- The CFCFM policy prioritizes clients that were less involved in previous rounds to reduce participation bias.The server maintains participation information and gives higher priority to less-involved clients.
C. Discriminative Aggregation
SAFA uses a three-step discriminative aggregation procedure with a cloud cache, distinguishing picked, undrafted, and crashed clients to preserve useful progress and limit staleness.
- Three-step discriminative aggregation updates the cache, aggregates cached updates, then stores undrafted updates for a later round.Picked and undrafted updates are deliberately treated differently during aggregation.
- Picked clients’ updates remain cached after being merged into the global model, while undrafted updates are carried into the next round.The cache enables updates that are not used immediately to remain available for subsequent aggregation.
- Crashed clients’ cache entries remain unchanged unless deprecated, in which case they are replaced with the previous global model to avoid heavy staleness.The cache distinguishes picked, undrafted, and crashed client sets in each round.
- The server distributes a lag-tolerant global model, collects local models, applies CFCFM selection, updates the cache, and aggregates each round.The workflow is coordinated by the server while clients train on their local datasets.
D. Analysis of Lag tolerance
Lag tolerance trades communication overhead against model-version variance and loss: small tolerances improve loss but force more synchronization, while moderate tolerance offers a practical balance.
- Large lag tolerance can increase version variance, degrading global-model quality.The study links high tolerance with greater variance among local-model versions and slower convergence.
- The experiments vary τ from 1 to 10 on a Boston Housing regression task over a maximum of 100 global rounds.They report best loss together with EUR, synchronization ratio, and version variance.
- Small lag-tolerance values achieve better global-model loss but incur relatively high synchronization-ratio overhead.Values such as τ = 1, 2, or 3 force more clients to synchronize because stragglers and stale models are tolerated less.
- EUR remains broadly level as lag tolerance changes and depends mainly on client fraction C and crash probability cr.At cr = 0.3, EUR is slightly above C because undrafted clients contribute; at cr = 0.7, it is limited by successfully committed updates.
- The authors suggest setting lag tolerance to 5 rounds as a general compromise between loss control and communication cost.This recommendation follows their observation that moderate tolerance avoids high synchronization overhead while restraining loss.
E. Bias Analysis
SAFA’s client-selection bias depends on both crash rates and client performance, unlike FedAvg’s crash-rate-only bias, with behavior varying across three selection regimes.
- FedAvg bias depends only on client crash rates because selected clients are chosen before training and the server waits for them.A selected client’s update is aggregated unless that client crashes.
- SAFA bias also depends on client performance because faster clients finish earlier and have higher chances of being selected from committed updates.Selection occurs after training, so completion speed affects participation probability.
- SAFA analyzes three cases based on C and crash ratio R: insufficient committed clients, an intermediate regime, and quota fulfillment from prioritized clients.The cases are defined by C ≥ 1 − R, (1 − C)(1 − R) ≤ C < 1 − R, and C < (1 − C)(1 − R).
- In the intermediate case, prioritizing previously undrafted or crashed clients can reduce the slowest client’s bias below FedAvg’s level.The analysis identifies client B as the slowest client in the extreme comparison.
- The client-selection bias in all analyzed cases converges after a few federated rounds.Figure 5 visualizes the bias trajectories for FedAvg and SAFA across the three cases.
A. Experiment Setup
The experiments evaluate SAFA against FedAvg, FedCS, and fully local training across three tasks and varied federated-learning settings. They measure global-model accuracy, round efficiency, communication overhead, and local resource utilization under simulated client heterogeneity and crashes.
- Tasks: Experiments cover regression, CNN digit classification, and network-intrusion classification tasks using Boston Housing, MNIST, and KDD Cup’99 data.Task 1 uses regression, Task 2 uses a lightweight CNN, and Task 3 uses SVM classification.
- Environment: Client unreliability is simulated by assigning every client the same independent crash probability in each federated round.The crash probability is denoted cr, with ρk = cr for all clients.
- Environment: Data imbalance and device heterogeneity are modeled with Gaussian local-data sizes and exponentially distributed client processing performance.Local partition sizes follow N(µ, 0.3µ), while client performance follows an exponential distribution with λ = 1.0.
- Evaluation: SAFA is compared with FedAvg, FedCS, and fully local training using accuracy, round duration, communication overhead, and local resource metrics.The evaluation examines both model quality and holistic efficiency across multiple FL settings.
- Metrics: Round length includes local training and communication overheads, with distribution time determined by model copies and server bandwidth.The setup assumes parallel server-side distribution, a 10Gbps server bandwidth, a 10MB model, and 1.40Mbps per-client bandwidth.
- Task 1: Regression: On Task 1, SAFA improves convergence and best global-model accuracy under unstable conditions, while halving FedAvg round time when C = 0.1.The accuracy and convergence gains are especially reported for cr ≥0.5; task-1 distribution overhead differs little because few devices participate.
Task 2: CNN
Task 2 evaluates the protocols on MNIST using a lightweight CNN distributed across 100 clients. SAFA maintains comparable final accuracy while substantially improving round efficiency, with distribution overhead remaining acceptable relative to long rounds.
- Task 2: CNN: The MNIST experiment distributes randomly partitioned data and randomly initialized CNN models across 100 clients.The CNN is tested with fully local training, FedAvg, FedCS, and SAFA under varied federated-learning settings.
- Accuracy: 96.0% ∼ 98.0% accuracy is achieved by FedAvg, FedCS, and SAFA, compared with around 90% for fully local training.These values are reported for the converged CNN classification task.
- Round efficiency: 27× and 6× speed-ups over FedAvg and FedCS are achieved by SAFA when clients frequently drop out and C = 0.1 or 0.3.The advantage is reported for round efficiency in unreliable environments with small participating fractions.
- Communication overhead: SAFA’s model-distribution overhead remains low when cr ≥0.5 but is slightly higher when cr < 0.5 because it incorporates more updates.The additional cost is described as tens of seconds and remains acceptable against rounds lasting thousands of seconds.
Task 3: SVM
On Task 3, SAFA produced highly accurate global models while substantially shortening federated rounds and preserving straggler progress in unreliable settings. Its efficiency advantage came with higher model-distribution overhead in some cases and diminished as more clients participated.
- Over 99% classification accuracy was achieved by FedAvg, FedCS, and SAFA after convergence.
- SAFA could incur higher model-distribution overhead because its synchronization ratio was larger in some cases.
- 7.7× and 3.7× shorter average rounds were achieved by SAFA than FedAvg and FedCS, respectively.The comparison is reported for Task 3 under unreliable-client settings.
- Below 4% futility meant SAFA retained most local training progress from stragglers for final-model convergence.
- SAFA's efficiency advantage decreased as more clients engaged in training, although it remained the most efficient protocol.
- The experiments across regression and classification tasks showed faster convergence, higher accuracy, shorter rounds, and greater utilization of straggler progress.
APPENDIX A DEDUCTION OF P (r)(A) AND P (r)(B)
The appendix derives probabilities for clients A and B entering the cache directly or through the bypass structure across several cases. These case distinctions are combined to obtain the expressions used in Section III-E.
- P_D^(r)(A) and P_D^(r)(B) are decomposed into sums of two probabilities.
- For client A, direct cache insertion depends on whether local training finishes without a crash and, in one case, on prior-round status and selection.
- Client A's bypass entry takes effect only when the server ignores A in both rounds while A completed local training in the previous round.
- For client B, a bypass entry can take effect when B crashes in the current round after being undrafted in the previous round.
- The case analyses and recurrence relations are resolved into expressions in r and combined to derive Eqs. (13) and (14) in Section III-E.
APPENDIX B SUPPLEMENTARY RESULTS OF EXPERIMENT
Appendix B provides supplementary tables covering accuracy, synchronization, futility, round length, and model-distribution overhead across the evaluated tasks.
- Task 1: Tables X and XI report Task 1 global-model accuracy, synchronization ratio, and futility percentage.
- Task 2: Tables XII and XIII report Task 2 global-model accuracy, synchronization ratio, and futility percentage.
- Task 3: Tables XIV and XV report Task 3 global-model accuracy, synchronization ratio, and futility percentage.