1 Introduction↩︎

Federated Learning (FL) has emerged as a privacy-preserving distributed machine learning paradigm that enables collaborative model training when data cannot be centrally shared [1]–[3]. By performing training on local devices and exchanging only model updates, FL allows distributed data resources to be effectively utilized without direct access to raw data and has demonstrated significant potential in applications such as mobile intelligence, the Internet of Things and cross-organizational collaboration [4], [5].

However, most existing federated learning frameworks adopt a centralized and synchronous training paradigm, where a central server collects model updates from all clients and aggregates them in each training round. While such designs perform well under ideal network conditions, they face multiple challenges in real-world systems. First, the central server introduces a single point of bottleneck and failure, which limits scalability due to constraints on communication bandwidth, computation capacity and reliability in large-scale deployments [6]. Second, synchronous training requires strict temporal alignment of clients at round boundaries, making the system vulnerable to device heterogeneity and system variability and leading to the well-known straggler problem that significantly degrades training efficiency [7], [8]. Finally, centralized architectures are often difficult to deploy in cross-organizational or cross-domain scenarios and conflict with the growing demand for trustless and autonomous systems [6], [9].

To overcome these limitations, Decentralized Federated Learning (DFL) has attracted increasing attention. In DFL, clients exchange model information only with their neighboring nodes without relying on a central server, thereby improving system robustness and scalability [9], [10]. Nevertheless, most existing decentralized approaches still rely on synchronous update mechanisms, assuming that clients remain aligned across logical training rounds, an assumption that is difficult to satisfy in dynamic network environments [11], [12].

Consequently, Asynchronous Decentralized Federated Learning (ADFL) has been recognized as a more practical training paradigm for real-world deployments [12], [13]. ADFL allows clients to perform local updates and communications at different times without global synchronization, while supporting model collaboration solely through neighbor-to-neighbor communication [14], [15]. This setting naturally accommodates device heterogeneity, network variability and partial participation and enables clients to join the training process at arbitrary times [16], [17]. As a result, ADFL is well suited for edge computing, peer-to-peer networks and large-scale distributed systems, offering significant advantages in terms of system throughput, fault tolerance and deployment flexibility.

Despite these advantages, such a highly flexible training paradigm also introduces new challenges. Specifically, ADFL systems often face three fundamental difficulties simultaneously. First, since clients communicate only with their neighbors and model exchanges may occur frequently, directly transmitting full model parameters incurs prohibitive communication overhead, which is difficult to sustain in bandwidth-constrained or large-scale systems [1], [18]. Compared to centralized settings, decentralized architectures lack unified communication scheduling and aggregation, making communication efficiency a more prominent concern [9], [19]. Second, asynchronous updates combined with asymmetric communication topologies can lead to biased aggregation [20], [21]. In practice, clients may push models at different times and communication links can be unbalanced, under which naive neighbor averaging fails to guarantee unbiased consensus [15], [22]. Finally, the widely observed statistical heterogeneity (non-IID data) across clients is further amplified in asynchronous decentralized environments [12], [14], [23]. Local updates computed on non-identically distributed data tend to induce significant model drift, while asynchronous communication may delay or mismatch these updates, exacerbating training instability and degrading final performance [24], [25].

These challenges are not independent. Communication constraints necessitate compression. Compression can amplify client drift under non-IID data. Asynchrony further delays and skews these updates. Together, these effects exacerbate aggregation bias in decentralized training. Accordingly, the central research question addressed in this work is:

How can we jointly design compression, de-biased aggregation, and local-update stabilization for accurate and stable ADFL under asymmetric communication and non-IID data?

To address this research question, we propose a new ADFL framework, termed PushCen-ADFL (Push-Sum Centroid Asynchronous Decentralized Federated Learning). The proposed framework is built around lightweight centroid structures and integrates centroid-based compression with push-sum aggregation, where both aggregation and local optimization are constrained in the same centroid representation space, enabling communication-efficient and stable federated training without relying on a central server or global synchronization.

Our main contributions are summarized as follows:

• We propose PushCen-ADFL, an asynchronous framework that unifies centroid-based communication, push-sum de-biasing and buffered neighbor aggregation into a single decentralized training pipeline, where both aggregation and local optimization operate in the same centroid representation space.

• We design an average-preserving push-sum aggregation with mass splitting and a deduplicated bounded buffer, mitigating bias from asymmetric information flow and preventing stale messages from dominating aggregation.

• We develop a centroid-aligned proximal regularizer that stabilizes local updates in the same compressed centroid space used for communication. This alignment mitigates non-IID data distributions by contracting local trajectories toward a shared compressed reference.

• We provide a convergence analysis for PushCen-ADFL and validate it on CIFAR-10, CIFAR-100 and Tiny-ImageNet, improving accuracy by up to 6% over communication-efficient baselines, while reducing per-push transmitted payload by more than 80% less than full-model communication.

2 Related Work↩︎

2.1 Asynchronous Decentralized FL↩︎

A representative direction is to design wait-free or fully asynchronous communication mechanisms to mitigate stragglers. SWIFT proposes a wait-free decentralized FL algorithm that allows each client to proceed without synchronization barriers, while maintaining standard iteration complexity guarantees [11]. Complementarily, A\(^2\)CiD\(^2\) studies asynchronous decentralized deep learning from an optimization perspective and introduces a continuous local momentum to accelerate randomized gossip-style communication [26]. Beyond communication primitives, a second line of work explicitly addresses the staleness and heterogeneity issues that arise in ADFL. Ma et al. propose dynamic staleness control for ADFL in decentralized topologies, aiming to balance training efficiency with model quality by regulating the tolerated staleness degree and deriving scheduling/control policies with theoretical support [23]. For heterogeneous devices, Liao et al. develop AsyDFL, which integrates neighbor selection and gradient pushing to reduce communication cost and completion time under non-IID data and system heterogeneity [27]. More recently, DSpodFL provides a unified viewpoint by modeling both local updates and pairwise exchanges as sporadic random events, thereby capturing time-varying computation/communication patterns [28]. In addition, AEDFL proposes an ADFL framework that leverages reinforcement learning for neighbor model selection in heterogeneous, serverless training settings [12]. Despite these advances, most existing ADFL methods focus on asynchronous scheduling or staleness control while assuming full-precision communication, and thus fail to jointly address frequent peer-to-peer exchanges, aggregation bias on asymmetric communication, and model drift under non-IID data, limiting their practicality in communication-constrained decentralized systems.

2.2 Communication-Efficient Federated Learning↩︎

A prominent line of research leverages knowledge distillation to reduce the communication payload. FedKD adopts a local teacher-student scheme and transmits only a compact student (or distilled knowledge), substantially lowering uplink/downlink costs while preserving accuracy via distillation [29]. Another direction exploits sparsity to shrink communicated updates: SpaFL induces structured sparsity with low overhead through trainable thresholds, reducing both communication and computation [30]. In addition, low-precision methods cut the bit-width of local training and transmitted updates; Li et al. show that low-precision local training can already achieve competitive accuracy in FL [31]. Communication efficiency has also been explored under asynchronous decentralized settings: DivShare exchanges model fragments per interaction to better tolerate stragglers and bandwidth heterogeneity, improving wall-clock convergence in peer-to-peer training [32]. Overall, prior communication-efficient FL methods reduce communication cost but are not designed to handle the coupled challenges of aggregation bias and training instability in fully asynchronous decentralized environments.

3 Problem Formulation↩︎

We consider an ADFL system with \(N\) clients, denoted by \(\mathcal{V}=\{1,2,\dots,N\}\). Client communications are modeled by a directed graph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) induced by asynchronous gossip, where \((j \rightarrow i)\in\mathcal{E}\) indicates that client \(i\) can receive information from client \(j\). The communication topology can be asymmetric and unbalanced and there is no central server; clients communicate only with their neighbors. We denote the in-neighbors and out-neighbors of client \(i\) as \(\mathcal{N}_i^-\) and \(\mathcal{N}_i^+\), respectively.

Each client \(i\) holds a private local dataset \(\mathcal{D}_i\) with potentially heterogeneous (non-IID) data distributions, and maintains a local model copy \(w_i\). Let \(f_i(w)\) denote the empirical risk on \(\mathcal{D}_i\). We adopt a uniform client-level objective and formulate decentralized learning as a consensus optimization problem: \[\min_{\{w_i\}_{i=1}^{N}}\;\frac{1}{N}\sum_{i=1}^{N} f_i(w_i) \quad \text{s.t.}\quad w_i = w_j,\;\forall (j\rightarrow i)\in\mathcal{E}.\]

