Organizations: LAAS-SARA · EMINES, Mohammed VI Polytechnic University, Ben Guerir, Morocco · LAAS-CNRS, Université de Toulouse, CNRS, Toulouse, France · CNRS, LAAS-SARA
Synchronous federated learning scales poorly due to the straggler effect. Asynchronous algorithms increase the update throughput by processing updates upon arrival, but they introduce two fundamental challenges: gradient staleness, which degrades convergence, and bias toward faster clients under heterogeneous data distributions. Although algorithms such as AsyncSGD and Generalized AsyncSGD mitigate this bias via client-side task queues, most existing analyses neglect the underlying queueing dynamics and lack closed-form characterizations of the update throughput and gradient staleness. To close this gap, we develop a stochastic queueing-network framework for Generalized AsyncSGD that jointly models random computation times at the clients and the central server, as well as random uplink and downlink communication delays. Leveraging product-form network theory, we derive a closed-form expression for the update throughput, alongside closed-form upper bounds for both the communication round complexity and the expected wall-clock time required to reach an ε-stationary point. These results formally characterize the trade-off between gradient staleness and wall-clock convergence speed. We further extend the framework to quantify energy consumption under stochastic timing, revealing an additional trade-off between convergence speed and energy efficiency. Building on these analytical results, we propose gradient-based optimization strategies to jointly optimize routing and concurrency. Experiments on EMNIST demonstrate reductions of 29%--46% in convergence time and 36%--49% in energy consumption compared to AsyncSGD.
Figures & tables
Figure 1: Queueing model with computation times and communication delays.
Figure 2: Impact of concurrency m and routing probability p1 on E0[τϵ] . Left: Homogeneous resources. Right: Heterogeneous resources, where Client 2 is three times faster than Client 1 ( μ2s=3μ1s for s∈{c,u,d} ). Constants: Δ=L=σ=1 , M=5 , and G=14 .
Type
Description
μc
μu
μd
Count
A
Fast compute, slow network
10.0
2.0
2.5
15
B
Slow compute, fast network
0.3
9.0
10.0
15
C
Balanced
5.0
6.0
7.0
20
D
Straggler
0.15
0.1
0.12
40
E
Super Client
12.0
10.0
11.0
10
Table 1: Client clusters and service rates (Rate μ in tasks/sec).
Routing probabilities p×100
Staleness Impact Factor E0[Di(p,m)]pi−2×10−2
Type
p∗τ
p∗λ
p∗K
(p∗τ,m∗)
(p∗λ,n)
(p∗K,n)
(puni,n)
A
1.307
0.845
0.526
14.2
181.7
8.6
7.4
B
0.514
0.011
0.627
182.0
49 543.7
28.0
33.9
C
1.752
1.591
0.506
5.5
65.7
4.6
3.8
D
0.34
0.005
1.691
1 615.7
783 209.8
84.6
229.6
E
2.405
5.514
0.496
2.1
12.4
2.5
2.0
Table 2: Comparison of optimized routing probabilities and staleness impact factors across different client clusters (Types A–E).
Scenario
Time Reduction (%) vs.
Dist.
Data
Max-Throughput
Round-Optimized
AsyncSGD
Exp.
IID
67.5 (66.59)
62.59 (66.71)
46.28 (46.88)
Non-IID
79.3
57.04
35.6 (36.56)
LogN.
IID
59.08 (70.46)
64.35 (66.1)
41.77 (46.41)
Non-IID
79.17
62.44
37.0 (42.38)
Det.
IID
52.35 (64.24)
49.35 (61.38)
29.84 (38.86)
Table 3: Percentage time reduction relative to baselines for a target test accuracy of 0.6 ( 0.75 in parentheses).
Figure 3: Test set performance at the CS for the scenario in Section 5.3.1 . The top row displays test accuracy and the bottom row shows loss, both plotted against wall-clock time. Columns correspond to different service time distributions under homogeneous and heterogeneous data settings. Each subplot compares the four strategies. Simulations were repeated 10 times for 400 wall-clock time units. Solid lines indicate means; shaded areas represent standard deviations.
Coeff.
Relative Power Profile
Type
Characteristic Profile
κ
Pcomp
Pu
Pd
A
Compute-Efficient & Network-Limited
0.08
80.0
5.0
3.0
B
Compute-Constrained & Comm-Optimized
200.0
5.4
15.0
10.0
C
Balanced Speed & Power
0.25
31.3
4.0
3.0
D
Straggler & Highly Inefficient
14400.0
48.6
0.5
0.2
E
High Throughput & Power-Intensive
1.50
2592.0
50.0
40.0
Table 4: Energy coefficients and power profiles (normalized units). Computation power follows Pcomp=κ(μc)3 , where a lower κ indicates higher hardware efficiency.
Figure 4: Joint optimization analysis. Left: Time–Energy Pareto frontier annotated with ρ . Right: Evolution of optimal routing probabilities p∗ρ and optimal concurrency m∗ρ as a function of ρ , illustrating the systematic shift away from energy-inefficient Type E clients.
Figure 5: Empirical Time-Energy Pareto frontier for the KMNIST dataset, illustrating the mean clock-time versus mean energy required to reach a target test accuracy of 0.75 across 10 independent runs.
Dataset
Metric
Exponential
Lognormal
Deterministic
IID
Non-IID
IID
Non-IID
IID
Non-IID
KMNIST
Time
6.11
10.58
18.95
8.63
15.46
0.53
Energy
46.90
46.10
45.53
40.90
47.19
36.62
EMNIST
Time
15.41
3.90
6.12
6.93
7.12
-3.15
Energy
46.26
41.60
41.83
48.97
39.40
36.19
Table 5: Relative time and energy reduction (%) of (p∗ρ,m∗ρ) at ρ=0.1 compared to AsyncSGD at target accuracies of 0.80 (KMNIST) and 0.70 (EMNIST). Positive values indicate savings; negative denote increases.
Figure 6: Extended queueing network model incorporating computation, communication, and CS -side update latencies. Colors correspond to task classes.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Type
Profile
μc
μu
μd
Count
A
Fast compute, slow network
10.0
2.0
2.5
15
B
slow compute, Fast network
2.5
8.0
9.0
35
C
Balanced
5.0
5.0
6.0
30
D
Straggler
0.5
0.8
1.1
15
E
High-Performance
15.0
10.0
11.0
5
Appendix
Table 6: Client clusters, representative hardware profiles, and service rates (Rate μ in tasks/sec).
Routing Probabilities
Staleness Impact Factor
p×100
E0[Di]pi−2×10−2
Type
p∗λ
p∗K
p∗λ
puni
p∗K
A
0.405
0.788
373.9
40.9
3.0
B
0.422
0.754
274.8
29.1
2.0
C
1.421
0.748
75.5
23.8
1.8
D
0.045
1.033
14,869.5
500.2
9.7
Appendix
Table 7: Comparison of optimized routing probabilities and staleness impact factors across different client clusters (Types A–E).
Figure 7: Test set accuracy and loss vs. rounds for the EMNIST dataset ( n=100 , m=n ) using the client profiles defined in Table 6 . The subplots evaluate performance under three service time distributions: (Top Left) Exponential, (Top Right) Lognormal, and (Bottom) Deterministic. Each plot compares convergence across three data settings: Homogeneous (IID), Heterogeneous (Dirichlet α=0.2 ), and Highly Heterogeneous (3 classes/client).
Figure 8: Optimized expected time to ϵ -accuracy, E0[τϵ](p∗,m) , as a function of the concurrency level m . The curve illustrates the fundamental trade-off between parallel speedup and gradient staleness, with the inset highlighting the minimum achieved at the optimal concurrency m∗=91 .
Figure 9: Test set performance for the CIFAR-100 scenario described in Section 5.3.1 . The top row displays test accuracy and the bottom row shows loss, both plotted against wall-clock time. Columns correspond to different service time distributions under homogeneous (IID) and heterogeneous (Non-IID) data settings. Each subplot compares the three strategies. Simulations were repeated 3 times for 6000 wall-clock time units. Solid lines indicate means; shaded areas represent standard deviations.
Scenario
Time Reduction (%) vs.
Dist.
Data
Round-Optimized
AsyncSGD
Exp.
IID
67.95
40.04
Non-IID
60.52
31.26
LogN.
IID
67.31
40.01
Non-IID
65.46
28.86
Det.
IID
66.23
38.05
Appendix
Table 8: Percentage time reduction of the Time-optimized strategy relative to baselines for a target test accuracy of 0.5 on CIFAR-100.
Figure 10: Learning trajectories on the EMNIST dataset under the experimental scenario detailed in Section 5.3.1 and the power profile from Table 4 . The top and bottom rows display test accuracy as a function of total energy consumption and wall-clock time, respectively. Columns represent different service time distributions across homogeneous (IID) and heterogeneous (Non-IID) data partitions. Each panel compares the convergence dynamics of the five routing strategies. Results are averaged over 10 independent runs spanning 300,000 energy units and 300 time units, with solid lines indicating the mean and shaded regions representing the standard deviation.
Asynchronous federated learning lets distributed clients train shared models without waiting for every participant, despite delays, churn, and uneven data.
Asynchronous Federated Learning (AFL) has emerged as a significant research area in recent years. By not waiting for slower clients and executing the training process concurrently, it achieves faster training speed compared to traditional federated learning. However, due to the staleness introduced by the asynchronous process, its performance may degrade in some scenarios. Existing methods often use the round difference between the current model and the global model as the sole measure of staleness, which is coarse-grained and lacks observation of the model itself, thereby limiting the performance ceiling of asynchronous methods. In this paper, we propose FedPSA (Parameter Sensitivity-based Asynchronous Federated Learning), a more fine-grained AFL framework that leverages parameter sensitivity to measure model obsolescence and establishes a dynamic momentum queue to assess the current training phase in real time, thereby adjusting the tolerance for outdated information dynamically. Extensive experiments on multiple datasets and comparisons with various methods demonstrate the superior performance of FedPSA, achieving up to 6.37% improvement over baseline methods and 1.93% over the current state-of-the-art method.
Asynchronous SGD enables scalable distributed training but suffers from stale gradients. When delays depend on the data, slower samples may be underrepresented, biasing training toward faster samples. We introduce ordered momentum, a unified framework that attains the best-known rates for smooth convex and non-convex objectives under both data-independent and data-dependent delays. Notably, we establish (i) the first convergence guarantee for smooth convex objectives with data-dependent delays and, among analyses of data-dependent delays, the first to (ii) benefit from parallelization and (iii) match the tight data-independent rate, with a leading stochastic term independent of the number of workers. Finally, we derive robust learning rates that simplify hyperparameter tuning across convex and non-convex settings.
Tehila Dahan, Roie Reshef, Sharon Goldstein +1
Technion – Israel Institute of Technology, Haifa, Israel
In asynchronous federated learning (FL), client devices send updates to a central server at varying times based on their computational speed, often using stale versions of the global model. This staleness can degrade the convergence and accuracy of the global model. Previous work, such as AsyncFedED, proposed an adaptive aggregation method using Euclidean distance to measure staleness. In this paper, we extend this approach by exploring alternative distance metrics to more accurately capture the effect of gradient staleness. We integrate these metrics into the aggregation process and evaluate their impact on convergence speed, model performance, and training stability under heterogeneous clients and non-IID data settings. Our results demonstrate that certain metrics lead to more robust and efficient asynchronous FL training, offering a stronger foundation for practical deployment.
Patrick Wilhelm, Odej Kao
BIFOLD, Technische Universität Berlin, Berlin, Germany · Technische Universität Berlin, Berlin, Germany