arXiv CSopen access

Robust Synchronisation for Federated Learning in The Face of Correlated Device Failure

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

cloud distributedcomputing parallelcomputing

distributed computing, parallel computing, cloud

Robust Synchronisation for Federated Learning in The Face of Correlated Device Failure Stefan Behfar1 , Richard Mortier1 1 Computer Lab, University of Cambridge, Cambridge, United Kingdom

arXiv:2604.16090v1 [cs.DC] 17 Apr 2026

Abstract Probabilistic Synchronous Parallel (PSP) is a technique in distributed learning systems to reduce synchronization bottlenecks by sampling a subset of participating nodes per round. In Federated Learning (FL), where edge devices are often unreliable due to factors including mobility, power constraints, and user activity, PSP helps improve system throughput. However, PSP has a key limitation: it assumes device behavior is static and different devices are independent. This can lead to unfair distributed synchronization, due to highly available nodes dominating training while those that are often unavailable rarely participate and so their data may be missed. If both data distribution and node availability are simultaneously correlated with the device, then both PSP and standard FL algorithms will suffer from persistent under-representation of certain classes or groups resulting in inefficient or ineffective learning of certain features. We introduce Availability-Weighted PSP (AW-PSP), an extension to PSP that addresses the issue of co-correlation of unfair sampling and data availability by dynamically adjusting node sampling probabilities using real-time availability predictions, historical behavior, and failure correlation metrics. A Markov-based availability predictor distinguishes transient vs chronic failures, while a Distributed Hash Table (DHT) layer decentralizes metadata, including latency, freshness, and utility scores. We implement AW-PSP and trace-driven evaluation shows that it improves robustness to both independent and correlated failures, increases label coverage, and reduces fairness variance compared to standard PSP. AW-PSP thus provides an availability-aware, and fairness-conscious node sampling protocol for FL deployments that will scale to large numbers of nodes even in heterogeneous and failure-prone environments.

Introduction

Traditional approaches to synchronization in federated learning include Bulk Synchronous Parallel (BSP) and Asynchronous Parallel (ASP). BSP requires all workers to provide updates in one round before proceeding to the next, ensuring deterministic correctness but risking significant delays due to slow or unreliable nodes (termed stragglers) [1]. In contrast, ASP requires no synchronization at all between nodes, allowing updates to occur as quickly as possible but risking stragglers introducing stale gradients making convergence very unstable [2]. A middle ground is Stale Synchronous Parallel (SSP), which allows bounded delays before synchronization, reducing the impact of stragglers in BSP as well as the problem of stale gradients in ASP. However, it still

requires global state tracking, which becomes increasingly difficult at scale [3]. Many have explored ways to mitigate the impact of stragglers in Federated Learning (FL). Gradient coding [4] reduces the dependency on slow nodes by redundant encoding of gradients so the system can recover the full gradient even when some workers lag or fail. However, this targets synchronous training setups and does not address the unpredictable availability of nodes in federated environments. Sageflow [5] dynamically adjusts weight updates from clients when aggregating updates, mitigating the negative impact of unreliable or malicious nodes. While effective, its reliance on robust aggregation can fail to mitigate delays due to intermittent node participation. FLuID [6] uses invariant dropout to selectively ignore contributions from slow clients while maintaining model convergence. However, ignoring slow nodes altogether can reduce model diversity and hinder convergence in heterogeneous environments. Some FL frameworks such as Flower [7] and Flame [8] ignore node availability. Others, e.g., FedScale [9], Oort [10], and Google’s token-based availability model [11], have considered it but either rely on historical availability traces or perform system check-ins while empirical studies report that node availability fluctuates significantly, between 10%—80% across different datasets [9, 11, 12], and FL systems that ignore this can experience a drop in accuracy of up to 50% in real-world scenarios [13]. Probabilistic Synchronous Parallel (PSP) took a different approach, sampling a random subset of nodes to participate in the synchronization barrier for a given round. This eliminates the need for a central state controller, reduces bandwidth overheads thereby increases scalability as more nodes are involved, and significantly reduces the impact of stragglers as they can simply be ignored without weakening probabilistic convergence guarantees [14]. However, all the above approaches suffer from (i) participation unfairness, and (ii) data availability co-correlation. Participation unfairness arises when always-available nodes (e.g., desktop clients or stable cloud servers) dominate the training process, while intermittently available or mobile devices are rarely selected. This skewed participation reduces the diversity of training data, degrades personalization performance, and can amplify societal or geographic biases in the resulting models. Traditional approaches such as uniform random sampling (e.g., PSP [14]), check-in based (e.g., Google FL [11]), or trace-replay strategies (e.g., FedScale [9], Oort [10]) fail to address this imbalance effectively. Data availability co-correlation is a challenge because devices may become unavailable in correlated patterns for many reasons, from using shared infrastructure (e.g., the

same WiFi network or power supply) to being subject to shared user behaviors (e.g., devices being turned off at the same time due to sleep patterns). Such correlations in device unavailability lead to correlations in missing data as those devices are likely to have data with similar label distributions (e.g., when trying to learn features from local processing of SMS messaging data, timezones mean that data in particular languages may become simultaneously unavailable). Existing FL systems largely ignore such patterns, assuming node failures to be independent, leading to fragile training dynamics, stalled rounds, and poor fault tolerance. We begin by articulating and demonstrating these problems next (§2). In response we propose AW-PSP, a failure-resilient node selection mechanism that extends PSP with dynamic availability modeling and fairness-aware weighting. Unlike static and trace-based methods, AW-PSP predicts device availability in real time using lightweight Markov chains, allowing it to distinguish between transient and chronic failures, adapting sampling accordingly. It also reweights node selection based on both historical availability and recent utility, ensuring that even infrequently available but highly valuable participants are included. AW-PSP accounts for correlated failures by combining behavioral similarity (co-occurring availability patterns) with structural co-failure risks inferred from proximity metrics such as latency and packet loss. These signals are used to adjust per-node selection probabilities, actively diversifying participation to avoid synchronized dropouts. Finally, a Distributed Hash Table (DHT) overlay decentralizes metadata sharing, so that availability, latency, and freshness are propagated in a scalable and fault-tolerant manner, enabling proximity-aware and failure-resilient scheduling (§3). We evaluate AW-PSP by isolating the impact of (un)availability on learning, using published trace data to model correlated and uncorrelated device unavailability coupled with ResNet18/34 models applied to learn features of the CIFAR-10 dataset. We are not seeking to benchmark AW-PSP against the full landscape of client selection methods (Oort, FedGS, CA-Fed, etc) which often target faster convergence or throughput optimization under different assumptions. Rather, we consider how the additional mechanisms of AW-PSP improve performance over “classic PSP” in terms of fairness across nodes and classes, class coverage, and resilience (§4). We finish with a discussion of related work (§5) and presentation of conclusions (§6). Our contributions are threefold: (i) we articulate and quantify the negative impact of availability unawareness in FL (§2); (ii) we extend PSP with mechanisms that mitigate the effects of device unavailability (§3); and (iii) we show both analytically and empirically that incorporating availability and failure awareness through these mechanisms improves fairness without sacrificing robustness (§4). PSP is a simple yet strong baseline for synchronization in distributed settings, and our results establish that AW-PSP preserves its lightweight and practical design while addressing previously 2

overlooked issues of correlated failures, update starvation, and fairness imbalance. AW-PSP is thus a principled improvement over PSP that is in many ways orthogonal to rather than a universal replacement for existing FL client selection frameworks.

The Problem

Previous works in the Fair FL literature have assumed that client availability is uncorrelated with data distribution [15, 16]. This assumption makes analysis easier but unfortunately fails to capture real-world dynamics where correlations exist between certain types of data and client availability. This leads to systematic under-representation of certain groups/ classes, even when target weights are set to ensure proportionality of contribution to the learning process with respect to the amount of data available at each client. We begin by demonstrating the practical impact of dataavailability co-correlation on system performance. Using Mininet [17] we emulate a small FL system comprising 10 clients, each exhibiting realistic device behavior such as intermittent availability due to charging, sleep cycles, or user activity. These clients simulate common patterns of correlated behavior observed in practice and enable us to examine how clients (groups) becoming unavailable at the same time can slow training progress and create fairness imbalances, regardless of whether the network itself is congested. We examine how client unavailability affects model inference accuracy when unavailability is both correlated and uncorrelated with features of the training data distributed across clients. This enables detailed evaluation of how different unavailability modes—mirroring real outages—impact federated learning outcomes in a controlled, yet realistic, network environment. Specifically, we fine-tune a ResNet34 [18] model on a subset of the CIFAR-10 [19] dataset using federated training over 50 epochs with Cross Entropy Loss [20] and the Adam optimizer [21]. The central server broadcasts the current global ResNet-34 model to all active workers, each of which performs 𝐸 local training epochs on its class-specific data using cross-entropy loss and the Adam optimizer. Workers then send their locally updated model weights back to the server, which aggregates them by computing a weighted average. The global model is updated with this averaged state, and the process repeats for a total of 50 communication rounds. We assign data from specific CIFAR-10 classes evenly among workers, 𝑤 1, . . . , 𝑤 𝑁 , and train a ResNet34 DNN model from the resulting data distributions according to FedAvg [15]. After training we simulate an inference task by sending a mini-batch of images to each host, emulating real-world edge deployments where inference is performed locally on distributed devices after a federated training phase. We then implemented a process for inducing correlated unavailability across different groups of client devices. We

other dropouts and reconnections at random to simulate behaviours such as signal loss, device reboots, and app interruptions that would occur in practice. This sampling process thus explores two different behaviours: (i) random where each node becomes unavailable independently with a fixed probability, simulating uncorrelated unavailability, and (ii) correlated where nodes fail with probability dependent on the correlation of their unavailability with other nodes – so if one of two nodes that exhibit correlation above a threshold becomes unavailable, so does the other – simulating correlated unavailability. The results (averaged over 5 retrials) show a clear structural difference between random and correlated unavailability. Under random failures (Table 1), each host fails independently with probability 𝑝 𝑓 , producing a stochastic spread of unavailable nodes. As 𝑝 𝑓 increases, the number of active hosts decreases gradually. Performance exhibits distinct plateaus determined by the number of labels per client (approximately 73%, 76%, and 78.5% for labels/client = 1, 5, and 10, respectively). This indicates that, under random failures, the reported mean accuracy is largely governed by the underlying data partitioning—specifically label coverage—rather than the exact number of active participants, provided that sufficient clients remain to cover the label space. This stability is partly a consequence of the evaluation protocol: accuracy is computed only over labels that remain covered by at least one active host, and missing labels are excluded rather than counted as errors. When the number of active clients drops below this implicit coverage threshold, large portions of the label space become unrepresented, leading to sharp degradation in (or even undefined) accuracy. Under correlated failures (Table 2), unavailability is clustered in that hosts fail together if they share high availability correlation, defined by a threshold 𝑐. For low correlation thresholds (𝑐 ≤ 0.4), all hosts can become unavailable simultaneously, resulting in complete system collapse and zero accuracy. Once the correlation threshold exceeds that threshold (𝑐 ≥ 0.5), the system transitions sharply from minimal participation (1–2 active hosts) to a stable operating regime with sufficient active clients. Notably, the mean accuracy immediately recovers to plateau levels comparable to random failures, showing that co-correlation primarily affects availability, not model quality. This demonstrates that correlated failures introduce abrupt, threshold-driven system instability that is not captured by independent failure models. The per-class results (Tables 3 and 4) further highlight this distinction. Under random failures, class coverage degrades in a scattered manner, with different subsets of labels missing across runs. In contrast, correlated failures produce structured coverage gaps, where specific groups of classes disappear together due to shared availability patterns. When only a small number of hosts remain active, the model is effectively trained on a reduced label space, leading to biased predictions. This effect is most pronounced for labels/client

Figure 1. Distribution of device availability percentages for the trace data [22], where device availability percentage is defined as the percentage of time between the first and last times a device was seen to be live and available to perform FL, i.e., was charging and connected to Wi-Fi. Out of 1000 devices in the trace, 213 were available for <5% of the time, and over 60% were available for less than half the time.

