Phase-Free Over-the-Air Agreement on the Delay-Doppler Grid

Groups of fast-moving radios such as train cars, vehicle platoons, drones, or satellites often need to agree on a shared number: a clock offset, a position estimate, or an averaged model update. They have no central server to do it. The standard way to agree is for every node to message every other node, so traffic grows with the square of the group size. A physical-layer shortcut exists. If all nodes transmit at once, the radio waves add up in the air and a listener receives a sum directly. This is called over-the-air computation. It normally requires every transmitter to pre-correct its signal so the waves arrive in phase, which means knowing the exact channel. At 370 km/h, measured channel coefficients stay constant for only about a millisecond, while any multi-round agreement protocol runs for tens of milliseconds.

We propose to avoid phase alignment altogether. Each node encodes its quantized value as a burst of energy at a chosen cell of a delay-Doppler grid. The delay-Doppler grid is a signal layout, used by OTFS (orthogonal time frequency space) modulation, whose axes are path delay and Doppler shift instead of time and frequency. A listener measures only how much energy lands in each cell. That gives it a histogram of its neighbors' values. From the histogram it computes a trimmed mean, which discards the most extreme values and so tolerates Byzantine nodes (nodes that behave arbitrarily or maliciously). The method needs no per-frame channel phases. It uses only the large-scale path-power profile, which the same railway measurements show is stable for about 100 ms. Every neighborhood aggregates in a constant number of shared frames rather than one message per ordered pair of nodes.

Core Claim

Delay-Doppler modulation is useful for decentralized agreement for a reason prior work has not exploited. Coherent pre-equalization was the lever Huang, Hellström and Fischione used in Low-Complexity OTFS-Based Over-the-Air Computation Design for Time-Varying Channels. Our lever is different. On the delay-Doppler grid, the energy a transmitter deposits in a cell is predictable from slowly varying geometry and fluctuates little. The claim therefore splits the two timescales measured in Delay-Doppler Domain Channel Measurements and Modeling in High-Speed Railways. The fast timescale, the quasi-invariant interval of roughly 1 ms, governs phases, which our scheme never uses. The slow timescale, the quasi-stationary interval of roughly 100 ms, governs path powers, which our scheme uses once per stationarity window as fixed mixing weights.

Concretely, suppose node $u$ transmits a unit-energy delay-Doppler pulse at cell $q(x_u)$, where $x_u$ is its quantized value. Suppose also that the path support of the channel, with $L$ delay taps and $K$ Doppler taps, is known from the stationarity window. A listener then sums received energy over the support of cell $q$:

$$\hat{E}_q = \sum_{u:\,q(x_u)=q} g_u + \eta_q ,$$

Here $g_u$ is the large-scale received power from node $u$, which is stable over roughly 100 ms. The term $\eta_q$ collects noise, small-scale fluctuation, and cross-terms between colliding transmitters, which average toward zero over the pulse support. Normalizing $\hat{E}$ by the expected total power $\sum_u g_u$ gives a weighted histogram. The weights $g_u/\sum_u g_u$ act as a row-stochastic mixing matrix, meaning each row of weights sums to one. That matrix is fixed across the dozens of agreement rounds that fit inside one stationarity window.

Why expect $\eta_q$ to be small on this grid and not on an ordinary OFDM grid? Two effects work in its favor. First, each delay-Doppler symbol is spread across the whole time-frequency plane. Calderbank's OTFS study reports 0.2 dB of SNR variation over 10 ms against up to 4 dB for OFDM (Calderbank). Energy counts should inherit that stability. Second, Doppler moves energy to a predictable neighboring cell rather than smearing it across subcarriers as inter-carrier interference does. The number of distinguishable value levels is therefore about $MN/(LK)$ on an $M \times N$ grid. That quantity is set by channel spread, not by speed.

Relation to Prior Work

Three lines of work motivate the proposal by leaving a specific gap. Low-Complexity OTFS-Based Over-the-Air Computation Design for Time-Varying Channels shows that OTFS makes over-the-air averaging robust to speed. Its design is coherent and needs perfect channel knowledge at both transmitters and receiver. It targets a single fusion center, and its best scheme costs $O(U M^3 N^3)$. We drop the fusion center, the phase knowledge, and the matrix inversions. Decentralized Federated Learning via MIMO Over-the-Air Computation and Decentralized SGD with Over-the-Air Computation do decentralize over-the-air averaging. The latter also supplies our half-duplex scheduling device, a graph coloring that decides which nodes transmit and which listen. Both assume static or flat-fading channels and honest nodes. We inherit their mixing-matrix view of convergence and replace coherent sums with energy histograms.

