Optimization Trade-offs in Asynchronous Federated Learning: A Stochastic Networks Approach

Abdelkrim Alahyane; Céline Comte; Matthieu Jonckheere

cs.LGMar 27, 2026

Optimization Trade-offs in Asynchronous Federated Learning: A Stochastic Networks Approach

Authors: Abdelkrim Alahyane, Céline Comte, Matthieu Jonckheere

Organizations: LAAS-SARA · EMINES, Mohammed VI Polytechnic University, Ben Guerir, Morocco · LAAS-CNRS, Université de Toulouse, CNRS, Toulouse, France · CNRS, LAAS-SARA

Abstract

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 $p_{1}$ on $\mathbb{E}^{0}[\tau_{\epsilon}]$ . Left: Homogeneous resources. Right: Heterogeneous resources, where Client 2 is three times faster than Client 1 ( $\mu^{s}_{2}=3\mu^{s}_{1}$ for $s\in\{c,u,d\}$ ). Constants: $\Delta=L=\sigma=1$ , $M=5$ , and $G=14$ .

Type	Description	$\mu^{\text{c}}$	$\mu^{\text{u}}$	$\mu^{\text{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

\mu

in tasks/sec).

	Routing probabilities $p\times 100$			Staleness Impact Factor $\mathbb{E}^{0}[D_{i}(p,m)]\,p_{i}^{-2}\times 10^{-2}$
Type	$p^{\ast\tau}$	$p^{\ast\lambda}$	$p^{\ast K}$	$(p^{\ast\tau},\,m^{\ast})$	$(p^{\ast\lambda},\,n)$	$(p^{\ast K},\,n)$	$(p^{\text{uni}},\,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)
Exp.	Non-IID	79.3	57.04	35.6 (36.56)
LogN.	IID	59.08 (70.46)	64.35 (66.1)	41.77 (46.41)
LogN.	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	$\boldsymbol{\kappa}$	$\mathbf{P_{\text{comp}}}$	$\mathbf{P_{\text{u}}}$	$\mathbf{P_{\text{d}}}$
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

P_{\text{comp}}=\kappa(\mu^{c})^{3}

, where a lower

\kappa

indicates higher hardware efficiency.

Figure 4: Joint optimization analysis. Left: Time–Energy Pareto frontier annotated with

\rho

. Right: Evolution of optimal routing probabilities

p^{\ast\rho}

and optimal concurrency

m^{\ast\rho}

as a function of

\rho

, 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
Dataset	Metric	IID	Non-IID	IID	Non-IID	IID	Non-IID
KMNIST	Time	6.11	10.58	18.95	8.63	15.46	0.53
KMNIST	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
EMNIST	Energy	46.26	41.60	41.83	48.97	39.40	36.19

Table 5: Relative time and energy reduction (%) of

(p^{\ast\rho},m^{\ast\rho})

\rho=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	$\mu^{\text{c}}$	$\mu^{\text{u}}$	$\mu^{\text{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

\mu

in tasks/sec).

	Routing Probabilities		Staleness Impact Factor
	$p\times 100$		$\mathbb{E}^{0}[D_{i}]\,p_{i}^{-2}\times 10^{-2}$
Type	$p^{\ast\lambda}$	$p^{\ast K}$	$p^{\ast\lambda}$	$p^{\text{uni}}$	$p^{\ast 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).

Panel of Figure 7 — 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 $\alpha=0.2$ ), and Highly Heterogeneous (3 classes/client).

Figure 8: Optimized expected time to

\epsilon

-accuracy,

\mathbb{E}^{0}[\tau_{\epsilon}](p^{\ast},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^{\ast}=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
Exp.	Non-IID	60.52	31.26
LogN.	IID	67.31	40.01
LogN.	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

Asynchronous federated learning lets distributed clients train shared models without waiting for every participant, despite delays, churn, and uneven data.

See all 25 papers

FedPSA: Modeling Behavioral Staleness in Asynchronous Federated Learning
Feb 17, 2026Chaoyi Lu, Yiding Sun, Zhichuan Yang +3Asynchronous Federated Learning Federated Learning Aggregation
Bringing Order to Asynchronous SGD: Towards Optimality under Data-Dependent Delays with Momentum
May 3, 2026Tehila Dahan, Roie Reshef, Sharon Goldstein +1Momentum Methods Distributed Optimization
Technion – Israel Institute of Technology, Haifa, Israel
Revisiting Gradient Staleness: Evaluating Distance Metrics for Asynchronous Federated Learning Aggregation
Mar 9, 2026Patrick Wilhelm, Odej KaoFederated Learning Aggregation Asynchronous Federated Learning
BIFOLD, Technische Universität Berlin, Berlin, Germany · Technische Universität Berlin, Berlin, Germany

Feb 17, 2026J/K move · Enter open · S save

FedPSA: Modeling Behavioral Staleness in Asynchronous Federated Learning

Chaoyi Lu, Yiding Sun, Zhichuan Yang, Jinqian Chen+2

Asynchronous Federated Learning Federated Learning Aggregation

Open paper AskPDF arXiv

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.

Abstract

Asynchronous Federated Learning

Explore similar work

FedPSA: Modeling Behavioral Staleness in Asynchronous Federated Learning

Bringing Order to Asynchronous SGD: Towards Optimality under Data-Dependent Delays with Momentum

Revisiting Gradient Staleness: Evaluating Distance Metrics for Asynchronous Federated Learning Aggregation