started with the trace of devices involved in an FL system published by [22]. Based on the availability trace data provided in the GitHub link associated with [22], the distribution of device availability percentages in Figure 1 indicates that the majority of devices exhibit less than 40% availability, where device availability percentage is defined as the percentage of time between the first and last times a device was seen to be live that it was available to perform FL, which presents challenges for designing reliable and robust distributed or FL systems over these edge devices. When high unavailability happens in a correlated manner, large groups of devices become simultaneously unavailable. This can drastically reduce the number of available clients, sometimes leaving too few (if any!) devices to participate. This trace contains a number of timestamped events per device, including WiFi on and battery charging on which we take in combination to indicate that a device is networkconnected and plugged in (ready to participate in federated training according to Google [11]), followed by WiFi off or battery charged off which we take to indicate that the device has now gone to sleep, i.e., has become unavailable. We randomly sample from that trace to produce per-client device availability traces, where device availability is correlated as described, over a specified number of time steps. To compute the correlations between client availability, we first generate binary availability vectors for each client with 1/0 indicating that the client is active/inactive in each time step. We then calculate the pairwise correlation matrix from these vectors, quantifying how much clients become unavailable and remain unavailable together. We also intermingle 3

Table 1. Summary results under random failures for different numbers of labels per client. 𝑝𝑓 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

Labels/client = 1 Mean Acc. Active Failed 73.50 10 0 73.50 10 0 75.63 8 2 67.50 6 4 78.33 3 7 65.00 5 5 76.25 4 6 85.00 1 9 – 0 10

Labels/client = 5 Mean Acc. Active Failed 76.00 9 1 76.00 9 1 76.00 9 1 76.00 7 3 76.00 5 5 76.00 3 7 76.00 2 8 – 0 10 76.00 2 8

Labels/client = 10 Mean Acc. Active Failed 78.50 10 0 78.50 7 3 78.50 3 7 78.50 4 6 78.50 6 4 78.50 6 4 78.50 1 9 78.50 2 8 – 0 10

Table 2. Summary results under correlated failures for different numbers of labels per client. 𝑐 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

Labels/client = 1 Mean Acc. Active Failed – 0 10 – 0 10 – 0 10 – 0 10 70.00 1 9 60.00 2 8 66.67 6 4 73.50 10 0 73.50 10 0

Labels/client = 5 Mean Acc. Active Failed – 0 10 – 0 10 – 0 10 – 0 10 83.00 1 9 83.00 2 8 76.00 6 4 76.00 10 0 76.00 10 0

= 1, where each client contributes a narrow slice of the data distribution and correlated unavailability can eliminate entire regions of the label space. For higher label densities (5 and 10), although individual clients hold more diverse data, correlated failures can still remove overlapping subsets of labels simultaneously. As a result, redundancy does not fully prevent coverage loss; instead, it mainly stabilizes performance once a sufficient subset of classes remains available, preserving the plateau behavior observed in the aggregate results. Overall, the number of active hosts determines whether the system is operational, while the joint structure of data partitioning and availability correlation determines the effective training distribution and thus the achievable accuracy. Random failures primarily reduce participation, whereas correlated failures reshape the data distribution itself by removing coherent subsets of clients. Increasing labels per client improves robustness by introducing redundancy in class coverage, making the system resilient to both forms of unavailability. Conversely, sparse partitions amplify the impact of correlated failures, leading to threshold-driven collapse, systematic bias, and reduced generalization. These findings (relevant to non-IID effects and data heterogeneity) align with prior work on mitigating non-IID effects through data sharing, personalized FL, or heterogeneity-aware aggregation techniques [23–29], highlighting the critical interplay between failure dynamics and data heterogeneity in shaping system behavior.

Labels/client = 10 Mean Acc. Active Failed – 0 10 – 0 10 – 0 10 – 0 10 78.50 1 9 78.50 2 8 78.50 6 4 78.50 10 0 78.50 10 0

Availability Weighted PSP

In AW-PSP, the probability of selecting a node is no longer uniform as in Classic-PSP, but instead depends on a composite availability score that incorporates three factors: the node’s ability to complete both computation and communication within a tolerable deadline, its likelihood of recovering from recent failures, and its risk of being affected by correlated failures with nearby nodes. Concretely, each node’s selection probability combines its empirical availability (estimated through recent success rates of computation and communication), a recovery probability that accounts for transient failures and allows temporarily offline nodes to rejoin, and a group-level correlation penalty that reduces the weight of nodes likely to fail together (e.g., on the same subnet or switch). These availability estimates are further refined by blending local history with information from neighboring nodes in the DHT overlay, ensuring that proximity in terms of latency and computation speed also informs the sampling. By embedding these enhanced availability scores into the PSP framework, AW-PSP adaptively prioritizes nodes that are both reliable and diverse, thereby mitigating stragglers, reducing synchronization delays, and improving fairness compared to the purely random selection of Classic-PSP. 3.1

Modeling Node Availability

Node availability can be defined as: comp

𝑎𝑖 (𝑡) = 𝑃 (𝑇𝑖 where: 4

(𝑡) + 𝑇𝑖comm (𝑡) ≤ 𝑇max )

(1)

Table 3. Per-class accuracies under random failures for labels/client = 1, 5, and 10. Empty cells indicate no value could be computed because no response was received from a host trained on that class. 𝑝𝑓 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

1 65 65 65 65 90 65 90 85

2 90 90 90 50 70 50 50

3 50 50 85 70 75 50 85

Labels/client = 1 4 5 6 7 85 70 80 50 85 70 80 50 70 50 75 85 50 85 85 75 80

8 75 75 85

9 85 85

10 1 85 56 85 56 85 56 66 66 83

2 85 85 76 80 80 72 69

3 80 80 92 72 91 83

Labels/client = 5 4 5 6 7 90 72 80 76 72 90 76 80 75 76 80 55 91 76 77 72 72 77

8 80 80 88

9 72 72 50

1 90 70 77 84 80 80 79 80

2 80 77 76 82 73 73

Labels/client = 10 4 5 6 7 8 80 60 65 70 85 93 80 77 65

3 85 83 83 76 80 80

72 73 73

80 80

9 10 95 75

87 87

Table 4. Per-class accuracies under correlated failures for labels/client = 1, 5, and 10. Empty cells indicate no value could be computed because no response was received from a host trained on that class. 𝑐 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

70 50 65 65 65

70 90 90 90

50 50 50

Labels/client = 1 4 5 6 7

70 85 85

50 70 70

75 80 80

50 50

75 75

85 85

83 76 66 85 85

90 76 85 85

92 80 80

Labels/client = 5 4 5 6 7

76 75 75

comp

• 𝑇𝑖 (𝑡) is the computation time of node 𝑖 for the current training round. • 𝑇𝑖comm (𝑡) is the communication delay for sending the model update. • 𝑇max is the maximum tolerable delay before a node is considered unavailable. A node is available if it can complete and communicate updates within 𝑇max with high probability. We estimate 𝑎𝑖 (𝑡) using historical response times with an exponentially weighted moving average (EWMA): comp

𝑎𝑖 (𝑡) = 𝜆𝑎𝑖 (𝑡 −1) + (1−𝜆)𝐼 (𝑇𝑖

(𝑡) +𝑇𝑖comm (𝑡) ≤ 𝑇max ) (2)