where the constraints \(w_i = w_j\) specify the desired agreement among local models at convergence, while local models may differ during asynchronous training. The system operates in a fully asynchronous manner without global synchronization. Clients perform local computation and communication at arbitrary times and received messages may correspond to stale model states due to heterogeneous computation speeds and network delays. Moreover, clients may become active at arbitrary times, and only active clients generate updates and participate in communication.

Under directed and potentially unbalanced topologies, achieving the above consensus objective requires decentralized aggregation mechanisms that preserve the uniform client-level average. Accordingly, the problem addressed in this work is to design a communication-efficient ADFL framework that enables stable and robust training under asymmetric communication and non-IID data distributions.

4 Push-Sum Centroid Asynchronous Decentralized Federated Learning↩︎

4.1 Overview of PushCen-ADFL↩︎

The overall workflow of PushCen-ADFL is illustrated in Figure 1 and summarized in Algorithm 2.

Clients exchange information only with their neighbors over a peer-to-peer communication, without relying on a central coordinator or round-based synchronization.

PushCen-ADFL is built on three coupled principles. First, each push transmits a centroid message \((V_i, A_i)\) instead of dense parameters, so the communication payload is controlled by the centroid budget. Second, aggregation follows a mass split push-sum update, using the mass push-sum \(s_i\) to correct bias and preserve the averaging under directed asynchronous mixing. Third, local optimization is stabilized by a centroid proximal term anchored at the current dictionary estimate \(G_i\), so that both communication and stabilization operate in the same centroid representation space. In addition, a deduplicated bounded buffer retains only the most recent message per sender, preventing stale or repeated messages from dominating the event-driven aggregation.

Concretely, each client \(i\) maintains a local model \(w_i\), a push-sum mass \(s_i\) that tracks the mixing weight for de-biased aggregation, and a local centroid dictionary estimate \(G_i\) that defines the shared compressed representation space, together with a bounded buffer \(\mathcal{B}_i\) that stores recent neighbor messages (line 1). When a neighbor message \((V_j, A_j, \sigma_{j\rightarrow i}, j)\) arrives, client \(i\) updates \(\mathcal{B}_i\) via BufferUpdate (lines 3–5), which replaces older entries from the same sender and enforces a fixed buffer capacity; see Section 4.5. Upon a local compute event, client \(i\) aggregates buffered information using PushSumAgg (line 6), which jointly updates \((w_i, G_i, s_i)\) in an average-preserving manner under directed and potentially unbalanced communication; see Section 4.4. Client \(i\) then performs LocalUpdate on \(\mathcal{D}_i\) (line 7). For communication, the model is encoded in a centroid form \((V_i, A_i)\) (Section 4.3); for optimization, the update is anchored to a centroid-based reference constructed from \(G_i\), yielding a centroid-aligned proximal effect that contracts local trajectories and mitigates non-IID drift; see Section 4.2. Finally, client \(i\) splits its push-sum mass (line 8) and sends \((V_i, A_i, \sigma_i, i)\) to all out-neighbors (line 9), ensuring that subsequent asynchronous aggregations remain average-preserving.

4.2 Centroid Regularization↩︎

Non-IID data can cause client drift, which is further amplified by asynchronous execution. To mitigate this drift, PushCen-ADFL introduces a lightweight centroid regularization in the local update step (Algorithm 3). Client \(i\) first applies WCP to initialize the assignments \(A_i\) and pruning mask \(M_i\) (line 1), and then constructs a centroid anchor from its current centroid dictionary estimate \(G_i\) (line 2), where \(A_i\) specifies how centroids are indexed to form a layer-wise reference. We instantiate the centroid anchor \(\tilde{w}_i\) by decoding the assignment map \(A_i\) with the centroid dictionary \(G_i\) through an element-wise lookup: \[\tilde{w}_{i,l} \triangleq G_{i,l}[A_{i,l}], \label{eq:anchor-def}\tag{1}\] where each entry of \(\tilde{w}_{i,l}\) takes the centroid value indexed by the corresponding entry in \(A_{i,l}\), yielding the same shape as \(w_{i,l}\).

Client \(i\) then performs local optimization with a proximal-style regularizer while enforcing pruning: \[\min_{w_i}\;f_i(w_i;\mathcal{D}_i) + \lambda \|w_i - \tilde{w}_i\|_2^2, \label{eq:cen-reg}\tag{2}\] where \(M_i\) is a binary mask and masked coordinates are kept inactive via \(w_i \leftarrow w_i \odot M_i\) (lines 3–5). Here, \(\lambda\) controls the regularization strength and \(\tilde{w}_i\) is fixed during the local update. Unlike conventional proximal terms that pull toward a global model, \(\tilde{w}_i\) is decoded from the current centroid dictionary, keeping \(w_i\) close to a centroid-structured reference and reducing re-encoding distortion before communication. After local training, client \(i\) applies Weight Clustering Pruning (WCP) to refresh the centroid representation \((V_i,A_i)\) for subsequent communication (line 6) and returns \((w_i,V_i,A_i)\) (line 7).

The motivation is to stabilize asynchronous local optimization without decoupling it from centroid-based compression. In fully asynchronous decentralized training, a client can take many local steps before receiving fresh information; under non-IID data, this can move \(w_i\) into regions poorly represented by the current centroid dictionary, leading to unstable trajectories and larger distortion when the model is re-encoded. The proximal term \(\lambda\|w_i-\tilde{w}_i\|_2^2\) provides a local contraction toward \(\tilde{w}_i\), curbing drift while keeping the iterate close to the dictionary-induced quantized manifold. Figure 4 provides a visualization of centroid regularization. Because \(\tilde{w}_i\) is constructed from \((G_i,A_i)\), the regularizer directly ties the optimization path to the centroid structure used for communication, yielding more stable local updates under asynchrony.

4.3 Centroid-based Model Compression↩︎

PushCen-ADFL compresses communication by encoding each weight layer in a centroid form rather than transmitting dense parameters. For layer \(l\), client \(i\) vectorizes weights \(\theta=\mathrm{vec}(w_{i,l})\in\mathbb{R}^{d_l}\) and clusters its entries into \(K\) scalar centroids, producing a centroid table \(V_{i,l}\in\mathbb{R}^{K}\) and an assignment map \(A_{i,l}\in\{1,\dots,K\}^{d_l}\). Reconstruction uses an element-wise lookup \(w_{i,l}\approx V_{i,l}[A_{i,l}]\), so the payload scales with \(K\) (typically \(K\ll d_l\)) rather than \(d_l\).

Algorithm 5 implements this encoding via WCP. When available, WCP warm-starts centroids from the local dictionary estimate \(G_{i,l}\in\mathbb{R}^{K}\) by setting \(\mu=[0;\,G_{i,l}[1{:}K\!-\!1]]\), fixing one centroid at \(0\) and refining the others by alternating nearest-centroid assignment and cluster-mean updates. It returns \((V_{i,l},A_{i,l})\) and a binary pruning mask \(M_{i,l}\), where SortRemap reorders centroid indices into a canonical order and remaps \(A_{i,l}\) accordingly to ensure consistent encoding. Full cost details are deferred to Appendix 8.

4.4 Asynchronous Push-Sum Aggregation↩︎

Asynchronous decentralized training is inherently imbalanced: fast clients (due to higher compute speed or lower latency) can generate and disseminate updates more frequently, which may cause their local trajectories to dominate aggregation when using naive neighbor averaging. This issue is compounded on directed or unbalanced graphs, where information flow is asymmetric. PushCen-ADFL addresses both effects with an average-preserving push-sum style aggregation that tracks a scalar mass and uses it to normalize heterogeneous message rates and topology asymmetry.

Each client \(i\) maintains a local model \(w_i\), a push-sum mass \(s_i>0\), a local estimate of the centroid dictionary \(G_i\) and a buffer \(\mathcal{B}_i\) that stores neighbor messages received. A buffered message from neighbor \(j\) is denoted by \((V_j, A_j, \sigma_{j\rightarrow i}, j)\), where \((V_j,A_j)\) is the centroid representation and \(\sigma_{j\rightarrow i}\) is the mass share sent to \(i\). Upon aggregation, client \(i\) implicitly reconstructs a quantized neighbor model \(\hat{w}_j=\mathcal{R}(V_j,A_j)\) (Algorithm 6, line 4). It then computes the total mass \[\begin{align} S \leftarrow s_i + \sum_{(V_j,A_j,\sigma_{j\rightarrow i},j)\in\mathcal{B}_i}\sigma_{j\rightarrow i}, \label{eq:pushsum-mass} \end{align}\tag{3}\] which serves as the normalization constant for mass-conserving averaging. Client \(i\) updates its model via \[\begin{align} w_i \leftarrow \frac{s_i}{S}w_i + \sum_{(V_j,A_j,\sigma_{j\rightarrow i},j)\in\mathcal{B}_i}\frac{\sigma_{j\rightarrow i}}{S}\,\hat{w}_j, \label{eq:pushsum-model} \end{align}\tag{4}\]