On the agreement side, Asynchronous Approximate Agreement with Quadratic Communication provides the target guarantee. Honest nodes converge to within $\epsilon$ of each other, inside the range of honest inputs, by repeatedly trimming extreme values. It still sends a quadratic number of messages over error-free links. Our histograms are the physical-layer analogue of its trimming step. Byzantine Consensus in Wireless Networks constrains the design. It achieves $O(1)$ forwarding per node using broadcast non-equivocation and aggregate signatures, but only on an idealized channel without collisions or Doppler. Signatures require decoding each packet individually, which is incompatible with superposition. We therefore obtain robustness from bounded transmit power and trimming rather than from cryptography, and we accept a weaker, physical threat model in exchange. MAR-FL is the strongest logical-layer alternative. It reduces peer-to-peer communication to $O(N \log N)$ with group all-reduce over reliable links, and we use it as a baseline.

Research Program

The first component is the waveform and estimator. We will design the value-to-cell codebook, including guard spacing sized to the TDDL-A, B, and C delay-Doppler spreads. We will also design the energy estimator over each cell's path support. We will analyze the error term $\eta_q$ in closed form: its mean, which comes from noise and fractional-Doppler leakage, and its variance, which comes from small-scale fading and collisions between transmitters at the same value. We will compare the result against the same construction on an OFDM grid. Cell-to-cell leakage from fractional Doppler is the known weak point, and we will measure it rather than assume it away.

The second component is the protocol. Rounds use a random or colored split into talkers and listeners, so each node listens in a constant expected number of frames per round. Large-scale gains are re-estimated once per stationarity window from a single pilot frame. Each listener applies a weighted trimmed mean that removes mass $f\,w_{\max}$ from each tail, where $f$ is the number of tolerated Byzantine neighbors and $w_{\max}$ is the largest neighbor weight. We will prove $\epsilon$-convergence under three conditions: bounded histogram error, a lower bound on honest weights, and a transmit-power cap on Byzantine nodes.

The threat model is stated plainly. A Byzantine node can put its capped energy in any cells, but it cannot exceed the cap undetected, because listeners compare total received energy to the stationary sum $\sum_u g_u$. Nearby Byzantine nodes carry more weight, so the tolerance threshold is weight-based rather than count-based. The analysis will quantify how much this costs relative to the geometric thresholds of Byzantine Consensus in Wireless Networks.

The third component is the complexity accounting. The quantity counted is channel uses per agreement round for the whole network, compared against quadratic digital exchange. Values with more precision than one grid allows are handled by splitting them across several frames, and this extra cost is counted explicitly.

Baselines

The naive reference point is digital all-to-all approximate agreement: each node sends its value to every neighbor in an orthogonal time slot on an ordinary OFDM link, with the cyclic prefix and fading margin a practitioner would choose, running the trimming protocol of Asynchronous Approximate Agreement with Quadratic Communication. It shows the quadratic wall directly. It uses the same bandwidth and power as our scheme. Beating it means reaching the same $\epsilon$ in fewer total channel uses at every tested network size, with the gap growing with $n$.

The strongest existing method is coherent OTFS over-the-air averaging. We take Scheme S1 of Low-Complexity OTFS-Based Over-the-Air Computation Design for Time-Varying Channels and extend it to each neighborhood with the same talk/listen split. It is given pilot retraining whenever the elapsed time exceeds the quasi-invariant interval, and pilot frames are charged as channel uses. It is the fairest strong competitor because it uses the same waveform and the same superposition gain and differs only in coherence. We will run it on the same channel realizations with the same power budget, and tune its power-scaling and denoising factors on held-out realizations with the same effort we spend tuning our codebook. The file does not report a numerical MSE for S1: no reported result found on Lacuna for OTFS-AirComp computation error. We will reproduce it on the paper's own configuration of $M=32$, $N=16$, $U=20$, 1,000 realizations, and 127 and 253 km/h. Beating it means lower agreement error per channel use once pilot overhead is counted, together with bounded error under Byzantine inputs, where the coherent mean has no protection at all.