where, 𝐼 (·) is an indicator function. 𝜆 (e.g., 0.9) controls the decay rate, giving more or less weight to recent behavior. (

72 80 80

80 80

55 55

80 80

Labels/client = 10 4 5 6 7

50 50

79 80 80 90 90

77 73 80 80

80 85 85

73 80 80

85 85

95 95

75 75

80 60 60

87 65 65

70 70

2. Computation proximity: comp

Δ𝑇𝑖,𝑗

comp

= |𝑇𝑖

comp

Δ𝑇𝑖,𝑗

comp

− 𝑇𝑗

≤ 𝜏𝑐

(6) (7)

We estimate computation and communication availability using recent history across the last 𝑇 rounds: 𝑇

comp

𝑎𝑖

1 ∑︁ comp 𝐻 (𝑡), 𝑇 𝑡 =1 𝑖

𝑇

𝑎𝑖comm =

1 ∑︁ comm 𝐻 (𝑡) 𝑇 𝑡 =1 𝑖

(8)

comp

(𝑡) = 1 if the node has participated in more than • 𝐻𝑖 a threshold fraction of rounds (70%) up to time 𝑡, and 0 otherwise. 𝜏𝑐 is a threshold for historical success rate. • 𝐻𝑖comm (𝑡) = 1 if latency is below a threshold 𝜏lat (e.g., 100 ms) and packet loss below a threshold 𝜏loss (e.g., 40%), and 0 otherwise.

if node 𝑖 finished on time The overall availability is then: otherwise (3) comp Predicting node availability based on DHT: To predict 𝑎𝑖 (𝑡) = 𝑎𝑖 · 𝑎𝑖comm (9) node availability in computation and communication, we Availability based on recovery probability: The releverage Distributed Hash Table (DHT)-based metadata to covery probability, 𝛽𝑖 , represents the likelihood that a node benefit from Physical and Computation Proximity: will recover from a failure in the current round and return 1. Physical proximity: to completing its tasks within the maximum allowable time. The recovery probability 𝛽𝑖 is modeled as the conditional 𝑑𝑖,𝑗 = 𝑅𝑇𝑇𝑖,𝑗 = 𝑅𝑇𝑇 𝑗,𝑖 (4) probability that the node will meet the deadline in the next 𝑑𝑖,𝑗 ≤ 𝜏𝑑 (5) round, given that it failed in the previous round. We define 5

comp 𝐼 (𝑇𝑖 (𝑡)+𝑇𝑖comm (𝑡) ≤ 𝑇max ) =

1, 0,

88 90 90

𝛽𝑖 as:

adj

𝑎𝑖 (𝑡) = 𝑎˜𝑖 (𝑡) · (1 − 𝜌𝑖 (𝑡)) (14) (10) This formulation downweights nodes that are heavily entangled in unreliable clusters, improving resilience against # times node 𝑖 recovered after a failure (in last 𝑇 rounds) cascading or simultaneous failures. comp

(𝑡 + 1) + 𝑇𝑖comm (𝑡 + 1) ≤ 𝑇max comp 𝑇𝑖 (𝑡) + 𝑇𝑖comm (𝑡) > 𝑇max

𝛽𝑖 (𝑡) = Pr 𝑇𝑖

𝛽𝑖 (𝑡) ≈

# times node 𝑖 failed in last 𝑇 rounds which takes into account the node’s previous failures and provides a more nuanced prediction for future availability. This approach assumes that there is some likelihood that a node may recover from a failure, possibly due to transient network issues, resource availability changes, or system optimization. Future availability is estimated based on the node’s previous availability and its predicted return probability: 𝑎˜𝑖 (𝑡) = 𝑎˜𝑖 (𝑡 − 1) + (1 − 𝑎˜𝑖 (𝑡 − 1))𝛽𝑖 (𝑡)

3.3

We define the final sampling probability 𝑝𝑖′ for each node 𝑖 below. The theoretical justification and guarantees aree discussed in appendix A. comp comm comp 𝑝𝑖′ (𝑡) = 𝑝· 𝑎𝑖 · 𝑎𝑖 + 1 − 𝑎𝑖 · 𝑎𝑖comm · 𝛽𝑖 (𝑡) ·(1 − 𝜌𝑖 (𝑡)) (15) where: • 𝑝 is the baseline uniform sampling probability, comp • 𝑎𝑖 · 𝑎𝑖comm is the immediate availability estimate of node 𝑖, • 𝛽𝑖 (𝑡) is the return (recovery) probability if the node was recently unavailable, • 𝜌𝑖 (𝑡) is the correlation penalty capturing the node’s entanglement with unstable peers (frequently failing, dropping, or unreliable).

(11)

where 𝑎˜𝑖 (𝑡) is the baseline availability estimate. 3.2

Modeling Runtime Co-Correlation in Federated Edge Environments

In real-world federated systems, device failures and unavailabilities are often correlated rather than independent. Devices co-located in the network topology (e.g., sharing the same subnet or region) or exhibiting similar usage patterns (e.g., nighttime disconnection) may fail together.

Evaluation

Our methodological goal is to isolate the effects of availabilityweighted sampling and correlated failures on distributed synchronization. Below we quantify the workload and show that a single, well-provisioned workstation suffices while preserving experimental control and reproducibility. Workload characteristics. CIFAR-10 occupies ∼170 MB on disk; when cached as float32, it requires ∼220 MB RAM if fully resident, but our experiments stream in mini-batches or single images during inference, keeping the steady-state working set substantially lower. We use ResNet-18/34 for inference on containerized clients. ResNet-18 has ∼11.7M parameters (∼45 MB weights), ResNet-34 ∼21.8M (∼85 MB weights). With batch size 32 and no gradient storage, perprocess inference memory is typically ∼150–300 MB (weights + activations + framework/runtime). We start with 10 concurrent physical clients plus one coordinator. Training and Resource implications. Training increases per-process memory and CPU demands due to activations, optimizer state, and gradient buffers. We use a single server host with 64 GB RAM and 110 vCPUs (our bottleneck); also we adopt practical mitigations: (i) small local batch sizes of 32 images, (ii) modest model variant (ResNet-18) which emulates a mobile device resource capacity, and (iii) Docker resource limits to emulate heterogeneous device capacities. In reality, each client utilizes up to 800% CPU (Saturating all 8 cores) with an average memory usage of 687 MB. Each global round consists of (i) selecting a subset of clients according to the sampling policy (AW-PSP or ClassicPSP), (ii) dispatching the current global model to the selected

trace ). This denotes a static Trace-based correlation (𝛾𝑖,𝑗 correlation score between nodes 𝑖 and 𝑗, computed offline from their historical binary availability traces. It is loaded before the simulation and remains fixed during execution. This score captures long-term similarity in availability behavior. fail

Runtime co-failure correlation (𝛾𝑖,𝑗 (𝑡)). This denotes a dynamic co-failure score between nodes 𝑖 and 𝑗 at round 𝑡, computed from the history of rounds in which both nodes were observed as failed. In the implementation, each pair of failed neighboring nodes records the current round in a failure_correlation structure, and the runtime score is defined as the fraction of elapsed rounds in which the pair has failed together. This score is updated online during execution and captures recent correlated-failure behavior. trace fail 𝛾𝑖,𝑗 (𝑡) = 𝛼 · 𝛾𝑖,𝑗 + (1 − 𝛼) · 𝛾𝑖,𝑗 (𝑡)

Sampling Probability in AW-PSP

(12)

where 𝛼 ∈ [0, 1] balances the contribution between historical co-behavior and recent co-failure evidence. Each node 𝑖 is associated with a set of significantly correlated peers: G𝑖 (𝑡) = { 𝑗 | 𝛾𝑖,𝑗 (𝑡) > 𝜏corr } and its correlation penalty as: ∑︁ 𝜌𝑖 (𝑡) = 𝐶ˆ𝑖,𝑗 · 𝛾𝑖,𝑗 (𝑡) (13) 𝑗 ∈ G𝑖 (𝑡 )

where 𝐶ˆ𝑖,𝑗 is a proximity weight, e.g., based on DHT logical distance or latency measurements. We define a latency threshold in the empirical section. The correlation penalty adjusts the availability prediction for node 𝑖 as follows: 6

clients, (iii) each selected client performing a fixed number of local training epochs (three local epochs in our setup), and (iv) returning the local update to the coordinator for aggregation. We run the full experiment for 50 global epochs (more epochs result in no performance improvement). After each global epoch the coordinator evaluates the aggregated global model by distributing a small test partition to available clients and collecting local predictions; these per-epoch evaluations produce the accuracy/loss curves reported in the results. In our experimental setup, we fixed the target probabilistic client selection to 5 nodes per round, while assuming 4 neighbors per node in the DHT overlay. Process isolation. Each client and the coordinator run in separate Docker containers. In our setup we instantiate 11 containers (10 clients and 1 coordinator). Each container runs an independent Python runtime with the model weights and inference scripts. The CIFAR-10 dataset is mounted read-only from the host into each container, which avoids duplication of storage while ensuring consistent data availability across all clients.FL deployments in real-world environments often involve thousands to millions of devices, such as mobile phones and edge nodes, which exhibit heterogeneous data distributions, intermittent availability, and correlated failures. However, it is impractical to physically deploy and execute training across such a large number of devices in a controlled experimental environment. Even with cloud infrastructure, running hundreds or thousands of independent training processes simultaneously introduces significant overhead in compute, memory, and orchestration. To bridge this gap, we adopt the concept of logical clients. Logical clients represent a large population of virtual participants whose availability patterns, data characteristics, and correlation structures are explicitly modeled, while only a smaller number of physical workers execute training. This abstraction enables us to evaluate FL algorithms under realistic large-scale conditions. In each training round, the server first selects a subset of logical clients according to the scheduling policy. These selected logical clients are then mapped to a smaller pool of physical clients using a wave-based execution mechanism. If 𝑚 = [10, 30, 100] logical clients are selected among 𝑁 == [100, 300, 1000, 3000] population and 𝑃 physical clients are available, training is executed in ⌈𝑚/𝑃⌉ waves, where each physical client sequentially processes multiple logical clients. This decoupling enables scalable evaluation while maintaining bounded system resource usage. Failure injection. Failures are injected at the network layer using the TopologyProvider abstraction, which wraps each client container with configurable link properties. For each node, we instantiate e.g. link_latency=20, link_loss=5. Here, link_latency and link_loss specify the baseline delay (20 ms) and packet loss rate (5%) applied to the virtual link connecting the container to the bridge. These impairments are implemented internally with Linux, ensuring they are enforced at the veth interface that connects the container to the 7

virtual switch. To detect failures, we continuously measure the round-trip latency of each client by issuing controlled ping probes. A node is considered failed if the measured latency exceeds a threshold of 100 ms, which indicates either severe congestion or effective disconnection. The choice of 100 ms is motivated by synchronization requirements in distributed training: latencies above this range cause straggler effects that significantly degrade training throughput and convergence speed. Thus, while a node may still be technically reachable, any client exceeding this bound is treated as unavailable for synchronization purposes. 4.1

Trace Data and Correlated Failures

While trace data provides insight into device availability patterns, it does not capture actual runtime failures that occur during training—such as dropped connections or infrastructurerelated outages. To model better these conditions, we introduce synthetic failures driven by real-time telemetry: • Independent Failures: A node is marked as failed during a round if its measured latency exceeds a defined threshold (here we consider 100ms) or if its packet loss rate indicates unreliable connectivity. These failures are dynamically detected based on runtime metrics rather than injected probabilistically. • Correlated Failures: Nodes that are topologically or behaviorally close (e.g., sharing DHT proximity or latency profiles, where 4 closest nodes are assumed neighbors) are monitored for correlated failure likelihood. If a node fails, its neighbor with high correlation score is considered as a correlated failure, if trace score or fail score is greater than a threshold, simulating clustered failures due to shared network infrastructure. These failure events are reflected in each node’s DHT metadata, which includes latency measurements, packet loss, recent availability history, and round participation. The AWPSP strategy leverages this decentralized availability data to prioritize reliable nodes and avoid synchronized dropouts. Each node periodically updates its availability based on its recent computation and communication success rates. Availability is calculated separately for computation and communication tasks and integrated into the metadata for querying, comp according to Eq. 8, where 𝐻𝑖 (𝑡) and 𝐻𝑖comm (𝑡) indicate success (1) or failure (0) of computation and communication tasks at time 𝑡, respectively. If latency is greater than a threshold or server state update exceeds a timeout, the node is considered failed. Each node periodically updates its metadata in the DHT based on its availability and performance. To evaluate the effectiveness of our proposed sampling strategy, we implement a baseline version of PSP (ClassicPSP) that selects a fixed number of nodes uniformly at random from the pool of currently online devices, without considering any availability, freshness (i.e., recency of participation), or failure correlation information. This serves as

Algorithm 1 Federated Learning with DHT-Based Node Selection

• RQ3: How well does AW-PSP maintain class coverage and balance label participation relative to Classic-PSP? • RQ4: Under correlated failures, does AW-PSP reduce the fraction of failed selections and improve resilience?

1: for each candidate node 𝑖 do 2: Availability: 𝑎˜𝑖 (𝑡 ) = 𝑎˜𝑖 (𝑡 − 1) + (1 − 𝑎˜𝑖 (𝑡 − 1) )𝛽𝑖 (𝑡 )

4.2.1 Global accuracy for different heterogeneity. In order to evaluate the impact of data heterogeneity on system performance, we calculate the overall training accuracy under different label distributions across clients in a system with 100 clients. Specifically, we consider increasingly less heterogeneous settings in which each client holds 2 labels, 5 labels, or all 10 labels. As shown in Figure 2, the results indicate that AW-PSP consistently outperforms both PSP and Oort across all heterogeneity levels. In the 2-label setting, where heterogeneity is strongest, all methods exhibit substantial fluctuations and relatively low accuracy, but AWPSP generally attains higher peaks and stronger late-round performance than PSP and Oort, showing better robustness under severe non-IID conditions. In the 5-label setting, although the three methods remain unstable, AW-PSP still tends to achieve competitive or superior accuracy more frequently than the baselines, again remaining above PSP and Oort in many rounds. In the 10-label setting, where data distribution is more balanced, all methods converge more smoothly near 72% accuracy, but AW-PSP remains slightly ahead overall, demonstrating the best and most stable final performance among the three approaches. Overall, these results show two important findings. First, increasing the number of labels per client reduces the non-IID effect, leading to higher accuracy and more stable convergence. Second, and more importantly, AW-PSP consistently surpasses PSP and Oort under all tested label-distribution settings. Oort is implemented by vendoring the oort.py module from https://github.com/SymbioticLab/Oort for the server to import and run that selector directly in the training pipeline for direct comparison against AW-PSP and Classic-PSP. This implementation includes Oort exploration/exploitation, pacer logic, blacklist/duration penalties, while the setup adds utility wiring and logs fairness/accuracy metrics.

Correlated Failure Risk:

𝜌𝑖 (𝑡 ) =

∑︁

𝐶ˆ𝑖,𝑗 · 𝛾𝑖,𝑗 (𝑡 )

𝑗 ∈G𝑖

Adjusted Availability: adj

𝑎𝑖 (𝑡 ) = 𝑎˜𝑖 (𝑡 ) · (1 − 𝜌𝑖 (𝑡 ) )

Final Sampling Probability: h i comp comp 𝑝𝑖′ (𝑡 ) = 𝑝 · (𝑎𝑖 · 𝑎𝑖comm ) + (1 − 𝑎𝑖 · 𝑎𝑖comm ) · 𝛽𝑖 (𝑡 )

· (1 − 𝜌𝑖 (𝑡 ) )

6: end for 7: Node Selection: Choose top 𝑁 nodes with highest score𝑖 . 8: Distribute Training: Send global model and instructions to selected nodes. 9: Local Training: Each node trains on its local data and sends model updates back. 10: Aggregation: Server aggregates all updates and refines the global model.

a control to isolate the benefits introduced by the AW-PSP mechanism. Our AW-PSP algorithm prioritizes node selection based on a dynamic score that integrates real-time availability predictions, freshness, and class diversity, according to Algorithm 1. Additionally, it excludes nodes participating in correlated failure clusters, identified using two orthogonal signals: user behavior traces and proximity-based co-failure detection (per §4.1). This proactive filtering ensures robustness against subnet-level outages or synchronous dropouts. The core selection mechanism for the AW-PSP strategy aims to choose a subset of active nodes to participate in the current training round. This selection is done by prioritizing nodes based on their predicted availability, their freshness, and ensuring class label coverage: • Filter out unavailable or failed nodes, including those involved in correlated failures. • Among the remaining active nodes, calculate a selection score for each defined as the product of that node’s availability and freshness. Nodes that are highly available and recently active are ranked higher. • From the top-ranked nodes, greedily select clients to maximize class label coverage, ensuring that the selected nodes represent as many data labels as possible. • For each selected node, evaluate their contribution by computing loss deltas. • Finally, calculate three fairness metrics by analyzing the variance of loss deltas across nodes and classes. 4.2

4.2.2 Fairness variance metrics. We define two complementary fairness variance metrics that capture fairness at different levels, see references [30, 31]. At round 𝑡, let Y denote the set of all classes, and let 𝐿𝑐 (𝑡) = {ℓ𝑐,1 (𝑡), . . . , ℓ𝑐,𝑁𝑐 (𝑡)} be the set of per-sample losses for class 𝑐 among the selected nodes S𝑡 . Define the average loss for class 𝑐 as: 𝑁

ℓ𝑐 (𝑡) =

Results and Discussion

In designing our evaluation, we explicitly structure the experiments to answer core research questions: • RQ1: How does client-level data heterogeneity impact global accuracy? • RQ2: Does AW-PSP improve fairness across nodes and classes compared to Classic-PSP?

𝑐 1 ∑︁ ℓ𝑐,𝑖 (𝑡). 𝑁𝑐 𝑖=1

(16)

(a) Average of Within Class Variance or Avg(class-var) or dispersion. This measures the heterogeneity of losses inside each class, then averages across the observed classes: 1 ∑︁ 2 𝜎within-class (𝑡) = Var 𝐿𝑐 (𝑡) , (17) |Y𝑡 | 𝑐 ∈ Y𝑡

(a) Accuracy test for 2 Labels/Client

(b) Accuracy test for 5 Labels/Client

Figure 2. Comparison of accuracy for AWPSP/PSP/Oort and different number of labels per client. where Y𝑡 ⊆ Y is the set of classes covered by S𝑡 in round 𝑡. High values indicate that samples of the same class, observed across different nodes, exhibit highly inconsistent behavior. AW-PSP might increase this metric, because it selects a more diverse set of devices per round, leading to greater variability.

Figure 4 shows the second fairness metric, Var(class-avg), which directly reflects imbalance across class-level mean losses. The trends demonstrate a consistent ordering across all label settings. For 2 labels per client (Fig. 4(a)), ClassicPSP exhibits noticeable early-round spikes, indicating unstable class-level fairness, while Oort shows large oscillations across many rounds. AW-PSP remains significantly smoother and lower overall. For 5 labels per client (Fig. 4(b)), Oort again displays extreme peaks, indicating large fluctuations in class-level performance, whereas Classic-PSP shows moderate variability. AW-PSP maintains the lowest and most stable variance trajectory. With 10 labels per client (Fig. 4(c)), all methods show gradual variance growth as training progresses, but AW-PSP consistently stays below Classic-PSP, while Oort exhibits the highest and fastest increase. Figure 5 shows that AWPSP consistently achieves the highest accuracy while maintaining significantly lower variance across both fairness metrics compared to PSP and Oort. Notably, performance remains stable under latency, communication, and computation changes, indicating robustness to these parameters. In contrast, recovery and correlation perturbations introduce more pronounced effects, particularly increasing variance for PSP and Oort, while AWPSP degrades more gracefully.

(b) Variance of Class Means or Var(class-avg) or spread. This measures disparity in average performance across classes: 2 𝜎across-classes (𝑡) = Var {ℓ𝑐 (𝑡) : 𝑐 ∈ Y𝑡 } . (18) High values indicate that some classes systematically experience higher losses than others, reflecting a fairness imbalance in training. AW-PSP reduces this variance, since its availability- and freshness-aware selection increases label coverage and balances updates across classes, pulling class-level performance closer together. Both client selection strategies, AW-PSP and Classic-PSP, are evaluated under identical experimental conditions, including the same model initialization, number of clients selected per round, and failure injection, while varying the degree of data heterogeneity using 2, 5, and 10 labels per client. Their performance is compared against Oort using two complementary class-level fairness metrics: Avg(class-var) and Var(class-avg). Figure 3 presents the results for the first fairness metric, Avg(class-var). Across all label configurations, AW-PSP consistently produces the lowest variance growth, indicating more stable within-class behaviour compared to both Classic-PSP and Oort. For 2 labels per client (Fig. 3(a)), all three methods start with similar variance levels, but Oort quickly diverges and exhibits substantially larger increases in later rounds. Classic-PSP shows moderate growth, while AW-PSP maintains the lowest trajectory throughout most of the training process. For 5 labels per client (Fig. 3(b)), Oort demonstrates pronounced instability with repeated spikes, whereas Classic-PSP and AW-PSP follow smoother trends, with AW-PSP remaining consistently lower. When the number of labels increases to 10 per client (Fig. 3(c)), the separation between the three methods becomes clearer: Oort shows the steepest increase in variance, Classic-PSP remains intermediate, and AW-PSP continues to maintain the lowest overall within-class variability.

4.2.3 Other fairness measures. We evaluate AW-PSP against Classic-PSP and Oort along three complementary dimensions capturing class coverage, distributional balance, and participation fairness. At round 𝑡, let Y denote the set of all classes. For each class 𝑐 ∈ Y, let 𝐿𝑐 (𝑡) = {ℓ𝑐,1 (𝑡), . . . , ℓ𝑐,𝑁𝑐 (𝑡)} be the set of per-sample losses associated with class 𝑐 among the selected clients S𝑡 , where 𝑁𝑐 is the number of samples of class 𝑐 observed at round 𝑡. We define the empirical class distribution 𝑃𝑡 (𝑐) = Í ′ 𝑁𝑐 𝑁𝑐 ′ . Let the uniform distribution 𝑐 ∈Y over classes be 𝑈 (𝑐) = | Y1 | . See references [31, 32]. 1. KL divergence (distributional imbalance). We quantify deviation from uniform class participation via: ∑︁ 𝑃𝑡 (𝑐) 𝐷 KL (𝑃𝑡 ∥ 𝑈 ) = 𝑃𝑡 (𝑐) log (19) 𝑈 (𝑐) 𝑐∈Y

(a) Avg(class-var) for 2 Labels/Client

(b) Avg(class-var) for 5 Labels/Client

Figure 3. Comparison of our 1st fairness metric for AWPSP/PSP/Oort and different number of labels per client.

(a) Var(class-avg) for 2 Labels/Client

(b) Var(class-avg) for 5 Labels/Client

Figure 4. Comparison of our 2nd fairness metric for AWPSP/PSP/Oort and different number of labels per client. AWPSP

PSP

AWPSP

Oort

PSP

AWPSP

Oort

PSP

Oort

Var(class-avg)

Avg(class-var)

Accuracy (%)

25 L9 0 L1 00 M 0.7 5 M 1.0 C0 .75 C1 .0 R0 .5 R1 .0 P0 .5 P1 .0

L9 0 L1 00 M 0.7 5 M 1.0 C0 .75 C1 .0 R0 .5 R1 .0 P0 .5 P1 .0

L9 0 L1 0 M 0 0.7 5 M 1.0 C0 .75 C1 .0 R0 .5 R1 .0 P0 .5 P1 .0

Figure 5. Sensitivity of AWPSP, PSP, and Oort to parameter perturbations across five parameter groups: latency threshold (L), communication weight (M), computation weight (C), recovery probability (R), and correlation penalty (P). This metric captures how skewed the selected data distribution is. Lower values indicate better class balance and improved representativeness. 2. Unseen classes (coverage gap). We measure the number of classes that are completely absent in the selected set. This metric directly quantifies failure of coverage. Lower values indicate that more classes are represented in each round. 𝑈 miss (𝑡) = |{𝑐 ∈ Y : 𝑁𝑐 = 0}|

coefficient below, which measures inequality in participation across clients over time. Lower values indicate more uniform participation and improved fairness Í𝑁 Í𝑁 𝑖=1 𝑗=1 𝑛𝑖 (𝑡) − 𝑛 𝑗 (𝑡) 𝐺 (𝑡) = (21) Í𝑁 2𝑁 𝑖=1 𝑛𝑖 (𝑡) Figure 6 demonstrates the comparison between AW-PSP, Classic-PSP, and Oort across the three fairness-related metrics. Together, these metrics provide strong evidence that AW-PSP consistently improves fairness of client selection, leading to more balanced and representative training data across rounds. Looking first at KL divergence, AW-PSP maintains consistently low values throughout the training process, typically remaining close to zero, indicating that the class

(20)

3. Gini coefficient (participation inequality). Let 𝑛𝑖 (𝑡) denote the cumulative number of times client 𝑖 has been selected up to round 𝑡. Define the Gini 10

(a) KL divergence comparison

(b) Unseen classes comparison

Figure 6. Comparison of AWPSP/PSP/Oort in terms of KL divergence, Unseen classes (coverage gap), and Gini coefficient.

(a) AW-PSP Accuracy scalability

(b) AW-PSP Avg(class-var) scalability

Figure 7. Scalability in terms of accuracy, fairness metric 1 and fairness metric 2 for [100,300,1000,3000] clients. distribution of selected clients closely matches the global distribution. In contrast, Classic-PSP shows larger fluctuations, while Oort frequently produces significantly higher KL values, often exceeding 0.5. This indicates that AW-PSP more effectively mitigates distribution skew, ensuring that no subset of labels dominates the training process. Next, examining the number of unseen classes, AW-PSP maintains values near zero across nearly all rounds, meaning that almost all classes are represented in each training round. Classic-PSP occasionally fails to cover some classes, while Oort exhibits the largest variation, with unseen-class ratios reaching as high as 0.5 in some rounds. This demonstrates that AW-PSP achieves significantly better label coverage. Finally, the Gini coefficient, which measures inequality in class representation, further confirms the advantage of AW-PSP. AW-PSP rapidly reduces the Gini value and stabilizes at very low levels (close to 0.05), indicating highly balanced participation of different classes. Classic-PSP converges more slowly and stabilizes at higher inequality levels (around 0.25), while Oort remains consistently higher (around 0.30–0.35), suggesting greater imbalance in selected client data.

challenging. In such conditions, we expect a robust selection strategy to maintain stable accuracy while preserving balanced class representation as the client pool grows. Looking first at model accuracy, Figure 7(a) shows that AW-PSP maintains relatively stable performance as the number of clients increases. While the absolute accuracy remains lower than in less heterogeneous settings due to the extreme label skew, the curves for larger populations (1000 and 3000 clients) remain comparable to those observed with 100 and 300 clients. This indicates that AW-PSP successfully scales without significant degradation in predictive performance. The stability of the accuracy curves suggests that increasing the client pool does not introduce additional bias, demonstrating that the selection mechanism continues to identify useful and representative participants even when label diversity per client is highly constrained. Next, we examine Average of Class Variance, which measures variability within each class across participating clients. As shown in Figure 7(b), the average within-class variance increases gradually as the number of clients grows. This trend is expected: with more clients available, the sampling process captures a wider range of feature distributions for each class. Importantly, the growth is smooth and controlled rather than abrupt, indicating that AW-PSP maintains consistent representation of each class despite the limited label availability per client. This behavior suggests that AW-PSP effectively balances exploration of diverse clients while preserving stability in class-specific learning. Finally, we analyze the Variance of Class Means; Figure 7(c) shows that it remains relatively low and stable

4.2.4 Scalability. To evaluate the scalability of AW-PSP under highly heterogeneous conditions, we analyze its behavior when the number of clients increases from 100 to 300, 1000, and 3000, while each client contains only 2 labels. This represents an extremely non-IID scenario, where each individual client provides very limited class diversity, making fair and representative client selection particularly 11

Table 5. Impact of Correlation Noise (2 Labels per Client) Method c0 c10 c20 c40 Δ𝑐10 AWPSP 33.75 33.32 31.42 29.78 -1.3% PSP 27.85 26.77 27.53 26.84 -3.9% Oort 24.65 24.02 23.82 24.92 -2.6% Avg(within-class) AWPSP 0.36 0.38 0.58 0.58 +5.6% PSP 0.47 0.53 0.98 1.10 +12.8% Oort 0.68 1.22 1.69 3.08 +79.4% Var(class-avg) AWPSP 0.33 0.34 0.34 0.38 +3.0% PSP 1.16 1.22 1.35 1.29 +5.2% Oort 1.47 1.85 2.02 3.09 +25.9% Metric Accuracy (%)

across different client scales, with only moderate fluctuations as the number of clients increases. This indicates that AW-PSP continues to distribute participation opportunities evenly across classes even when the candidate pool is large.

Δ𝑐40 -11.8% -3.6% +1.1% +61.1% +134.0% +352.9% +15.2% +11.2% +110.2%

selection under heterogeneous data, but they optimize accuracy–latency trade-offs without considering fairness imbalance or correlated outages. Recent work such as Sageflow [5] and FLuID [6] handle stragglers and adversaries, while FedScale [9] provides large-scale benchmarking of heterogeneity and resource constraints, yet none of these lines systematically model failure correlations or fairness starvation as we do. Even availability-oriented studies such as CA-Fed [34] or F3AST [35] restrict attention to independent client churn, ignoring the clustered or synchronized unavailability patterns that naturally arise in real systems. AW-PSP complements existing frameworks but introduces a distinct failure- and fairness-aware probabilistic sampling that remains effective even when availability shocks are correlated across groups.

4.2.5 Ablation (Correlation Impact). Correlation noise (i.e., failure correlation among clients) introduces dependencies among selected participants and affects all methods; however, its impact differs significantly across selection strategies. As shown in Table 5, AW-PSP exhibits a gradual and consistent degradation in accuracy as correlation increases, with only −1.3% at 𝑐10, −6.9% at 𝑐20, and −11.8% at 𝑐40. In contrast, PSP shows smaller but irregular fluctuations, while Oort remains unstable and does not follow a consistent degradation trend, even slightly improving at high correlation. The differences become substantially more pronounced when examining fairness metrics. For Avg(withinclass) (intra-class variability), AW-PSP shows a controlled increase, rising moderately from 0.36 to 0.58 (+61.1%), indicating bounded degradation in within-class consistency. In contrast, PSP exhibits significantly larger growth (+134.0%), while Oort demonstrates extreme sensitivity, with intra-class variability increasing sharply from 0.68 to 3.08 (+352.9%). A similar pattern is observed for Var(class-avg) (inter-class fairness). AW-PSP remains relatively stable, with only a modest increase (+3.0% to +15.2%), indicating robustness in maintaining balanced class-level performance under correlated failures. PSP shows moderate degradation, while Oort again exhibits substantial imbalance, with variance increasing by up to +110.2% at 𝑐40.

Δ𝑐20 -6.9% -1.1% -3.4% +61.1% +108.5% +148.5% +3.0% +16.4% +37.4%

Conclusion

This work introduces AW-PSP, a client selection framework that integrates availability prediction, correlated-failure modeling, and DHT-based proximity into FL scheduling. Unlike prior approaches, AW-PSP explicitly models data-availability co-correlation, capturing both behavioral similarity in availability traces and structural co-failure risks arising from shared infrastructure. By incorporating correlation-aware recovery probabilities into a health score defined as availability(t) × freshness (t), AW-PSP proactively diversifies client selection while still prioritizing reliable nodes, thereby reducing the likelihood of synchronized dropouts. Extensive trace-driven evaluation demonstrates that AW-PSP consistently outperforms Classic-PSP and Oort across multiple dimensions. First, AW-PSP improves fairness by maintaining lower Var(class-avg) imbalance, near-zero unseen classes, and reduced KL divergence, indicating more balanced and representative participation across labels. Second, AW-PSP preserves class coverage and stabilizes Avg(class-var), leading to more consistent convergence even under highly nonIID settings (2 labels per client). Third, under correlated failures, AW-PSP shows significantly higher robustness where impact of correlation noise on accuracy and fairness is substantially smaller compared to PSP with larger degradation. Furthermore, scalability experiments with up to 3000 clients show that AW-PSP maintains stable accuracy and fairness.

Related Work

Prior work in distributed and federated learning has largely focused on stragglers, non-IID data, and heterogeneity, but has not treated correlated availabilities and co-failures as first-class challenges. Classic scheduling approaches such as PSP [14], SSP [3], and gradient coding [4] mitigate slow or failing workers, but assume independent failures and do not address systematic, infrastructure-driven unavailability. In the FL domain, methods like FedAvg [15], FedProx [27], FedGS [33], and Oort [10] improve efficiency or 12

References

[17] J. Yan and D. Jin, “Vt-mininet: Virtual-time-enabled mininet for scalable and accurate software-defined network emulation,” in Proceedings of the 2nd ACM SIGCOMM Symposium on Software Defined Networking Research (SOSR), 2015, pp. 27:1–27:7. [18] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016, pp. 770–778. [19] A. K. et al., “Learning multiple layers of features from tiny images,” University of Toronto, Tech. Rep., 2009, cifar-10 dataset. [Online]. Available: https://www.cs.toronto.edu/~kriz/cifar.html [20] “Cross-Entropy loss,” Wikipedia, https://en.wikipedia.org/wiki/Crossentropy, accessed July 2025. [21] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” arXiv preprint arXiv:1412.6980, 2014. [Online]. Available: https://arxiv.org/abs/1412.6980 [22] C. Yang, Q. Wang, M. Xu, Z. Chen, K. Bian, Y. Liu, and X. Liu, “Characterizing impacts of heterogeneity in federated learning upon large-scale smartphone data,” in Proceedings of the Web Conference 2021. ACM, 2021, pp. 935–946. [Online]. Available: https://dl.acm.org/doi/10.1145/3442381.3449851 [23] Y. Zhao, M. Li, L. Lai, N. Suda, D. Civin, and V. Chandra, “Federated learning with non-iid data,” arXiv preprint arXiv:1806.00582, 2018. [Online]. Available: https://arxiv.org/abs/1806.00582 [24] D. Li, J. Hu, and Y. Wang, “Fedmd: Heterogeneous federated learning via model distillation,” in NeurIPS Workshop on Federated Learning, 2019. [25] A. Fallah, A. Mokhtari, and A. Ozdaglar, “Personalized federated learning with theoretical guarantees: A model-agnostic meta-learning approach,” in NeurIPS, 2020. [26] V. Smith, C.-K. Chiang, M. Sanjabi, and A. Talwalkar, “Federated multitask learning,” in NeurIPS, 2017. [27] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith, “Federated optimization in heterogeneous networks,” in MLSYS, 2020. [28] T. Li, M. Sanjabi, A. Beirami, and V. Smith, “Fair resource allocation in federated learning,” in ICLR, 2020. [29] F. Sattler, K.-R. Müller, and W. Samek, “Clustered federated learning: Model-agnostic distributed multi-task optimization under privacy constraints,” in IEEE Transactions on Neural Networks and Learning Systems, 2020. [30] J. Pei, “Fair federated learning framework with adaptive regularization,” Knowledge-Based Systems, vol. 316, p. 113392, 2025, received 16 Oct 2024; Revised 8 Mar 2025; Accepted 18 Mar 2025; Available online 27 Mar 2025; Version of Record 1 Apr 2025. [Online]. Available: https://doi.org/10.1016/j.knosys.2025.113392 [31] S. Liu, “Fedga: A fair federated learning framework based on the gini coefficient,” arXiv preprint arXiv:2507.12983, 2025, accepted for publication in Transactions on Machine Learning Research (TMLR). [Online]. Available: https://arxiv.org/abs/2507.12983 [32] Y. Shi, H. Yu, and C. Leung, “Towards fairness-aware federated learning,” arXiv preprint arXiv:2111.01872, 2021. [Online]. Available: https://arxiv.org/abs/2111.01872 [33] Z. Wang, X. Fan, J. Qi, H. Jin, P. Yang, S. Shen, and C. Wang, “Fedgs: Federated graph-based sampling with arbitrary client availability,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 37, no. 8, 2023, pp. 10 271–10 278. [34] A. Rodio, F. Faticanti, O. Marfoq, G. Neglia, and E. Leonardi, “Federated learning under heterogeneous and correlated client availability,” IEEE/ACM Transactions on Networking, pp. 1–10, 2023. [Online]. Available: https://arxiv.org/abs/2301.04632 [35] M. Ribero, H. Vikalo, and G. De Veciana, “Federated learning under intermittent client availability and time-varying communication constraints,” IEEE Journal of Selected Topics in Signal Processing, vol. 16, no. 3, pp. 403–418, 2022. [Online]. Available: https: //arxiv.org/abs/2205.06730

[1] L. G. Valiant, “A bridging model for parallel computation,” Communications of the ACM, vol. 33, no. 8, pp. 103–111, 1990. [2] A. Koloskova, S. U. Stich, and M. Jaggi, “Sharper convergence guarantees for asynchronous SGD for distributed and federated learning,” in Advances in Neural Information Processing Systems, 2022. [Online]. Available: https://proceedings.neurips.cc/paper_files/paper/2022/file/ 6db3ea527f53682657b3d6b02a841340-Paper-Conference.pdf [3] Q. Ho, J. Cipar, H. Cui, S. Lee, J. K. Kim, P. B. Gibbons, G. A. Gibson, G. R. Ganger, and E. P. Xing, “More effective distributed ml via a stale synchronous parallel parameter server,” in Advances in Neural Information Processing Systems, 2013, pp. 1223–1231. [Online]. Available: https://dl.acm.org/doi/10.5555/2999611.2999748 [4] R. Tandon, Q. Lei, A. G. Dimakis, and A. Karbasi, “Gradient coding: Avoiding stragglers in distributed learning,” in Proceedings of the 34th International Conference on Machine Learning, 2017, pp. 3368–3376. [Online]. Available: https://dl.acm.org/doi/pdf/10.5555/ 3305890.3306029 [5] J. Park, D.-J. Han, M. Choi, and J. Moon, “Sageflow: Robust federated learning against both stragglers and adversaries,” in Advances in Neural Information Processing Systems, 2021. [Online]. Available: https://proceedings.neurips.cc/paper/2021/file/ 076a8133735eb5d7552dc195b125a454-Paper.pdf [6] I. Wang, P. J. Nair, and D. Mahajan, “Fluid: Mitigating stragglers in federated learning using invariant dropout,” in Advances in Neural Information Processing Systems, 2023. [Online]. Available: https://papers.neurips.cc/paper_files/paper/2023/ file/e7feb9dbd9a94b6c552fc403fcebf2ef-Paper-Conference.pdf [7] D. J. Beutel, T. Topal, A. Mathur, X. Qiu, J. Fernandez-Marques, Y. Gao, L. Sani, H. L. Kwing, T. Parcollet, P. P. de Gusmão, and N. D. Lane, “Flower: A friendly federated learning research framework,” preprint arXiv:2007.14390, 2020. [8] H. Daga, J. Shin, D. Garg, A. Gavrilovska, M. Lee, and R. R. Kompella, “Flame: Simplifying topology extension in federated learning,” in Proceedings of the ACM Symposium on Cloud Computing (SoCC ’23), 2023. [9] F. Lai, Y. Dai, S. Singapuram, J. Liu, X. Zhu, H. Madhyastha, and M. Chowdhury, “Fedscale: Benchmarking model and system performance of federated learning at scale,” in International Conference on Machine Learning. PMLR, 2022, pp. 11 814–11 827. [10] F. Lai, X. Zhu, H. V. Madhyastha, and M. Chowdhury, “Oort: Efficient federated learning via guided participant selection,” in 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI 21), 2021, pp. 19–35. [11] K. Bonawitz, H. Eichner, W. Grieskamp, D. Huba, A. Ingerman, V. Ivanov, C. Kiddon, J. Konečny, S. Mazzocchi, and B. M. et al., “Towards federated learning at scale: System design,” Proceedings of Machine Learning and Systems, vol. 1, pp. 374–388, 2019. [12] E. Wang, B. Chen, M. Chowdhury, A. Kannan, and F. Liang, “Flint: A platform for federated learning integration,” Proceedings of Machine Learning and Systems, vol. 5, 2023. [13] D. Garg, D. Sanyal, M. Lee, A. Tumanov, and A. Gavrilovska, “Client availability in federated learning: It matters!” EuroMLSys ’25, Rotterdam, Netherlands, 2025. [Online]. Available: https://dl.acm.org/ doi/pdf/10.1145/3721146.3721964 [14] L. Wang, B. Catterall, and R. Mortier, “Probabilistic synchronous parallel,” preprint arXiv:1709.07772, 2017, version 2, last revised 5 Oct 2017. [Online]. Available: https://arxiv.org/abs/1709.07772 [15] B. McMahan, E. Moore, D. Ramage, and S. Hampson, “Communicationefficient learning of deep networks from decentralized data,” in AISTATS, 2017. [16] H. Wang and et al., “Optimizing federated learning on non-iid data with reinforcement learning,” in IEEE Annual Joint Conference: INFOCOM, IEEE Computer and Communications Societies, 2020.

Theoretical Justification and Guarantees for the Model in Section 3

is the Bayes-optimal classifier for predicting computational feasibility.

This appendix rigorously validates the availability construction introduced in Section 3, specifically Eq. (8)–(10). We derive these expressions from an explicit generative model of client participation and show that the proposed formulation is statistically optimal or a controlled approximation under clearly stated assumptions. A.1

Proof. Consider predicting binary variable 𝑍𝑖 (𝑡) = 1{𝐶𝑖 (𝑡) ≥ 𝐶 min } Under 0–1 loss, the Bayes classifier is 1 ˆ 𝑍𝑖 (𝑡) = 1 P(𝑍𝑖 (𝑡) = 1 | 𝐶𝑖 (𝑡)) ≥ 2

Generative Model of Round Success

For client 𝑖 at round 𝑡, define the binary success variable:

P(𝑍𝑖 (𝑡) = 1 | 𝐶𝑖 (𝑡)) = 1{𝐶𝑖 (𝑡) ≥ 𝐶 min }

A.3

comp

𝑎𝑖 (𝑡) = 𝑎𝑖

(𝑡) · 𝑎𝑖comm (𝑡)

(35)

Theorem A.2 (Exact Factorization Under Conditional Independence). Assume that conditional on system state 𝑆𝑖 (𝑡), computation and communication failures are independent:

(25)

𝐶𝑖 (𝑡) ⊥ 𝐵𝑖 (𝑡) | 𝑆𝑖 (𝑡)

(36)

comp

(37)

Then

Participation is feasible iff

𝑝𝑖true (𝑡) = 𝑎𝑖

(𝑡) · 𝑎𝑖comm (𝑡)

Proof. By definition,

(27)

Define the true participation probability:

A.2

Multiplicative Composition

Eq. (9) defines total availability as

Computation and communication delays are functions of comp the available resources, i.e., 𝑇𝑖 = 𝑓 (𝐶𝑖 (𝑡)) and 𝑇𝑖comm = 𝑔(𝐵𝑖 (𝑡)). Node availability is then defined as the probability of completing within a deadline: comp 𝑎𝑖 (𝑡) = 𝑃 𝑇𝑖 (𝑡) + 𝑇𝑖comm (𝑡) ≤ 𝑇max (26)

𝑝𝑖true (𝑡) = P(𝑌𝑖 (𝑡) = 1)

(34)

Thus the Bayes decision boundary is exactly 𝐶𝑖 (𝑡) = 𝐶 min . No alternative rule achieves smaller expected misclassification risk. Therefore thresholding is not heuristic, but the unique optimal decision rule under feasibility semantics. □

A node is resource-feasible if

𝑌𝑖 (𝑡) = 1 ⇐⇒ 𝐶𝑖 (𝑡) ≥ 𝐶 min and 𝐵𝑖 (𝑡) ≥ 𝐵 min

(33)

Since 𝑍𝑖 (𝑡) is deterministically defined by 𝐶𝑖 (𝑡),

𝑌𝑖 (𝑡) ∈ {0, 1} (22) where 𝑌𝑖 (𝑡) = 1 indicates successful completion of the FL round. Let the client resource vector be: 𝐶𝑖 (𝑡) 𝑅𝑖 (𝑡) = (23) 𝐵𝑖 (𝑡) where 𝐶𝑖 (𝑡) and 𝐵𝑖 (𝑡) denote available computation and communication resources. Let the minimum required resources for participation be 𝐶 𝑅min = min (24) 𝐵 min 𝑌𝑖 (𝑡) = 1{𝐶𝑖 (𝑡) ≥ 𝐶 min, 𝐵𝑖 (𝑡) ≥ 𝐵 min }

(32)

𝑝𝑖true (𝑡) = P(𝐶𝑖 ≥ 𝐶 min, 𝐵𝑖 ≥ 𝐵 min ) (28)

(38)

Condition on 𝑆𝑖 (𝑡):

Optimality of Threshold-Based Availability = E𝑆𝑖 [P(𝐶𝑖 ≥ 𝐶 min, 𝐵𝑖 ≥ 𝐵 min | 𝑆𝑖 )]

In Eq. (8), computation success at time 𝑡 is defined as: comp 𝐻𝑖 (𝑡) = 1{𝐶𝑖 (𝑡) ≥ 𝐶 min }

(29)

(39)

Under conditional independence,

We estimate computation availability using recent history across the last 𝑇 rounds: 𝑇 1 ∑︁ comp comp 𝑎𝑖 = 𝐻 (𝑡) (30) 𝑇 𝑡 =1 𝑖

= E𝑆𝑖 [P(𝐶𝑖 ≥ 𝐶 min | 𝑆𝑖 ) · P(𝐵𝑖 ≥ 𝐵 min | 𝑆𝑖 )]

(40)

If 𝑆𝑖 (𝑡) is observed via telemetry, the conditional expectation collapses and

Theorem A.1 (Bayes Optimality of Threshold Rule). Assume successful computation is equivalent to 𝐶𝑖 (𝑡) ≥ 𝐶 min . Under 0–1 loss, the estimator comp 𝑌ˆ (𝑡) = 1{𝐶𝑖 (𝑡) ≥ 𝐶 min } (31)

comp

𝑝𝑖true (𝑡) = 𝑎𝑖

(𝑡)𝑎𝑖comm (𝑡)

(41)

Thus multiplication follows directly from probability axioms. □

𝑖

A.4

A.7

Dependence Case and Approximation Error

We now prove that the availability model used in Section 3 is a statistically consistent approximation of the true roundsuccess probability under a realistic stochastic participation model.

When independence does not hold, define deviation comp

𝛿𝑖 (𝑡) = 𝑝𝑖true (𝑡) − 𝑎𝑖

(𝑡)𝑎𝑖comm (𝑡)

(42)

Theorem A.3 (Sharp Fréchet Error Bound). For arbitrary dependence, |𝛿𝑖 (𝑡)| ≤ min(𝑎𝑐 , 𝑎𝑏 ) − 𝑎𝑐 𝑎𝑏 comp where 𝑎𝑐 = 𝑎𝑖 (𝑡) and 𝑎𝑏 = 𝑎𝑖comm (𝑡)

Probability Space. Let (Ω, F , P) be a probability space. For each client 𝑖 and round 𝑡, define random variables:

(43) 𝐶𝑖 (𝑡),

(44)

Subtract 𝑎𝑐 𝑎𝑏 and take absolute value. The maximum deviation occurs at the endpoints, giving the stated bound. □

Recovery Probability

𝑌𝑖 (𝑡) = 1{E𝑖 (𝑡)} · (1 − 𝐹𝑖 (𝑡))

comp 𝛽𝑖 (𝑡) = Pr 𝑇𝑖 (𝑡 + 1) + 𝑇𝑖comm (𝑡 + 1) ≤ comp 𝑇max 𝑇𝑖 (𝑡) + 𝑇𝑖comm (𝑡) > 𝑇max

𝑝𝑖true (𝑡) = P(𝑌𝑖 (𝑡) = 1)

comp

𝑝𝑖′ (𝑡) = 𝑝 · 𝑎𝑖

comp

(𝑡)𝑎𝑖comm (𝑡) (1 − 𝜌𝑖 (𝑡))

(54)

(𝑡) = P(𝐶𝑖 (𝑡) ≥ 𝐶 min ),

(55)

𝑎𝑖comm (𝑡) = P(𝐵𝑖 (𝑡) ≥ 𝐵 min )

(56)

𝜌𝑖 (𝑡) = P(𝐹𝑖 (𝑡) = 1)

(57)

𝑎𝑖

Theorem A.5 (Nonasymptotic Consistency with Explicit Error Decomposition). Assume: 1. (Bounded Dependence) There exists 𝜅𝑖 (𝑡) such that comp

P(E𝑖 (𝑡)) − 𝑎𝑖

Conditioned on the node being in a failed state at time 𝑡, the probability of recovery within the next interval Δ is

(𝑡)𝑎𝑖comm (𝑡) ≤ 𝜅𝑖 (𝑡)

(58)

2. (Failure Independence from Resources) 𝐹𝑖 (𝑡) ⊥ (𝐶𝑖 (𝑡), 𝐵𝑖 (𝑡))

(48)

(59)

3. (Recovery Approximation Accuracy) If recovery probability is estimated using

Interpreting Δ as the duration of one FL round yields the desired result. For constant hazard (exponential recovery), the expression is exact. □

𝛽𝑖 (𝑡) = 1 − 𝑒 −𝜆𝑖 (𝑡 )Δ

(60)

then for small Δ:

Global Consistency Theorem

1 |𝜌𝑖 (𝑡) − 𝛽𝑖 (𝑡)| ≤ Λ𝑖2 Δ2 2 where Λ𝑖 = sup𝑡 𝜆𝑖 (𝑡).

The AW-PSP model defines: (𝑡)𝑎𝑖comm (𝑡) (1 − 𝜌𝑖 (𝑡))

(53)

where:

comp

(52)

Model Estimator. The AW-PSP model defines:

(45)

Proof. Let 𝑇𝑖 denote the time until the node returns to a state where it meets the deadline. The survival function of remaining in the failed state is ∫ 𝑡 𝑆𝑖 (𝑡) = exp − 𝜆𝑖 (𝑠) 𝑑𝑠 (47)

𝑝𝑖′ (𝑡) = 𝑝 · 𝑎𝑖

(51)

Thus the true participation probability is:

Theorem A.4 (Recovery under Hazard-Based Model). Ascomp sume that the completion time 𝑇𝑖 (𝑡) = 𝑇𝑖 (𝑡) + 𝑇𝑖comm (𝑡) follows a stochastic process with hazard rate 𝜆𝑖 (𝑡) governing the recovery from deadline violations. Then, for a small time interval Δ corresponding to one round, the recovery probability satisfies 𝛽𝑖 (𝑡) = 1 − exp(−𝜆𝑖 (𝑡)Δ) + 𝑂 (Δ2 ) (46)

Pr(𝑇𝑖 ≤ Δ | 𝑇𝑖 > 0) = 1 − exp(−𝜆𝑖 (𝑡)Δ) + 𝑂 (Δ2 )

(50)

True round success is defined as:

Eq. (10) defines the recovery probability as the conditional probability that a node meets the deadline in the next round, given that it failed in the previous round:

A.6

𝐹𝑖 (𝑡) ∈ {0, 1}

E𝑖 (𝑡) = {𝐶𝑖 (𝑡) ≥ 𝐶 min } ∩ {𝐵𝑖 (𝑡) ≥ 𝐵 min }

Thus multiplicative composition is the maximum-entropy joint model with bounded worst-case error. A.5

𝐵𝑖 (𝑡),

where: • 𝐶𝑖 (𝑡) = available computation resource, • 𝐵𝑖 (𝑡) = available bandwidth, • 𝐹𝑖 (𝑡) = 1 indicates correlated failure event Define feasibility event:

Proof. By Fréchet–Hoeffding bounds: max(0, 𝑎𝑐 + 𝑎𝑏 − 1) ≤ 𝑝𝑖true ≤ min(𝑎𝑐 , 𝑎𝑏 )

Consistency of the Availability Model

(49) 15

(61)

Step 5: Combine bounds. Substituting:

Then the participation estimator satisfies: 1 (𝑡)𝑎𝑖comm (𝑡) Λ𝑖2 Δ2 (62) 2 In particular, if 𝜅𝑖 (𝑡) → 0 and Δ → 0, then comp

𝑝𝑖′ (𝑡) − 𝑝𝑖true (𝑡) ≤ 𝑝 𝜅𝑖 (𝑡) + 𝑝 𝑎𝑖

comp comm 1 2 2 𝑎𝑖 Λ𝑖 Δ

𝑝𝑖′ (𝑡) − 𝑝𝑖true (𝑡) ≤ 𝑝 𝜅𝑖 (𝑡) + 𝑝 𝑎𝑖

This completes the proof. 𝑝𝑖′ (𝑡) → 𝑝𝑖true (𝑡)

(63)

A.8

Proof. Step 1: Expand true participation probability. By definition, 𝑝𝑖true (𝑡) = P(E𝑖 (𝑡) ∩ {𝐹𝑖 (𝑡) = 0}) Using independence assumption (2): = P(E𝑖 (𝑡))P(𝐹𝑖 (𝑡) = 0)

(64)

comp

(𝑡)𝑎𝑖comm (𝑡) (1 − 𝜌𝑖 (𝑡))

Consistency of the Availability Model with Correlated Failures (Eq. 12–15)

Probability Space and Failure Graph Model. Let (Ω, F , P) be a probability space. For each round 𝑡, define:

(65)

𝐶𝑖 (𝑡), 𝐵𝑖 (𝑡) and a vector of binary failure variables:

(66)

Step 2: Insert multiplicative decomposition. Add and subtract the product form: 𝑝𝑖true (𝑡) = 𝑎𝑖

(67)

trace fail 𝛾𝑖,𝑗 (𝑡) = 𝛼𝛾𝑖,𝑗 + (1 − 𝛼)𝛾𝑖,𝑗 (𝑡)

(68)

(80)

Define:

By assumption (1), comp

P(E𝑖 (𝑡)) − 𝑎𝑖 Therefore, comp

(78)

Z(𝑡) = (𝑍 1 (𝑡), . . . , 𝑍 𝑁 (𝑡)) ∈ {0, 1}𝑁 (79) where 𝑍𝑖 (𝑡) = 1 denotes that client 𝑖 experiences a failure (dropout or timeout) at round 𝑡. Define the (paper) correlation score:

comp P(E𝑖 (𝑡)) − 𝑎𝑖 (𝑡)𝑎𝑖comm (𝑡) (1 − 𝜌𝑖 (𝑡))

𝑝𝑖true (𝑡) − 𝑎𝑖

□

We refine the consistency analysis to explicitly account for the paper’s runtime co-correlation model (Eq. 12–14) and the correlation penalty 𝜌𝑖 (𝑡).

Thus, 𝑝𝑖true (𝑡) = P(E𝑖 (𝑡)) (1 − 𝜌𝑖 (𝑡))

(77)

(𝑡)𝑎𝑖comm (𝑡) ≤ 𝜅𝑖 (𝑡)

(𝑡)𝑎𝑖comm (𝑡) (1 − 𝜌𝑖 (𝑡)) ≤ 𝜅𝑖 (𝑡)

G𝑖 (𝑡) = { 𝑗 : 𝛾𝑖,𝑗 (𝑡) > 𝜏corr } Define the correlation penalty (Eq. 14): ∑︁ 𝜌𝑖 (𝑡) = 𝐶ˆ𝑖,𝑗 𝛾𝑖,𝑗 (𝑡)

(69)

(70)

(82)

𝑗 ∈ G𝑖 (𝑡 )

Step 3: Insert recovery approximation. Now consider estimator: comp

(81)

We interpret 𝜌𝑖 (𝑡) as an upper bound on conditional failure risk induced by correlated peers.

𝑝𝑖′ (𝑡) = 𝑝𝑎𝑖 (𝑡)𝑎𝑖comm (𝑡) (1 − 𝛽𝑖 (𝑡)) Subtract from true probability:

(71)

𝑝𝑖′ (𝑡) − 𝑝𝑖true (𝑡)

(72)

True Success Variable. Define feasibility event: E𝑖 (𝑡) = {𝐶𝑖 (𝑡) ≥ 𝐶 min } ∩ {𝐵𝑖 (𝑡) ≥ 𝐵 min } Define true round success:

comp comp ≤ 𝑝 𝑎𝑖 𝑎𝑖comm (1 − 𝛽𝑖 ) − 𝑎𝑖 𝑎𝑖comm (1 − 𝜌𝑖 ) + 𝑝𝜅𝑖 (𝑡)

(73)

(83)

𝑌𝑖 (𝑡) = 1{E𝑖 (𝑡)} · (1 − 𝑍𝑖 (𝑡))

(84)

𝑝𝑖true (𝑡) = P(𝑌𝑖 (𝑡) = 1)

(85)

Thus:

Factor: comp = 𝑝𝑎𝑖 𝑎𝑖comm |𝜌𝑖 − 𝛽𝑖 | + 𝑝𝜅𝑖 (𝑡)

(74)

AW-PSP Estimator. AW-PSP uses:

Step 4: Apply hazard expansion bound. By Taylor expansion of exponential: 1 𝛽𝑖 (𝑡) = 𝜆𝑖 (𝑡)Δ − 𝜆𝑖 (𝑡) 2 Δ2 + 𝑂 (Δ3 ) 2

(75)

h i comp comp 𝑝𝑖′ (𝑡) = 𝑝 · (𝑎𝑖 𝑎𝑖comm ) + (1 −𝑎𝑖 𝑎𝑖comm )𝛽𝑖 (𝑡) (1 − 𝜌𝑖 (𝑡)) (86) For the purpose of validating Eq. (8)–(10) plus the correlation penalty, we focus on the primary factorization:

1 |𝜌𝑖 (𝑡) − 𝛽𝑖 (𝑡)| ≤ Λ𝑖2 Δ2 2

(76)

comp 𝑝˜𝑖 (𝑡) = 𝑝 · 𝑎𝑖 (𝑡)𝑎𝑖comm (𝑡) (1 − 𝜌𝑖 (𝑡))

Thus

(87)

Theorem A.6 (Consistency with Explicit Correlated-Failure Error Term). Assume: 1. (Bounded dependence of resources) There exists 𝜅𝑖 (𝑡) such that comp

P(E𝑖 (𝑡)) − 𝑎𝑖

(𝑡)𝑎𝑖comm (𝑡) ≤ 𝜅𝑖 (𝑡)

comp

P(E𝑖 (𝑡)) = 𝑎𝑖

(100)

where |Δ𝑖 (𝑡)| ≤ 𝜅𝑖 (𝑡) by Assumption (1). Hence:

(88) comp comm 𝑎𝑖 (1 − 𝜌𝑖 (𝑡)) + Δ𝑖 (𝑡) (1 − 𝜌𝑖 (𝑡))

P(E𝑖 (𝑡)) (1 − 𝜌𝑖 (𝑡)) = 𝑎𝑖

2. (Correlated failure upper bound) The correlation penalty 𝜌𝑖 (𝑡) satisfies:

(101)

𝜌 P(𝑍𝑖 (𝑡) = 1 | E𝑖 (𝑡)) ≤ 𝜌𝑖 (𝑡) + 𝜖𝑖 (𝑡) (89) 𝜌 for some 𝜖𝑖 (𝑡) ≥ 0 capturing mismatch between the

Taking absolute values: comp comm 𝑎𝑖 (1 − 𝜌𝑖 (𝑡))

P(E𝑖 (𝑡)) (1 − 𝜌𝑖 (𝑡)) − 𝑎𝑖

penalty model and the true conditional failure risk. 3. (Recovery approximation) The recovery estimator satisfies: 𝛽 |P(𝑍𝑖 (𝑡 + 1) = 0 | 𝑍𝑖 (𝑡) = 1) − 𝛽𝑖 (𝑡)| ≤ 𝜖𝑖 (𝑡)

(𝑡)𝑎𝑖comm (𝑡) + Δ𝑖 (𝑡)

≤ 𝜅𝑖 (𝑡) (102)

Step 4: combine. Recall:

(90)

comp 𝑝˜𝑖 (𝑡) = 𝑝 · 𝑎𝑖 (𝑡)𝑎𝑖comm (𝑡) (1 − 𝜌𝑖 (𝑡))

Then, for each round 𝑡,

(103)

Thus:

comp 𝜌 𝑝˜𝑖 (𝑡) − 𝑝𝑖true (𝑡) ≤ 𝑝 𝜅𝑖 (𝑡)+𝑝 𝜖𝑖 (𝑡)+𝑝 𝑎𝑖 (𝑡)𝑎𝑖comm (𝑡)𝜌𝑖 (𝑡)𝜅𝑖 (𝑡) comp 𝜌 𝑝˜𝑖 (𝑡) − 𝑝𝑖true (𝑡) ≤ 𝑝 𝜅𝑖 (𝑡) +𝑝 𝜖𝑖 (𝑡) +𝑝 𝑎𝑖 𝑎𝑖comm 𝜌𝑖 (𝑡)𝜅𝑖 (𝑡) (91) (104) Moreover, incorporating recovery yields 𝜌 where the final product term arises from bounding P(E𝑖 (𝑡))𝜖𝑖 (𝑡) comp comm using P(E𝑖 (𝑡)) ≤ 𝑎𝑖 𝑎𝑖 + 𝜅𝑖 (𝑡). 𝜌 𝛽 𝑝𝑖′ (𝑡) − 𝑝𝑖true (𝑡) ≤𝑝 𝜅𝑖 (𝑡) + 𝑝 𝜖𝑖 (𝑡) + 𝑝 𝜖𝑖 (𝑡) Step 5: recovery term. The extension to 𝑝𝑖′ (𝑡) follows by (92) comp adding Assumption (3) and bounding the induced deviation + 𝑝 𝑎𝑖 (𝑡)𝑎𝑖comm (𝑡)𝜌𝑖 (𝑡)𝜅𝑖 (𝑡) 𝛽 by 𝜖𝑖 (𝑡), since the recovery component contributes only Proof. Step 1: expand true success probability. By definiwhen feasibility fails and 𝑍𝑖 (𝑡) = 1. The approximation error 𝜌 tion, 𝜖𝑖 (𝑡) captures the extent to which runtime correlation structure (Eq. 12–14) matches the true co-failure process; when 𝜌 𝑝𝑖true (𝑡) = P(E𝑖 (𝑡) ∩ {𝑍𝑖 (𝑡) = 0}). (93) 𝜖𝑖 (𝑡) is small, multiplicative downweighting by (1 − 𝜌𝑖 (𝑡)) Condition on E𝑖 (𝑡): is theoretically justified. □

𝑝𝑖true (𝑡) = P(E𝑖 (𝑡)) · P(𝑍𝑖 (𝑡) = 0 | E𝑖 (𝑡)) Rewrite: P(𝑍𝑖 (𝑡) = 0 | E𝑖 (𝑡)) = 1 − P(𝑍𝑖 (𝑡) = 1 | E𝑖 (𝑡))

Theorem A.7 (Convergence under Bounded Sampling Distortion). Consider the global objective

(94)

𝐹 (𝑤) =

(95)

𝜌

(96)

𝜌

(97)

𝜌

𝑁 ∑︁

𝑞𝑖 = 1

(105)

𝑖=1

𝑔𝑡 =

𝑁 ∑︁ 𝑖=1

𝑝𝑖true (𝑡) ≥ P(E𝑖 (𝑡)) (1 − 𝜌𝑖 (𝑡)) − P(E𝑖 (𝑡))𝜖𝑖 (𝑡)

𝑞𝑖 ≥ 0,

where each 𝐹𝑖 is 𝐿-smooth and 𝜇-strongly convex. Let 𝑤 ∗ = arg min𝑤 𝐹 (𝑤). At round 𝑡, client 𝑖 is selected with true inclusion probability 𝑝𝑖true (𝑡), while AW-PSP uses proxy probabilities 𝑝𝑖′ (𝑡). Let 𝐼𝑖 (𝑡) ∈ {0, 1} denote the inclusion indicator, with E[𝐼𝑖 (𝑡) | 𝑤𝑡 ] = 𝑝𝑖true (𝑡). Define the AW-PSP gradient estimator

thus P(𝑍𝑖 (𝑡) = 0 | E𝑖 (𝑡)) ≥ 1 − 𝜌𝑖 (𝑡) − 𝜖𝑖 (𝑡) Therefore,

𝑞𝑖 𝐹𝑖 (𝑤),

𝑖=1

Step 2: compare correlated-failure factor. By Assumption (2), P(𝑍𝑖 (𝑡) = 1 | E𝑖 (𝑡)) ≤ 𝜌𝑖 (𝑡) + 𝜖𝑖 (𝑡)

𝑁 ∑︁

𝐼𝑖 (𝑡)

𝑞𝑖 ∇𝐹𝑖 (𝑤𝑡 ; 𝜉𝑖𝑡 ) 𝑝𝑖′ (𝑡)

(106)

and update

(98)

𝑤𝑡 +1 = 𝑤𝑡 − 𝜂𝑡 𝑔𝑡

Similarly, trivially P(𝑍𝑖 (𝑡) = 0 | E𝑖 (𝑡)) ≤ 1 implies

(107)

Assume: (A1) Bounded sampling distortion: there exists 𝛿 > 0 such that

𝑝𝑖true (𝑡) ≤ P(E𝑖 (𝑡)) (99) Step 3: compare feasibility factor. Insert and subtract comp 𝑎𝑖 𝑎𝑖comm :

|𝑝𝑖′ (𝑡) − 𝑝𝑖true (𝑡)| ≤ 𝛿, 17

∀𝑖, 𝑡 .

(108)

(A2) Positive lower bound on sampling probabilities: there exists 𝑝 min > 0 such that 𝑝𝑖′ (𝑡) ≥ 𝑝 min − 𝛿 > 0,

𝑝𝑖true (𝑡) ≥ 𝑝 min,

Define

∀𝑖, 𝑡 (109)

(A3) Unbiased local stochastic gradients: E ∇𝐹𝑖 (𝑤𝑡 ; 𝜉𝑖𝑡 ) | 𝑤𝑡 = ∇𝐹𝑖 (𝑤𝑡 ) E ∥∇𝐹𝑖 (𝑤𝑡 ; 𝜉𝑖𝑡 ) − ∇𝐹𝑖 (𝑤𝑡 ) ∥ 2

𝑤𝑡 ≤ 𝜎 ,

(110)

∀𝑖, 𝑡

∀𝑖, 𝑤

1 , 𝜇 (𝑡 + 𝛾)

(121)

𝑔𝑡 = E[𝑔𝑡 | 𝑤𝑡 ] + 𝜁𝑡 , E[𝜁𝑡 | 𝑤𝑡 ] = 0 Í Í We first bound E∥𝑔𝑡 ∥ 2 . By ∥ 𝑖 𝑎𝑖 ∥ 2 ≤ 𝑁 𝑖 ∥𝑎𝑖 ∥ 2 ,

(111)

𝑞𝑖 ∥𝑔𝑡 ∥ = 𝐼𝑖 (𝑡) ′ ∇𝐹𝑖 (𝑤𝑡 ; 𝜉𝑖𝑡 ) 𝑝𝑖 (𝑡) 𝑖=1

(112)

≤𝑁

𝑁 ∑︁

𝐼𝑖 (𝑡)

𝑖=1

𝛾 ≥ max{1, 𝐿/𝜇},

(113)

𝑞𝑖2 ∥∇𝐹𝑖 (𝑤𝑡 ; 𝜉𝑖𝑡 ) ∥ 2 ′ (𝑝𝑖 (𝑡)) 2

E∥∇𝐹𝑖 (𝑤𝑡 ; 𝜉𝑖𝑡 ) ∥ 2 =∥∇𝐹𝑖 (𝑤𝑡 ) ∥ 2 + E∥∇𝐹𝑖 (𝑤𝑡 ; 𝜉𝑖𝑡 ) − ∇𝐹𝑖 (𝑤𝑡 ) ∥ 2

E[𝐹 (𝑤𝑡 ) − 𝐹 (𝑤 ∗ )] ≤

𝐶1 + 𝐶 2 𝛿, 𝑡 +𝛾

∀𝑡 ≥ 0

≤ 𝐺2 + 𝜎2

(114)

(124) together with E[𝐼𝑖 (𝑡) | 𝑤𝑡 ] = 𝑝𝑖true (𝑡) ≤ 1, we obtain

Hence AW-PSP converges to a neighborhood of the optimum whose radius is 𝑂 (𝛿), and recovers the standard 𝑂 (1/𝑡) rate when 𝛿 = 0.

E[∥𝑔𝑡 ∥ 2 | 𝑤𝑡 ] ≤ 𝑁

Proof. We divide the proof into four steps.

𝑞𝑖2 2 2 ′ (𝑡)) 2 (𝐺 + 𝜎 ) (𝑝 𝑖 𝑖=1

𝑁 ∑︁

Step 1: Bias of the AW-PSP gradient estimator. Define the conditional bias

≤

𝑁 𝑁 (𝐺 2 + 𝜎 2 ) ∑︁ 2 𝑞 (𝑝 min − 𝛿) 2 𝑖=1 𝑖

𝑏𝑡 := E[𝑔𝑡 | 𝑤𝑡 ] − ∇𝐹 (𝑤𝑡 ).

≤

𝑁 (𝐺 2 + 𝜎 2 ) =: 𝑉 (𝑝 min − 𝛿) 2

(115)

Using the definition of 𝑔𝑡 , the tower property, and Assumption (A3), 𝑁 ∑︁

E[𝐼𝑖 (𝑡) | 𝑤𝑡 ]

𝑖=1

𝑝 true (𝑡) ∇𝐹𝑖 (𝑤𝑡 ) = 𝑞𝑖 𝑖 ′ 𝑝𝑖 (𝑡) 𝑖=1

E[∥𝑔𝑡 ∥ 2 | 𝑤𝑡 ] ≤ 𝑉

Step 3: One-step recursion in squared distance. Let 𝑟𝑡 := E∥𝑤𝑡 − 𝑤 ∗ ∥ 2 .

(116)

∥𝑤𝑡 +1 − 𝑤 ∗ ∥ 2 = ∥𝑤𝑡 − 𝑤 ∗ ∥ 2 − 2𝜂𝑡 ⟨𝑤𝑡 − 𝑤 ∗, 𝑔𝑡 ⟩ + 𝜂𝑡2 ∥𝑔𝑡 ∥ 2 (128) (117)

Taking conditional expectation given 𝑤𝑡 , E ∥𝑤𝑡 +1 − 𝑤 ∗ ∥ 2 | 𝑤𝑡 = ∥𝑤𝑡 − 𝑤 ∗ ∥ 2 − 2𝜂𝑡 ⟨𝑤𝑡 − 𝑤 ∗, ∇𝐹 (𝑤𝑡 )

By Assumptions (A1)–(A2), 𝑝𝑖true (𝑡) |𝑝𝑖true (𝑡) − 𝑝𝑖′ (𝑡)| 𝛿 − 1 = ≤ ′ ′ 𝑝𝑖 (𝑡) 𝑝𝑖 (𝑡) 𝑝 min − 𝛿 Í Using 𝑖 𝑞𝑖 = 1 and Assumption (A5),

+ 𝑏𝑡 + 𝜂𝑡2 E[∥𝑔𝑡 ∥ 2 | 𝑤𝑡 ]

(118)

(129) Since 𝐹 is 𝜇-strongly convex, ⟨∇𝐹 (𝑤𝑡 ), 𝑤𝑡 − 𝑤 ∗ ⟩ ≥ 𝜇 ∥𝑤𝑡 − 𝑤 ∗ ∥ 2

𝑝 true (𝑡) ∥𝑏𝑡 ∥ ≤ 𝑞𝑖 𝑖 ′ − 1 ∥∇𝐹𝑖 (𝑤𝑡 ) ∥ 𝑝𝑖 (𝑡) 𝑖=1 𝑁 ∑︁

𝑝 min − 𝛿 𝑖=1

𝑞𝑖 𝐺 =

(127)

Using the update rule,

true 𝑁 ∑︁ 𝑝𝑖 (𝑡) 𝑏𝑡 = 𝑞𝑖 − 1 ∇𝐹𝑖 (𝑤𝑡 ) 𝑝𝑖′ (𝑡) 𝑖=1

𝑁 ∑︁

(126)

where 𝑉 is finite and independent of 𝑡.

Therefore,

𝛿

(125)

Hence

𝑞𝑖 E ∇𝐹𝑖 (𝑤𝑡 ; 𝜉𝑖𝑡 ) | 𝑤𝑡 ′ 𝑝𝑖 (𝑡)

𝑁 ∑︁

≤

(123)

Taking conditional expectation and using

the iterates satisfy

E[𝑔𝑡 | 𝑤𝑡 ] =

(122)

𝑁 ∑︁

Then there exist constants 𝐶 1, 𝐶 2 > 0, independent of 𝑡 and 𝛿, such that for the diminishing stepsize 𝜂𝑡 =

∥𝑏𝑡 ∥ ≤ 𝐵𝛿 = 𝑂 (𝛿)

Step 2: Second-moment bound for the estimator. Write

(A5) Bounded gradients: ∥∇𝐹𝑖 (𝑤) ∥ ≤ 𝐺,

(120)

Then

(A4) Bounded variance: there exists 𝜎 2 such that

𝐺𝛿 . 𝑝 min − 𝛿

𝐵𝛿 :=

𝐺𝛿 𝑝 min − 𝛿

(130)

Also, because 𝐹 is the weighted average of functions with gradient norm bounded by 𝐺, (119)

∥∇𝐹 (𝑤) ∥ =

𝑁 ∑︁ 𝑖=1

𝑞𝑖 ∇𝐹𝑖 (𝑤) ≤

𝑁 ∑︁ 𝑖=1

𝑞𝑖 ∥∇𝐹𝑖 (𝑤) ∥ ≤ 𝐺 (131)

Since ∇𝐹 (𝑤 ∗ ) = 0, strong convexity implies ∗

Taking expectation and using (140), 𝐿 E[𝐹 (𝑤𝑡 ) − 𝐹 (𝑤 ∗ )] ≤ 𝑟𝑡 2 𝐿𝐾 𝐿 ≤ + 𝐴 2(𝑡 + 𝛾) 2 𝐿𝐾 𝐿𝐺 = + 2 𝐵𝛿 2(𝑡 + 𝛾) 𝜇 Recalling

∗

𝜇 ∥𝑤𝑡 −𝑤 ∥ ≤ ∥∇𝐹 (𝑤𝑡 ) − ∇𝐹 (𝑤 ) ∥ = ∥∇𝐹 (𝑤𝑡 ) ∥ ≤ 𝐺 (132) hence ∥𝑤𝑡 − 𝑤 ∗ ∥ ≤

𝐺 𝜇

(133)

Therefore, using (121), 𝐺 |⟨𝑤𝑡 − 𝑤 ∗, 𝑏𝑡 ⟩| ≤ ∥𝑤𝑡 − 𝑤 ∗ ∥ ∥𝑏𝑡 ∥ ≤ 𝐵𝛿 𝜇

(134)

Substituting (130), (126), and (134), 𝐺 E ∥𝑤𝑡 +1 − 𝑤 ∗ ∥ 2 | 𝑤𝑡 ≤ (1 − 2𝜇𝜂𝑡 ) ∥𝑤𝑡 − 𝑤 ∗ ∥ 2 + 2𝜂𝑡 𝐵𝛿 + 𝜂𝑡2𝑉 𝜇 (135) Taking full expectation gives 𝑟𝑡 +1 ≤ (1 − 2𝜇𝜂𝑡 )𝑟𝑡 + 2𝜂𝑡

𝐺 𝐵𝛿 + 𝜂𝑡2𝑉 𝜇

Step 4: Solve the recursion. Choose 1 , 𝛾 ≥ 1. 𝜂𝑡 = 𝜇 (𝑡 + 𝛾) Then (136) becomes 2 2𝐺𝐵𝛿 1 𝑉 1 𝑟𝑡 +1 ≤ 1 − 𝑟𝑡 + + 𝑡 +𝛾 𝜇 2 𝑡 + 𝛾 𝜇 2 (𝑡 + 𝛾) 2

(136)

(137)

(138)

Define

2𝐺𝐵𝛿 𝑉 , 𝐶 := 2 (139) 2 𝜇 𝜇 We claim that there exists a constant 𝐾 > 0, independent of 𝑡 and 𝛿, such that 𝐾 𝑟𝑡 ≤ +𝐴 ∀𝑡 ≥ 0. (140) 𝑡 +𝛾 𝐴 :=

We prove this by induction. For 𝑡 = 0, choose 𝐾 ≥ 𝛾𝑟 0 , so the claim holds. Assume it holds at time 𝑡. Then from (138), 2 𝐾 𝐴 𝐶 𝑟𝑡 +1 ≤ 1 − +𝐴 + + 𝑡 +𝛾 𝑡 +𝛾 𝑡 + 𝛾 (𝑡 + 𝛾) 2 2𝐾 𝐶 1 𝐾 =𝐴 1− + − + 𝑡 +𝛾 𝑡 + 𝛾 (𝑡 + 𝛾) 2 (𝑡 + 𝛾) 2 𝐾 𝐾 ≤𝐴+ − provided 𝐾 ≥ 𝐶. (141) 𝑡 + 𝛾 (𝑡 + 𝛾) 2 Since 𝐾 𝐾 𝐾 𝐾 𝐾 = − ≥ − 𝑡 + 𝛾 + 1 𝑡 + 𝛾 (𝑡 + 𝛾) (𝑡 + 𝛾 + 1) 𝑡 + 𝛾 (𝑡 + 𝛾) 2 (142) we obtain 𝐾 𝑟𝑡 +1 ≤ 𝐴 + (143) 𝑡 +𝛾 + 1 Thus (140) holds for all 𝑡. Finally, since 𝐹 is 𝐿-smooth and minimized at 𝑤 ∗ , 𝐿 𝐹 (𝑤𝑡 ) − 𝐹 (𝑤 ∗ ) ≤ ∥𝑤𝑡 − 𝑤 ∗ ∥ 2 (144) 2

𝐵𝛿 =

𝐺𝛿 𝑝 min − 𝛿

(145)

(146)

, we obtain 𝐶1 + 𝐶2 𝛿 (147) 𝑡 +𝛾 for suitable constants 𝐶 1, 𝐶 2 > 0 independent of 𝑡. This proves the claim. □ E[𝐹 (𝑤𝑡 ) − 𝐹 (𝑤 ∗ )] ≤

Record · ID 31240 · SHA-256 632af5de76ba044f
Conceptio Open Knowledge Archive — every document is proof-bundled with source, license, and retrieval metadata.