so that a sender’s influence is determined by conserved mass rather than raw message frequency. The same weights are applied to update the centroid dictionary estimate using the received centroid tables. \[\begin{align} G_i \leftarrow \frac{s_i}{S}G_i + \sum_{(V_j,A_j,\sigma_{j\rightarrow i},j)\in\mathcal{B}_i}\frac{\sigma_{j\rightarrow i}}{S}\,V_j. \label{eq:pushsum-pool} \end{align}\tag{5}\] aligning the shared centroid structure with the aggregated model trajectory. After aggregation, client \(i\) sets \(s_i\leftarrow S\) and clears \(\mathcal{B}_i\).

After local training, client \(i\) performs mass splitting before communication. Let \(d_i^{+}=|\mathcal{N}_i^{+}|\) be the out-degree; client \(i\) sends \(\sigma_i=s_i/(d_i^{+}+1)\) to each out-neighbor and updates \(s_i\leftarrow \sigma_i\). This mass-splitting rule prevents fast clients from dominating the network dynamics under asynchrony.

4.5 Buffered Neighbor Updates↩︎

In a fully asynchronous decentralized setting, message arrivals are decoupled from local compute events. A client may receive neighbor messages at arbitrary times, possibly in bursts, and some messages can be stale by the time aggregation is triggered. PushCen-ADFL therefore maintains a local buffer \(\mathcal{B}_i\) at each client \(i\) to cache received neighbor information until the next compute event, when aggregation is performed.

The buffer is designed to be sender-deduplicated and capacity-bounded. When a new message from neighbor \(j\) arrives, client \(i\) removes any existing buffered entry from \(j\) and keeps only the latest one. This enforces the principle that each sender contributes at most one message per aggregation event, preventing bursty arrivals from being counted multiple times and distorting the intended neighbor weighting, which per-message push-sum normalization alone does not prevent.

Empirically, removing sender deduplication consistently degrades performance (Section 5.2.4), indicating that discarding older messages from the same neighbor is beneficial in practice. Finally, to control memory and limit the influence of long-delayed messages under high communication rates, we impose a buffer size limit and drop the oldest entries upon overflow. Together, these rules provide a lightweight interface between asynchronous communication and push-sum aggregation, as summarized in Algorithm 7.

4.6 Convergence Analysis of PushCen-ADFL↩︎

4.6.1 Assumptions↩︎

We summarize the assumptions used in our convergence analysis; full definitions, update rules and proofs are deferred to Appendix 9.

4.6.1.1 Assumption 1: Smoothness and lower boundedness [33], [34].

Each \(f_i\) is \(L\)-smooth and \(F(w)\triangleq \frac{1}{N}\sum_{i=1}^N f_i(w)\) is lower bounded by \(F^\star\).

4.6.1.2 Assumption 2: Stochastic gradients [33], [34].

\(\mathbb{E}[g_i(w;\xi)\mid w]=\nabla f_i(w)\) and \(\mathbb{E}[\|g_i(w;\xi)-\nabla f_i(w)\|_2^2\mid w]\le \sigma^2\).

4.6.1.3 Assumption 3: Uniform heterogeneity [34].

For all \(i\) and \(w\), \(\|\nabla f_i(w)-\nabla F(w)\|_2^2\le \zeta^2\).

4.6.1.4 Assumption 4: Bounded staleness [21], [35].

Any message used at event \(t\) is generated within the last \(\tau\) events.

4.6.1.5 Assumption 5: Directed push-sum mixing [36].

The time-varying directed communication is \(B\)-window strongly connected and push-sum masses stay positive.

4.6.1.6 Assumptions 6: Absolute compression error [37].

\(\|\mathcal{R}(\mathcal{C}(w)) - w\|_2 \le \varepsilon_c\) for any transmitted model \(w\).

To simplify constants, we further assume bounded push-sum masses, bounded iterates, and bounded gradient second moments. These are given in Assumptions 9.6.1.1 in Appendix 9.

4.6.2 De-biased reference and stationarity metric↩︎

On directed and potentially unbalanced graphs, the arithmetic mean is not preserved. We therefore analyze the de-biased push-sum reference \(\bar w^t \triangleq X_{\mathrm{tot}}^t/Y_{\mathrm{tot}}^t\) (defined via system-level accounting that includes buffered/in-flight messages; Appendix 9) and measure convergence by \(\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\|\nabla F(\bar w^t)\|_2^2\).

4.6.3 Main theorem↩︎

5 Experiments↩︎

4pt

5pt

5.1 Experimental Setup↩︎

5.1.1 Experimental Environment↩︎

We conduct experiments on a Slurm-managed cluster with two compute nodes. Node A has an Intel Core i9-13900K CPU, 64GB RAM and one NVIDIA GeForce RTX 4090 GPU; Node B has an Intel Xeon Silver 4309Y CPU, 128GB RAM and two NVIDIA A40 GPUs. All methods are implemented in Python. Our method and all baselines are implemented in PyTorch ¹ and trained/inferred on GPUs. To emulate client asynchrony and message arrivals in asynchronous decentralized FL, we implement an event-driven simulator that schedules local computation and communication events independently for each client, allowing updates and message deliveries to occur at arbitrary times. Unless otherwise stated, all experiments use a fixed random seed, set \(K=32\), and cap the FIFO buffer at \(L=16\) to bound memory under bursty asynchronous arrivals. Each client pushes to 10 random neighbors via a gossip protocol. The code was released at ².

5.1.2 Datasets and Models↩︎

We evaluate our method on three standard vision classification benchmarks: CIFAR-10, CIFAR-100 and Tiny-ImageNet. Following common practice, we pair datasets with architectures of appropriate capacity: LeNet for CIFAR-10 and ResNet-18 for CIFAR-100 and Tiny-ImageNet [38]–[41]. All methods are trained under the same data preprocessing and training pipeline to ensure fair comparisons.

5.1.3 Data Partitioning and Heterogeneity↩︎

To emulate the statistical heterogeneity (non-IID data) commonly observed in real-world federated learning, we partition each dataset using a Dirichlet distribution with concentration parameters \(\alpha\in\{0.1,0.4,1.0\}\), where smaller \(\alpha\) induces more skewed client data distributions. CIFAR-10 is partitioned across 100 clients, while CIFAR-100 and Tiny-ImageNet are each distributed among 50 clients to avoid overly small per-client datasets under Dirichlet splits, which can make training unstable. For evaluation under each client’s local distribution, we further split each client’s data into local training and test sets and report performance on the corresponding local test data.

5.1.4 Delayed Client Scenario and Evaluation Protocol↩︎

To evaluate delayed client participation in asynchronous decentralized federated learning, we adopt a round-free (pseudo-time–based) evaluation protocol consistent with ADFL. Training proceeds over a fixed global pseudo-time horizon, uniformly divided into 60 evaluation intervals, at which the average Top-1 accuracy of all online clients is reported. For each dataset, 10% of clients are randomly designated as delayed clients prior to training, while all remaining clients participate from the beginning. Each delayed client joins the system at a randomly sampled time during training. To ensure a fair comparison, both the identities of delayed clients and their join times are fixed and shared across all compared methods.

5.1.5 Baseline Methods↩︎

We compare against four representative baselines. Async-DFedAvg serves as a canonical benchmark, capturing a standard asynchronous decentralized adaptation of the FedAvg-style aggregation paradigm [1]. DivShare represents a state-of-the-art communication-efficient approach in asynchronous decentralized settings and is included to benchmark communication efficiency [32]. Independent performs purely local training without any model exchange, providing a non-collaborative lower bound. Finally, SWIFT is a representative asynchronous decentralized FL algorithm and is commonly used as a baseline for handling statistical heterogeneity under asynchrony [11].

5.2 Experimental Results↩︎

5.2.1 Model Accuracy↩︎