The digital logical-layer baseline is MAR-FL-style group averaging (MAR-FL) running over orthogonally scheduled OTFS links with ideal coding. The comparison is the number of channel uses needed to reach a target accuracy or $\epsilon$. MAR-FL reports up to a 10x reduction in communication load against peer-to-peer baselines at 125 peers. As a physical-layer reference, Decentralized SGD with Over-the-Air Computation reports 57 time slots for orthogonal peer-to-peer transfer against 19 for over-the-air aggregation on MNIST.

Three ablations isolate the key ingredients. The first runs the identical histogram protocol on an OFDM grid, which isolates the delay-Doppler contribution. The second replaces the trimmed mean with the histogram mean, which isolates the source of Byzantine robustness. The third swaps long-term gain weights for per-frame instantaneous gains, which tests whether the slow-timescale split actually matters.

Why not just…?

Why not just use coherent OTFS over-the-air computation and retrain pilots every millisecond? This alternative is a real threat at low node counts and moderate speeds, where pilot cost is small and coherent sums use energy far more efficiently than histograms. Its costs grow with the conditions that motivate this work. Pilot retraining per link grows with neighborhood size and speed. Coherent sums cannot be trimmed, so a single Byzantine node can move the mean arbitrarily. The strongest-baseline comparison will map the crossover in speed, neighborhood size, and $f$. If coherent retraining wins everywhere with $f=0$ and pilots counted, we will narrow the claim to the Byzantine regime.

Why not just do energy histograms on ordinary OFDM? Energy detection is phase-free on any waveform, so this alternative threatens the claim that delay-Doppler signaling is necessary. The argument against it is specific. Doppler-induced inter-carrier interference spills energy into neighboring value cells, biasing the counts. OFDM per-cell energy also fluctuates by several dB over the timescale of a round, compared with 0.2 dB for OTFS (Calderbank), which inflates count variance. The OFDM ablation settles this directly. If histogram error on OFDM is within noise of the OTFS version on TDDL-A at 371 km/h, the delay-Doppler part of the proposal fails, and we will report that.

Why not just run digital group aggregation with signatures, as in MAR-FL or signature-based wireless consensus? Digital schemes give cryptographic, count-based Byzantine guarantees that ours does not match. Their cost is that every value needs its own decoded, scheduled packet, and the orthogonal-scheduling slot counts in Decentralized SGD with Over-the-Air Computation show that this overhead is substantial. The signature approach of Byzantine Consensus in Wireless Networks has also only been analyzed on an ideal channel. The comparison with the MAR-FL baseline measures the channel-use gap. The weight-based threshold analysis measures the security we give up. We will report both rather than claim dominance.

Proposed Experiments

Channels come from the TDDL-A, B, and C tapped delay-Doppler models of the Beijing-Shenyang measurements (371 km/h, 465 MHz, 5 MHz bandwidth, Delay-Doppler Domain Channel Measurements and Modeling in High-Speed Railways). To stay comparable with prior work, we also use the configuration of Low-Complexity OTFS-Based Over-the-Air Computation Design for Time-Varying Channels at 127 and 253 km/h. Nodes move along linear and platoon topologies with $n$ from 10 to 200 and Byzantine fractions from 0 to 20%. Adversaries follow three strategies: extreme values, power splitting across many cells, and equivocation-free value drift.

The primary task is scalar approximate agreement. The metrics are channel uses to reach a given $\epsilon$, final honest spread, and whether outputs stay within the range of honest inputs. The secondary task is decentralized learning on non-IID MNIST with a small model, using coordinate-wise trimmed aggregation of quantized updates, the setting of MAR-FL and Decentralized SGD with Over-the-Air Computation. Here we report accuracy against total channel uses, with multi-frame quantization cost included.

Three checks decide whether the claim holds. First, the histogram error $\eta_q$ must stay flat between 127 and 371 km/h on OTFS while growing on OFDM; otherwise the delay-Doppler claim is false. Second, holding gain weights fixed across a full 100 ms window must leave convergence unchanged compared with per-frame weights; otherwise the timescale split is false. Third, total channel uses per round must scale with the number of listening frames rather than with $n^2$, and must beat coherent retraining once pilots are counted, at least whenever $f>0$.