FedQueue: Queue-Aware Federated Learning for Cross-Facility HPC Training
Yijiang Li 1 Emon Dey 1 Zilinghan Li 2 Krishnan Raghavan 1 Ravi Madduri 2 Kibaek Kim 1
arXiv:2605.02125v1 [cs.DC] 4 May 2026
Abstract
Queue-induced delays fundamentally change FL dynamics. Synchronous protocols like FedAvg (McMahan et al., 2017) suffer severe straggler effects as the slowest queued facility dictates progress. Fully asynchronous protocols (Xie et al., 2019; Chen et al., 2021) avoid blocking but accumulate heavy-tailed staleness when delays are stochastic, aggregating updates from outdated models. Existing system-aware methods (Li et al., 2024a) profile compute throughput but assume static availability patterns and do not model or control scheduler-driven queue dynamics.
Federated learning (FL) across multiple HPC facilities faces stochastic admission delays from batch schedulers that dominate wall-clock time. Synchronous FL suffers from severe stragglers, while asynchronous FL accumulates stale updates when queues spike. We propose F ED Q UEUE, a queue-aware FL protocol that incorporates scheduler delays directly into training and aggregation, which (i) predicts per-facility queue delays online to budget local work, (ii) applies cutoff-based admission that buffers late arrivals to bound staleness, and (iii) performs staleness-aware aggregation to stabilize heterogeneous local workloads. We prove the convergence for non-convex ob√ jectives at rate O(1/ R) under bounded staleness, and show that the admission controls yield bounded staleness with high probability under queue-prediction error. Real-world cross-facility deployment of F ED Q UEUE shows 20.5% improvement over baseline algorithms. Controlled queue simulations demonstrate robust improvement over the baselines; in particular, about 34% reduction in time to reach a target accuracy level under high queue variance and non-IID partitions.
We propose F ED Q UEUE, a queue-aware FL protocol that predicts and controls scheduler admission delays to achieve robust wall-clock progress with provably bounded staleness. F ED Q UEUE combines: (i) online queue prediction to budget per-facility job time and local steps, (ii) cutoff-based admission that avoids blocking while bounding staleness, and (iii) staleness-aware aggregation with inverse learning rate scaling. We prove non-convex convergence under provably bounded staleness for F ED Q UEUE. These guarantees ensure that F ED Q UEUE converges reliably despite queue variability, a key requirement for production HPC deployments where queue dynamics are unpredictable and time-varying. The key contributions of this work include: (1) Queueaware FL algorithm. We formalize cross-facility FL under stochastic scheduler delays and introduce F ED Q UEUE, combining online prediction, adaptive budgeting, admission control, and staleness-aware aggregation. (2) Convergence theory with √ staleness control. We prove convergence at rate O(1/ R) with bounded staleness, which our admission policy achieves with high probability under sub-Gaussian prediction errors. (3) Empirical validation. Real-world deployment shows 20.5% improved loss over the baselines while experiments with controlled synthetic queues show 34% faster convergence and validate our theory.
1. Introduction Federated learning (FL) enables collaborative model training across data silos without centralizing raw data (McMahan et al., 2017; Kairouz et al., 2021). An important application is cross-facility FL for scientific and industrial workloads (Zhang et al., 2025; Zhuang et al., 2023; Kim et al., 2024; Li et al., 2026), where each client is a highperformance computing (HPC) facility operating under a batch scheduler (e.g., Slurm, PBS). The dominant challenge in this application is admission delay: jobs may wait minutes to hours in scheduler queues before starting, with wait times varying unpredictably due to system load and priority policies (Feitelson, 2015; Etsion & Feitelson, 2007).
2. Related Work 2.1. FL Under Asynchrony and Staleness
1 Mathematics and Computer Science Division, Argonne National Laboratory, Lemont, IL, USA 2 Data Science and Learning Division, Argonne National Laboratory, Lemont, IL, USA. Correspondence to: Kibaek Kim <[email protected]>.
FedAvg (McMahan et al., 2017) and many follow-ups (Li et al., 2020; Karimireddy et al., 2020) assume synchronous rounds, which are sensitive to stragglers. Asynchronous and buffered variants reduce blocking by aggregating updates as they arrive (Xie et al., 2019; Chen et al., 2021; Nguyen
Preprint. May 5, 2026.
1
FedQueue: Queue-Aware Federated Learning
et al., 2022). Their analyses typically require bounded staleness (or impose staleness-dependent weighting) to control instability in non-convex settings (Nguyen et al., 2022; Fraboni et al., 2023; Forootani & Iervolino, 2025). A complementary line studies semi-/deadline-asynchronous protocols that explicitly control delay via deadlines or staleupdate filtering (Yu et al., 2023; 2024b; Liu et al., 2024; Damaskinos et al., 2022). F ED Q UEUE targets a distinct delay mechanism—scheduler-induced admission delay—and enforces bounded staleness via queue prediction and admission control rather than assuming it a priori.
2.5. Positioning
2.2. System Heterogeneity and Client Availability
3. Problem Formulation
Beyond asynchrony, FL must cope with heterogeneous data and systems. Methods such as FedProx and SCAFFOLD stabilize training under non-IID data (Li et al., 2020; Karimireddy et al., 2020). Other approaches adapt client selection or resource allocation under heterogeneous compute and participation (Ribero et al., 2022; Wang & Ji, 2022; Garg et al., 2025). FedCompass (Li et al., 2024a) is closely related: it profiles client throughput and allocates local steps to equalize progress. However, throughput profiling alone does not capture time-varying admission delay that can dominate wall-clock time in batch-scheduled HPC. F ED Q UEUE complements profiling-based approaches by treating admission delay as a critical time-varying signal and shaping the realized staleness distribution through admission control.
3.1. Problem Setup
Most asynchronous/buffered FL methods treat delay and staleness as exogenous and analyze convergence under an assumed staleness bound (Xie et al., 2019; Nguyen et al., 2022). Profiling-based system-aware methods, in contrast, focus on stable throughput heterogeneity (Li et al., 2024a). F ED Q UEUE explicitly models scheduler-driven admission delay, predicting it online, and using cutoff-based admission to induce bounded staleness with high probability, enabling principled convergence guarantees.
We consider FL over K clients (HPC facilities), indexed by k ∈ {1, . . . , K}. Client k holds a local dataset Dk and minimizes a local empirical risk Fk (w). The global PK objective is minw∈Rp F (w) := k=1 pk Fk (w), where w ∈ Rp is theP model parameter vector, pk ≥ 0 are client weights with k pk = 1 (typically pk ∝ |Dk |). We are motivated by the cross-facility regime where each client is a batch-scheduled HPC system and the dominant source of systems heterogeneity is scheduler-induced admission delay (Feitelson, 2015; Etsion & Feitelson, 2007). Importantly, scheduler-induced admission delay does not modify the learning objective F (w); rather, it changes when each client can compute and return an update. As a result, the server may apply an update computed from a stale global model rather than the current iterate. This timing-induced staleness is the primary mechanism by which queue delays affect convergence and wall-clock time-to-quality.
2.3. HPC Scheduling and Queue-Time Prediction Batch schedulers such as Slurm, PBS, and Maui govern most HPC systems (Yoo et al., 2003; Henderson, 1995; Jackson et al., 2001), and extensive empirical work characterizes their workload dynamics and waiting-time variability (Feitelson, 2015; Etsion & Feitelson, 2007). Queue wait-time prediction has been studied to support workflow planning and scheduling decisions (Brown et al., 2022; 2024; Jancauskas et al., 2019). We use a lightweight and easy to deploy predictor, exponential weighted moving average (EWMA) across sites, but our analysis is predictionagnostic.
Unlike static throughput heterogeneity, queue delays in HPC systems are stochastic and time-varying due to batch scheduling policies and changing system load (Feitelson, 2015; Etsion & Feitelson, 2007). Critically, these delays are not known in advance and thus the server must predict them to effectively coordinate training. This uncertainty necessitates an adaptive approach that combines queue prediction, dynamic work budgeting, and staleness-aware aggregation.
2.4. Cross-Facility Training on HPC
3.2. Round Timeline and Arrival Times
Cross-facility FL frameworks (e.g., xFFL) demonstrate endto-end orchestration across supercomputers using workflow systems and remote job submission (Casella et al., 2024; Aldinucci et al., 2024). These efforts surface practical issues such as queue variability and robustness, but focus on orchestration rather than algorithm design with queue-aware control and convergence guarantees. F ED Q UEUE fills this gap by providing a queue-aware FL protocol with theory and time-to-quality evaluation under real scheduler dynamics.
We specialize the standard asynchronous-FL timeline notation to batch-scheduled HPC settings. Throughout, superscripts r index server rounds (out of total R rounds). To compare methods under stochastic scheduler delays, we parameterize training by a server wall-clock schedule where the server operates on a fixed timer, advancing a logical round counter r every Tsync seconds (a user-chosen synchronization horizon), independent of which updates have arrived. This fixed cadence defines deadlines for update admission.
2
FedQueue: Queue-Aware Federated Learning
At the beginning of round r (at time rTsync ), the server broadcasts the current global model w(r) and triggers job submission at each facility. Client k experiences a queue (r) (admission) delay qk ≥ 0 before the job starts, then trains (r) for local compute time hk ≥ 0, and returns an update at (r) (r) (r) (r) arrival time ak := rTsync + qk + hk . Because qk is stochastic and unknown at round start, updates may arrive after the server has already advanced to subsequent rounds.
all available updates with staleness-aware weighting, and buffers any late arrivals for future rounds. Algorithm 1 FedQueue Server input Initial model w(0) , synchronization horizon Tsync , safety buffer δ, EWMA rate α, base learning rate ηbase , staleness decay ϕ(·), facility weights {pk }K k=1 , throughputs {ck }K , maximum rounds R . max k=1 max output Global models {w(r) }R r=0 . 1: Initialize queue predictions q̂k for all k; buffer B ← ∅. 2: for r = 0, 1, . . . , Rmax − 1 do 3: for k = 1, . . . , K do (r) (r) (r) 4: Jk ← Tsync − q̂k − δ; Ek ← ⌊ck Jk ⌋ 5: end for (r) (r) 6: Emin ← mink Ek 7: for k = 1, . . . , K do (r) (r) (r) 8: ηk ← ηbase Emin /Ek (r) (r) (r) 9: Broadcast (w(r) , r, Jk , Ek , ηk ) to facilitry k 10: end for (r) 11: Set cutoff time tcut ← (r + 1) Tsync 12: Receive messages (k, s, ∆, q) at time t: 13: B ← B ∪ {(k, s, ∆, t)}, q̂k ← (1 − α)q̂k + αq (r) (r) 14: A ← {(k, s, ∆) : (k, s, ∆, t) ∈ B, t ≤ tcut } (r) 15: B ← B \P{(k, s, ∆, t) ∈ B : t ≤ tcut } (r) 16: S ← (k,s,∆)∈A(r) pk ϕ(r − s) P 1 17: w(r+1) ← w(r) + S (r) (k,s,∆)∈A(r) pk ϕ(r − s) ∆ 18: end for
3.3. Staleness and Update Buffering Since jobs may complete after the server has advanced the global model, updates can be computed on stale parameters. (r) Let Rk ≤ r denote the index of the global model that client k used to compute an update that is aggregated at (r) (r) server round r, the staleness is τk := r − Rk ≥ 0. For (s) example, if client k receives w at the start of round s but its update arrives after round s has ended, that update will be buffered and aggregated at a later round r > s with (r) staleness τk = r − s. Excessive staleness degrades convergence because the up(r) date direction computed from w(Rk ) may no longer align (r) well with the current model w . To control staleness while maintaining high system utilization, we need mechanisms to predict queue delays and adaptively budget local work.
4. Queue-Aware FL Algorithm 4.1.1. Q UEUE D ELAY P REDICTION
In this section, we present our Queue-Aware FL (F ED Q UEUE) algorithm, which addresses the challenges of training across multiple HPC facilities with unpredictable queue delays by combining three key components: (1) Queue prediction and adaptive budgeting: Maintain online predictions of queue delays and dynamically allocate per-client compute budgets to target consistent wall-clock progress. (2) Deadline-based admission control: Use cutoff times to bound update staleness while buffering late arrivals for incorporation in subsequent rounds. (3) Stalenessaware aggregation: Down-weight stale updates and scale learning rates inversely with local step counts to stabilize optimization.
(r)
Queue delays qk are not known when planning round r, the (r) server must maintain an online predictor q̂k . When client k’s update arrives, the server observes the realized queue (r) delay qk and updates its predictor for future rounds. We employ EWMA, a lightweight baseline commonly used in queue-time prediction (Jancauskas et al., 2019; Brown et al., (r+1) (r) (r) 2022; 2024): q̂k = (1 − α)q̂k + αqk , where α ∈ (0, 1) is the EWMA rate controlling the trade-off between responsiveness to recent observations and noise stability. Our convergence analysis does not assume a particular predictor form (prediction-agnostic framework): it only requires that prediction errors satisfy a sub-Gaussian concentration property (see Section 5). This allows practitioners to substitute more sophisticated predictors directly as needed for their specific HPC environments.
4.1. Server Algorithm Components Algorithm 1 presents the server-side protocol for F ED Q UEUE. At the start of each round r, the server main(r) tains queue delay predictions q̂k for all clients, computes (r) (r) per-client job-time budgets Jk and local step budgets Ek based on the profiled throughput ck and predictor state (r) (r) q̂k , determines adaptive learning rates ηk , and broad(r) (r) (r) casts (w(r) , r, Jk , Ek , ηk ) to all clients. The server then collects arriving updates until a deadline, aggregates
4.1.2. A DAPTIVE W ORK B UDGETING (r)
Given the queue delay prediction q̂k , the server allocates (r) a per-round job-time budget Jk to each client to target completion within the synchronization horizon Tsync (Line (r) (r) 4 in Algorithm 1): Jk := Tsync − q̂k − δ, where δ > 0 is a safety buffer that accounts for prediction error and system 3
FedQueue: Queue-Aware Federated Learning Round 1
Round 2
𝑇!"#$
𝑇!"#$
Round 0 (Warm up Stage) (%) 𝑞%
Client #1
(!)
𝐸!
Client #2
(!) 𝐸$ = 38 steps
(%)
Client #3
(!)
𝐸%
Assign training steps
FedQueue Server
(#)
𝑞"%
Resourced Allocated
𝑇!"#$ Synchronization Horizon (')
𝐸%
(') 𝑞%
())
Resourced Freed
(')
𝑞'%
ℎ) (%)
𝐸%
= 65 steps
= 63 steps
Assign training steps Estimation Update
(!) 𝑞"! (%) 𝑞"% (%) 𝑞"&
(&)
𝑞"!
(&)
𝑞"%
(&)
𝑞"&
Queue Delay Estimation (sec)
Real Queue Delay for Client 𝑘 in Round 𝑟
Local Training Step Budget for Client 𝑘 in Round 𝑟
())
𝑞)
Assign training steps Estimation Update
(!) 𝑞"! (!) 𝑞"% (!) 𝑞"&
(#) 𝑞"&
Resource Queued
($)
ℎ(
(%) 𝐸$ = 37 steps
(()
𝐸%
())
())
𝑞(
ℎ)
= 65 steps
Assign training steps Estimation Update
(#)
𝑞"!
(()
𝑞)
ℎ)
20 steps
= 45 steps
($) 𝐸$ = 36 steps
(%)
𝑞)
($)
𝐸! (() ℎ(
(() 𝑞(
(%) ℎ(
20 steps
(() ℎ%
Unexpected delay
= 45 steps
(%)
𝑞(
𝑇!"#$
(() 𝑞%
(%) ℎ%
20 steps
Round 3
(') ℎ%
Queue Delay Estimator
Local Training Time for Client 𝑘 in Round 𝑟
Queue Delay Estimation for Client 𝑘 in Round 𝑟
Figure 1. Illustration of the FedQueue Algorithm. The FedQueue server first obtains initial queuing delay estimates for each client (0) (r) (q̂k ) during a warm-up stage, and accordingly assigns the number of local training steps (Ek ). In each round r, the FedQueue server (r) updates the estimates based on the recent queuing delay (qk ) and performs global aggregation using all client updates received before the admission deadline (rTsync ). If a certain client fails to return its update within the deadline due to an unexpected delay (e.g., Client 1 in Round 2), its update will be deferred and incorporated in the next aggregation round, with the staleness factor applied. (r)
overheads (e.g., data transfer, job initialization).j The cork (r) (r) responding local training step budget is Ek := ck Jk , where ck > 0 is the profiled training throughput of client k in local SGD steps per second. We therefore enforce that (r) local training time hk respects the job-time budget for all (r) (r) clients (i.e., hk ≤ Jk for all k, r).
with smaller Ek receive larger per-step learning rates to maintain their influence on the global model despite fewer local iterations. This relationship is used explicitly in our analysis (Section 5) to bound the accumulated local drift. 4.1.4. D EADLINE -BASED A DMISSION C ONTROL To bound staleness while maintaining high utilization, F ED Q UEUE uses a deadline-based admission policy with buffering (Lines 11-17 in Algorithm 1). At the end of each (r) round r, the server sets a cutoff time tcut := (r + 1)Tsync and aggregates all updates that have arrived by this deadline. For a job submitted at the start of round s (time sTsync ), the update is included in the aggregation for round s if (s) and only if ak ≤ (s + 1)Tsync . Updates arriving after the cutoff are not discarded; instead, they are buffered (Line 15 adds updates to B) and incorporated in the first subsequent round whose cutoff they meet. Specifically, an (s) update produced from w(s) and arriving at time ak is aggregated at next available round, i.e., round r such that (s) r = min{j ≥ s : ak ≤ (j + 1)Tsync } with staleness (r) τk = r−s. This buffering mechanism ensures that no computational work is wasted while still maintaining bounded staleness through the cutoff discipline.
This adaptive budgeting mechanism enables F ED Q UEUE to balance heterogeneous queue conditions: clients experiencing longer predicted queues receive smaller compute budgets to increase their likelihood of meeting the round deadline, while clients with shorter predicted queues can perform more local work. 4.1.3. A DAPTIVE L EARNING R ATE S CALING The adaptive budgeting mechanism produces heterogeneous (r) local step counts Ek across facilities due to varying queue predictions and compute speeds. Without compensation, clients performing more local steps would dominate the aggregation and cause excessive drift from the global model. To stabilize training under heterogeneous local step counts (r) Ek , we adopt an inverse learning rate scaling strategy (r)
inspired by FedCompass (Li et al., 2024a): ηk = ηbase (Line 8 in Algorithm 1), where ηbase > 0.
(r)
Emin
(r)
Ek
4.1.5. S TALENESS -AWARE AGGREGATION
This scaling equalizes the effective local displacement across heterogeneous step budgets: facilities with larger (r) Ek take more gradient steps but apply smaller per-step learning rates to prevent overshooting. Conversely, facilities
To mitigate the impact of stale updates while retaining the benefits of asynchrony, we down-weight delayed updates using a staleness decay function ϕ : N → R+ with ϕ(0) = 1 (Lines 16-17 in Algorithm 1). We use harmonic decay by default (with a parameter β), ϕ(τ ) = (1 + βτ )−1 . The global 4
FedQueue: Queue-Aware Federated Learning
where σk2 is the local gradient variance at facility k.
model is updated using the staleness-weighted aggregation: w(r+1) = w(r) +
X 1 (r) (r) pk ϕ(τk )∆k , S (r) (r)
Assumption 5.3 (Bounded Dissimilarity). The local objectives exhibit bounded heterogeneity. There exists G ≥ 0 such that for all k ∈ [K]:
k∈A
where A(r) denotes the set of updates meeting the cutoff (r) deadline for round r (Line 17), ∆k denotes the update P (r) from the client, and S (r) := k∈A(r) pk ϕ(τk ) is a normalization factor ensuring proper scaling (Line 20).
∥∇Fk (w) − ∇F (w)∥2 ≤ G2 .
Assumptions 5.1 and 5.2 are standard in non-convex federated optimization and hold for typical neural network training with smooth losses such as cross-entropy or mean squared error. Assumption 5.3 is common in heterogeneous FL settings and holds when local data distributions are not arbitrarily different from the global distribution.
4.2. Client Algorithm Components Algorithm 2 FedQueue Client (Facility k) (r)
(r)
(r)
input (w(r) , r, Jk , Ek , ηk ) from server. (r) (r) output Message (k, r, ∆k , qk ). (r) 1: tsub ← current time; submit a job for Jk seconds. (r) 2: Set tstart ← start time and qk ← tstart − tsub . (r) 3: Initialize wk ← w (r) ; run local SGD for at most Ek (r) steps (or until time budget expires) with step size ηk . (r) 4: ∆k ← wk − w (r) . (r) (r) 5: Send (k, r, ∆k , qk ) to server.
5.1. Main Convergence Result We first show that the admission window induces a boundedstaleness regime with high probability under mild subGaussian queue-prediction errors and properly chosen safety buffer δ. Lemma 5.4 (Admission-Induced Bounded Staleness). Fix Tsync > 0 and δ > 0, and let γ ≥ 0 be an analysis threshold. Assume the local training time respects the job-time budget, (r) (r) i.e., hk ≤ Jk for all k, r. holds.
Algorithm 2 presents the client-side protocol for F ED Q UEUE. Once each client k receives the broadcast from the server, it submits a batch job to its local scheduler, (r) (r) observes the realized queue delay qk , runs up to Ek local SGD steps (or stops when the job-time budget expires), and (r) returns the update ∆k (Line 4) along with the round index r and the observed queue delay to the server for determining staleness and updating queuing delay estimates.
(r)
(r)
(r)
Let ek := qk − q̂k denote the queue-delay prediction error (Section 4.1.1), and let Fr−1 denote the filtration up to round r − 1. Suppose that conditionally on the history up (r) to round r − 1, ek is zero-mean and ρk -sub-Gaussian: 2 2 h i λ ρk (r) E exp λek | Fr−1 ≤ exp 2
for all λ ∈ R. (1)
Figure 1 illustrates the lifecycle of an FL experiment under the F ED Q UEUE algorithm. In practice, we implement an extra warm-up stage to obtain the initial queuing estimates.
Consider the buffering rule in Section 3.3. If a job submitted at time rTsync completes by time rTsync + (1 + γ)Tsync , then it must be incorporated within at most ⌈1 + γ⌉ subsequent server cutoffs, yielding a staleness bound.
5. Theoretical Analysis
Then, for any ε ∈ (0, 1), if δ is chosen such that s
This section establishes theoretical convergence guarantees for F ED Q UEUE under standard non-convex assumptions. We prove that its convergence rates are comparable to existing asynchronous FL methods while explicitly accounting for queue delay prediction error and staleness variance.
γTsync + δ ≥ max
k∈[K]
KR , ε
(2)
for all k, r.
(3)
2ρ2k log
we have, with probability at least 1 − ε, (r)
τk
To establish convergence guarantees, we make the following standard assumptions in non-convex federated optimization. Assumption 5.1 (L-smooth objective). The global objective F is L-smooth, i.e., for all w, w′ ∈ Rp :
≤ τmax := ⌈1 + γ⌉
We report empirical staleness distributions and violation frequencies to validate the practical tightness of this bound in Section 6.
∥∇F (w) − ∇F (w′ )∥ ≤ L∥w − w′ ∥.
We present our main convergence theorem for F ED Q UEUE under non-convex objectives with bounded staleness and queue prediction error.
Assumption 5.2 (Bounded Gradient Variance). The stochastic gradient has bounded variance. For each facility k and any w ∈ Rp :
Theorem 5.5 (Convergence of FedQueue). Under Assump(r) tions 5.1–5.3, suppose the staleness is bounded by τk ≤
Eξ∼Dk ∥∇ξ ℓ(w; ξ) − ∇Fk (w)∥2 ≤ σk2 ,
5
FedQueue: Queue-Aware Federated Learning (r)
(r)
τmax for all k ∈ [K] and r ∈ [R]. Let ηk = ηbase
Emin (r)
Ek
6.1. Large-Scale Cross-Facility Evaluation
with
Experimental setup. This experiment aims to measure efficiency of F ED Q UEUE in real-world deployment. Therefore, four production HPC facilities participate as FL clients (denoted as System A-System D), with the FL server running on a separate dedicated cluster. Each facility allocates two GPU nodes for client training and we use APPFL (Li et al., 2024b; Ryu et al., 2022) to implement all methods. We also use G LOBUS suite (Li et al., 2022; Zheng et al., 2024) to submit and monitor jobs across facilities.
(r)
ηbase ≤ 8LE1max , where Emax = maxk,r Ek . Assume the staleness decay function satisfies ϕ(τ ) ≥ ϕmin > 0 for all τ ≤ τmax . Then, for the iterates generated by F ED Q UEUE (Algorithm 1), there exist constants C0 , C1 > 0 such that R−1 i F (w(0) ) − F ∗ 1 X h E ∥∇F (w(r) )∥2 ≤ C0 R r=0 ηbase Emin R 2 + C1 ηbase Emax L2 τmax + G2 + σ 2 .
Model, dataset, and training. We fine-tune a pretrained LLaMA2-7B model (Touvron et al., 2023) on SMolInstruct (Yu et al., 2024a), a curated chemistry instruction dataset partitioned across the four facilities by task categories. Each algorithm runs until a wall-clock budget of 17,000 seconds is exhausted and uses time-to-quality as a measurement to identify performance. To ensure fair comparison under realistic but comparable conditions, all algorithms were executed during roughly similar times of day, so that facilities experienced similar load patterns, while still being subject to the stochastic queue dynamics.
(r)
where F ∗ = inf w F (w), Emin = mink,r Ek , and σ 2 = maxk σk2 . Remark 5.6√(Convergence). Theorem 5.5 matches the standard O(1/ R) √ stationarity rate for non-convex FL when ηbase = Θ(1/ R). The bias scales with heterogeneity (G2 ), stochasticity (σ 2 ), and the square of the staleness bound 2 (τmax ), underscoring the importance of admission-induced staleness control. Our convergence bound deviates from the standard FL algorithm in three ways: 1) Our asynchronous approach allows updates from models up to τmax rounds 2 stale, introducing the penalty term L2 τmax in the bias. However, τmax is a controlled system parameter that does not grow with R. 2) We allow adaptive local steps, introducing Emin and Emax . The optimization error scales with the slowest client while the bias scales with the fastest client. 3) We introduce adaptive learning rate that is computed based on ηbase which prevents clients with more local steps from dominating the updates. We demonstrate the convergence of F ED Q UEUE empirically in Section 6. Remark 5.7 (Queue Prediction Threshold). Lemma 5.4 provides a high-probability bound on staleness under the buffering rule by selecting an analysis threshold γ and setting τmax = ⌈1 + γ⌉. Importantly, γ is not an algorithm parameter in F ED Q UEUE; it only indexes the probabilistic arrival-time event used in the staleness bound.
6.1.1. R EAL -W ORLD D EPLOYMENT E FFICIENCY
6. Experiments
Figure 2. Test loss of the federated global models versus wallclock time across all algorithms. There are two configurations of F ED Q UEUE tested. FedQueue-1 has (Tsync , δ) = (20min, 1min) while FedQueue-2 has (Tsync , δ) = (40min, 2min). F ED Q UEUE starts to achieve lower test loss once it builds accurate queue and compute estimates of the HPC systems and ultimately reaches the smallest test among the algorithms. Additional details on the setup is available in Appendix C.
F ED Q UEUE is evaluated through two sets of experiments. First, Section 6.1 demonstrates superior time-to-quality and final model performance in a real-world cross-facility training on production HPC systems under unpredictable queue delays. Second, Section 6.2 uses controlled simulations to validate our convergence theory, quantify performance gains under varying queue variability and client arrivals while demonstrating resource efficiency improvements. Across these set of experiments, we use four baselines: FedAvg, FedAsync, FedBuff, and FedCompas. More details on the experimental setup are provided in Appendices C and D.
Time-to-threshold analysis. Figure 2 shows global model test loss versus wall-clock time for all methods. To quantify deployment efficiency, we measure the time required for each algorithm to reach several target loss thresholds (ℓ ∈ {1.0, 0.8, 0.6, 0.4}) and report the final loss values at the wall-clock budget. Table 1 summarizes these results with detailed facility-level loss trajectories provided in Appendix C. As noted, F ED Q UEUE achieves the best final loss values while being the only algorithm to attain loss below 0.4 and reaches 0.6 approximately 1.78× faster than FedAvg and 1.36× faster than the FedCompass. FedCompass
The proofs of Lemma 5.4 and Theorem 5.5 are deferred to the Appendices A and B.
6
FedQueue: Queue-Aware Federated Learning
Setup. We simulate K = 4 clients with non-IID MNIST data partitions with a CNN and a cross-entropy loss. We measure test accuracy and fix the optimizer, batch size, evaluation cadence, and per-round resource requests across all baselines; differences are confined to orchestration (sync/async), budgeting, admission, and aggregation logic. Additional details are provided in Appendix D.1.
degrades as queue conditions shift over the roughly 5-hour window even with impressive early performance. Table 1. Time-to-loss-threshold comparison. Time required to reach target test loss thresholds for each algorithm. ”—” indicates threshold not reached within 17,000 second budget. FedAsync converges quickly to early thresholds but plateaus at poor final loss. Only F ED Q UEUE reaches loss value below 0.4. Threshold
FedAvg
FedAsync
FedBuff
FedCompass
FedQueue-1
FedQueue-2
1.0 0.8 0.6 0.4
2284 4567 9502 —
1245 3038 11079 —
1574 3351 9328 —
1454 3490 7270 —
2807 4597 7216 15727
2680 5331 5331 16881
Final loss
0.4549
0.5381
0.4987
0.4345
0.3947
0.3658
6.2.1. C ONVERGENCE U NDER Q UEUE VARIABILITY We study the impact of queue variability on convergence by sweeping the queue-noise parameter ρk ∈ {0.1, 0.5, 0.9}, while holding the model architecture, optimizer, batch size, and per-round resource requests fixed. Performance is evaluated using wall-clock time-to-target accuracy (95%), maximum achieved accuracy, and the data movement ratio required to reach 95% accuracy.
6.1.2. Q UEUE DYNAMICS AND A DMISSION B EHAVIOR Observed queue patterns. We use Globus Compute Endpoint to submit jobs to its native production scheduler (PBS or Slurm) with Table 2 detailing the queue conditions. Notably, queue times exhibit high variance across facilities with random delays, reflecting realistic heterogeneity in production HPC environments forcing static profiling approaches (e.g., FedCompass) to struggle in production settings.
F ED Q UEUE consistently accelerates convergence under queue variability. Across all queue regimes, F ED Q UEUE achieves faster time-to-target accuracy than the other baselines with the gains becoming most pronounced under high queue variance. Specifically, when ρk = 0.9, referring to high queue variance, F ED Q UEUE improves time-to-target by 37% relative to FedAvg, 35% relative to FedBuff, and 60% relative to FedAsync and outperforms FedCompass by approximately 39%. These improvements, indicated in Table 4 and Figure 3 cement that F ED Q UEUE maintains rapid and stable convergence even when queue noise increases.
Table 2. Cross-facility systems and observed queue conditions. Hardware configuration and queue behavior observed across four production HPC facilities. Facilities operate different schedulers with heterogeneous GPU counts. Queue times exhibit substantial cross-facility heterogeneity and high within-facility variance. Statistics computed over all jobs during the experimental period. GPUs
Queue time (sec.)
Facility
Scheduler
per node
per job
median
p90
System-A System-B System-C System-D
PBS PBS Slurm Slurm
12 4 8 4
24 8 16 8
1015.53 471.15 741.14 673.68
1638.38 1673.44 1188.86 1668.29
Admission decisions and staleness. Table 3 summarizes F ED Q UEUE’s admission behavior where F ED Q UEUE admits 71.7% of submitted updates. It maintains bounded staleness with maximum observed staleness is one, consistent with Lemma 5.4.
Figure 3. Time-to-quality. Validation accuracy vs. elapsed time to reach 95% accuracy under increasing queue variance ρk ( ρ=0.9, ρ=0.5, ρ=0.1.)
Table 3. Combined admission and utilization statistics from the two runs of F ED QUEUE. Max delay ratio for each HPC system tk is defined as maxr Tsync . Facility
Jobs submitted
Admitted
Deferred
Max Delay↓
System-A System-B System-C System-D
10 10 12 12
6 6 10 10
4 4 2 2
1.34 1.33 1.16 1.09
Faster convergence is achieved with significantly improved resource efficiency. Beyond wall-clock speedups, F ED Q UEUE also exhibits superior communication efficiency and local resource utilization. Analysis of the model movement ratio Dr and total local steps #Ek in Table 4 shows that F ED Q UEUE saves model transfers by up to 67%, and approximately 2.1× reduction in local resource usage as compared to the baselines.
6.2. Controlled Synthetic Queue Experiments
6.2.2. S ENSITIVITY TO A RRIVAL VARIABILITY.
To further understand the reasons behind impressive performance of F ED Q UEUE, we run controlled experiments under synthetic queue dynamics. We defer extended analyses to Appendix D and focus on main results.
The safety buffer δ controls a fundamental trade-off: staleness vs. convergence speed. In our budgeting rule, δ provides slack against queue-delay uncertainty, making the per-round job-time budget more conservative. Larger δ in7
FedQueue: Queue-Aware Federated Learning (r)
Table 4. Synthetic summary. Max accuracy, time-to-target, and model movement ratio (Dr ), and total local steps (#Ek ) to 95% accuracy under a fixed non-IID partition and high queue variability (ρ = 0.9). Method F ED Q UEUE FedAvg FedAsync FedBuff FedCompass
Max-A↑
Time-to-A⋆ ↓ (s)
Dr ↓
#Ek ↓
96.62 ± 0.18 95.63 ± 0.69 95.75 ± 0.94 97.45 ± 0.16 97.21 ± 0.35
154.72 ± 5.56 245.60 ± 4.29 384.07 ± 8.18 235.10 ± 4.27 254.44 ± 7.79
1.00 1.51 1.67 1.11 1.15
5893 11520 12400 7440 8449
a fixed learning rate per facility independent of Ek . These results are presented in Table 5 with 85% target accuracy. Table 5. Ablation results. Final Accuracy, time-to-target accuracy (85%), empirical probability of arrival beyond the cutoff (P), Normalized expectation of delay (Êd ), Normalized maximum delay (Rd ) for different F ED Q UEUE variants. Method variant F ED Q UEUE (Baseline) w/o inverse LR w/o EWMA w/o staleness decay
creases the fraction of clients that finish and arrive before the cutoff Tsync , thereby concentrating staleness and improving stability (as in Lemma 5.4), but it also reduces the effective amount of local progress per time, wich can slow the time to A∗ . Figure 4 demonstrates this effect: larger δ (green histogram) leads to a histogram whose tail does not cross the Tsync line, but achieves slower time to A∗ (right panel). Conversely, smaller δ (blue histogram) crosses Tsync more frequently, implying more buffered (stale) updates, but it reaches A∗ faster due to more aggressive local work.
Final A% ↑
Time-to-85% (s) ↓
P↓
Êd ↓
Rd ↓
96.62 90.89 96.01 87.18
26.68 28.13 116.59 34.61
0.015 0.020 0.035 0.015
1.13 1.15 1.32 1.14
1.17 1.16 1.38 1.17
Queue prediction matters. Removing EWMA degrades performance (time to 85%) by 330% and normalized expected delay (Êd ) by 17%, despite comparable final accuracy. Therefore, EWMA is essential in the presence of non-stationary scheduler dynamics. Staleness weighting is stabilizing. Disabling staleness decay (ϕ(τ ) ≡ 1) reduces final accuracy by approximately 10% and increases time-to-target by approximately 30%, a behavior that aligns with Theorem 5.5. Notably without decay, stale updates contribute disproportionately to updates increasing optimization variance.
Queue variability ρ and safety buffer δ are typically not in the designer’s control, as they depend on HPC system characteristics and scheduler behavior. Our theory and controlled experiments show that F ED Q UEUE is robust to variation in queue dynamics and client arrival patterns. Appendix D.2 provides detailed analysis of how sweeping ρ and γ affects client arrival probability beyond Tsync , time-toquality, and maximum delay.
Inverse LR scaling prevents domination. Removing inverse learning-rate scaling leads to an approximately 6% drop in final accuracy and an approximately 5% increase in time-to-target. Notably staleness significantly impacts accuracy while EWMA significantly impacts solution time. It is expected that, this trade-off can be decided by choosing the values of α and γ depending on the requirement of the practitioner. However, F ED Q UEUE allows this flexibility.
7. Conclusion and Limitations We introduced F ED Q UEUE, a queue-aware federated learning protocol that addresses the challenge of unpredictable scheduler admission delays in cross-facility training. By combining online queue prediction, adaptive compute budgeting, deadline-based admission control, and stalenessaware aggregation, F ED Q UEUE achieves provably bounded staleness and maintains convergence guarantees under stochastic queue dynamics. Experiments demonstrate substantial improvements over existing approaches in both realworld cross-facility deployment and controlled simulations.
Tsync
Figure 4. Impact of admission buffer. (Left) Effect of scaling the buffer δ on histogram of arrival times and (Right) corresponding time to quality (95%). This test exposes the trade-off between better convergence value and convergence time in the presence of client arrival variability. Note that the histograms of δ = 1, 2 are almost identical and overlapped each other.
Our framework assumes that facility throughput can be profiled and that queue-prediction errors satisfy sub-Gaussian concentration, reasonable for typical HPC schedulers, but potentially limiting for adversarial or highly non-stationary systems. Additionally, while our buffering mechanism handles late arrivals, we do not explicitly model job failures or cancellations which result in lost updates rather than buffered aggregations.
6.2.3. A BLATION S TUDIES There are three main components in F ED Q UEUE: EWMA, staleness decay and inverse LR. We ablate these components to understand their impact on performance. We consider: (i) w/o EWMA: replace queue prediction by a static estimate (r) q̂k ≡ µk . (ii) w/o staleness decay: set ϕ(τ ) ≡ 1 in aggregation weights, and (iii) w/o inverse LR scaling: use 8
FedQueue: Queue-Aware Federated Learning
Acknowledgment
Chen, Y., Ning, Y., and Rangwala, H. A fully asynchronous training paradigm for federated learning. In International Joint Conference on Artificial Intelligence, pp. 2265– 2271, 2021.
This work was supported by the U.S. Department of Energy, Office of Science, Advanced Scientific Computing Research, under Contract DE-AC02-06CH11357. We gratefully acknowledge the computing resources provided on Improv, a high-performance computing cluster operated by the Laboratory Computing Resource Center at Argonne National Laboratory.
Damaskinos, G., Guerraoui, R., Kermarrec, A.-M., Nitu, V., Patra, R., and Taiani, F. Fleet: Online federated learning via staleness awareness and performance prediction. ACM Transactions on Intelligent Systems and Technology (TIST), 13(5):1–30, 2022.
An award of computer time was provided by the ASCR Leadership Computing Challenge (ALCC) program. This research used resources of the Argonne Leadership Computing Facility, which is a U.S. Department of Energy Office of Science User Facility operated under contract DE-AC0206CH11357.
Etsion, Y. and Feitelson, D. G. Experience with fine-grain synchronization in mimd architectures. In Workshop on Job Scheduling Strategies for Parallel Processing, pp. 94–113. Springer, 2007. Feitelson, D. G. Workload modeling for computer systems performance evaluation. Cambridge University Press, 2015.
This research used resources of the Oak Ridge Leadership Computing Facility at the Oak Ridge National Laboratory, which is supported by the Office of Science of the U.S. Department of Energy under Contract No. DE-AC0500OR22725.
Forootani, A. and Iervolino, R. Asynchronous federated learning with non-convex client objective functions and heterogeneous dataset. IEEE Transactions on Artificial Intelligence, 2025.
This research used resources of the National Energy Research Scientific Computing Center (NERSC), a Department of Energy User Facility using NERSC award ALCCERCAP0038201.
Impact Statement
Fraboni, Y., Vidal, R., Kameni, L., and Lorenzi, M. A general theory for federated optimization with asynchronous and heterogeneous clients updates. Journal of Machine Learning Research, 24(110):1–43, 2023.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Garg, D., Sanyal, D., Lee, M., Tumanov, A., and Gavrilovska, A. Client availability in federated learning: It matters! In Proceedings of the 5th Workshop on Machine Learning and Systems, pp. 114–121, 2025.
References
Henderson, R. L. Job scheduling under the portable batch system. Technical report, Springer, 1995.
Aldinucci, M., Atwell, S., Bagnasco, S., Casella, B., Colonnelli, I., Costa, A., et al. Cross-facility federated learning. Procedia Computer Science, 240:148–159, 2024.
Jackson, D., Snell, Q., and Clement, M. Maui scheduler. In Workshop on Job Scheduling Strategies for Parallel Processing, pp. 126–159. Springer, 2001.
Brown, N., Gibb, G., Belikov, E., and Nash, R. Predicting batch queue job wait times for informed scheduling of urgent HPC workloads. arXiv preprint arXiv:2204.13543, 2022.
Jancauskas, V., Piontek, T., Kopta, P., and Bosak, B. Predicting queue wait time probabilities for multi-scale computing. Philosophical Transactions of the Royal Society A, 377(2142):20180151, 2019.
Brown, N., Gibb, G., Belikov, E., and Nash, R. Predicting accurate batch queue wait times on production supercomputers by combining machine learning techniques. Concurrency and Computation: Practice and Experience, 36(15):e8112, 2024.
Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., et al. Advances and open problems in federated learning. Foundations and Trends in Machine Learning, 14(1–2):1–210, 2021.
Casella, B., Esposito, R., Moro, G., and Aldinucci, M. A performance analysis of vm-based trusted execution environments for confidential federated learning. In European Conference on Parallel Processing, pp. 1–15, 2024.
Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S., Stich, S., and Suresh, A. T. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pp. 5132–5143. PMLR, 2020. 9
FedQueue: Queue-Aware Federated Learning
Kim, K., Raghavan, K., Kotevska, O., Dorier, M., Madduri, R., Ryu, M., Munson, T., Ross, R., Flynn, T., Kagawa, A., et al. Privacy-preserving federated learning for science: Challenges and research directions. In 2024 IEEE International Conference on Big Data (BigData), pp. 7849–7853. IEEE, 2024.
Ryu, M., Kim, Y., Kim, K., and Madduri, R. K. Appfl: open-source software framework for privacy-preserving federated learning. In 2022 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pp. 1074–1083. IEEE, 2022. Touvron, H., Martin, L., Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., Bikel, D., Blecher, L., Ferrer, C. C., Chen, M., Cucurull, G., Esiobu, D., Fernandes, J., Fu, J., Fu, W., Fuller, B., Gao, C., Goswami, V., Goyal, N., Hartshorn, A., Hosseini, S., Hou, R., Inan, H., Kardas, M., Kerkez, V., Khabsa, M., Kloumann, I., Korenev, A., Koura, P. S., Lachaux, M.-A., Lavril, T., Lee, J., Liskovich, D., Lu, Y., Mao, Y., Martinet, X., Mihaylov, T., Mishra, P., Molybog, I., Nie, Y., Poulton, A., Reizenstein, J., Rungta, R., Saladi, K., Schelten, A., Silva, R., Smith, E. M., Subramanian, R., Tan, X. E., Tang, B., Taylor, R., Williams, A., Kuan, J. X., Xu, P., Yan, Z., Zarov, I., Zhang, Y., Fan, A., Kambadur, M., Narang, S., Rodriguez, A., Stojnic, R., Edunov, S., and Scialom, T. Llama 2: Open foundation and fine-tuned chat models. Preprint arXiv:2307.09288, 2023. URL https://arxiv.org/abs/2307.09288.
Li, T., Sahu, A. K., Zaheer, M., Sanjabi, M., Talwalkar, A., and Smith, V. Federated optimization in heterogeneous networks. In Proceedings of Machine Learning and Systems, volume 2, pp. 429–450, 2020. Li, Y., Li, Z., Chard, K., Foster, I., Munson, T., Madduri, R., and Kim, K. Scalable cross-facility federated learning for scientific foundation models on multiple supercomputers. arXiv preprint arXiv:2603.19544, 2026. Li, Z., Chard, R., Babuji, Y., Galewsky, B., Skluzacek, T. J., Nagaitsev, K., Woodard, A., Blaiszik, B., Bryan, J., Katz, D. S., Foster, I., and Chard, K. FuncX: Federated function as a service for science. IEEE Transactions on Parallel and Distributed Systems, 33(12):4948–4963, 2022. Li, Z., Chaturvedi, P., He, S., Chen, H., Singh, G., Kindratenko, V., Huerta, E. A., Kim, K., and Madduri, R. Fedcompass: Efficient cross-silo federated learning on heterogeneous client devices using a computing poweraware scheduler. In International Conference on Learning Representations, 2024a.
Wang, S. and Ji, M. A unified analysis of federated learning with arbitrary client participation. Advances in neural information processing systems, 35:19124–19137, 2022. Xie, C., Koyejo, S., and Gupta, I. Asynchronous federated optimization. arXiv preprint arXiv:1903.03934, 2019.
Li, Z., He, S., Yang, Z., Ryu, M., Kim, K., and Madduri, R. Advances in appfl: A comprehensive and extensible federated learning framework. arXiv preprint arXiv:2409.11585, 2024b.
Yoo, A. B., Jette, M. A., and Grondona, M. Slurm: Simple linux utility for resource management. In Workshop on Job Scheduling Strategies for Parallel Processing, pp. 44–60. Springer, 2003.
Liu, J., Jia, J., Che, T., Huo, C., Ren, J., Zhou, Y., Dai, H., and Dou, D. FedASMU: Efficient asynchronous federated learning with dynamic staleness-aware model update. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 13900–13908, 2024.
Yu, B., Baker, F. N., Chen, Z., Ning, X., and Sun, H. LlaSMol: Advancing large language models for chemistry with a large-scale, comprehensive, high-quality instruction tuning dataset. In First Conference on Language Modeling, 2024a. URL https://openreview. net/forum?id=lY6XTF9tPv.
McMahan, H. B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A. Communication-efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pp. 1273–1282. PMLR, 2017.
Yu, J., Zhou, R., Chen, C., Li, B., and Dong, F. ASFL: Adaptive semi-asynchronous federated learning for balancing model accuracy and total latency in mobile edge networks. In Proceedings of the 52nd International Conference on Parallel Processing, pp. 443–451, 2023.
Nguyen, J., Malik, K., Zhan, H., Yousefpour, A., Rabbat, M., Malek, M., and Huba, D. Federated learning with buffered asynchronous aggregation. In International Conference on Artificial Intelligence and Statistics, pp. 3581– 3607. PMLR, 2022.
Yu, M., Choi, J., Lee, J., and Oh, S. Staleness aware semiasynchronous federated learning. Journal of Parallel and Distributed Computing, 193:104950, 2024b.
Ribero, M., Vikalo, H., and De Veciana, G. Federated learning under intermittent client availability and time-varying communication constraints. IEEE Journal of Selected Topics in Signal Processing, 17(1):98–111, 2022.
Zhang, N., Xu, X., Liu, X., Wu, J., and Tang, H. Incentive mechanism of foundation model enabled cross-silo federated learning. Scientific Reports, 15(1):24181, 2025. 10
FedQueue: Queue-Aware Federated Learning
Zheng, W., Kordas, J., Skluzacek, T. J., Kettimuthu, R., and Foster, I. Globus service enhancements for exascale applications and facilities. The International Journal of High Performance Computing Applications, 38(6):658–670, 2024. doi: 10.1177/10943420241281744. URL https: //doi.org/10.1177/10943420241281744. Zhuang, W., Chen, C., and Lyu, L. When foundation model meets federated learning: Motivations, challenges, and future directions. arXiv preprint arXiv:2306.15546, 2023. The submitted manuscript has been created by UChicago Argonne, LLC, Operator of Argonne National Laboratory (“Argonne”). Argonne, a U.S. Department of Energy Office of Science laboratory, is operated under Contract No. DE-AC02-06CH11357. The U.S. Government retains for itself, and others acting on its behalf, a paid-up nonexclusive, irrevocable worldwide license in said article to reproduce, prepare derivative works, distribute copies to the public, and perform publicly and display publicly, by or on behalf of the Government. The Department of Energy will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan (http://energy.gov/downloads/doe-publicaccess-plan).
11
FedQueue: Queue-Aware Federated Learning
A. Proof of Lemma 5.4 (r)
Fix any facility k ∈ [K] and round r ∈ {0, . . . , R − 1}. By definition of Jk and assuming that local training time respects (r) (r) the job-time budget, i.e., hk ≤ Jk for all k, r. holds, (r)
hk
(r)
≤ Jk
(r)
= Tsync − q̂k − δ.
Hence the total completion time of the job submitted at time rTsync satisfies (r)
(r)
(r)
ak = rTsync + qk + hk (r)
(r)
(r)
(r)
(r)
≤ rTsync + qk + Tsync − q̂k − δ = rTsync + Tsync + ek − δ,
(r)
where ek = qk − q̂k . Therefore, if the prediction error satisfies (r)
ek
≤ γTsync + δ,
(4)
then the completion time bound above implies (r)
ak ≤ rTsync + Tsync + (γTsync + δ) − δ = rTsync + (1 + γ)Tsync . Under the buffering rule in Section 3.3 (aggregation at cutoffs (j + 1)Tsync ), any update that arrives by time rTsync + (1 + γ)Tsync is incorporated by at most ⌈1 + γ⌉ subsequent cutoffs, hence its staleness is at most τmax := ⌈1 + γ⌉. Using the sub-Gaussian assumption (1) and standard tail bounds, we obtain for any u > 0 u2 (r) P ek > u | Fr−1 ≤ exp − 2 . 2ρk Set u = γTsync + δ. Then (γTsync + δ)2 (r) P ek > γTsync + δ | Fr−1 ≤ exp − . 2ρ2k By the choice of δ in (2), we have (γTsync + δ)2 exp − 2ρ2k
≤
ε KR
Thus, for each fixed (k, r), (r) P ek > γTsync + δ ≤
for all k ∈ [K].
ε . KR
We now apply a union bound over all k ∈ [K] and r ∈ {0, . . . , R − 1}: ε (r) P ∃k, r such that ek > γTsync + δ ≤ KR · = ε. KR Hence, with probability at least 1 − ε, we have (r)
ek
≤ γTsync + δ
for all k, r.
Next we relate completion time to staleness under the buffering rule (Section 3.3). If a job submitted at time rTsync completes by rTsync + (1 + γ)Tsync , then at most ⌈1 + γ⌉ end-of-round cutoffs elapse between submission and completion. Therefore, the update is incorporated within staleness at most τmax := ⌈1 + γ⌉. Finally, we absorb the factor ε/2 into ε by redefining the target failure probability (or by tightening the constant in (2)). Thus, for any prescribed ε ∈ (0, 1), by choosing δ according to (2) (with a slightly larger constant if needed), we obtain (r) P τk ≤ τmax for all k, r ≥ 1 − ε, which proves (3). 12
FedQueue: Queue-Aware Federated Learning
B. Proof of Theorem 5.5 (r)
We provide a convergence proof for FedQueue under Assumptions 5.1–5.3 and bounded staleness τk
≤ τmax .
(r) Recall the notation: w(r) is the global model at round r, Rk is the round index of the global model used by client k to (r) (r) (r) (r) compute its update incorporated at round r, τk = r − Rk is the staleness, and dk := w(r) − w(Rk ) is the model drift
for client k at round r. (r)
(r,Ek )
(r)
The local update from client k at round r is ∆k = wk ∆(r) := w(r+1) − w(r) =
1
(r)
X
S (r)
(r)
− w(Rk ) , and the global update is (r)
k∈A(r)
(r)
X
S (r) :=
pk ϕ(τk ) ∆k ,
pk ϕ(τk ).
k∈A(r)
(r)
We denote Emin := mink,r Ek . B.1. One-Step Descent Inequality Lemma B.1 (Descent under staleness). Under Assumption 5.1, for any round r, we have: (r) 1 X (r) (r) F (w(r+1) ) ≤ F (w(r) ) + (r) pk ϕ(τk )⟨∇F (w(Rk ) ), ∆k ⟩ S k∈A(r) 2 X 1 (r) L L 1 (r) (r) ∥dk ∥2 + ∥∆k ∥2 + ∥∆(r) ∥2 . pk ϕ(τk ) + (r) 2 2 2 S (r)
(5)
k∈A
Proof. By Assumption 5.1 (L-smoothness), L (r) 2 ∥∆ ∥ . 2
F (w(r+1) ) ≤ F (w(r) ) + ⟨∇F (w(r) ), ∆(r) ⟩ + Using the aggregation rule, * ⟨∇F (w
(r)
(r)
), ∆
⟩=
∇F (w
(r)
),
+
1 S (r)
X
(r) (r) pk ϕ(τk )∆k
=
k∈A(r)
1
X
S (r)
(r)
(r)
pk ϕ(τk )⟨∇F (w(r) ), ∆k ⟩.
k∈A(r)
For each k ∈ A(r) , (r)
(r)
(r)
(r)
(r)
⟨∇F (w(r) ), ∆k ⟩ = ⟨∇F (w(Rk ) ), ∆k ⟩ + ⟨∇F (w(r) ) − ∇F (w(Rk ) ), ∆k ⟩. By Lipschitz continuity and Young’s inequality, (r)
(r)
(r)
(r)
|⟨∇F (w(r) ) − ∇F (w(Rk ) ), ∆k ⟩| ≤ ∥∇F (w(r) ) − ∇F (w(Rk ) )∥∥∆k ∥ (r)
(r)
(r)
(r)
≤ L∥w(r) − w(Rk ) ∥∥∆k ∥ = L∥dk ∥∥∆k ∥ ≤
L2 (r) 2 1 (r) 2 ∥d ∥ + ∥∆k ∥ . 2 k 2
Thus, (r)
(r)
(r)
⟨∇F (w(r) ), ∆k ⟩ ≤ ⟨∇F (w(Rk ) ), ∆k ⟩ +
L2 (r) 2 1 (r) 2 ∥d ∥ + ∥∆k ∥ . 2 k 2
Substituting back completes the proof. B.2. Staleness Drift Accumulation (r)
Lemma B.2 (Drift bound). If τk
≤ τmax for all k, r, then (r)
∥dk ∥2 ≤ τmax
r−1 X
∥∆(t) ∥2 ≤ τmax
r−1 X t=0
(r)
t=Rk
13
∥∆(t) ∥2 .
FedQueue: Queue-Aware Federated Learning (r)
Proof. The drift is the cumulative change in the global model over τk r−1 X
(r)
(r)
dk = w(r) − w(Rk ) =
rounds: r−1 X
(w(t+1) − w(t) ) =
(r) t=Rk
∆(t) .
(r) t=Rk
By the triangle inequality: r−1 X
(r)
∥dk ∥ =
∆(t) ≤
r−1 X
∥∆(t) ∥.
(r)
(r)
t=Rk
t=Rk
By Cauchy-Schwarz: 2 r−1 r−1 r−1 X X X (r) (r) (t) (t) 2 ≤ (r − R ∥∆ ∥∆ ∥ ) ∥ = τ ∥∆(t) ∥2 . k k
(r)
(r)
(r)
Since τk
(r)
t=Rk
t=Rk
t=Rk
≤ τmax , the result follows.
B.3. Local Update Variance and Bias (r)
Lemma B.3 (Local update decomposition). Under Assumptions 5.1–5.3, for each facility k performing Ek local SGD steps starting from w
(r) (Rk )
(r) with learning rate ηk ≤ 1 (r) , there exist absolute constants c1 , c2 , c3 > 0 (independent of 4LE k
k, r) such that (r)
(r)
(r)
(r)
(r)
(r)
(r)
(r)
E[⟨∇F (w(Rk ) ), ∆k ⟩ | w(Rk ) ] ≤ −c1 ηk Ek ∥∇F (w(Rk ) )∥2 + c2 (ηk )2 (Ek )2 (G2 + σk2 ), and (r) (r) (r) (r) E[∥∆k ∥2 | w(Rk ) ] ≤ c3 (ηk )2 (Ek )2
(r)
(R ) ∥∇F (wk k )∥2 + G2 + σk2
(r,0)
Proof. Recall that facility k performs local SGD starting from wk (r,e+1)
wk (r,e)
where gk
(r,e)
= wk
(6)
.
(7)
(r)
= w(Rk ) :
(r) (r,e)
− ηk gk
,
is a stochastic gradient sampled from Dk . The local update is: (r)
(r)
(r) (r,E ) (r) (r) ∆k = wk k − w(Rk ) = −ηk
Ek −1
X
(r,e)
gk
.
e=0
Taking expectation: (r)
(r) (r) (r) E[∆k | w(Rk ) ] = −ηk
Ek −1
X
(r)
(r) (r,e) (r) E[gk | w(Rk ) ] = −ηk
e=0
Ek −1
X
(r,e)
∇Fk (wk
).
e=0
We want to bound: D E (r) (r) (r) (r) (r) (r) E[⟨∇F (w(Rk ) ), ∆k ⟩ | w(Rk ) ] = ∇F (w(Rk ) ), E[∆k | w(Rk ) ] (r)
Ek −1 (r) = −ηk
X e=0
14
h i (r) (r) (r,e) E ⟨∇F (w(Rk ) ), ∇Fk (wk )⟩ | w(Rk ) .
(8)
FedQueue: Queue-Aware Federated Learning
For each term in the sum, we have (r)
(r,e)
⟨∇F (w(Rk ) ), ∇Fk (wk
(r) (r) 1 1 (r,e) ∥∇F (w(Rk ) )∥2 − ∥∇F (w(Rk ) ) − ∇Fk (wk )∥2 2 2 (r) 1 ≥ ∥∇F (w(Rk ) )∥2 2 (r) (r) (r) 1 (R ) (r,e) − 2∥∇F (w(Rk ) ) − ∇Fk (wk k )∥2 + 2∥∇Fk (w(Rk ) ) − ∇Fk (wk )∥2 2 (r) (r) 1 (r,e) ≥ ∥∇F (w(Rk ) )∥2 − G2 − L2 ∥w(Rk ) − wk ∥2 2
)⟩ ≥
From the local SGD update:
∥w
(r) (Rk )
(r,e) (r) − wk ∥2 = (ηk )2
e−1 X (r,j) gk
2 (r)
≤ (ηk )2 e
j=0
e−1 X
(r,j) 2
∥gk
∥ ,
j=0
where the inequality uses Cauchy-Schwarz. Taking expectations and using the variance bound: (r) (r) (Rk ) (Rk ) (r,j) 2 (r,j) 2 E ∥gk ∥ | wk ≤ 2E ∥∇Fk (wk )∥ | wk + 2σk2 . (r,j)
Now we relate ∥∇Fk (wk
(r,j)
)∥2 to ∇F (wk
(r,j)
∥∇Fk (wk (r,j)
so ∥∇Fk (wk
) using Assumption 5.3,
(r,j)
)∥ ≤ ∥∇F (wk (r,j)
)∥2 ≤ ∥∇F (wk
(r,j)
)∥ + ∥∇Fk (wk
(r,j)
)∥ ≤ ∥∇F (wk
(r,j)
− wk k ∥2 .
) − ∇F (wk
(r,j)
)∥ + G,
)∥2 + G2 . By Assumption 5.1, (r,j)
∥∇F (wk
(R
(r)
)
)∥2 ≤ 2∥∇F (wk k )∥2 + 2L2 ∥wk
(R
(r)
)
Combining these gives (r) (r) (r) (r) (Rk ) (Rk ) 2 (Rk ) 2 (Rk ) (r,j) 2 (r,j) 2 2 2 E ∥gk ∥ | wk ≤ C0 ∥∇F (wk )∥ + G + σk + L E ∥wk − wk ∥ | wk , for a constant C0 . Plugging into the drift bound, h i (r) (r) (r,e) E ∥w(Rk ) − wk ∥2 | w(Rk ) e−1 (r) (r) (r) X (Rk ) 2 (Rk ) 2 (Rk ) (r) 2 (r,j) 2 2 2 ≤ C0 (ηk ) e ∥∇F (wk )∥ + G + σk + L E ∥wk − wk ∥ | wk j=0
Using the small step-size condition η ≤ 1/(4LE), one can show by induction on e that the L2 E∥wj − w0 ∥2 part does not explode and can be absorbed into the constant (this is a standard argument in non-convex SGD analyses (e.g., Nguyen et al. (2022)). Concretely, there exists a constant C1 > 0 such that h i (r) (r) (r) (Rk ) 2 (r,e) 2 (r) 2 2 (Rk ) (Rk ) 2 2 E ∥w − wk ∥ | w ≤ C1 (ηk ) e ∥∇F (wk )∥ + G + σk Summing over e gives (r)
Ek −1
X
h
E ∥w
(r)
(Rk )
(r) (r,e) − wk ∥2 | w(Rk )
i
(r) ≤ C1 (ηk )2
(r)
(R ) ∥∇F (wk k )∥2 + G2 + σk2
e=0
(r) EX k −1
e2
e=0 (r) (r) ≤ C2 (ηk )2 (Ek )3
15
(r)
(R ) ∥∇F (wk k )∥2 + G2 + σk2
,
FedQueue: Queue-Aware Federated Learning
where the last inequality uses
PE−1 2 3 e=0 e ≤ E /3. Substituting the bounds to (8), (r)
(r)
(r) (r) (r) η E (r) (r) (r) E[⟨∇F (w(Rk ) ), ∆k ⟩ | w(Rk ) ] ≤ − k k ∥∇F (w(Rk ) )∥2 + ηk Ek G2 2 (r)
Ek −1 (r) + ηk L2
X
i h (r) (r) (r,e) E ∥w(Rk ) − wk ∥2 | w(Rk )
e=0 (r) (r) ηk Ek
(r)
(r)
(r)
∥∇F (w(Rk ) )∥2 + ηk Ek G2 (r) (R ) (r) (r) + C2 L2 (ηk )3 (Ek )3 ∥∇F (wk k )∥2 + G2 + σk2 .
≤−
(r)
Under the step-size constraint ηk
≤
2
(r) 3 C2 1 2 (r) 3 ≤ 64L , so for some (r) , the last term can be bounded as C2 L (ηk ) (Ek ) 4LEk
constant c1 ∈ (0, 0.5) and c2 > 0, we obtain the result (6). To derive the variance bound: h E
i (r)
(r) ∥∆k ∥2 | w(Rk )
(r) = (ηk )2 E
2
(r)
Ek −1
X
(r,e) gk
|w
(r)
(r)
Ek −1
(r) 2 (r) ≤ (ηk ) Ek
X
(Rk )
e=0
(r,e)
2
gk
E
(r) | w(Rk ) ,
e=0
where the inequality holds by Cauchy-Schwarz. Similarly, (r)
Ek −1 h i X 2 (r) (r) (r) 2 (r) 2 (r) (r,e) (Rk ) (Rk ) E ∥∆k ∥ | w ≤ (ηk ) Ek E gk |w e=0 (r) (r) ≤ c3 (ηk )2 (Ek )2
(r)
(R ) ∥∇F (wk k )∥2 + G2 + σk2
.
This completes the proof. B.4. Aggregate Update Norm Lemma B.4 (Aggregate norm and weights). For any round r, ∥∆(r) ∥2 ≤
1 S (r)
X
(r)
(r)
pk ϕ(τk )∥∆k ∥2 .
(9)
k∈A(r)
Proof. The global update is bounded as follows: 2
∥∆(r) ∥2 =
1 S (r)
(r) (r) pk ϕ(τk )∆k
X k∈A(r)
≤
1 (S (r) )2
X
(r) pk ϕ(τk )
k∈A(r)
X
(r) (r) pk ϕ(τk )∥∆k ∥2 =
k∈A(r)
where the inequality holds due to Cauchy-Schwarz. 16
1 S (r)
X k∈A(r)
(r)
(r)
pk ϕ(τk )∥∆k ∥2 ,
FedQueue: Queue-Aware Federated Learning
B.5. Telescoping Sum and Final Convergence Rate We now combine Lemmas B.1–B.4 to prove Theorem 5.5. We take expectations in Lemma B.1 (conditional on the history up to round r): E[F (w(r+1) )] ≤ E[F (w(r) )] (r) 1 X (r) (r) pk ϕ(τk )E[⟨∇F (w(Rk ) ), ∆k ⟩] + (r) S (r)
(Progress)
k∈A
+ + +
1
L2 (r) E[∥dk ∥2 ] 2
(Staleness)
(r) 1 (r) pk ϕ(τk ) E[∥∆k ∥2 ] 2 (r)
(Local Variance)
X
S (r)
(r)
pk ϕ(τk )
k∈A(r)
1
X
S (r)
k∈A
L E[∥∆(r) ∥2 ]. 2
(Global Variance)
By Lemma B.3, (r)
(r)
(r)
(r)
(r)
(r)
(r)
(r)
E[⟨∇F (w(Rk ) ), ∆k | w(Rk ) ⟩] ≤ −c1 ηk Ek ∥∇F (w(Rk ) )∥2 + c2 (ηk )2 (Ek )2 (G2 + σk2 ) (r)
2 2 ≤ −c1 ηbase Emin ∥∇F (w(Rk ) )∥2 + c2 ηbase Emin (G2 + σ 2 )
Substituting this into the Progress term gives: (Progress) ≤ −
(r) c1 ηbase Emin X (r) 2 2 pk ϕ(τk )E[∥∇F (w(Rk ) )∥2 ] + c2 ηbase Emin (G2 + σ 2 ) (r) S (r)
k∈A
(r)
To relate ∥∇F (w(Rk ) )∥2 to ∥∇F (w(r) )∥2 , we use Assumption 5.1: (r)
(r)
∥∇F (w(Rk ) ) − ∇F (w(r) )∥ ≤ L∥dk ∥, which implies (r)
∥∇F (w(Rk ) )∥2 ≥
1 (r) ∥∇F (w(r) )∥2 − L2 ∥dk ∥2 . 2
Combining these, we get: (Progress) ≤ −
c1 ηbase Emin X 1 (r) 2 (r) (r) 2 2 E[∥∇F (w )∥ ] − L E[∥d ∥ ] + c2 ηbase Emax (G2 + σ 2 ) p ϕ(τ ) k k k 2 S (r) (r) k∈A
≤−
c1 ηbase Emin c1 ηbase Emin L2 X (r) (r) E[∥∇F (w(r) )∥2 ] + pk ϕ(τk )E[∥dk ∥2 ] 2 S (r) (r) k∈A
+ c2 ηbase Emax (G2 + σ 2 ). We next bound the Local Variance and Global Variance terms using Lemmas B.3 and B.4. Lemma B.3 gives: (r) (r) (r) 2 2 E[∥∆k ∥2 | w(Rk ) ] ≤ c3 ηbase Emin E[∥∇F (w(Rk ) )∥2 ] + G2 + σ 2 Using Lemma B.4, we have (Global Variance) ≤
X L (r) (r) pk ϕ(τk )E[∥∆k ∥2 ] (r) 2S (r) k∈A
2 2 X (r) Lc3 ηbase Emin (r) (Rk ) 2 2 2 ≤ p ϕ(τ ) E[∥∇F (w )∥ ] + G + σ . k k 2S (r) (r) k∈A
17
FedQueue: Queue-Aware Federated Learning
Similarly, the Local Variance term is (Local Variance) ≤
2 2 X (r) c3 ηbase Emin (r) 2 2 (Rk ) 2 . )∥ ] + G + σ p ϕ(τ ) E[∥∇F (w k k 2S (r) (r) k∈A
Combining these two terms and absorbing constants into c3 > 0, we obtain (Global Variance) + (Local Variance) ≤
2 2 X (r) c3 ηbase Emin (r) 2 2 (Rk ) 2 . )∥ ] + G + σ p ϕ(τ ) E[∥∇F (w k k S (r) (r)
(10)
k∈A
Using the smoothness relation above: (r)
(r)
∥∇F (w(Rk ) )∥2 ≤ 2∥∇F (w(r) )∥2 + 2L2 ∥dk ∥2 , we bound the gradient term in (10) as 1 S (r)
X
(r)
(r)
pk ϕ(τk )E[∥∇F (w(Rk ) )∥2 ] ≤ 2E[∥∇F (w(r) )∥2 ] +
k∈A(r)
2L2 X (r) (r) pk ϕ(τk )E[∥dk ∥2 ]. S (r) (r) k∈A
Substituting this to (10) and absorbing constants, we have 2 2 (Global Variance) + (Local Variance) ≤ c4 ηbase Emin E[∥∇F (w(r) )∥2 ] +
2 2 c5 ηbase Emin L2 X (r) (r) pk ϕ(τk )E[∥dk ∥2 ] (r) S (r) k∈A
2 2 + c6 ηbase Emin
2
G +σ
2
,
for some constants c4 , c5 , c6 > 0. Combining (Progress), (Staleness), (Local Variance), and (Global Variance), we see that all drift-related contributions appear with a common structure 1 X (r) (r) Dr := (r) pk ϕ(τk )E[∥dk ∥2 ], S (r) k∈A
2 2 multiplied by coefficients of order ηbase Emin L2 and ηbase Emin L2 .
By Lemma B.2, the Staleness term is Dr ≤
1 S (r)
X
(r)
pk ϕ(τk )τmax
r−1 X
E[∥∆(t) ∥2 ] = τmax
t=0
k∈A(r)
r−1 X
E[∥∆(t) ∥2 ]
t=0
Lemmas B.3 and B.4 imply that each E[∥∆(t) ∥2 ] is of order X (t) 1 (t) 2 2 pk ϕ(τk )E[∥∇F (w(Rk ) )∥2 ] + G2 + σ 2 E[∥∆(t) ∥2 ] ≤ c3 ηbase Emin S (t) (t) k∈A X (t) (t) 2 2 1 ≤ c3 ηbase Emin pk ϕ(τk ) 2E[∥∇F (w(t) )∥2 ] + 2L2 ∥dk ∥2 + G2 + σ 2 S (t) (t) k∈A
2c η 2 E 2 L2 X 3 base min (t) (t) 2 2 ≤ c3 ηbase Emin 2E[∥∇F (w(t) )∥2 ] + G2 + σ 2 + pk ϕ(τk )∥dk ∥2 S (t) (t)
k∈A
Define as := E[∥∆(s) ∥2 ]. Then we can write (11) as the recursive inequality at ≤ αE[∥∇F (w
(t)
2
2
2
)∥ ] + β(G + σ ) + γ
t−1 X
as
s=0
≤ αE[∥∇F (w(t) )∥2 ] + β(G2 + σ 2 ) + γt max as , 0≤s≤t
18
(11)
FedQueue: Queue-Aware Federated Learning 2 2 2 2 2 2 where α = 2c3 ηbase Emin , β = c3 ηbase Emin , and γ = 2c3 ηbase Emin L2 τmax . Let Mt := max0≤s≤t as . Taking maximum on the left: Mt ≤ α max E[∥∇F (w(s) )∥2 ] + β(G2 + σ 2 ) + γRMt−1 , s≤t
since t ≤ R. Rearranging the RHS term with Mt−1 : 1 (s) 2 2 2 α max E[∥∇F (w )∥ ] + β(G + σ ) Mt ≤ s≤t 1 − γR 1 For small enough ηbase , the factor 1−γR is a finite constant that depends only on (L, τmax , R) and is independent of k, t. Absorb this into a new constant C7 , and focus back on at ≤ Mt : 2 2 2 at = E[∥∆(t) ∥2 ] ≤ c7 ηbase Emin E[∥∇F (w(t) )∥2 ] + L2 τmax + G2 + σ 2 ,
where 2 max ∥∇F (w(s) )∥2 ≤ 2∥∇F (w(t) )∥2 + 2L2 τmax . s≤t
Then, the drift-related term can be bounded as Dr ≤ τmax
r−1 X
(t) 2
2 2 ∥ ] ≤ c7 τmax ηbase Emin
E[∥∆
t=0
r−1 X
! E[∥∇F (w
(t)
2
2 )∥ ] + rL2 τmax + rG2 + rσ 2
.
t=0
Plugging (Progress), (Staleness), (Local Variance), and (Global Variance), we have: c1 ηbase Emin 2 2 E[F (w(r+1) )] − E[F (w(r) )] ≤ − + c4 ηbase Emin E[∥∇F (w(r) )∥2 ] 2 2 2 + (c2 ηbase Emin + c6 ηbase Emin )(G2 + σ 2 ) 1 2 2 L2 Dr + c1 ηbase Emin + c5 ηbase Emin + 2 c1 ηbase Emin 2 2 ≤ − + c4 ηbase Emin + A E[∥∇F (w(r) )∥2 ] 2 2 2 + (c2 ηbase Emin + c6 ηbase Emin + Ar)(G2 + σ 2 ) 2 + ArL2 τmax ,
where
1 2 2 2 2 A = c7 τmax ηbase Emin L2 c1 ηbase Emin + c5 ηbase Emin + 2 Summing over r = 0, . . . , R − 1, and telescoping the left-hand side gives: R−1 R−1 r−1 X XX c1 ηbase Emin 2 2 E[F (w(R) )] − E[F (w(0) )] ≤ − + c4 ηbase Emin E[∥∇F (w(r) )∥2 ] + A E[∥∇F (w(t) )∥2 ] 2 r=0 r=0 t=0 ! R−1 X 2 2 + R c2 ηbase Emin + c6 ηbase Emin +A r (G2 + σ 2 ) r=0 2 + AL2 τmax
R−1 X
r
r=0
≤
−
c1 ηbase Emin 2 2 + c4 ηbase Emin + AR 2
R−1 X
2 2 + R c2 ηbase Emin + c6 ηbase Emin + AR2 2 + AL2 τmax R2
≤ −c8 ηbase Emin
R−1 X
E[∥∇F (w(r) )∥2 ]
r=0
(G2 + σ 2 )
2 2 2 E[∥∇F (w(r) )∥2 ] + c9 Rηbase Emin (L2 τmax + G2 + σ 2 )
r=0
19
FedQueue: Queue-Aware Federated Learning
where there exists a step-size constant small enough to guarantee descent condition. Using F (w(R) ) ≥ F ∗ , we rearrange R−1
E[F (w(0) )] − F ∗ 1 X 2 E[∥∇F (w(r) )∥2 ] ≤ C0 + C1 ηbase Emin (L2 τmax + G2 + σ 2 ), R r=0 ηbase Emin R where C0 = c18 and C1 = cc98 .
C. Additional Details for Large-Scale Experiments This appendix complements Section 6.1 by providing additional details on the experimental setup and per facility-level diagnostics for the cross-facility LLaMA2-7B experiment. C.1. Experimental Setup We configure two F ED Q UEUE runs (FedQueue-1 and FedQueue-2) with synchronization horizon and safety buffer set to (Tsync , δ) = (20, 1) minutes and (Tsync , δ) = (40, 2) minutes respectively. The rest of the parameters are identical across the two F ED Q UEUE runs. All methods use identical per-round resource requests and training hyperparameters. The configurations for the real-world cross-facility deployment and F ED Q UEUE-specific parameters are presented in Table 6. Table 6. Training protocols. Configuration
Value
Model / tuning Sequence length Dataset Optimizer / LR Evaluation Wall-clock budget
LLaMA2-7B / full fine-tuning 512 Partition by task categories (non-IID) AdamW / fixed and fine-tuned LR After each aggregation 17,000 seconds
FedQueue-specific parameters: Tsync 20 min for FedQueue-1; 40 min for FedQueue-2 Safety buffer δ 1 min for FedQueue-1; 2 min for FedQueue-2 EWMA rate α 0.5 Staleness weight ϕ(τ ) harmonic with β = 0.5 (1) Initial budget Ek 20 training steps
C.2. Per Facility-level Diagnoistics While the main text reports consolidated time-to-quality metrics (Figure 2 and Table 1), Figure 5 presents detailed loss trajectories for each method, showing both individual facility and global model performances. Several patterns emerge from the facility-level view. FedAvg maintains relatively synchronized updates across facilities, but this synchronization comes at the cost of slower overall progress due to stragglers. FedAsync shows more rapid early progress, but ultimately plateaus at a higher final loss, suggesting that uncontrolled asynchrony may not be ideally in this real-world deployment case. In addition, FedCompass achieves competitive early performance as well through static queue profiling, but its reliance on fixed estimates causes performance degradation as queue conditions shift over the 5-hour experimental window. Finally, both FedQueue configurations demonstrate more balanced facility utilization while achieving superior final global models, with FedQueue-2’s longer synchronization horizon (40 minutes) enabling better adaptation to queue variability and ultimately reaching the lowest final loss.
D. Controlled Experiments and Extended Results This appendix provides (i) the complete controlled-experiment configuration and (ii) extended results that validate Lemma 5.4 under synthetic queue dynamics. The main text in Section 6.2 reports a compact subset (time-to-quality, expected delay, max delay, Data movement ratio, total local steps); here we include the full sweeps over queue variability, admission tolerance, predictor quality, and safety-buffer stress tests, plus ablations. 20
FedQueue: Queue-Aware Federated Learning
Figure 5. Facility-level loss trajectories for all methods. Each panel shows test loss over time for individual facilities (colored dashed lines) and the federated global model (purple solid line). FedQueue configurations achieve better balance between facility utilization and global model quality.
D.1. Experimental Overview We use synthetic queue processes which let us vary queue variance, prediction quality, and admission thresholds in a reproducible way, directly probing the assumptions behind Lemma 5.4. Table 7 records the dataset/model/optimization and evaluation configuration used for all controlled experiments. Unless stated otherwise, all methods share the same learning workload, compute settings, and evaluation protocol; differences are restricted to orchestration, budgeting, admission, and aggregation. Baselines. We compare F ED Q UEUE against: • FedAvg (McMahan et al., 2017): synchronous FL with fixed local work per round and blocking aggregation. • FedAsync (Xie et al., 2019): fully asynchronous aggregation with a staleness weight w(τ ) = (1 + τ )−1 . • FedBuff (Nguyen et al., 2022): buffered asynchronous FL with a fixed buffer size. • FedCompass (Li et al., 2024a): a system-aware baseline that allocates local work using static throughput profiling without adapting to queue dynamics. Metrics. We report: • Time-to-quality: training loss / validation metric versus elapsed time to reach a target metric. r • Empirical probability of client arrival beyond the cutoff: P(t h i k > Tsync , ∀(k, r))
• Normalized expectation of delay: Êd = E
• Normalized maximum delay: Rd =maxk,r
tk Tsync tk > Tsync , tk Tsync
21
FedQueue: Queue-Aware Federated Learning
Dataset and Partitioning. We use the MNIST handwritten digit classification benchmark with a custom data loader. Unless otherwise stated, each client k receives a disjoint training partition and all clients share a common held-out test set for evaluation. We consider (i) IID partitions and (ii) non-IID partitions generated by a Dirichlet allocation with concentration parameter αdir = 0.5. Each client evaluates on the shared test set to ensure comparable time-to-quality curves across methods. Model. We train a lightweight CNN composed of two 3 × 3 convolution layers with channel sizes (32, 64) and padding 1, each followed by 2 × 2 max pooling, then a fully connected layer 64 · 7 · 7 → 128, dropout p = 0.5, and a final 10-way linear classifier. ReLU activations are used throughout. The objective is cross-entropy and we report test accuracy as the primary quality metric. Hyperparameter Optimization. We performed a targeted hyperparameter sweep focusing on the learning rate and batch size, while holding all other training settings fixed to isolate their effects. The learning rate was explored over the set {0.001, 0.003, 0.005, 0.0001, 0.0005}, and the batch size over {32, 64, 96, 128}. Each configuration was evaluated using the same training protocol and validation metric, and the optimal setting was selected based on validation accuracy. This search identified a learning rate of 0.003 with a batch size of 64 as the best-performing combination for our experiments. To support reproducibility, Table 7 summarizes the core hyperparameters. Baseline Implementation. We implemnted all the reported baseline methods using APPFL (Ryu et al., 2022), and varied the respective hyperparameters according to Table 7 to simulate the impact of queue variance, and admission control. D.2. Queue Knobs and Sweep Design We vary three parameters aligned with Lemma 5.4: (i) queue variability via the sub-Gaussian scale ρk , (ii) admission (r) (r) (r) tolerance γ (implying τmax = ⌈1 + γ⌉), and (iii) prediction quality via EWMA rate α controlling the error ek = qk − q̂k and thus the safety-buffer requirement. All sweeps are reported using pre-specified artifacts (Figures 6, 7, 8 and Table 8). Rho sweep (staleness concentration). Figure 6 illustrates the empirical CDF of client arrivals beyond Tsync under increasing queue variability for both IID and non-IID data partitions. Under low queue variance (ρk = 0.1), the CDF rises sharply: over 90% arrive before 8 seconds. As queue variability increases, the delay distribution becomes progressively heavier tailed. For ρk = 0.5, the 90th percentile shifts to roughly 10–12 seconds, while for ρk = 0.9 it extends beyond 15 seconds. The vertical dashed line marking Tsync highlights that although the majority of updates still arrive before the cutoff, the tail mass near the boundary increases from only a few percent at ρk = 0.1 to well over 10% at ρk = 0.9. This trend is consistent across both IID and non-IID regimes, with the non-IID case exhibiting a slightly heavier tail.
rho=0.1 rho=0.5 rho=0.9
Tsync
Tsync
rho=0.1 rho=0.5 rho=0.9
Figure 6. Staleness under queue variance. Empirical CDF of clients arrived beyond Tsync under a sweep of ρ. This plot audits the bounded-staleness behavior induced by ρ.
Gamma sweep (time-to-quality). Figure 7 shows how tightening/relaxing admission tolerance γ affects the time-to-quality and convergence across baselines. Across all γ values, F ED Q UEUE consistently reaches high accuracy earlier than competing baselines. In the IID case, F ED Q UEUE with γ = 0.9 surpasses 98% validation accuracy within roughly 30–40 seconds, whereas FedBuff and FedCompass require approximately 60–90 seconds to reach the same level. Under non-IID data, the gap widens: F ED Q UEUE reaches 95% accuracy in about 70–90 seconds, while FedBuff and FedCompass typically require 150–200 seconds. Increasing γ accelerates early convergence for all methods; however, F ED Q UEUE exhibits the strongest 22
FedQueue: Queue-Aware Federated Learning
sensitivity.
Figure 7. Time-to-quality varying admission parameter. Validation accuracy versus elapsed time under a sweep of admission parameter γ (low/medium/high or a multi-level sweep). F ED Q UEUE consistently converges faster and reaches the highest accuracy compared to the baselines for both IID and non-IID cases.
Alpha sweep (staleness concentration). Figure 8 shows how tightening/relaxing EWMA rate α affects the empirical CDF of clients arriving after Tsync . Both α = 0.1 (slow tracking) and α = 1.0 (aggressive tracking) exhibit samples extending beyond the synchronization horizon Tsync , indicating that overly conservative smoothing and overly reactive delay estimation can each induce late client arrivals. In contrast, the moderate choice α = 0.5 ensures all client updates arriving within the synchronization window Tsync , which is consistent across both IID and non-IID settings.
Tsync
Tsync
Figure 8. Staleness under EWMA rate (α) variation. Empirical CDF of clients arrived beyond Tsync under a sweep of α. This plot audits the bounded-staleness behavior induced by α.
Bound verification grid. Table 8 reports violation frequencies, and maximum observed delay across a representative grid of (ρk , γ, α) settings, together with time-to-target. 23
FedQueue: Queue-Aware Federated Learning Table 8. Bound verification grid (controlled). For each setting in a representative (ρk , γ, α) grid, we report the empirical probability of client arrival beyond the cutoff, P, Normalized expectation of delay, Êd , Normalized maximum delay, Rd , and the wall-clock time to reach target accuracy A⋆ (95%).
ρ
δ
α
P↓
Êd ↓
Rd ↓
Time-to-A⋆ (s)↓
0.1 0.5 0.9
4 4 4
0.5 0.5 0.5
0.000 0.020 0.035
1.14 1.38
1.18 1.52
156.65 159.31 163.95
0.1 0.1 0.1
1 2 4
0.5 0.5 0.5
0.035 0.015 0.000
1.32 1.06 -
1.56 1.17 -
146.66 151.89 156.65
0.1 0.1 0.1
4 4 4
0.1 0.5 1.0
0.015 0.000 0.020
1.32 1.34
1.44 1.46
162.73 156.65 164.62
24
FedQueue: Queue-Aware Federated Learning
Table 7. Controlled experiment configuration and hyperparameters. This table consolidates the controlled-workload specification (MNIST + CNN) and the concrete run configuration/hyperparameters used in Appendix C sweeps (queue variability, admission tolerance, and prediction quality). Parameter
Value
Role / notes
Workload (data/model/metric) Dataset Partition data.alpha Model
MNIST iid / non-iid 0.5 SimpleCNN
loss.name
CELoss
Custom data loader; shared held-out test set across clients. Non-iid via Dirichlet allocation. Dirichlet concentration (for non-iid). 2 conv (3×3) with channels (32,64), max-pool, FC 64 · 7 · 7 → 128, dropout 0.5, 10-way head. Cross-entropy objective.
Federated protocol (shared across baselines) seed num clients num rounds gpus batch size Optimizer local steps
42 4 50 cuda:0,1,2,3 64 Adam 100
Reproducibility seed. Number of participating clients. Total FL communication rounds. GPU devices assigned to clients (local testbed / simulation). Client runtime config. Client runtime config. Client runtime config (per admitted update unless otherwise specified).
FedQueue orchestration / queue model knobs (swept in Appendix C) algo.name fedqueue immediate / next round algo.broadcast when algo.delay mode simulate / sleep Tsync 10.0 2.0 q init gamma 0.2 delta 2.0 alpha 0.5 10 warmup steps lognormal sim queue queue fixed 0.5,1.5,2.4,6 queue means 1.5,2.5,3.5,4.5 queue rho 0.4 slowdown 1.0,1.0,1.0,1.0 harmonic staleness mode staleness phi 0.5 horizon admission horizon client weight mode equal 0.003 lr base 67,155,147,15 fedavg.num local steps
Algorithm selector (fedqueue/fedavg/fedasync/fedbuff/fedcompass). Broadcast timing policy. Delay handling (simulation vs. wall-clock sleeping). Target sync window (Tsync ). Initial delay prior for admission control. Slack fraction on Tsync for admission windowing. Safety buffer inside budget Jk (maps to safety-buffer scaling). EWMA smoothing for delay estimate q̂k . Warm-up steps to estimate throughput ck . Queue model (fixed / lognormal). Fixed delays per client (if sim queue=fixed). Lognormal means per client. Lognormal standard deviation. Compute slowdown multipliers per client. Staleness decay (harmonic / exp). Staleness decay strength. Admission policy (horizon / all). Client weight mode (equal / data size). Base learning rate. Local steps per client under FedAvg path.
Global AsyncFL settings num local steps staleness fn staleness fn kwargs alpha optimize memory
155 polynomial {a=1.0} 0.5 true
Number of local update steps per client Staleness decay function (constant / polynomial / hinge) Polynomial decay coefficient Staleness scaling factor Enables memory-optimized aggregation
FedBuff overrides K
2/3/4
Buffer size (number of updates before aggregation)
FedCompass overrides staleness fn staleness fn kwargs alpha max local steps min local steps speed momentum latest time factor
polynomial {} 0.5 200 20 0.6 1.1
Staleness-aware weighting function Uses default polynomial parameters Staleness scaling factor Upper bound on adaptive local steps Lower bound on adaptive local steps Momentum term for client speed estimation latest allowable arrival window
25