Table 1 reports the Top-1 accuracy together with the corresponding standard deviation (SD) under different levels of non-IID data. In addition to mean performance, the SD provides a sensitivity analysis that characterizes the variability of model accuracy across clients and training trajectories in asynchronous decentralized settings. On CIFAR-10, PushCen-ADFL achieves the best accuracy under high heterogeneity, with particularly strong gains as data become more non-IID. At \(\alpha=0.4\) and \(\alpha=0.1\), PushCen-ADFL reaches 66.22% and 58.30%, respectively, outperforming the communication-efficient baseline DivShare by clear margins, while exhibiting SDs that are comparable to and often lower than, those of competing methods on CIFAR-10. When heterogeneity is mild (\(\alpha=1.0\)), PushCen-ADFL remains highly competitive with full-communication baselines and shows similar variability. On more challenging datasets (CIFAR-100 and Tiny-ImageNet), PushCen-ADFL consistently outperforms DivShare across all heterogeneity levels, with more pronounced improvements under stronger non-IID distributions. For example, at \(\alpha=0.1\), PushCen-ADFL improves accuracy by 2.22% on CIFAR-100 and 6.18% on Tiny-ImageNet, while maintaining overall variability comparable to the baselines across heterogeneity levels. PushCen-ADFL achieves competitive mean accuracy and comparable SDs relative to full-communication methods, demonstrating that its centroid-based compression and regularization enable strong, robust performance in heterogeneous and asynchronous decentralized training without increasing sensitivity to updates.

5.2.2 Communication Cost↩︎

Table 2 reports the communication cost of a single client push event, which is the total payload transmitted when a client broadcasts its message to 10 neighbors. This metric isolates the per-push communication footprint from the overall pseudo-time horizon and thus directly reflects the bandwidth burden induced by one communication action in our asynchronous decentralized protocol. We focus on the per-push cost because total system communication scales with the per-push payload times the number of push events. The event count depends on asynchrony, client delays, and scheduling, rather than the message format itself. As expected, full-precision methods that transmit dense model information (Async-DFedAvg and SWIFT) incur substantially larger per-push traffic, reaching 10.27 MB on CIFAR-10 and about 449 to 451 MB on CIFAR-100 and Tiny-ImageNet. In contrast, communication-efficient baselines significantly reduce the payload size. DivShare lowers the per-push cost to 2.06 MB (CIFAR-10) and 89.82 to 90.23 MB (CIFAR-100 and Tiny-ImageNet), while PushCen-ADFL achieves the smallest per-push footprint across all datasets, requiring only 1.62 MB on CIFAR-10 and 76.33 to 76.65 MB on CIFAR-100 and Tiny-ImageNet.

We further normalize the per-push communication volume to PushCen-ADFL, where PushCen-ADFL is 1.00 by definition. Under this normalization, DivShare requires 1.27\(\times\) more bandwidth per push on CIFAR-10 and 1.18\(\times\) on CIFAR-100 and Tiny-ImageNet, whereas Async-DFedAvg and SWIFT require 6.33\(\times\) on CIFAR-10 and about 5.88 to 5.89\(\times\) on CIFAR-100 and Tiny-ImageNet. Overall, these results demonstrate that PushCen-ADFL substantially reduces the communication footprint of each decentralized push, which is particularly important in asynchronous settings where communication are frequent and uncoordinated.

5.2.3 Computational overhead↩︎

8pt

Table 3 reports the computational cost (GFLOPs) of different methods on three datasets. Overall, PushCen-ADFL maintains a lightweight computation footprint comparable to baselines. On CIFAR-10, PushCen-ADFL slightly reduces the cost to 4.03 GFLOPs, marginally lower than Async-DFedAvg, DivShare and SWIFT. On Tiny-ImageNet, it achieves 42.41 GFLOPs, essentially matching the baseline range. On CIFAR-100, PushCen-ADFL reaches 11.93 GFLOPs versus 10.61–10.82 GFLOPs for other methods, remaining within a manageable range.

We observe a slightly higher computation cost on CIFAR-100, mainly due to WCP-related operations (centroid clustering and re-encoding) and the centroid-based anchor construction during local updates. This effect is more visible with \(K=32\), which yields less aggressive sparsity and thus provides limited training-time computation reduction while still incurring clustering overhead.

5.2.4 Ablation Study↩︎

4pt

Table 4 evaluates the contribution of two key components in PushCen-ADFL: the regularization term and the buffer-based message handling mechanism. Removing the regularization (No Reg) leads to a consistent decrease in accuracy across all datasets, from 66.22% to 65.30% on CIFAR-10, from 44.21% to 42.82% on CIFAR-100 and from 44.62% to 43.93% on Tiny-ImageNet. This indicates that the regularization is beneficial for stabilizing training and improving generalization under heterogeneous and asynchronous decentralized updates. Disabling the buffer mechanism (No Buffer) also degrades performance, with the most pronounced effect observed on CIFAR-100 (44.21% to 32.01%), suggesting that buffer-based handling of incoming messages plays an important role in mitigating adverse effects caused by asynchronous arrivals (e.g., redundant or highly stale information) on more challenging tasks. Overall, both components contribute to the final performance and the full PushCen-ADFL achieves the best results across all datasets.

5.3 Delayed Client Experiment Results↩︎

5pt

Table 5 reports delayed-client performance measured by the mean of each delayed client’s maximum test accuracy during training, together with the corresponding standard deviation (SD). On CIFAR-10, PushCen-ADFL reaches an accuracy of 72.77%, exceeding both the full-communication baselines and the communication-efficient. On CIFAR-100 and Tiny-ImageNet, PushCen-ADFL attains 46.50% and 43.08%, respectively, consistently improving over DivShare while remaining competitive with full-communication methods. These results indicate that PushCen-ADFL is particularly effective at incorporating delayed clients and enabling them to achieve strong personalized performance under their local distributions. Beyond the mean accuracy, SD shows that PushCen-ADFL also yields low variability across delayed clients, achieving the smallest SD on CIFAR-10 (0.356) and comparable to full-communication baselines on CIFAR-100 and Tiny-ImageNet. Detailed training curves for delayed clients are provided in Appendix 10.1.2.

5.4 Hyperparameter Sensitivity↩︎

5.4.1 Effect of centroid number \(K\).↩︎

Table 6 shows that increasing \(K\) improves accuracy at the cost of higher communication and computation. Even with \(K = 32\), PushCen-ADFL keeps per-push cost and GFLOPs strictly below all baselines, confirming that \(K\) provides a practical knob to trade accuracy for efficiency. We use \(K=32\) by default as it yields the best accuracy across all datasets.

2pt

5.4.2 Effect of regularization weight \(\lambda\).↩︎

Table 7 shows that enabling centroid regularization (\(\lambda>0\)) consistently outperforms \(\lambda=0\) across all datasets, confirming its role in stabilizing local updates under heterogeneity and asynchrony. On CIFAR-10, performance is stable for \(\lambda\in[0.01,0.10]\) (\({\approx}66\%\)). On CIFAR-100 and Tiny-ImageNet, smaller \(\lambda\) is slightly preferred, yet gains persist across a broad range. We adopt \(\lambda=0.1\) as a simple default.

6pt

5.5 Supplementary Experiments↩︎

We provide additional learning-dynamics analyses to complement the main results. The global accuracy curves show that PushCen-ADFL follows stable convergence trajectories across all datasets, supporting the final averaged accuracies reported in Table 1. The delayed-client accuracy curves on a pseudo-time axis further show that late-joining clients improve rapidly after entering the system and reach performance comparable to online clients within a short pseudo-time window, corroborating the delayed-client results summarized in Table 5. Together, these results reinforce the convergence stability and robustness of PushCen-ADFL under asynchronous and heterogeneous decentralized settings.

6 Conclusion↩︎

This work investigated asynchronous decentralized federated learning, where frequent peer-to-peer, asymmetric and unbalanced communication and the statistical heterogeneity jointly induce high bandwidth cost, aggregation bias and model drift. We proposed PushCen-ADFL, an asynchronous decentralized framework that couples communication, de-biased aggregation, and local stabilization in a shared centroid representation space, forming a closed loop between compression and optimization. It integrates centroid-based model representation, average-preserving push-sum aggregation, centroid regularization, and bounded sender-deduplicated buffering to enable stable and robust training with delayed client participation. Extensive experiments demonstrate that PushCen-ADFL consistently improves performance over existing asynchronous decentralized baselines while substantially reducing per-push communication cost, achieving a favorable accuracy-communication trade-off under dynamic settings.

7 Appendix Overview↩︎

The appendix provides complementary analyses and additional experimental results that support the main paper:

• Communication and computation properties of WCP. Appendix 8 revisits Weight Clustering Pruning (WCP) and derives its per-push communication cost as the sum of centroid transmission and index assignment, yielding an interpretable compression ratio mainly controlled by the number of centroids \(K\). It further compares the clustering overhead with standard training cost and shows that, under typical settings, WCP adds only a small fraction of extra computation.

• Detailed convergence analysis of PushCen-ADFL. Appendix 9 presents a full convergence analysis under an event-driven asynchronous model on directed graphs. It formalizes push-sum aggregation with buffered (possibly stale) messages, centroid compression/reconstruction error, and the centroid proximal regularization used in local updates. The analysis establishes key lemmas on system-level mass conservation, numerator perturbation induced by lossy re-encoding, a consensus-error recursion under directed mixing with staleness and compression, and bounds showing how the centroid proximal term suppresses local deviation from its anchor. These components are combined into a constant-closed stationarity guarantee that makes the impacts of heterogeneity, staleness, directed mixing, and compression distortion explicit.

• Supplementary experiments and ablations. Appendix 10 reports additional empirical evidence beyond the main tables, including global test-accuracy trajectories and delayed-client accuracy curves to visualize learning dynamics under asynchrony. It also provides ablations on the number of centroids \(K\) and the regularization weight \(\lambda\), quantifying the trade-offs between accuracy, per-push communication cost, and computational overhead, and validating the effectiveness and robustness of centroid regularization.

8 Communication and Computational Analysis of Weight Clustering Pruning↩︎

In this section, we provide a unified analysis of the communication and computational properties of Weight Clustering Pruning (WCP). Although WCP was originally introduced in our previous work, it remains a core component of the proposed method and plays an important role in reducing both communication cost and practical system overhead. For completeness, we revisit its theoretical properties and highlight why WCP remains efficient and well-suited for asynchronous federated learning.

8.1 Communication Efficiency of Weight Clustering Pruning↩︎

We first analyze how WCP reduces communication overhead compared to standard federated learning. In conventional federated optimization, each client transmits a full model parameter vector \(\theta \in \mathbb{R}^N\) at every communication event. Assuming each parameter is represented using \(B\) bits, the communication cost per client per round is \[C_{\text{full}} = N \times B \quad \text{bits}.\]

Under WCP, model parameters are represented using a clustered form. Specifically, weights are quantized into \(k\) clusters and represented by a centroid set and an index assignment. One centroid is fixed at zero to naturally encode pruned weights and therefore does not need to be transmitted.

The total communication cost consists of two components. The first is the transmission of centroid values. Only \(k-1\) non-zero centroids need to be communicated, leading to \[C_{\text{centroid}} = (k-1) \times B \quad \text{bits}.\]

The second component corresponds to the index sequence that maps each weight to its associated centroid. Each index requires \(\lceil \log_2 k \rceil\) bits, resulting in \[C_{\text{index}} = N \times \lceil \log_2 k \rceil \quad \text{bits}.\]

Combining the two terms, the total communication cost of WCP is \[C_{\text{WCP}} = (k-1) \times B + N \times \lceil \log_2 k \rceil.\]

To quantify the communication reduction, we define the compression ratio \[\rho = \frac{C_{\text{WCP}}}{C_{\text{full}}} = \frac{(k-1)B + N \lceil \log_2 k \rceil}{N B}.\]

Since modern neural networks typically satisfy \(N \gg k\), the centroid transmission term becomes negligible. Thus, the compression ratio can be approximated as \[\rho \approx \frac{\lceil \log_2 k \rceil}{B}.\]

This result shows that communication efficiency is primarily controlled by the number of clusters \(k\). A moderate choice of \(k\) yields substantial bandwidth savings while maintaining sufficient representational capacity, which is essential for preserving model accuracy.

8.2 Computational Overhead of Weight Clustering Pruning↩︎

We now examine the computational cost introduced by WCP and compare it to the standard training cost in federated learning.

Consider a neural network with \(L\) layers, where the parameter matrix of layer \(l\) contains \(P^l = n_{l-1} n_l\) parameters. The total number of parameters is \[P_{\text{tot}} = \sum_{l=1}^{L} P^l.\]

8.2.0.1 Training Cost.

For each training sample, the forward pass, backward pass and parameter update all incur costs proportional to the number of parameters. Thus, the per-sample training cost satisfies \[C_{\text{train}} = \mathcal{O}\!\left(\sum_{l=1}^{L} P^l \right).\] For a local dataset of size \(N\) and \(E\) training epochs, the total training cost becomes \[C_{\text{total\_train}} = \mathcal{O}\!\left(N E P_{\text{tot}}\right).\]

8.2.0.2 Clustering Cost.

WCP applies clustering independently to each layer. For a layer with \(P^l\) parameters, a K-means iteration consists of an assignment step with complexity \(\mathcal{O}(P^l k)\) and a centroid update step with complexity \(\mathcal{O}(P^l)\). Assuming \(T\) clustering iterations, the cost for layer \(l\) is \[C_{\text{cluster}}^{l} = \mathcal{O}(T k P^l).\] Summing over all layers yields \[C_{\text{total\_cluster}} = \mathcal{O}(T k P_{\text{tot}}).\]

8.2.0.3 Cost Comparison.

The ratio between training cost and clustering cost is therefore \[\frac{C_{\text{total\_train}}}{C_{\text{total\_cluster}}} = \frac{N E}{T k}.\]

Under typical experimental settings (e.g., \(E=1\), \(k=32\) and small \(T\)), this ratio is substantially larger than one. This indicates that the computational overhead introduced by WCP is dominated by the standard training process and remains a small fraction of the overall computation.

8.2.0.4 Summary.

Overall, WCP introduces negligible additional computation while providing significant communication savings. Its computational cost scales linearly with the number of parameters and clusters, ensuring good scalability. These properties make WCP particularly suitable for asynchronous and decentralized federated learning, where both communication efficiency and lightweight local computation are critical.

9 Detailed convergence analysis of PushCen-ADFL↩︎

9.1 Notation and Event-Driven Model↩︎

9.1.0.1 Network and directed communication.

We consider \(N\) clients indexed by \(\mathcal{V}=\{1,\dots,N\}\) connected by a directed graph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\). For client \(i\), denote its in-neighbors and out-neighbors by \(\mathcal{N}_i^{-}\) and \(\mathcal{N}_i^{+}\) and let \(d_i^{+}\triangleq|\mathcal{N}_i^{+}|\). Clients exchange messages only along directed edges; there is no central server.

9.1.0.2 Event-driven asynchronous timeline.

Training evolves on a global event timeline \(t=0,1,2,\dots\). At each event \(t\), either (i) a message arrives at some client and is appended into its local buffer, or (ii) a single client is activated and performs an aggregate \(\rightarrow\) local update \(\rightarrow\) broadcast cycle. Let \(i_t\in\mathcal{V}\) denote the activated client at event \(t\) (if any). No global synchronization is assumed and different clients may be activated at different rates.

9.1.0.3 Local client states.

Each client \(i\) maintains the following states at event \(t\):

• Model \(w_i^t\in\mathbb{R}^d\), the local trainable parameters (vectorized for analysis).

• Push-sum mass \(y_i^t>0\), corresponding to ps_mass in the implementation.

• centroid dictionary \(G_i^t\), the layer-wise centroid tables maintained/updated by aggregation.

• Buffer \(\mathcal{B}_i^t\), storing the most recent neighbor messages received since the last compute event.

Remark (local-only parameters). In the implementation, BatchNorm-related parameters/statistics are local-only (FedBN-style): they are not aggregated and remain purely local. Our analysis focuses on the shared trainable vector \(w_i^t\) (excluding such local-only components).

9.1.0.4 Centroid compression and reconstruction (implementation-aligned).

When client \(j\) transmits, it sends a centroid-compressed payload \(\mathcal{C}(w_j^t) \triangleq (V_j^t, A_j^t, U_j^t),\) where \(V_j^t\) is the centroid table, \(A_j^t\) is the assignment map and \(U_j^t\) contains uncompressed shared tensors that are communicated without clustering (e.g., biases or non-compressible layers). Local-only parameters (e.g., BatchNorm statistics) are not transmitted. Upon reception, client \(i\) reconstructs an approximate model \(\hat{w}_j^t = \mathcal{R}(\mathcal{C}(w_j^t)),\) where \(\mathcal{R}\) indexes \(V_j^t\) with \(A_j^t\) and copies \(U_j^t\). We define the reconstruction (compression) error: \[e_j^t \triangleq \hat{w}_j^t - w_j^t. \label{eq:compression-error-def}\tag{6}\]

