AirPlan Query-Optimized Topology Selection for Over-the-Air Decentralized Federated Learning

Jul 16, 2026

Upload by Ivy

Over-the-air (OTA) aggregation reduces communication latency and bandwidth by combining multiple devices’ gradient updates through wireless multiple-access superposition. While OTA has been studied for centralized federated learning, its decentralized counterpart—over peer-to-peer graphs without a central server—lacks a principled method for selecting communication topology. This work proposes AIRPLAN, recasting OTA-DFL topology selection as distributed query optimization over a DAG plan, using privacy-preserving workload estimation and a graph-aware cost model to minimize training cost under an accuracy SLA. Experiments on multiple graph families and vision benchmarks show near-oracle performance with low overhead.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages15

Reading Time38 min

Introduction

Background: Federated and Decentralized Federated Learning

OTA Computation and the Topology Design Problem

Systems Reframing as Query Plan Selection

AirPlan: Query-Optimized Topology Selection for Over-the-Air Decentralized Federated Learning 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 arXiv :2607 .04254v 1 [ cs .DC] 5 Jul 2026 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 AIRPLAN, 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-ksparsification 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 torecast topology selection as a query optimization problem: given a training workload (client count N, data heterogeneity α, channel SNR, model dimension d), AIRPLAN 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 AIRPLAN through systematic experiments across five graph families (ring, Erds–Rényi, small-world, clustered, fully connected), three standard vision benchmarks (CIFAR-10, CIFAR- 100, Tiny-ImageNet), four client scales (N ∈ {10, 20 , 50 , 100}), and a range of SNR conditions (0–20 dB). Our results demonstrate that AIRPLAN 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. Index Terms—Over-the-air computation, decentralized federated learning, graph topology, query optimization, approximate query processing, communication efficiency, wireless networks, spectral graph theory. I. INTRODUCTION Federated learning (FL) enables distributed model training without sharing raw data, making it a natural fit for privacysensitive applications across mobile networks, IoT deployments, and edge computing infrastructure. The dominant paradigm, 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 ex

FAQs

What problem does AIRPLAN address in OTA decentralized federated learning?

AIRPLAN targets the key pre-training design decision of which peer-to-peer communication topology should be used for OTA-DFL, since topology choice strongly affects convergence, noise sensitivity, and communication cost.

How does AIRPLAN connect OTA-DFL topology selection to distributed query processing?

Each OTA aggregation round is modeled as an approximate distributed SUM query over a communication-graph execution plan; the graph Laplacian’s spectral gap links to execution cost, while sparsification corresponds to approximate query processing.

How are candidate topologies chosen and evaluated under an accuracy requirement?

AIRPLAN estimates workload parameters using privacy-preserving Count-Min Sketch statistics, evaluates a graph-aware cost model across candidate topologies, and selects the plan that minimizes total training cost while satisfying a user-specified accuracy SLA.

Jul 16, 2026

Upload by Ivy