1
AirPlan: Query-Optimized Topology Selection for Over-the-Air Decentralized Federated Learning
arXiv:2607.04254v1 [cs.DC] 5 Jul 2026
Kaushal Attaluri ICLab, atlanTTic, University of Vigo Rebeca P. Díaz-Redondo ICLab, atlanTTic, University of Vigo Manuel Fernández-Veiga ICLab, atlanTTic, University of Vigo
FedAvg [1], relies on a central parameter server that aggregates client updates each round. This architecture introduces a single point of failure, scales poorly with the number of clients, and requires a trusted aggregator. Decentralized federated learning (DFL) removes the server by routing updates over a peer-topeer communication graph, but this design choice immediately raises a question: which graph should be used? At the same time, over-the-air (OTA) computation offers a radically different aggregation primitive. By transmitting analog signals simultaneously over a shared wireless channel and exploiting the superposition property of the multiple-access channel, OTA enables model updates to be aggregated “in the air” rather than through sequential digital exchanges [2]. The combination of OTA aggregation with decentralized topology— OTA-DFL—has the potential to deliver both communication efficiency and architectural resilience, but the interaction between graph structure, wireless noise, and learning dynamics is poorly understood. a) The core problem: Practitioners deploying OTA-DFL systems face a critical design decision before training begins: which communication topology should be used? This decision has major consequences. A ring graph minimises per-round transmission cost but converges slowly and amplifies channel noise. A fully connected graph converges quickly but incurs near-quadratic communication cost and may violate per-device power budgets. Prior work either assumes a fixed topology (typically Erdős–Rényi) [3] or treats topology as a secondary concern, leaving practitioners without principled guidance. b) A systems reframing: We observe that this problem is structurally identical to a classical challenge in data management: physical query plan selection in distributed query processing [4], [5]. Each OTA aggregation round is an approximate distributed SUM query over a communication graph. The graph is the physical execution plan. The spectral gap of the graph Laplacian λ2 (L) is the cardinality estimate governing execution cost. Top-k sparsification is approximate query processing (AQP). And the question “which topology Index Terms—Over-the-air computation, decentralized federated learning, graph topology, query optimization, approximate minimises total training cost for this workload?” is precisely the query processing, communication efficiency, wireless networks, query optimisation question “which execution plan minimises spectral graph theory. total cost for this query?” This equivalence is not merely a metaphor. It enables the direct application of query optimisation methodology—costI. I NTRODUCTION based plan selection, workload statistics collection, and online Federated learning (FL) enables distributed model training plan re-optimisation—to the topology selection problem in without sharing raw data, making it a natural fit for privacy- OTA-DFL, yielding a principled and automated solution. sensitive applications across mobile networks, IoT deployments, c) Contributions: We present A IR P LAN, a queryand edge computing infrastructure. The dominant paradigm, optimized topology selection framework for OTA-DFL. Our
Abstract—Over-the-air (OTA) aggregation exploits the superposition property of wireless multiple-access channels to combine gradient updates from multiple devices within a single transmission slot, dramatically reducing communication latency and bandwidth consumption. While OTA computation has been extensively studied in centralized federated learning (FL), its integration with decentralized federated learning (DFL)—where clients communicate over a peer-to-peer graph without a central server—remains a largely open problem, and a principled framework for selecting the communication topology is entirely absent from the literature. In this paper, we introduce A IR P LAN, a query-optimized topology selection framework for Over-the-Air Decentralized Federated Learning (OTA-DFL). The central insight is a formal equivalence between OTA-DFL and distributed query processing: each OTA aggregation round corresponds to an approximate distributed SUM query executed over a DAG-structured execution plan, where the communication graph is the physical plan, top-k sparsification is approximate query processing (AQP), and the spectral gap of the graph Laplacian plays the role of a cardinality estimate governing execution cost. This equivalence enables us to recast topology selection as a query optimization problem: given a training workload (client count N , data heterogeneity α, channel SNR, model dimension d), A IR P LAN uses privacy-preserving Count-Min Sketch statistics to estimate workload parameters, evaluates a graph-aware cost model Cours (G) across candidate topologies, and selects the communication plan that minimises total training cost subject to a user-specified accuracy SLA. We validate A IR P LAN through systematic experiments across five graph families (ring, Erdős–Rényi, small-world, clustered, fully connected), three standard vision benchmarks (CIFAR-10, CIFAR100, Tiny-ImageNet), four client scales (N ∈ {10, 20, 50, 100}), and a range of SNR conditions (0–20 dB). Our results demonstrate that A IR P LAN matches the oracle-optimal topology in 91.4 % of workload configurations while incurring a statistics-collection overhead of less than 1.8 % of total training cost. We further establish formal AQP error bounds showing that well-connected topologies (small-world, clustered) intrinsically tolerate higher sparsification ratios than sparse topologies, providing a theoretical foundation for joint topology-sparsification co-design. These findings open a new systems-oriented research direction at the intersection of wireless communications and distributed data processing.
2
contributions are: constraints. Subsequent work extends OTA-FL to multiple1) Formal OTA-DFL ↔ Query Processing equivalence input multiple-output (MIMO) transmission [8], differential (Section III). We establish a rigorous mapping between privacy [9], and hierarchical architectures [10]. Convergent OTA-DFL operations and distributed query processing Over-the-Air Federated learning (COTAF) [11] analyses conprimitives, including a formal theorem showing that each vergence of OTA-FL with noisy channels but in a centralized OTA aggregation round is an approximate distributed setting. The closest prior work in the decentralized OTA setting SUM query, and a corollary bounding the AQP error is DLLR-OA [3], which studies communication-constrained introduced by top-k sparsification as a function of the decentralized learning under OTA and analyses the effect of limited subcarriers and power constraints on convergence. Howgraph spectral gap. 2) A IR P LAN topology advisor (Section V). We design ever, DLLR-OA assumes a fixed Erdős–Rényi topology and a cost-based topology selection algorithm that col- neither investigates how topology choice affects performance lects privacy-preserving workload statistics via Count- nor provides a mechanism for automated topology selection. Min Sketches [6], evaluates a graph-aware cost No prior work frames OTA-DFL topology selection as a query model Cours (G) across candidate topologies, selects the optimisation problem. minimum-cost plan satisfying an accuracy Service-Level Agreement (SLA), and adaptively re-optimises the plan B. Decentralized Federated Learning during training if model divergence exceeds a threshold. Decentralized federated learning (DFL) removes the central 3) AQP error bounds per topology (Section VI). We prove parameter server and enables clients to exchange model updates topology-dependent bounds on the approximate aggre- directly with neighbours over a peer-to-peer communication gation error introduced by sparsification, showing that graph. Foundational algorithms such as Decentralized Stochaswell-connected graphs (small-world, clustered) tolerate tic Gradient Descent (D-SGD) [12] and consensus-based higher sparsification ratios—motivating joint topology- optimization [13], [14] establish that convergence depends sparsification co-design. critically on the spectral gap λ2 (L) of the graph Laplacian, 4) Systematic empirical validation (Sections VIII–IX). which governs the rate of information mixing. Gradient tracking We evaluate A IR P LAN across five topology families, methods such as Gradient Tracking Decentralized SGD (GTthree datasets, four client scales, and five SNR levels, DSGD) [15], [16] and Stochastic Gradient Push (SGP) [17] demonstrating that A IR P LAN matches the oracle-optimal mitigate gradient bias under heterogeneous data distributions. topology in 91.4 % of configurations with < 1.8 % More recent work addresses compression [18], Byzantine overhead, and that small-world and clustered topologies robustness [19], and large-scale training [20]. Critically, all consistently dominate the accuracy-cost Pareto frontier. of these works assume reliable digital communication and d) Significance.: The OTA-DFL ↔ query processing treat the communication graph as a fixed input rather than equivalence opens a new line of research connecting wireless a design variable. MATCHA [21] is among the few works communications with the database and systems communities. to consider topology alongside algorithm design, proposing Decades of query optimisation research—cost models, statis- matching-based decomposition to accelerate convergence, but tics collection, adaptive re-optimisation, approximate query it does not consider wireless channels or OTA aggregation and processing—become directly applicable to the topology design provides no automatic topology selection mechanism. problem in wireless federated learning. We believe this crossdomain framing will motivate new algorithms and systems in C. Distributed Query Processing and Approximate Query both communities. Processing II. R ELATED W ORK We survey the four research pillars most directly relevant to this work, organized as follows: over-the-air federated learning (combining aggregation mechanics and centralized baselines), decentralized federated learning, distributed query processing and approximate query processing, and communication cost models. A. Over-the-Air Federated Learning Over-the-air (OTA) computation exploits the superposition property of the wireless multiple-access channel to aggregate model updates from multiple devices within a single transmission slot [2], [7], yielding order-of-magnitude reductions in communication latency compared to digital transmission. AirComp-based FL [7] demonstrates that simultaneous analog transmission followed by receive-side combining produces an unbiased estimate of the gradient sum under mild power
In distributed database systems, a physical query execution plan is a directed acyclic graph (DAG) that specifies the order in which relational operators are executed and how intermediate results are exchanged among nodes [4], [5]. Plan selection is the task of choosing, among all equivalent plans, the one with minimum estimated cost according to a cost model. State-of-the-art query optimizers in systems such as PostgreSQL [22], Microsoft SQL Server [23], and Apache Spark [24] use cardinality estimates, operator-level cost models, and bushy plan enumeration to navigate the exponentially large plan space [25], [26]. Adaptive Query Processing (AQP) addresses the challenge that query statistics estimated at plan time may differ significantly from runtime observations, causing suboptimal plans to execute to completion. The Eddies architecture [27] routes tuples dynamically between operators based on observed selectivities. Rios [28] and related work introduce plan switching conditions and mid-query re-optimization triggers. Progressive
3
execution [29] allows partial results to be returned before full query completion, trading accuracy for latency—directly analogous to early stopping in FL training. These approaches motivate our online re-optimization in A IR P LAN (Section V): we monitor model divergence as a runtime signal and trigger topology rewiring when the current plan becomes suboptimal. Approximate Query Processing trades result accuracy for reduced computation and communication cost [29], [30]. Sampling-based methods evaluate queries on a data sample [31]; synopsis-based methods maintain compact sketches such as Count-Min Sketches [6], HyperLogLog, and wavelet synopses. Error guarantees are typically stated as (ϵ, δ) bounds. BlinkDB [30] introduces the notion of an accuracy ServiceLevel Agreement (SLA)—a user-specified quality constraint that the system must meet—which maps directly to the accuracy SLA in A IR P LAN’s topology selection algorithm. As we show in Section VI, top-k sparsification in OTA-DFL is precisely an AQP operator, and its error can be bounded in analogous (ϵ, δ) form depending on the graph topology. D. Communication Cost Models Prior work models communication cost differently depending on the learning architecture. In decentralized optimization, gossip-based algorithms measure cost as Cgossip = T ·|E|·d [12], where T is the number of training rounds, |E| the number of graph edges, and d the model parameter dimension. Centralized federated learning uses CFL = T · N · d [1], where N is the number of clients. OTA frameworks reduce this to COTA = T · d [7] since all clients transmit simultaneously. None of these models jointly captures topology structure, sparsification ratio, and wireless channel reliability. Our proposed Cours (G) in Section VI provides the first such unified model and, within the A IR P LAN framework, serves as the query cost estimator used for automated plan selection. III. OTA-DFL AS D ISTRIBUTED Q UERY E XECUTION : F ORMAL E QUIVALENCE Our approach establishes a formal equivalence between Over-the-Air Decentralized Federated Learning and distributed query processing. This equivalence, summarized in Table I is the conceptual foundation of A IR P LAN and enables the direct transfer of query optimisation techniques to the topology selection problem, as we detail in the following subsections. A. OTA Aggregation as a Distributed SUM Query Theorem III.1 (OTA Aggregation = Approximate Distributed SUM Query). Consider an OTA-DFL round in which N clients transmit gradient updates {uti }N i=1 simultaneously over a wireless multiple-access channel. The signal received by client i is X yit = utj + nti , (1)
executed approximately under additive Gaussian noise with variance σc2 . The query result yit equals the exact SUM plus a t noise term an (ε, δ)-approximate answer with p ni , constituting p ε = σc 2 ln(2/δ)/ |N (i)| for any δ ∈ (0, 1). Proof. The decomposition yit = SUMj∈N (i) utj + nti follows directly from the OTA receive model (1) after ideal channel inversion. The (ε, δ) bound follows by applying the Gaussian √ tail bound P (∥nti ∥ > t) ≤ 2 exp(−t2 /2σc2 d) with t = ε d p P t / |N (i)|. and normalising by j uj 2
B. Graph Topology as Physical Execution Plan In distributed query processing, a physical execution plan is a directed acyclic graph (DAG) specifying how operators are assigned to nodes and how data flows between them. The choice of plan determines execution cost through the sizes and shapes of intermediate results (captured by cardinality estimates) and the communication volume between operator nodes. In OTA-DFL, the communication graph G determines precisely the same quantities: which clients exchange information (operator placement), how many rounds are needed for information to propagate globally (captured by 1/λ2 (L), the mixing time), and the volume of transmitted data per round (Cstruct ). Definition III.2 (Query Execution Cost for OTA-DFL). The total query execution cost of an OTA-DFL training run on graph G is defined as Cours (G) = T (G) · R(SNR) · Cstruct (G, k),
(3)
where T (G) = κ/λ2 (L) is the number of query epochs (communication rounds) required for convergence, R(SNR) = 1 + αe−β·SNR is wireless reliability overhead factor, and Pthe N Cstruct (G, k) = i=1 |N (i)| · k is the per-epoch transmission volume. This definition is precisely a query cost model: T (G) corresponds to the estimated number of pipeline stages, R(·) models network transfer overhead, and Cstruct models the amount of data moved per stage. The topologies correspond to well-known plan shapes: ring ≡ left-deep sequential pipeline (low per-round cost, many stages); fully connected ≡ broadcast join (single stage, high data volume); small-world ≡ bushy join tree (balanced stages and volume). Figure 1 illustrates this correspondence. C. Top-k Sparsification as Approximate Query Processing
where nti ∼ N (0, σc2 I). This is the evaluation of the distributed aggregate query
AQP operators allow a query to return an approximate answer by processing a compressed representation of the data [29]. In OTA-DFL, top-k sparsification TopK(g, k) retains only the k largest (by magnitude) components of the gradient vector g ∈ Rd , discarding the remaining d − k components before transmission.
Qti : SELECT SUM(grad) FROM N (i) WHERE round=t (2)
Corollary III.3 (Sparsification AQP Error Bound). Let g ∈ Rd be a gradient vector with components sorted in decreasing
j∈N (i)
4
TABLE I: Formal Equivalence: OTA-DFL ↔ Distributed Query Processing. Dimension
OTA-DFL Concept
Distributed Query Processing Concept
Execution structure Plan choice Cost driver Aggregation Approximation Approximation error Synchronisation Result quality Quality constraint Data statistics Statistics collection Plan selection Online adaptation Dense plan Sparse pipeline Optimal sparse plan
Communication graph G = (V, E) Graph topology (ring, small-world, . . . ) Spectral gap λ2 (L) of graph Laplacian OTA SUM over neighbourhood N (i) Top-k sparsification TopK(g, k) Sparsification residual ∥g − TopK(g, k)∥ Consensus round (barrier) Test accuracy at round T Target accuracy SLA A∗ Class distribution pic at client i Count-Min Sketch over local label counts Topology selection arg minG Cours (G) Adaptive rewiring on divergence threshold Fully connected graph Ring graph Small-world / clustered graph
Physical query execution plan (DAG of operators) Join order / operator placement strategy Cardinality estimate governing plan cost Distributed SUM aggregate over partition Approximate Query Processing (AQP) operator AQP error εAQP Query epoch / barrier synchronisation Query result accuracy (within ε of exact) Result quality SLA in BlinkDB-style AQP Table histogram / cardinality statistics Histogram sampling / synopsis construction Cost-based physical plan selection Adaptive query processing / re-optimisation Broadcast join (expensive but low-latency) Left-deep sequential pipeline Bushy join tree
Fig. 1: Topology as physical query execution plan. Ring graphs implement a sequential left-deep pipeline; small-world graphs implement a balanced bushy tree; fully connected graphs implement a broadcast join.
Fig. 2: AQP error analysis. (a) Relative approximation error εAQP vs. sparsification ratio k/d per topology, alongside the theoretical upper bound (dashed). (b) Effective error εeff vs. channel SNR at fixed k/d = 0.1, showing that well-connected topologies suppress both sparsification and noise-induced error.
magnitude order, and let g̃ = TopK(g, k). The absolute sparsification error satisfies Corollary III.3 has a key practical implication: topology r and sparsification ratio should be co-designed. For a k (4) given accuracy budget ε , a well-connected topology (large ∥g − g̃∥2 ≤ ∥g∥2 1 − , tgt d p λ2 (L)) permits a higher sparsification ratio k/d to be used and the relative error satisfies εAQP ≤ 1 − k/d. Further- (lower communication) while still meeting the accuracy target, more, in a graph with spectral gap λ2 (L), the effective per- whereas a sparse topology (small λ (L)) requires either a lower 2 client error after one round of OTA aggregation is reduced sparsification ratio or accepts higher error. Figure 2 validates to p this bound empirically across all five topology families. 1 − k/d εeff (G, k) ≤ , (5) 0.5 + λ2 (L) D. What the Database Framing Enables Beyond Spectral so well-connected topologies (large λ2 (L)) average out sparsiGraph Theory fication errors across the neighbourhood, reducing the effective A natural question is: could the cost model Cours (G) and approximation noise. topology selection algorithm have been derived directly from Proof. The bound (4) follows from Parseval’s theorem convergence analysis without the database framing? 2 applied to the truncated gradient: ∥g − TopK(g, k)∥2 = The answer is partly yes—spectral graph theory alone is Pd 2 2 2 i=k+1 g(i) ≤ (d − k) · ḡk+1 ≤ (1 − k/d) ∥g∥2 , where g(i) de- sufficient to derive the convergence rate T (G) = Õ(1/λ2 (L)) 2 2 notes the i-th largest component and we used ḡk+1 ≤ ∥g∥2 /d. and the topology ranking. What the database framing enables The effective error bound (5) follows by noting that each beyond this are three concrete contributions: client receives |N (i)| independently sparsified updates; by (1) Privacy-preserving statistics collection via database the independence of sparsification errors across clients and sketching. The use of Count-Min Sketches (CMS) to estimate the mixing properties of graphs with spectral gap λ2 (L), the heterogeneity α̂ without sharing raw data is a direct transfer aggregate error scales as εAQP /(0.5 + λ2 (L)). from approximate query processing. No prior FL convergence
5
analysis suggested CMS as a mechanism for workload-adaptive where σp2 > 0 can model either privacy noise or a lower bound algorithm design. This is the strongest concrete technique on wireless transmission noise. transfer in this paper. (2) Framing as a query optimisation problem enables B. OTA Communication Model Pareto-optimal cost-accuracy enumeration. Standard spectral Communication is defined by an undirected graph G = analysis asks “does topology A converge faster than B?” The (V, E). Let L = D − A be the graph Laplacian, with D query optimisation framing asks “which topology minimises the degree matrix and A the adjacency matrix. The secondtotal cost subject to an accuracy Service-Level Agreement?”. smallest eigenvalue λ2 (L) of L is the spectral gap, governing This SLA-constrained optimisation (Equation (14)) would not information mixing speed. naturally arise from convergence analysis alone; it is motivated OTA aggregation requires synchronised transmissions. After by the BlinkDB accuracy SLA concept [30]. t (3) Adaptive plan re-optimisation during training. The channel inversion with coefficient hij , client i receives: X X Eddies and adaptive query processing literature [27], [28] yit = htij xtj + nti ≈ utj + nti , (9) motivates Phase 5 of A IR P LAN: monitoring runtime signals j∈N (i) j∈N (i) and switching plans mid-execution. This design principle is t t t novel in the FL topology literature. where xj = uj /hij is the channel-inverted transmission and We acknowledge that the formal equivalence is an anal- nt ∼ N (0, σ 2 I) is channel noise. Equation (9) is the distributed c i ogy that motivates technique transfer, not a strict algebraic SUM query of Theorem III.1. isomorphism. OTA aggregation is a noisy analog sum—not a relational SUM query in the formal sense—and the graph structure is undirected and homogeneous compared to the C. Consensus Update rich operator DAGs of physical query plans. The framing is Each client updates its model using the aggregated neighintended to open a productive channel for technique import bourhood signal: from a mature literature into a younger one, not to claim a t+ 1 wit+1 = wi 2 + γ yit , (10) deeper mathematical identity. IV. P ROBLEM F ORMULATION We consider a decentralised federated learning (DFL) system composed of N wireless clients. Each client i holds a local noni IID dataset Di = {(xij , yij )}nj=1 drawn from a distribution Pi . The global objective is to minimise min F (w) =
w∈Rd
N X
pi Fi (w),
i=1
where Fi (w) = n1i loss.
ni pi = P , j nj
(6)
Pni
j=1 ℓ(w; xij , yij ) is the local empirical
Assumption IV.1 (Standard Regularity). (i) Each Fi is L-smooth: ∥∇Fi (u) − ∇Fi (v)∥ ≤ L ∥u − v∥. (ii) Stochastic gradients are unbiased with bounded variance: 2 E[∥∇Fi (w; ξ) − ∇Fi (w)∥ ] ≤ σ 2 . (iii) Gradients are bounded: ∥∇Fi (w)∥ ≤ G for all i, w. (iv) The communication graph G = (V, E) is connected. Assumption IV.2 (Bounded PNGradient Dissimilarity).2 There exists δ ≥ 0 such that N1 i=1 ∥∇Fi (w) − ∇F (w)∥ ≤ δ 2 for all w. The parameter δ quantifies data heterogeneity: δ = 0 corresponds to IID data. A. Local Training and Sparsification At iteration t, each client i computes a stochastic gradient update: t+ 1 wi 2 = wit − η ∇Fi (wit ; ξit ). (7) t+ 1
The update vector git = wit − wi 2 is compressed via top-k sparsification and perturbed with Gaussian noise: uti = TopK(git , k) + N (0, σp2 I),
(8)
where γ > 0 is the consensus stepsize. Larger γ accelerates mixing but amplifies OTA noise; optimal γ balances these effects. D. Topology-Dependent Convergence Theorem IV.3 (OTA-DFL Convergence Rate). Under √ Assumptions IV.1 and IV.2, with learning rate η = O(1/ T N ) and consensus stepsize γ = O(λ2 (L)/(L + σc2 /λ2 (L))), OTA-DFL satisfies T −1 i C1 1 X h C2 δ 2 2 E ∇F (w̄t ) ≤ √ + T t=0 λ2 (L) TN | {z } | {z } SGD
C3 σc2 + + C4 ε2AQP , λ2 (L) | {z } | {z } sparsification
heterogeneity
(11)
OTA noise
P t 1 where w̄t = is the mean model, and i wi N C1 , C2 , C3 , C4 > 0 are constants depending on L, σ, G. Proof Sketch. The proof follows the standard decentralized SGD analysis framework [12], [13]. We decompose the update error into four √ terms: the standard SGD variance term (scales as 1/ T N ), a consensus error term arising from data heterogeneity (scales as δ 2 /λ2 (L)), a noise error floor from OTA channel noise (scales as σc2 /λ2 (L)), and a sparsification error term from Corollary III.3 (scales as ε2AQP ). The spectral gap λ2 (L) appears in the denominators of both the heterogeneity and OTA noise terms, confirming that well-connected graphs simultaneously accelerate convergence and mitigate noise. The complete proof with all constants is provided in the supplemental material.
6
B. Phase 2: Cost Table Construction Given the profiled workload (N, α̂, SNR, d), A IR P LAN constructs a cost table by evaluating Cours (G) for each candidate topology G ∈ G:
Fig. 3: A IR P LAN system workflow with five phases. Phase 1 (Section V-A): privacy-preserving Count-Min Sketch statistics collection. Phase 2 (Section V-B): workload profiling (N , α̂, SNR, d). Phase 3 (Section V-C): cost-model evaluation across candidate topologies. Phase 4 (Section V-C): minimum-cost plan selection subject to accuracy SLA. Phase 5 (Section V-D): online monitoring and adaptive rewiring.
G = {Ring, Erdős–Rényi, Small-World, Clustered, FC}. (13) For each topology, the spectral gap λ2 (L) is computed analytically (ring: 2 − 2 cos(2π/N ); FC: N ) or approximated for random graphs using known concentration results [32]. The convergence constant κ is calibrated once on a reference topology (Erdős–Rényi) and held fixed.
C. Phase 3: Topology Selection with Accuracy SLA A IR P LAN selects the topology that minimises total communication cost subject to a user-specified accuracy SLA A∗ :
Remark IV.4. Theorem IV.3 implies that the convergence neighbourhood—the irreducible error floor after convergence— G∗ = arg min Cours (G) subject to Acc(G, T ) ≥ A∗ , is O(δ 2 /λ2 (L) + σc2 /λ2 (L) + ε2AQP ). All three terms can be G∈G (14) controlled through topology choice (λ2 (L)) and sparsification ratio (εAQP ), confirming that topology is a first-class design where Acc(G, T ) is the predicted accuracy after T (G) rounds, estimated from the convergence bound (11). If no topology in parameter for OTA-DFL. G is predicted to meet A∗ , A IR P LAN falls back to the fully V. A IR P LAN : Q UERY-O PTIMIZED T OPOLOGY A DVISOR connected graph and warns the user. Drawing on the formal equivalence established in Section III, we present A IR P LAN: a query-optimised topology advisor for OTA-DFL that automates topology selection via cost-based D. Phase 4: Adaptive Re-Optimisation plan enumeration, privacy-preserving workload statistics, and Analogous to adaptive query processing [27], [28], A IR P LAN adaptive re-optimisation. The system workflow is illustrated in monitors the execution plan during training and triggers reFigure 3. optimisation when observed behaviour deviates from the cost model prediction. The divergence signal is the mean pairwise A. Phase 1: Privacy-Preserving Workload Statistics model distance: The cost model Cours (G) requires an estimate of the 1 X t data heterogeneity parameter α (which controls the Dirichlet ∆t = N wi − wjt 2 . (15) distribution from which local class distributions are drawn). 2 i<j Sharing raw class counts would leak sensitive information about local data. A IR P LAN instead uses Count-Min Sketches If ∆t > τ∆ for a user-defined threshold τ∆ (default: 3× the (CMS) [6] to collect approximate class distribution statistics value at round 10), the current topology is too sparse for the observed heterogeneity and A IR P LAN upgrades to the next without revealing exact counts. Count-Min Sketch collection.. Each client i maintains a denser topology in G. CMS Si ∈ Rr×c over its local label distribution, where r = ⌈ln(1/δs )⌉ rows and c = ⌈e/εs ⌉ columns guarantee that the estimated count of any label deviates from the true count E. AirPlan Algorithm by at most εs · ni with probability at least 1 − δs . Clients Algorithm 1 summarises the complete A IR P LAN procedure. broadcast their sketches (size r × c ≪ ni ) before training, Complexity. The CMS sketch has size O(r · c) = and the aggregator merges them by elementwise maximum to O(log(1/δs )/εs ) per client, independent of ni . Cost table obtain a global distribution sketch Ŝ. construction requires O(|G|) evaluations of Cours , each taking Heterogeneity estimation.. From the merged sketch, A IR O(N ) time. The overhead is dominated by the CMS broadcast, P LAN estimates the pairwise KL divergence between client which costs O(N · r · c) total—less than 1.8 % of training cost class distributions: at N = 100 (see Section IX-C). −1 X Privacy. CMS sketches provide approximate answers to 1 α̂ = N DKL (p̂i ∥p̂j ) , (12) count queries with additive error ε · n and do not expose s i 2 i<j individual data points or exact label counts. Combined with where p̂i is the class probability vector estimated from the the Gaussian noise already present in OTA transmission, the CMS of client i. Large α̂ corresponds to near-IID data; small statistics collection phase is compatible with (ϵ, δ)-differential α̂ indicates severe label skew. privacy via the standard Gaussian mechanism [33].
7
Algorithm 1 A IR P LAN: Query-Optimised Topology Selection Require: Clients {i}N i=1 , model dim d, SNR, accuracy SLA A∗ , divergence threshold τ∆ Ensure: Trained model w̄T , selected topology G∗ 1: // Phase 1: Statistics collection 2: for each client i do 3: Compute CMS sketch Si over local label distribution 4: Broadcast Si to coordinator 5: end for L 6: Merge: Ŝ ← i Si 7: // Phase 2: Workload profiling 8: Estimate α̂ from pairwise KL divergences via Ŝ 9: // Phase 3: Cost table and topology selection 10: for each topology G ∈ G do 11: Compute λ2 (L)(G) (analytical or approximated) 12: Evaluate Cours (G; N, α̂, SNR, d) 13: Predict Acc(G) using bound (11) 14: end for 15: G∗ ← arg minG: Acc(G)≥A∗ Cours (G) 16: // Phase 4: Training with adaptive re-optimisation 17: Initialise training with topology G∗ 18: for round t = 1, 2, . . . , T do 19: Execute OTA-DFL round (local SGD + OTA aggregation + consensus) 20: Compute divergence ∆t 21: if ∆t > τ∆ then 22: G∗ ← next denser topology in G 23: Re-initialise edges; update Cours and SLA check 24: end if 25: end for 26: return w̄ T , G∗
F. Formal Differential Privacy Analysis We provide a complete end-to-end differential privacy analysis of A IR P LAN’s five-phase pipeline. Theorem V.1 (End-to-End DP of AirPlan). Let each client i contribute a Count-Min Sketch Si with parameters (εs , δs ) computed from local data of size ni , with OTA channel noise σc2 per round. The A IR P LAN statistics collection phase (Phase 1) satisfies (ϵDP , δDP )-differential privacy with p εs 2 ln(1.25/δs ) ϵDP ≤ , δDP = δs , (16) σc nmin where nmin = mini ni . Phases 2–4 (cost table construction and topology selection) are deterministic functions of the aggregated sketch and introduce no additional privacy loss. Phase 5 (adaptive rewiring, triggered K times over training) incurs at most K-fold privacy composition [34]: the end-toend guarantee is (ϵtotal , δtotal ) with ϵtotal = (K + 1)ϵ √DP and δtotal = (K + 1)δDP under basic composition, or Õ( K ϵDP ) under advanced composition. Proof sketch. Phase 1 applies the Gaussian mechanism with sensitivity ∆ = εs (bounded by CMS additive error guarantee) and noise σc . The standard Gaussian mechanism bound [33] gives (16). Phases 2–4 satisfy the post-processing immunity
of DP. Phase 5 triggers rewiring based on observed gradient divergence ∥w̄i − w̄∥, which is a function of the alreadynoisy OTA aggregates; by the data processing inequality, each rewiring event contributes at most ϵDP additional privacy loss. The composition bounds follow from [34]. Remark V.2. For typical parameters (εs = 0.01, δs = 10−5 , σc = 0.1, nmin = 500, K ≤ 5), Theorem V.1 yields ϵtotal ≤ 0.13 and δtotal ≤ 6 × 10−5 —strong practical DP. VI. U NIFIED C OMMUNICATION C OST M ODEL In order to provide a consistent and fair comparison across topologies and datasets, we evaluate five key dimensions of performance: (i) test accuracy, (ii) convergence speed, (iii) communication cost, (iv) fairness, and (v) A IR P LAN advisor quality. The communication cost model underpins both the existing topology comparison and the A IR P LAN cost-based plan selection. A. Structural Cost per Round After top-k sparsification, each client transmits k coordinates per round. The total number of OTA symbols transmitted per round is N X Cstruct (G, k) = |N (i)| · k = 2|E| · k, (17) i=1
which captures the joint dependence on graph density and sparsification ratio. B. Wireless Reliability Factor OTA aggregation over a noisy channel may require retransmission or suffer from degraded signal quality at low SNR. We model this via a multiplicative reliability factor R(SNR) = 1 + αR exp(−βR · SNR),
(18)
where αR > 0 controls maximum retransmission overhead and βR > 0 controls how rapidly reliability improves with SNR. Parameters (αR , βR ) are fitted by least-squares regression to empirical retransmission rates measured in our simulator. C. Topology-Dependent Convergence Rounds From Theorem IV.3, the number of rounds to reach an ϵ-stationary point scales as κ T (G) = , (19) λ2 (L) where κ is a problem-dependent constant calibrated on a reference Erdős–Rényi topology and held fixed. Table II lists analytical spectral gaps for each topology family. D. Unified Query Cost Model Combining the three components, the total execution cost is Cours (G) = T (G) · R(SNR) · Cstruct (G, k).
(20)
This is the query cost estimator used by A IR P LAN for plan selection. Its multiplicative structure assumes approximate separability of convergence, per-round cost, and reliability— a standard modelling assumption in distributed system cost models.
8
TABLE II: Spectral gap λ2 (L) for each topology family (N = 50). Topology
λ2 (L) (analytical / typi- T (G) (rel.) cal)
Ring Erdős–Rényi Small-World Clustered Fully Connected
2−2 cos(2π/N )≈0.016 ≈ 0.32 ≈ 0.61 ≈ 0.74 N = 50
1.0 0.33 0.18 0.15 0.006
E. AQP Error Bounds and Sparsification Co-Design From Corollary III.3, the effective approximation error after p one OTA round is εeff (G, k) ≤ 1 − k/d/(0.5+λ2 (L)). A IR P LAN exploits this to jointly select topology and sparsification ratio: (G∗ , k ∗ ) = arg min Cours (G, k)
s.t.
εeff (G, k) ≤ εtgt ,
G∈G, k∈K
(21) where K = {k : k/d ∈ {0.01, 0.05, 0.1, 0.2}}. This is a joint combinatorial optimisation over |G|×|K| configurations, which A IR P LAN solves by full enumeration in O(20) constant-time cost evaluations—negligible overhead compared to training. F. Relation to Classical Cost Models Classical gossip cost Cgossip = T · |E| · d ignores wireless reliability; OTA cost COTA = T · d ignores topology. Cours strictly generalises both: setting R = 1 and k = d recovers Cgossip ; setting all edges present and R = 1 recovers the OTA model. The additional terms capture the topology-reliability interaction that determines the practical operating point of OTA-DFL systems. Figure 4 validates the predictive accuracy of Cours against measured training costs. VII. S YSTEM A RCHITECTURE & M ETHODOLOGY
Fig. 4: Query cost estimator accuracy. (a) Predicted vs. actual convergence rounds across 150 experiment configurations for all five topologies; points near the diagonal indicate accurate cost estimates. (b) Mean Absolute Percentage Error (MAPE) of Cours per topology, ranging from 2.9 % (FC) to 4.8 % (Erdős– Rényi). t+ 1
4) Consensus update. wit+1 = wi 2 + γyit . 5) Divergence monitoring. A IR P LAN computes ∆t and triggers adaptive rewiring if ∆t > τ∆ . Channel model.. OTA aggregation is simulated over a flatfading wireless multiple-access channel with additive white Gaussian noise. Channel inversion and power control are applied to approximate coherent aggregation (Equation (9)). SNR values are varied in {0, 5, 10, 15, 20} dB to cover the range from severely noisy to near-ideal channel conditions. The reliability parameters (αR , βR ) in (18) are fitted by leastsquares regression to measured retransmission rates. Model architectures.. A lightweight four-layer CNN is used for CIFAR-10; ResNet-18 [35] is used for CIFAR-100 and Tiny-ImageNet. All models are implemented in PyTorch and trained with cross-entropy loss. Optimisation.. Local optimisation uses SGD with momentum 0.9. The learning rate is selected from {0.01, 0.05, 0.1}; the number of local epochs per round is E ∈ {1, 2}. A IR P LAN sets the accuracy SLA as A∗ = 0.95 × AccFC by default, targeting 95 % of the fully connected baseline.
The A IR P LAN OTA-DFL framework executes fully decentralised training by combining local stochastic gradient updates with wireless analog aggregation over a communication graph selected by the topology advisor. The overall system architecture is illustrated in Figure 5. System operation.. The system operates in repeated communication rounds. A global dataset is partitioned across N clients under a Dirichlet distribution with parameter α; smaller α produces stronger non-IID distributions. A communication graph G = (V, E) selected by A IR P LAN defines the neighbourhood structure. Before training, A IR P LAN executes Phases 1–3 of Algorithm 1 to profile the workload and select the initial VIII. E XPERIMENTAL S ETUP topology. This incurs a one-time overhead of less than 1.8 % A. Datasets and Models of training cost (Section IX-C). Round structure.. Each training round proceeds as follows: We consider three standard image classification benchmarks 1) Local SGD. Each client i performs E steps of local of increasing complexity. CIFAR-10 [36] consists of 50,000 SGD on its current model wit , producing update git . training and 10,000 test images (32×32, 10 classes). CIFAR2) Sparsification. The update is compressed: g̃it = 100 [36] extends this to 100 classes. Tiny-ImageNet [37] TopK(git , k). includes 200 classes with 64×64 images, representing a 3) OTA transmission. All neighbours of i transmit simul- challenging large-scale setting. Datasets are partitioned across taneously; client P i receives the approximate SUM query N clients using a Dirichlet distribution with parameter α ∈ result yit = j∈N (i) utj + nti . {0.1, 0.5, 1.0}, where smaller α produces stronger label skew.
9
TABLE III: Per-topology accuracy, cost, and convergence rounds under CIFAR-10, N = 50, SNR = 10 dB, α = 0.5. All values: mean ± std over 30 seeds. Best Pareto-efficient value (excluding FC) in bold. Topology
Acc. (%)
Ring 83.1 ± 0.6 ER 87.8 ± 0.5 Small-World 90.2 ± 0.4 Clustered 91.0 ± 0.3 FC 92.1 ± 0.3
Norm. Cost Fairness Var. Conv. Rounds (×10−3 ) 1.0 1.8 2.0 2.3 3.5
21.0 ± 4.0 15.0 ± 3.0 10.0 ± 2.0 9.0 ± 2.0 8.0 ± 1.0
100 70 57 52 38
D. Baselines We compare against the following reference systems: FedAvg [1]: centralised FL with parameter server, full model aggregation. • Digital D-SGD: decentralized SGD over the same topology with packet-based communication (no OTA). • DLLR-OA [3]: the closest prior OTA-DFL baseline, approximated using Erdős–Rényi topology with identical sparsification and training settings. • MATCHA [21]: topology-aware decentralized FL using matching decomposition; adapted to the OTA setting. • Fixed-SW: OTA-DFL always using small-world topology (no advisor, no adaptive rewiring), as a strong static baseline.
•
E. Evaluation Metrics
Fig. 5: Overall architecture of the A IR P LAN OTA-DFL system, showing the five execution phases and the data flows between clients, the OTA channel, and the A IR P LAN topology advisor.
We report: (i) Test accuracy: top-1 accuracy on the held-out test set; (ii) Convergence rounds: rounds to reach a target accuracy; (iii) Communication cost: Cours (G) normalised to Ring; (iv) Fairness: variance of per-client test accuracy; (v) Advisor precision/recall: fraction of configurations in which A IR P LAN selects the oracle-optimal topology; (vi) Advisor overhead: CMS broadcast cost as a fraction of total training cost.
B. Topology Families We evaluate five representative topology families: Ring (sequential pipeline, λ2 (L) ≈ 0.016 at N = 50); Erdős–Rényi (ER) (random graph with connection probability p = 0.2); Watts–Strogatz Small-World (ring with O(log N ) shortcuts, βWS = 0.3); Clustered (dense communities of size ⌊N/5⌋ with sparse inter-cluster bridges); and Fully Connected (complete graph, upper bound).
C. AirPlan Configuration
F. Statistical Validation Each configuration is executed with 30 independent random seeds. Results report mean ± standard deviation. All key differences are verified to be statistically significant using a paired t-test (p < 0.05) unless noted otherwise. The A IR P LAN advisor evaluation uses a 5-fold cross-validation over workload configurations.
IX. R ESULTS
A IR P LAN uses CMS parameters εs = 0.05, δs = 0.01, Unless otherwise stated, experiments correspond to CIFARgiving sketch size 4 × 55 per client. The accuracy SLA is 10 with N = 50 clients, non-IID partitioning (α = 0.5), and A∗ = 0.95 × AccFC . The divergence threshold τ∆ = 3 × ∆10 SNR = 10 dB. All results are averaged over 30 independent ran(3× the divergence measured at round 10). The sparsification dom seeds; mean ± standard deviation is reported throughout. ratio k/d ∈ {0.01, 0.05, 0.1, 0.2} is jointly optimised with the Statistically significant differences are verified using a paired topology as described in Section VI-E. t-test (p < 0.05) unless noted otherwise.
10
TABLE IV: Comparison of A IR P LAN and OTA-DFL variants against all baselines (CIFAR-10, N = 50, SNR = 10 dB). † Requires a central server. ‡ Packet-based digital communication. § OTA-adapted (original design assumes digital channels). ¶ Topology chosen by A IR P LAN cost-model; no manual configuration. Method
Acc. (%)
Norm. Cost Server? Topology auto?
Centralised FL (reference upper bounds) FedAvg† [1] 93.0 ± 0.3 FedProx† [38] 92.6 ± 0.4
4.0 4.0
Yes Yes
N/A N/A
Decentralised digital (non-OTA) Digital D-SGD‡ (SW) [12] GT-DSGD‡ (SW) [15] SGP‡ [17] PowerGossip‡ [39]
88.5 ± 0.5 89.4 ± 0.4 88.9 ± 0.5 89.2 ± 0.4
2.5 2.6 2.4 2.3
No No No No
No No No No
OTA / wireless decentralised MATCHA§ [21] DLLR-OA [3] OTA-GT (ours, GT-DSGD + OTA) OTA-SGP (ours, SGP + OTA)
89.1 ± 0.4 87.6 ± 0.5 90.7 ± 0.4 90.1 ± 0.5
2.2 1.8 2.1 2.0
No No No No
No No No No
Topology selection Random search (500 trials)
90.8 ± 0.4
2.4
No
Yes
A IR P LAN (this work) A IR P LAN (auto)¶
91.0 ± 0.3
2.3
No
Yes
Fig. 6: A IR P LAN advisor evaluation across 150 workload configurations. (a) Confusion matrix (normalised by row): A IR P LAN matches oracle in 91.4 % of configurations. (b) Pertopology precision, recall, and F1 score; all F1 > 0.87. (c) Advisor overhead as a fraction of total training cost: below 1.8 % at all scales.
A. Topology Characterisation Table III characterises the five topology families. Topology ordering is consistent with spectral gap λ2 (L) (Table ??), confirming Theorem IV.3. Ring converges slowest (83.1±0.6 % at round 100) owing to its small spectral gap (λ2 (L) ≈ 0.016 at N = 50); each client’s information must diffuse along a linear chain. Erdős–Rényi (ER) improves mixing substantially (87.8 ± 0.5 %) but exhibits higher variance across random instantiations. Small-World achieves 90.2 ± 0.4 % with approximately 20 % fewer rounds than ER, while Clustered achieves 91.0 ± 0.3 % through fast local consensus within communities and efficient inter-cluster bridges. Fully Connected (FC) serves as the performance upper bound (92.1 ± 0.3 %) at 3.5× Ring’s communication cost. These results motivate A IR P LAN: the optimal topology varies by workload, and no single fixed topology is universally best.
Fig. 7: A IR P LAN vs. fixed-topology baselines across four representative workloads. (a) Accuracy: A IR P LAN tracks the oracle closely. (b) Accuracy gap to oracle with recommended topology annotations.
equivalent quality with a single cost-function evaluation, justifying the query-optimisation framing. C. AirPlan Advisor Evaluation
Figure 6 evaluates A IR P LAN across 150 workload configurations (5 × 5 × 5 grid of N , α, SNR). A IR P LAN matches the oracle-optimal topology in 91.4 % of cases; errors concentrate at the Small-World / Clustered boundary where the costaccuracy trade-off is tightest. When sub-optimal, the accuracy B. Comparison with Baselines gap is ≤ 0.3 pp in all cases. F1 scores exceed 0.87 across all Table IV provides a comprehensive comparison. A IR P LAN topologies, with Ring and FC scoring 0.97 (the extreme plan automatically selects Clustered for this workload (N = 50, choices are easiest to rule out). CMS sketch collection costs α = 0.5, SNR = 10 dB), matching the oracle-optimal topology at most 1.8 % of training at N = 100, confirming negligible without manual configuration. overhead. Among OTA baselines, our OTA-GT adaptation (90.7 %) Figure 7 compares A IR P LAN against fixed-topology policies. achieves the strongest fixed-topology result, confirming that Always-Ring loses 5–11 pp; always-ER loses 2–6 pp. A IR P LAN gradient tracking improves convergence under non-IID data dynamically adapts (FC for IID/small-N , Clustered for severe even in the OTA setting. OTA-SGP (90.1 %) also outperforms non-IID) and achieves ≤ 0.3 pp gap to oracle across all MATCHA (89.1 %) and DLLR-OA (87.6 %). Crucially, A IR - workloads. P LAN outperforms all fixed-topology methods, as it selects the topology matched to the workload—Clustered provides +0.3 pp over OTA-GT at lower cost (2.3 vs. 2.1), confirming D. Cost Model Sensitivity Analysis the value of topology-aware design. Figure 8 analyses A IR P LAN’s cost model. The per-topology Against learned topology selection: random search over 500 MAPE ranges from 2.9 % (FC, which has a closed-form topology candidates (×5 categories) achieves 90.8 % at cost spectral gap) to 4.8 % (ER, whose spectral gap requires Monte 2.4, nearly matching A IR P LAN’s 91.0 %, but with 500× higher Carlo approximation). Residuals are approximately symmetric search overhead. A IR P LAN’s cost-model approach achieves and zero-mean, confirming no systematic bias.
11
Fig. 8: Cost model analysis. (a) Predicted vs. actual Cours (G); MAPE ≤ 4.8 % (per-topology MAPE annotated). (b) Distribution of signed residuals per topology. (c) Impact of MAPE on topology selection: fraction of workloads where a k % cost model error causes wrong topology selection.
Fig. 9: Straggler and client dropout analysis. (a) Accuracy degradation vs. dropout rate for each topology; A IR P LAN reselects to Clustered at ≥ 20 % dropout. (b) A IR P LAN topology recommendation as a function of dropout rate; topology shifts from Small-World to Clustered at higher dropout. (c) Number of adaptive rewiring events per 100 training rounds vs. dropout rate.
To translate MAPE into decision quality, we inject Gaussian cost noise of magnitude k % and measure how often A IR P LAN selects the wrong topology. At MAPE = 4.8 %, only 2.1 % of workload configurations receive a wrong recommendation, and in all such cases the accuracy gap to oracle is < 0.5 pp. The cost-model approach is thus robust to the observed prediction error level. The calibration constant κ is estimated from a single ER trial (approximately 2 % of total training cost). Although this is a fixed overhead, it scales with N and d; we discuss an alternative approach to eliminating this step through theoretical calibration in Section X. E. Straggler and Client Dropout Robustness OTA requires synchronised transmissions; we evaluate robustness by simulating uniform client dropout at rates {0, 10, 20, 30} % per round. Dropped clients are excluded from that round’s OTA aggregation. Figure 9(a) shows accuracy degradation per topology. Ring degrades most severely (−6.2 pp at 30 % dropout) because missing links disconnect the chain. Clustered is most robust (−1.8 pp at 30 %): community structure provides redundant paths that maintain global connectivity even when 30 % of nodes are absent. Figure 9(b) shows how A IR P LAN adapts its topology recommendation under dropout. At ≥ 20 % dropout, A IR P LAN
Fig. 10: Per-client fairness analysis. (a) CDF of per-client test accuracy per topology (N = 50, α = 0.5, SNR = 10 dB). (b) Jain’s fairness index J and mean accuracy per topology; Small-World and Clustered achieve the best joint accuracyfairness trade-off. (c) Fairness–accuracy Pareto frontier: A IR P LAN selects topologies on the frontier.
correctly shifts its recommendation from Small-World to Clustered, recognising that redundant community paths dominate under unreliable participation. This adaptation is automatic and requires no user intervention. Figure 9(c) shows rewiring frequency increases with dropout rate, peaking at 3.4 rewiring events per 100 rounds at 30 % dropout. False-positive rewiring (triggered but accuracy actually improves) occurs in 7 % of events; the latency penalty is bounded at 0.12 rounds equivalent per rewiring event. F. Fairness Analysis Table III reports per-topology fairness variance; here we provide a deeper P P analysis. We use Jain’s fairness index J = ( i ai )2 /(N i a2i ), where ai is the final test accuracy of client i. Figure 10(a) shows the CDF of per-client accuracy. Ring has the heaviest left tail: 18 % of clients achieve below 75 % accuracy, reflecting slow information diffusion at chain endpoints. Clustered and Small-World nearly eliminate lowaccuracy clients; fewer than 3 % fall below 80 %. Figure 10(b) shows Jain’s index per topology. Clustered achieves J = 0.965, the highest fairness, while Ring has J = 0.891. Small-World achieves J = 0.951 at lower cost than Clustered. Figure 10(c) shows that Small-World and Clustered both lie on the accuracy-fairness Pareto frontier; A IR P LAN selects between them based on the accuracy SLA and workload statistics. G. Scalability Projection Figure 11 extends the scalability analysis. For N ≤ 100, results are empirical (30 seeds); for N ∈ {200, 500, 1000} we use cost-model extrapolation validated against all empirical points (MAPE ≤ 4.8 %). At N = 1000, FC becomes impractical: its normalised cost reaches 71× Ring’s baseline (vs. 3.5× at N = 50), confirming O(N 2 ) growth. Small-World and Clustered grow at O(N log N ), reaching 6.2× and 7.4× at N = 1000. A IR P LAN adapts its recommendation to Clustered for N ≥ 50, keeping cost within 8× Ring across all scales. The primary architectural bottleneck preventing larger empirical evaluation is the synchronous OTA requirement: all participating clients must transmit simultaneously, which
12
Fig. 11: Extended scalability analysis. (a) Empirical accuracy for N ∈ {10, 20, 50, 100} (solid lines) with cost-model extrapolation to N ∈ {200, 500, 1000} (dashed). Shaded bands show ±1 standard deviation from 30 seeds (empirical) or model uncertainty (extrapolated). (b) Normalised communication cost; FC explodes at O(N 2 ) while A IR P LAN maintains O(N log N ) growth.
requires tight time synchronisation (≤ 1 µs at typical carrier frequencies). Asynchronous OTA variants that relax this constraint [10] are a promising direction for scaling beyond N = 1000. H. Additional Observations Non-IID heterogeneity (α ∈ {0.1, 0.5, 1.0}). Under severe label skew (α = 0.1), Clustered outperforms Small-World by 1.8 pp (p < 0.05). Under mild heterogeneity (α = 1.0), the two are statistically indistinguishable. A IR P LAN correctly selects Clustered for α̂ < 0.3 and Small-World otherwise in 94 % of cases. Sparsification co-design. Joint optimisation of topology and k/d yields an additional 0.9 pp accuracy gain at identical cost compared to fixing k/d = 0.1, validating the AQP co-design approach. Cross-dataset consistency. All findings on CIFAR-10 replicate on CIFAR-100 and Tiny-ImageNet. X. D ISCUSSION A. Implications of the Query Processing Equivalence
A small neural network trained on (workload, topology) → (convergence rounds) pairs could improve prediction accuracy beyond the 3–5 % MAPE of our current model. c) AQP error and wireless channel duality: Corollary III.3 establishes that OTA channel noise and sparsification error play symmetric roles in the convergence bound (11): both contribute an error floor that scales as 1/λ2 (L). This duality implies that in the high-SNR regime (small σc2 ), aggressive sparsification (k/d → 0) is beneficial, while in the low-SNR regime the two error sources compound. A IR P LAN accounts for this interaction through the joint (G, k) co-design in Section VI-E. B. Limitations and Assumptions a) Ideal channel inversion: Our OTA model assumes that channel state information (CSI) is available at each transmitter and that transmit power is sufficient for full channel inversion. In practice, CSI estimation introduces error and power constraints may limit inversion accuracy. We expect the topology-dependent trends to persist under imperfect CSI, but the exact error floors will increase. Extending A IR P LAN to account for power-constrained channel inversion is a natural direction for future work. b) Static graph families: A IR P LAN selects from five fixed topology families. The space of possible graphs is exponentially large; more general graph search methods (e.g., spectral graph sparsification [40] or graph neural network-based topology design) may find topologies outside these families that further reduce Cours (G). c) Synchronous communication: OTA aggregation requires synchronised transmissions for the superposition property to hold. In heterogeneous edge deployments where clients have widely varying computation speeds, synchronisation incurs a straggler penalty. Asynchronous OTA variants [10] are a promising direction but require a revised cost model. d) Simulation-based evaluation: All experiments use simulated flat-fading AWGN channels. Hardware experiments on a real wireless testbed (e.g., using software-defined radios) would validate practical feasibility and reveal implementationlevel constraints not captured in simulation.
The formal equivalence between OTA-DFL and distributed C. Connection to Systems Research query processing has implications that extend beyond the A IR P LAN is, to our knowledge, the first system that applies specific problem studied here. database-style physical plan selection to a wireless distributed a) Cross-community transfer of techniques: Our results learning problem. The result is practically significant: topology suggest that the vast literature on query optimisation—bushy selection, which was previously a manual and empirical choice, plan enumeration, histogram-based cost estimation, join order is now automated, principled, and takes less than 1.8 % of optimisation, and adaptive re-optimisation—is directly applica- training time to execute. ble to the topology design problem in decentralized wireless From a systems perspective, the A IR P LAN advisor resembles learning. Conversely, OTA aggregation offers a new physical existing database advisor tools such as the Microsoft Index Adexecution primitive not available in classical database systems: visor and IBM DB2 Design Advisor [41], which automatically multiple clients can transmit and aggregate simultaneously in a recommend index structures given a query workload. A IR P LAN single time slot over the wireless channel, which has no direct plays the analogous role for wireless federated learning: given a analogue in digital message passing. training workload, it recommends the communication structure b) Topology selection as a learned cost model: Our cost (topology + sparsification) that minimises total execution cost. estimator Cours (G) uses a handcrafted model calibrated on a We anticipate that this framing will motivate new systems reference topology. A natural extension is to learn the cost contributions in both the ML and database communities, model from observed training trajectories, analogous to learned including topology-aware FL frameworks that are deployable cardinality estimation in neural database query optimisers [26]. as first-class distributed data processing systems.
13
D. Energy and Memory Cost Analysis For realistic edge AI deployment, we analyse three additional resource dimensions. Per-device energy consumption. Each OTA round requires all clients to transmit simultaneously for one time slot. The per-device transmission energy is Etx = Ptx · Ts , where Ptx is the transmit power and Ts the slot duration. For a typical mobile device (Ptx = 23 dBm, Ts = 1 ms), Etx ≈ 0.2 mJ per round. Over T rounds, total energy scales as E = T ·Etx . Since A IR P LAN reduces T by selecting faster-converging topologies— Small-World reaches target accuracy 20 % sooner than ER—the energy saving is proportional to the round reduction. At N = 50 and SNR = 10 dB, Clustered topology saves approximately 16 % total energy vs. Ring. CMS sketch memory footprint. Each client stores a CMS of size r × c = ⌈ln(1/δs )⌉ × ⌈e/εs ⌉. For (εs = 0.01, δs = 10−5 ): r = 12, c = 272, requiring r × c × 4 bytes = 13 KB per client. This is negligible for any modern edge device and imposes no practical memory constraint. RF hardware requirements. OTA aggregation requires analog combining at the receiver and simultaneous transmission from all clients, which mandates: (i) a shared uplink carrier frequency with tight synchronisation (≤ 1 µs offset), achievable with standard GPS or network time protocol (NTP) disciplined oscillators; (ii) power control to equalise received amplitudes, standard in LTE/5G; (iii) a receive-side analog combiner, which can be implemented in a commodity software-defined radio (SDR). These requirements are met by current 5G NR uplink designs and do not impose hardware costs beyond standard cellular infrastructure. XI. C ONCLUSIONS We presented A IR P LAN, a query-optimised topology selection framework for Over-the-Air Decentralized Federated Learning. The central contribution is a formal equivalence between OTA-DFL and distributed query processing, which recasts the topology selection problem as physical query plan optimisation. Within this framework, the communication graph is the execution plan, the spectral gap of the graph Laplacian is the cardinality estimate, top-k sparsification is an AQP operator, and the unified cost model Cours (G) is the query cost estimator. Building on this equivalence, A IR P LAN automates topology selection via privacy-preserving Count-Min Sketch statistics, cost-based plan enumeration, and adaptive plan re-optimisation triggered by model divergence monitoring. We proved formal AQP error bounds (Corollary III.3) showing that well-connected topologies intrinsically tolerate higher sparsification ratios, enabling joint topology-sparsification co-design. Empirical evaluation across five topology families, three datasets, four client scales, and five SNR levels demonstrates that: • Small-world and clustered topologies consistently Paretodominate the accuracy-cost frontier, delivering ≈90 % of the accuracy gain of a fully connected graph at 57 % of its communication cost. • A IR P LAN matches the oracle-optimal topology in 91.4 % of workload configurations with ≤ 1.8 % overhead.
The formal convergence bound (Theorem IV.3) accurately captures the joint effect of data heterogeneity, OTA noise, and sparsification error on the convergence neighbourhood. a) Future Work.: Several directions remain open. Learned cost models: replacing the handcrafted Cours (G) with a neural query cost estimator trained on observed training trajectories could improve prediction accuracy and generalise to topology families outside G. Hardware validation: experiments on a real wireless testbed would confirm practical feasibility and reveal implementation constraints. Asynchronous OTA: extending A IR P LAN to handle straggler-tolerant asynchronous OTA aggregation is essential for heterogeneous deployments. Broader plan space: spectral graph sparsification and graph neural networkbased topology design may discover communication graphs outside the five studied families that achieve lower Cours (G) for specific workloads. Privacy-utility trade-off : a systematic analysis of the DP guarantee per topology, accounting for the Gaussian noise inherent in OTA aggregation, would strengthen the privacy claims of the framework. •
ACKNOWLEDGMENTS This work was partially funded by the grant PID2023-148716OB-C31 funded by MCIU/AEI/ 10.13039/501100011033 (DISCOVERY project) and by the Galician Regional Government under project ED431B 2024/41 (GPC). R EFERENCES [1] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. Agüera y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in Proc. AISTATS, 2017, pp. 1273–1282. [2] G. Zhu, Y. Wang, and K. Huang, “Broadband analog aggregation for low-latency federated edge learning,” in Proc. IEEE Globecom, 2019. [3] J. Qiao, S. Shen, S. Chen, X. Zhang, T. Lan, X. Cheng, and D. Yu, “Communication resources limited decentralized learning with privacy guarantee through over-the-air computation,” in Proc. ACM MobiHoc, 2023. [4] P. G. Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price, “Access path selection in a relational database management system,” in Proc. ACM SIGMOD, 1979, pp. 23–34. [5] Y. E. Ioannidis, “Query optimization,” ACM Computing Surveys, vol. 28, no. 1, pp. 121–123, 1996. [6] G. Cormode and S. Muthukrishnan, “An improved data stream summary: The count-min sketch and its applications,” in Journal of Algorithms, vol. 55, no. 1, 2005, pp. 58–75. [7] M. M. Amiri and D. Gündüz, “Federated learning over wireless fading channels,” IEEE Transactions on Wireless Communications, vol. 19, no. 5, pp. 3546–3557, 2020. [8] K. Yang, T. Jiang, Y. Shi, and Z. Ding, “Joint transmit beamforming and receive combining for over-the-air federated learning,” IEEE Transactions on Wireless Communications, vol. 21, no. 2, pp. 965–978, 2022. [9] X. Cao et al., “Privacy-preserving over-the-air federated learning via user-distinguishable channel,” IEEE Journal on Selected Areas in Communications, vol. 40, no. 3, 2022. [10] S. Lin, G. Zhu et al., “Hierarchical over-the-air federated learning with relay-assisted aggregation,” in Proc. IEEE Globecom, 2023. [11] T. Sery, N. Shlezinger, K. Cohen, and Y. C. Eldar, “COTAF: Convergent over-the-air federated learning,” IEEE Transactions on Wireless Communications, vol. 20, no. 12, pp. 8258–8274, 2021. [12] X. Lian, C. Zhang, H. Zhang, C.-J. Hsieh, W. Zhang, and J. Liu, “Can decentralized algorithms outperform centralized algorithms? A case study for decentralized parallel stochastic gradient descent,” in Advances in Neural Information Processing Systems (NeurIPS), 2017. [13] K. Scaman, F. Bach, S. Bubeck, Y. T. Lee, and L. Massoulié, “Optimal algorithms for smooth and strongly convex distributed optimization in networks,” Journal of Machine Learning Research, vol. 20, pp. 1–31, 2019.
14
[14] A. Koloskova, S. Stich, and M. Jaggi, “Decentralized deep learning with arbitrary communication compression,” in Proc. ICLR, 2020. [15] S. Pu and A. Nedić, “A distributed algorithm for computing a common fixed point of a family of paracontractions,” in Proc. American Control Conference, 2018. [16] H. Yuan and T. Ma, “Federated accelerated stochastic gradient descent,” arXiv:2006.08950, 2020. [17] M. Assran, N. Loizou, N. Ballas, and M. Rabbat, “Stochastic gradient push for distributed deep learning,” in Proc. ICML, 2019. [18] A. Koloskova, S. Stich, and M. Jaggi, “Decentralized stochastic optimization and gossip algorithms with compressed communication,” in Proc. ICML, 2019. [19] Y. Chen, L. Su, and J. Xu, “Byzantine-robust decentralized learning via consensus filtering,” IEEE Transactions on Signal Processing, vol. 71, pp. 440–455, 2023. [20] Y. Lu, Z. Zhang et al., “GraphFL: A graph-based communication-efficient federated learning framework,” IEEE Transactions on Mobile Computing, 2022. [21] J. Wang, H. Liang, and G. Joshi, “MATCHA: Speeding up decentralized SGD via matching decomposition sampling,” in Proc. IEEE Indian Conference on Computer Vision, Graphics and Image Processing, 2019. [22] PostgreSQL Global Development Group, “PostgreSQL 16 documentation: Query planning,” 2023. [Online]. Available: https://www.postgresql.org/ docs/current/planner-optimizer.html [23] G. Graefe, “The Volcano model of data-flow and query evaluation,” in Proceedings of the IEEE Data Engineering Bulletin, 1993, pp. 20–27. [24] M. Armbrust, R. S. Xin, C. Lian, Y. Huai, D. Liu, J. K. Bradley, X. Meng, T. Kaftan, M. J. Franklin, A. Ghodsi, and M. Zaharia, “Spark SQL: Relational data processing in Spark,” in Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. ACM, 2015, pp. 1383–1394. [25] V. Leis, A. Gubichev, A. Mirchev, P. Boncz, A. Kemper, and T. Neumann, “How good are query optimizers, really?” in Proc. VLDB Endowment, vol. 9, no. 3, 2015. [26] J. Sun and G. Li, “An end-to-end learning-based cost estimator,” in Proc. VLDB Endowment, vol. 13, no. 3, 2019, pp. 307–319. [27] R. Avnur and J. M. Hellerstein, “Eddies: Continuously adaptive query processing,” in Proc. ACM SIGMOD, 2000, pp. 261–272. [28] A. Deshpande, Z. Ives, and V. Raman, “Adaptive query processing,” in Foundations and Trends in Databases, vol. 1, no. 1, 2007, pp. 1–140. [29] J. M. Hellerstein, P. J. Haas, and H. J. Wang, “Online aggregation,” in Proc. ACM SIGMOD, 1997, pp. 171–182. [30] S. Agarwal, B. Mozafari, A. Panda, H. Milner, S. Madden, and I. Stoica, “BlinkDB: Queries with bounded errors and bounded response times on very large data,” in Proc. ACM EuroSys, 2013, pp. 29–42. [31] S. Chaudhuri, B. Ding, and S. Kandula, “Approximate query processing: No silver bullet,” Proc. ACM SIGMOD, pp. 511–519, 2017. [32] F. Chung, L. Lu, and V. Vu, “The eigenvalues of random graphs,” Proceedings of the National Academy of Sciences, vol. 100, no. 11, pp. 6313–6318, 2003. [33] C. Dwork and A. Roth, The Algorithmic Foundations of Differential Privacy. Now Publishers, 2014. [34] C. Dwork, G. N. Rothblum, and S. Vadhan, “Boosting and differential privacy,” in Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2010, pp. 51–60. [35] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in Proc. IEEE CVPR, 2016, pp. 770–778. [36] A. Krizhevsky, “Learning multiple layers of features from tiny images,” University of Toronto, Tech. Rep., 2009. [37] Y. Le and X. Yang, “Tiny ImageNet visual recognition challenge,” CS231n Course Report, Stanford University, 2015. [38] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith, “Federated optimization in heterogeneous networks,” in Proceedings of Machine Learning and Systems (MLSys), vol. 2, 2020, pp. 429–450. [39] T. Vogels, L. He, S. P. Karimireddy, and M. Jaggi, “PowerGossip: Practical low-rank communication compression in decentralized deep learning,” in Advances in Neural Information Processing Systems (NeurIPS), vol. 33, 2020, pp. 13 895–13 906. [40] D. A. Spielman and S.-H. Teng, “Spectral sparsification of graphs,” SIAM Journal on Computing, vol. 40, no. 4, pp. 981–1025, 2011. [41] S. Chaudhuri and V. Narasayya, “Self-tuning database systems: A decade of progress,” Proc. VLDB Endowment, pp. 3–14, 2007.
A PPENDIX A C OMPLETE P ROOF OF T HEOREM IV.3 Setup. We consider the OTA-DFL update rule. At round t, client i computes a stochastic gradient git of its local objective Fi , applies top-k sparsification to obtain g̃it = TopK(git , k), and transmits over the OTA channel with additive noise nti ∼ N (0, σc2 I). The aggregated gradient received at client i is: X ĝit = Wij g̃jt + ntj , (22) j∈N (i)
where W is the doubly stochastic weight matrix associated with graph G. Assumptions. We use Assumptions ?? and ?? (smoothness with constant L, gradient variance bounded by σ 2 ). We additionally assume: Assumption A.1 (Top-k approximation error). The sparsification error satisfies E∥g̃ − g∥2 ≤ (1 − k/d)∥g∥2 . Assumption A.2 (Spectral gap). The graph Laplacian L satisfies λ2 (L) > 0, and the weight matrix W = I − ηW L has spectral radius ρ(W − N1 11⊤ ) = 1 − ηW λ2 (L) < 1. Proof of Theorem IV.3. Step 1: Consensus error P bound. Define the consensusPerror at round t as et = N1 i ∥w̄t − wit ∥2 , where w̄t = N1 i wit . By the mixing property of W [12]: et+1 ≤ ρ2 et +
2η 2 L2 C1 2η 2 σc2 C2 + , λ2 (L) λ2 (L)
(23)
where ρ = 1 − ηW λ2 (L) < 1, C1 = 1−k/d (sparsification k/d σ2
c factor), and C2 = λ2 (L) 2 (OTA noise amplification). The constants C1 and C2 depend on k/d, σc , and G through λ2 (L); their explicit dependence on L and σc2 is made PT −1precise in (23). Unrolling (23) over T steps and using t=0 ρ2t ≤ 1/(1 − ρ2 ): T −1 e0 2η 2 C3 1 X t e ≤ 2 + , (24) T t=0 ρ T λ2 (L)(1 − ρ2 )
where C3 = L2 C1 + C2 collects all topology-independent constants. Step 2: Gradient descent descent lemma. Using Lsmoothness and the update rule, for the global average w̄t : F (w̄t+1 ) ≤ F (w̄t ) − η∥∇F (w̄t )∥2 Lη 2 σ 2 Lη 2 C4 t + + e, N λ2 (L)
(25)
where C4 = 4L2 bounds the cross-term between gradient and consensus error. The explicit dependency on L is through the smoothness constant; on σ 2 through gradient variance; on G through λ2 (L) and et . Step 3: Telescoping and averaging. Telescoping (25) over T steps, dividing by T , and substituting (24): T −1
1 X E∥∇F (w̄t )∥2 T t=0 ≤
2[F (w̄0 ) − F ∗ ] Lησ 2 2ηLC3 + + . ηT N λ2 (L)(1 − ρ2 )
(26)
15
√ √ Setting η = O(1/ T ) gives convergence at rate O 1/ T + O σc2 /λ2 (L) , matching the statement of Theorem IV.3. The OTA noise floor C3 σc2 /λ2 (L) is the additional term beyond standard D-SGD; it cannot be reduced by increasing T , only by improving SNR or using a topology with larger λ2 (L). Non-triviality of the contribution. The result extends the standard D-SGD analysis [12] in two non-trivial ways. First, the OTA channel noise introduces a noise floor ∝ σc2 /λ2 (L) that is absent from digital analyses: this couples wireless channel quality to the algorithmic convergence rate. Second, top-k sparsification introduces a sparsification floor ∝ (1 − k/d)/λ2 (L): these two error sources are additive but interact through the shared 1/λ2 (L) factor, motivating their joint analysis and the co-design framework of Section VI-E. The combination of OTA noise and sparsification in the same bound, with explicit topology dependence, is not available in any prior work. A PPENDIX B P ROOF OF T HEOREM V.1 (E ND - TO -E ND DP) Phase 1 DP. Each client i submits Si . Define the sensitivity of Si with respect to a single data point as ∆ = εs (bounded by the CMS additive error guarantee for one count update). By the Gaussian mechanism [33], adding i.i.d. Gaussian noise Np (0, σc2 ) to each CMS cell p achieves (ϵ1 , δ1 )-DP with ϵ1 = ∆ 2 ln(1.25/δ1 )/σc = εs 2 ln(1.25/δs )/(σc nmin ). Post-processing (Phases 2–4). Topology selection is a deterministic function of the aggregate sketch, satisfying DP by post-processing immunity [33]. Adaptive rewiring (Phase 5). Each rewiring trigger is a function of ∥w̄i − w̄∥, computed from OTA-noisy aggregates already protected by DP. The data processing inequality guarantees each trigger adds at most ϵ1 privacy loss. With at most K rewirings, basic composition gives ϵtotal p≤ (K + 1)ϵ1 . Under advanced composition [34]: ϵtotal ≤ ϵ1 2(K + 1) ln(1/δ ′ ) + (K + 1)ϵ1 (eϵ1 − 1). □