9.1.0.5 Buffered messages.

A message sent from \(j\) to \(i\) is represented as \(m_{j\to i}^t = (\hat{w}_j^t, V_j^t, y_{j\to i}^t, j),\) where \(y_{j\to i}^t>0\) is the push-sum mass share attached to the message (field ps_mass_share). At event \(t\), client \(i\)’s buffer is \(\mathcal{B}_i^t=\{m_{j\to i}^t: j\in\mathcal{S}_i^t\},\) where \(\mathcal{S}_i^t\subseteq\mathcal{N}_i^{-}\) indexes the set of senders currently stored. The implementation keeps only the newest message per sender (sender deduplication) and may enforce a capacity bound; in analysis we treat \(\mathcal{B}_i^t\) as an arbitrary finite set of most-recent neighbor messages.

9.1.0.6 Push-sum reformulation (numerator/denominator variables).

To make average-preservation explicit under directed, potentially unbalanced communication, we introduce the standard push-sum numerator variable \[x_i^t \triangleq y_i^t\, w_i^t \in \mathbb{R}^d. \label{eq:pushsum-x-def}\tag{7}\] The de-biased local estimate is always recovered as \(w_i^t = x_i^t / y_i^t\).

9.1.0.7 Mass splitting (code-consistent).

After finishing a local update, client \(i\) splits its current mass uniformly among its out-neighbors and itself: \[y_{i\to k}^t \;=\; \frac{y_i^t}{d_i^{+}+1},\quad \forall k\in\mathcal{N}_i^{+}, \qquad y_i^{t+} \;=\; \frac{y_i^t}{d_i^{+}+1}. \label{eq:mass-splitting}\tag{8}\] Each outgoing message to \(k\) carries \(y_{i\to k}^t\) and client \(i\) keeps the same share locally. Hence, the sender-side conservation holds exactly: \(d_i^{+}\cdot \frac{y_i^t}{d_i^{+}+1} + 1\cdot \frac{y_i^t}{d_i^{+}+1} = y_i^t.\) Analogously, the transmitted numerator share is \(x_{i\to k}^t \triangleq y_{i\to k}^t \hat{w}_i^t\) and the locally retained numerator is \(x_i^{t+}\triangleq y_i^{t+} w_i^{t+}\).

9.1.0.8 System-level accounting for in-flight/buffered mass.

Under asynchronous message passing, a portion of mass may reside in buffers (or be in transit) between send and aggregation events. Let \(\mathcal{M}^t\) denote the set of all messages that are currently buffered or in transit in the system at event \(t\). For each message \(m\in\mathcal{M}^t\), let \(y_m\) be its mass share and \(x_m\) its numerator share. We define the total system mass and total system numerator: \[Y_{\mathrm{tot}}^t \triangleq \sum_{i=1}^{N} y_i^t + \sum_{m\in\mathcal{M}^t} y_m, \qquad X_{\mathrm{tot}}^t \triangleq \sum_{i=1}^{N} x_i^t + \sum_{m\in\mathcal{M}^t} x_m . \label{eq:total-mass-def}\tag{9}\] The mass-splitting rule 8 and the aggregation rule (which transfers buffered shares into the local states) together imply that \((Y_{\mathrm{tot}}^t, X_{\mathrm{tot}}^t)\) are invariant over time; this will be formalized in the mass-conservation lemma.

9.1.0.9 De-biased global reference sequence.

Using the conserved system totals, we define the canonical de-biased global reference model: \[\bar{w}^t \triangleq \frac{X_{\mathrm{tot}}^t}{Y_{\mathrm{tot}}^t}. \label{eq:global-reference}\tag{10}\] This sequence is well-defined on asymmetric and unbalanced graphs and serves as the main reference trajectory for optimality analysis (while \(w_i^t\) are local de-biased estimates with a consensus error).

9.1.0.10 Local objective and centroid proximal target.

Client \(i\) holds a private dataset \(\mathcal{D}_i\) and local objective \(f_i(w)\triangleq \mathbb{E}_{\xi\sim\mathcal{D}_i}[\ell(w;\xi)].\) Before each compute event, client \(i\) constructs a proximal target \(\tilde{w}_i^t\) from its current centroid dictionary estimate \(G_i^t\) and its current assignment map (obtained by clustering the current local model) and performs local stochastic optimization on \[f_i(w) + \lambda \|w-\tilde{w}_i^t\|_2^2, \label{eq:local-prox-objective}\tag{11}\] where \(\lambda\ge 0\) is the regularization weight. The construction of \(\tilde{w}_i^t\) is implementation-aligned: it is produced by indexing centroid tables using the assignment map so that \(\tilde{w}_i^t\) matches the shape of \(w_i^t\).

9.2 Assumptions↩︎

We list the standard assumptions required to establish the convergence of PushCen-ADFL. These assumptions cover stochastic optimization with heterogeneous data distributions, asynchronous communication with message delays and centroid-based lossy communication over directed graphs. All random variables are defined on a common probability space induced by data sampling, client activations and message arrivals.

9.2.0.1 (A1) Smoothness and lower boundedness.

Each local objective \(f_i:\mathbb{R}^d\rightarrow\mathbb{R}\) is \(L\)-smooth: \[\|\nabla f_i(u)-\nabla f_i(v)\|_2 \le L\|u-v\|_2,\quad \forall u,v\in\mathbb{R}^d, \label{eq:assump-smooth}\tag{12}\] and the global objective \(F(w)\triangleq \frac{1}{N}\sum_{i=1}^N f_i(w)\) is lower bounded, i.e., \(F(w)\ge F^\star\) for some finite \(F^\star\).

9.2.0.2 (A2) Unbiased stochastic gradients with bounded variance.

At client \(i\), a stochastic gradient computed from a mini-batch \(\xi\sim\mathcal{D}_i\) satisfies \[\mathbb{E}\!\left[g_i(w;\xi)\mid w\right] = \nabla f_i(w), \qquad \mathbb{E}\!\left[\|g_i(w;\xi)-\nabla f_i(w)\|_2^2 \mid w\right] \le \sigma^2, \label{eq:assump-sgd}\tag{13}\] for some \(\sigma^2<\infty\). When centroid proximal regularization is applied, we equivalently view the client as optimizing the regularized objective \(f_i^\lambda(w)\triangleq f_i(w)+\lambda\|w-\tilde{w}_i\|_2^2\), and the stochastic gradient is taken w.r.t.\(f_i^\lambda\).

9.2.0.3 (A3) Uniform client heterogeneity.

There exists a constant \(\zeta^2<\infty\) such that for all \(w\in\mathbb{R}^d\) and all clients \(i\in[N]\), \[\|\nabla f_i(w)-\nabla F(w)\|_2^2 \le \zeta^2, \qquad\text{where}\qquad F(w)\triangleq \frac{1}{N}\sum_{j=1}^{N} f_j(w). \label{eq:A3-uniform}\tag{14}\]

Remark. Assumption A3 is a standard strengthening of the mean-heterogeneity condition and is commonly used in non-convex FL analyses to control one-step descent for the activated client under asynchrony.

9.2.0.4 (A4) Bounded asynchrony (message staleness).

Messages aggregated at event \(t\) may correspond to stale model states due to heterogeneous computation/communication. We assume there exists an integer \(\tau\ge 0\) such that any message used by an activated client at event \(t\) was generated within the last \(\tau\) activations/events. Equivalently, if a buffered message \(m_{j\to i}^t\) carries a reconstruction \(\hat{w}_j^{\kappa}\), then its generation time \(\kappa\) satisfies \[t-\kappa \le \tau. \label{eq:assump-stale}\tag{15}\]

9.2.0.5 (A5) Directed mixing and push-sum well-posedness.

The directed communication graph is strongly connected and the sequence of effective communication events is sufficiently mixing. Concretely, there exists an integer \(B\ge 1\) such that for any window of \(B\) consecutive events, the union of directed edges along which messages are delivered is strongly connected. Moreover, the push-sum masses are uniformly bounded away from zero: there exists \(y_{\min}>0\) such that \[y_i^t \ge y_{\min},\quad \forall i\in\mathcal{V},\;\forall t. \label{eq:assump-mass-lb}\tag{16}\] This ensures the de-biased ratios \(w_i^t = x_i^t/y_i^t\) and the global reference \(\bar w^t\) are well-defined.

9.2.0.6 (A6) Bounded absolute compression error (C1).

The centroid compression-reconstruction operator \(\mathcal{R}\circ\mathcal{C}\) induces a bounded absolute error: there exists \(\varepsilon_c\ge 0\) such that for any communicated model \(w\), \[\|\mathcal{R}(\mathcal{C}(w)) - w\|_2 \le \varepsilon_c. \label{eq:assump-compress-C1}\tag{17}\] Equivalently, with \(e_j^t\) defined in 6 , we have \(\|e_j^t\|_2 \le \varepsilon_c\) for all transmitted messages. This assumption captures the deterministic quantization/clustering distortion introduced by WCP with a fixed number of centroids \(K\).

Remark. Assumptions (A1)-(A3) are standard in stochastic non-convex optimization and federated learning. Assumptions (A4)-(A5) formalize bounded staleness and directed-graph mixing needed for asynchronous push-sum. Assumption (A6) matches our implementation, where WCP-based centroid encoding introduces deterministic reconstruction distortion controlled by the clustering resolution (e.g., \(K=32\)).

9.3 Update Rules↩︎

We formalize the event-driven update rules of PushCen-ADFL (ADFLCenReg) by separating (i) asynchronous push-sum aggregation over buffered neighbor messages and (ii) local stochastic optimization with centroid proximal regularization. Throughout, we use the push-sum numerator-denominator representation \(x_i^t = y_i^t w_i^t\) introduced in 7 .

9.3.0.1 Message format and staleness-aware notation.

When client \(j\) is activated and broadcasts to an out-neighbor \(i\in\mathcal{N}_j^{+}\), it transmits a tuple \[m_{j\to i}^{(\kappa)} \;=\; \big(\mathcal{C}(w_j^{\kappa}),\; y_{j\to i}^{(\kappa)},\; j \big), \label{eq:message-format}\tag{18}\] where \(\kappa\) denotes the generation event index at which the message is produced, \(\mathcal{C}(w_j^{\kappa})=(V_j^{\kappa},A_j^{\kappa},U_j^{\kappa})\) is the centroid-compressed payload and \(y_{j\to i}^{(\kappa)}>0\) is the attached mass share. Upon reception at some later event \(t\ge \kappa\), client \(i\) reconstructs the (possibly stale) neighbor model \[\hat{w}_{j\to i}^t \;\triangleq\; \mathcal{R}\!\left(\mathcal{C}(w_j^{\kappa})\right), \label{eq:stale-recon}\tag{19}\] and buffers the tuple \((\hat{w}_{j\to i}^t, V_j^{\kappa}, y_{j\to i}^{(\kappa)}, j)\). ³ At the time client \(i\) is activated at event \(t\), let \(\mathcal{B}_i^t\) denote its buffer, i.e., the set of currently stored messages to be aggregated (sender-deduplicated and possibly capacity-bounded).

9.3.0.2 C1. Asynchronous push-sum aggregation (buffer processing).

When client \(i=i_t\) is activated at event \(t\), it aggregates all buffered neighbor messages \(\mathcal{B}_i^t = \{(\hat{w}_{j\to i}^t, V_j^{\kappa}, y_{j\to i}^{(\kappa)}, j)\}\). Define the post-buffer total mass at \(i\): \[Y_i^t \;\triangleq\; y_i^t + \sum_{(\cdot,\cdot,y_{j\to i}^{(\kappa)},\cdot)\in\mathcal{B}_i^t} y_{j\to i}^{(\kappa)}. \label{eq:agg-total-mass}\tag{20}\] The de-biased model update is \[w_i^{t+\frac{1}{3}} \;=\; \frac{y_i^t}{Y_i^t}\, w_i^t \;+\; \sum_{(\hat{w}_{j\to i}^t,\cdot,y_{j\to i}^{(\kappa)},\cdot)\in\mathcal{B}_i^t} \frac{y_{j\to i}^{(\kappa)}}{Y_i^t}\, \hat{w}_{j\to i}^t, \label{eq:agg-model}\tag{21}\] with the mass update and buffer clearing \[y_i^{t+\frac{1}{3}} \;=\; Y_i^t, \qquad \mathcal{B}_i^{t+\frac{1}{3}} \;=\; \emptyset. \label{eq:agg-mass}\tag{22}\] Equivalently, in numerator-denominator form, letting \(x_i^t=y_i^t w_i^t\) and \(x_{j\to i}^{(\kappa)}\triangleq y_{j\to i}^{(\kappa)} \hat{w}_{j\to i}^t\), the aggregation is additive: \[x_i^{t+\frac{1}{3}} \;=\; x_i^t + \sum_{(\cdot,\cdot,y_{j\to i}^{(\kappa)},\cdot)\in\mathcal{B}_i^t} x_{j\to i}^{(\kappa)}, \qquad y_i^{t+\frac{1}{3}} \;=\; y_i^t + \sum_{(\cdot,\cdot,y_{j\to i}^{(\kappa)},\cdot)\in\mathcal{B}_i^t} y_{j\to i}^{(\kappa)}. \label{eq:agg-xy}\tag{23}\] Finally \(w_i^{t+\frac{1}{3}} = x_i^{t+\frac{1}{3}} / y_i^{t+\frac{1}{3}}\).

9.3.0.3 centroid dictionary aggregation.

Client \(i\) updates its centroid dictionary estimate using the same push-sum weights: \[G_i^{t+\frac{1}{3}} \;=\; \frac{y_i^t}{Y_i^t}\, G_i^t \;+\; \sum_{(\cdot,V_j^{\kappa},y_{j\to i}^{(\kappa)},\cdot)\in\mathcal{B}_i^t} \frac{y_{j\to i}^{(\kappa)}}{Y_i^t}\, V_j^{\kappa}. \label{eq:agg-pool}\tag{24}\] (We treat \(G_i^t\) as an auxiliary state whose role is to form the proximal target in the local update.)

9.3.0.4 C2. Local stochastic optimization with centroid proximal regularization.

After aggregation, client \(i\) performs \(E\) local epochs/steps of SGD on \[\Phi_i^t(w) \;\triangleq\; f_i(w) + \lambda \|w - \tilde{w}_i^t\|_2^2, \label{eq:local-phi}\tag{25}\] where \(\tilde{w}_i^t\) is the centroid-based proximal target constructed from the current centroid dictionary \(G_i^{t+\frac{1}{3}}\) and the current assignment map (obtained by applying WCP to \(w_i^{t+\frac{1}{3}}\)). Let \((V_i^t,A_i^t,M_i^t)\) be the centroid table, assignment map and pruning mask produced by WCP at the beginning of the local update. For \(e=0,\dots,E-1\), we write the masked proximal-SGD step as

\[\begin{align} w_{i,e+1} &= \Pi_{M_i^t}\!\Bigl( w_{i,e} - \eta\, g_i\!\left(w_{i,e};\xi_{i,e}\right) \\ &\qquad\quad - 2\eta\lambda\,(w_{i,e}-\tilde{w}_i^t) \Bigr), \qquad w_{i,0} = w_i^{t+\frac{1}{3}} . \end{align} \label{eq:local-sgd}\tag{26}\]

where \(\xi_{i,e}\) is a mini-batch sampled from \(\mathcal{D}_i\) and \(g_i(\cdot;\xi)\) is the stochastic gradient of \(\ell(\cdot;\xi)\). The masking operator \(\Pi_{M_i^t}(\cdot)\) enforces pruning by element-wise multiplication, \[\Pi_{M_i^t}(u) \triangleq u \odot M_i^t, \label{eq:mask-proj}\tag{27}\] matching the implementation (w\(\leftarrow\)w * M). We denote the post-local-update model by \[w_i^{t+\frac{2}{3}} \;\triangleq\; w_{i,E}. \label{eq:local-output}\tag{28}\]

9.3.0.5 C3. Post-training re-encoding and broadcast (mass splitting).

After local optimization, client \(i\) re-encodes its model via WCP to obtain an updated centroid representation \(\mathcal{C}(w_i^{t+\frac{2}{3}})=(V_i^{t+\frac{2}{3}},A_i^{t+\frac{2}{3}},U_i^{t+\frac{2}{3}})\) to be transmitted. It then performs push-sum mass splitting: \[y_{i\to k}^{t+\frac{2}{3}} \;=\; \frac{y_i^{t+\frac{1}{3}}}{d_i^{+}+1},\quad \forall k\in\mathcal{N}_i^{+}, \qquad y_i^{t+1} \;=\; \frac{y_i^{t+\frac{1}{3}}}{d_i^{+}+1}, \label{eq:broadcast-mass}\tag{29}\] and sends \((\mathcal{C}(w_i^{t+\frac{2}{3}}), y_{i\to k}^{t+\frac{2}{3}}, i)\) to each \(k\in\mathcal{N}_i^{+}\). Finally, \[w_i^{t+1} \;\triangleq\; w_i^{t+\frac{2}{3}}, \qquad x_i^{t+1} \;\triangleq\; y_i^{t+1} w_i^{t+1}. \label{eq:end-of-event}\tag{30}\] For any client \(\ell\neq i_t\) that is not activated at event \(t\), we keep its local state unchanged: \((w_\ell^{t+1},x_\ell^{t+1},y_\ell^{t+1},G_\ell^{t+1})=(w_\ell^{t},x_\ell^{t},y_\ell^{t},G_\ell^{t})\).

9.4 Key Quantities↩︎

To analyze PushCen-ADFL under directed asynchronous communication, we introduce a de-biased global reference sequence together with two key error measures: an optimality metric that tracks progress toward stationary points and a consensus metric that tracks network disagreement.

9.4.0.1 De-biased global reference (push-sum average).

Recall the total system numerator and mass defined in 9 : \(X_{\mathrm{tot}}^t\) and \(Y_{\mathrm{tot}}^t\). We define the (virtual) de-biased global reference model as \[\bar{w}^t \triangleq \frac{X_{\mathrm{tot}}^t}{Y_{\mathrm{tot}}^t}. \label{eq:key-wbar}\tag{31}\] Unlike the naive arithmetic mean \(\frac{1}{N}\sum_{i=1}^N w_i^t\), \(\bar{w}^t\) is the correct average-preserving reference on directed and potentially unbalanced graphs under push-sum dynamics.

9.4.0.2 Local de-biased models (node states).

Each client maintains a local push-sum numerator \(x_i^t\) and mass \(y_i^t\). The local de-biased model held at node \(i\) is \[w_i^t \triangleq \frac{x_i^t}{y_i^t}. \label{eq:key-local-debias}\tag{32}\] Important: We strictly distinguish the local model \(w_i^t\) from the centroid proximal anchor \(\tilde{w}_i^t\) defined in 25 , where \(\tilde{w}_i^t\) serves as the regularization target during local updates.

9.4.0.3 Consensus error (network disagreement).

We quantify network disagreement by the mean-squared deviation of local models from the de-biased global reference: \[\mathcal{E}_{\mathrm{con}}^t \triangleq \frac{1}{N}\sum_{i=1}^{N}\left\|w_i^t - \bar{w}^t\right\|_2^2. \label{eq:key-consensus}\tag{33}\] This term captures the combined effects of directed mixing, asynchronous staleness and lossy reconstruction on consensus.

9.4.0.4 Optimality (stationarity) measure.

For the global objective \(F(w)\triangleq \frac{1}{N}\sum_{i=1}^{N} f_i(w)\), we use the standard non-convex stationarity metric evaluated at the de-biased global reference sequence: \[\mathcal{E}_{\mathrm{opt}}^t \triangleq \mathbb{E}\left[\left\|\nabla F(\bar{w}^t)\right\|_2^2\right]. \label{eq:key-optimality}\tag{34}\] Bounding \(\frac{1}{T}\sum_{t=0}^{T-1}\mathcal{E}_{\mathrm{opt}}^t\) implies convergence to a stationary neighborhood.

Remark. Our analysis proceeds by (i) deriving a recursion for \(\mathcal{E}_{\mathrm{con}}^t\) under push-sum mixing with perturbations (compression and staleness) and (ii) proving a descent inequality for \(F(\bar{w}^t)\) whose error terms are controlled by \(\mathcal{E}_{\mathrm{con}}^t\). Combining the two yields a bound on the averaged stationarity measure in 34 .

9.5 Key Lemmas↩︎

9.5.1 Lemma 1↩︎

Remark. In contrast to the mass variable, the system numerator \(X_{\mathrm{tot}}^t\) may be perturbed by lossy compression: in the implementation, a sender retains the full-precision local model \(w_i\) while transmitting a compressed representation that reconstructs to \(\hat{w}_i\neq w_i\) at receivers. This perturbation will be explicitly handled in subsequent lemmas when deriving consensus and optimality recursions under Assumption 17 .

9.5.2 Lemma 2↩︎

9.5.3 Lemma 3↩︎

9.5.4 Lemma 4↩︎

9.5.5 Lemma 5↩︎

9.5.6 Lemma 6↩︎

9.6 Main Theorem and Proof↩︎

We now present a fully explicit (constant-closed) stationarity guarantee for PushCen-ADFL.

9.6.1 Standing assumptions.↩︎

We use Assumptions (A1)-(A6) in Appendix 9.2 and additionally adopt the following standard technical conditions that close all constants.

9.6.1.1 Mass positivity and boundedness

There exist constants \(0<y_{\min}\le y_{\max}<\infty\) such that for all events \(t\) and all nodes \(i\), \(y_i^t \in [y_{\min},y_{\max}].\) Consequently, for the activated node \(i_t\), the normalized mass weight \[\gamma_t \triangleq \frac{y_{i_t}^{t+\frac{1}{3}}}{Y_{\mathrm{tot}}} \quad\text{satisfies}\quad \underline{\gamma}\triangleq \frac{y_{\min}}{Ny_{\max}} \le \gamma_t \le 1. \label{eq:gamma-lb}\tag{78}\]

9.6.1.2 Bounded stochastic gradient second moment

There exists \(G^2<\infty\) such that for all \(i,w\) and any sample \(\xi\), \(\mathbb{E}\big[\|g_i(w;\xi)\|_2^2\big]\le G^2.\)

9.6.1.3 Bounded iterates

There exists \(W<\infty\) such that for all events \(t\) and all nodes \(i\), \[\|w_i^t\|_2 \le W \qquad\text{and}\qquad \|\tilde{w}_i^t\|_2 \le W . \label{eq:bounded-iterates}\tag{79}\] In particular, \(\|w_i^t-\tilde{w}_i^t\|_2^2 \le 4W^2\) for all \(i,t\).

9.6.2 Notation.↩︎

Let \(F(w)\triangleq \frac{1}{N}\sum_{i=1}^N f_i(w)\) and \(F^\star\triangleq \inf_w F(w)\). Let \(\rho\in(0,1)\) and \(C_1,C_2,C_3>0\) be the constants in Lemma 3. Let \(\tau\) be the staleness bound (Assumption (A4)) and let \(\varepsilon_c\) be the bounded absolute compression error (Assumption (A6)). Let \(d_{\max}\triangleq \max_i d_i^+\). Define the uniform broadcast perturbation coefficient (Lemma 2) \[\overline{c} \triangleq \max_t \frac{d_{i_t}^+}{d_{i_t}^+ + 1}\cdot \frac{y_{i_t}^{t+\frac{1}{3}}}{Y_{\mathrm{tot}}} \le \frac{y_{\max}}{Ny_{\min}}. \label{eq:cbar}\tag{80}\]

10 Supplementary Experiments↩︎

10.1 Accuracy Curves↩︎

To provide a more complete view of the learning dynamics beyond the final averaged accuracy, we report accuracy curves for all datasets. Specifically, we include (i) global test accuracy trajectories across communication rounds and (ii) accuracy trajectories of delayed clients measured on a pseudo-time axis that reflects asynchronous progress. These curves complement the main results by visualizing convergence speed, stability and robustness under system asynchrony.

10.1.1 Global Accuracy Curves↩︎

This subsection reports the evolution of global test accuracy across communication rounds. Figures 8 (a)-8 (c) show the global accuracy curves on CIFAR-10, CIFAR-100 and Tiny-ImageNet, respectively. These curves illustrate the overall convergence behavior of different methods, including their convergence speed and final performance, under identical experimental settings.

10.1.2 Delayed Client Accuracy Curves↩︎

This subsection presents accuracy curves for delayed clients, evaluated along a pseudo-time axis that reflects asynchronous local progress. Figures 9, 11 and 13 report the average test accuracy across delayed clients on CIFAR-10, CIFAR-100 and Tiny-ImageNet, respectively. In addition, Figures 10, 12 and 14 visualize the accuracy trajectories of representative individual delayed clients, providing a fine-grained view of training stability under client delays.

References↩︎

---

1. https://pytorch.org↩︎

2. https://github.com/SHVleV9CYWkK/ADFLab↩︎

3. Here \(\hat{w}_{j\to i}^t\) denotes the content available at client \(i\) at event \(t\). Due to asynchrony, it generally represents a stale state of client \(j\), i.e., \(\hat{w}_{j\to i}^t\approx w_j^{t-\tau}\) under Assumption 15 .↩︎