Running a Federated Fleet at Saturation: Heavy-Traffic Scheduling for Nonlinear System Identification

When many robots or drones learn a shared model of their own dynamics, each one repeatedly sends compressed summaries of its recent trajectories over a shared wireless uplink to a server. Existing work treats this uplink as free and instantaneous, so it never asks the basic engineering question: how much should each agent send? Our answer is that, when bandwidth is the binding constraint, the best amount is close to the most the link can carry. Each extra bit carries useful information about the dynamics until queueing delay starts to cancel the gain, and that crossover sits near saturation. Running the link that hot is exactly the regime that heavy-traffic queueing theory studies. Heavy-traffic queueing theory is the mathematics of networks run at nearly 100% load, where the right scheduling rule makes many separate queues behave like one pooled fast queue.

We propose an uplink scheduler that ranks waiting packets by how much each one would reduce the server's model error per bit, using the gradient of a nonlinear error measure, and serves packets with a cost-weighted MaxWeight rule whose weights are updated as learning proceeds. We would test the claim on the pendulum and 13-state quadrotor fleets used in federated nonlinear system identification. The prediction is that this scheduler reaches a given identification error, and a given closed-loop control quality, in less wall-clock time than queue-oblivious federated averaging, Lyapunov device scheduling, and event-triggered communication. We also expect its backlog to match a heavy-traffic lower bound as load approaches capacity.

Core Claim

The setting is the one in Federated Nonlinear System Identification (FNSysID). That paper learns piecewise-affine dynamics $x_{t+1}=\sum_k \theta_k \phi_k(x_t,u_t)$ from many agents, with the nonlinear feature maps $\phi_k$ known in advance. It proves the error shrinks as $1/\sqrt{M}$ in the number of agents $M$, and it assumes synchronous, delay-free rounds.

We exploit one structural fact this setting provides. Because the model is linear in its parameters, each agent's local least-squares statistics for region $k$ simply add up across agents. These statistics are the Gram matrix $G_k$ of features and the cross-term with next states. The server can therefore rebuild the centralized estimate exactly from whatever statistics packets it has received.

Each packet then becomes a queueing "job" with three properties: a class (agent, region), a known size in bits (set by the agent's compression level), and a known value. The value is the reduction it would cause in the server-side error proxy

$$E=\sum_k \mathrm{tr}\big(G_k^{-1}\big),$$

where $G_k$ is the Gram matrix already delivered to the server for region $k$. This is the standard A-optimal design criterion, which tracks parameter-estimate variance under the persistent-excitation conditions FNSysID assumes.

$E$ is nonlinear: it is convex in the delivered information and differs sharply across regions. A packet for a rarely visited region near a stability boundary can be worth far more than a large packet for a well-explored region. The cost of letting a packet of class $i$ wait is therefore its holding cost $c_i(t)=-\partial E/\partial(\text{info}_i)$ per bit, and this cost drifts as $G_k$ grows.

Our central claim has two parts. First, because $G_k$ changes on the slow timescale of learning while queues fluctuate on the fast timescale of packet arrivals, the scheduler can freeze $c(t)$ within epochs. Second, with $c(t)$ frozen, the cost-tilted state space collapse result of On Heavy-Traffic Optimal Scaling of c-Weighted MaxWeight Scheduling in Input-Queued Switches applies epoch by epoch. "State space collapse" means the multi-queue backlog concentrates on a low-dimensional cone. That paper proves this cone is tilted by a fixed linear cost vector $c$, and it explicitly leaves nonlinear costs open.

We do not claim to solve heavy-traffic optimality for arbitrary nonlinear costs. We target the narrower case where a nonlinear cost varies slowly relative to queue dynamics. That case is exactly the shape that learning-driven traffic produces.

The second claim is empirical. The compression level sets the arrival load $\rho$, so sweeping compression traces an error-versus-time curve, and its minimum should lie at $\rho$ close to 1. If that is wrong and the optimum sits at moderate load, the heavy-traffic machinery is unnecessary. We treat that outcome as the proposal's main falsification test.

Research Program

The first piece is a simulator. A fleet of $M$ agents runs the pendulum, synthetic 3-state, and 13-state quadrotor systems from FNSysID with heterogeneous physical parameters, which reproduces that paper's error floor from heterogeneity. The agents share an uplink of capacity $C$ that serves one or several aggregation workers. Each agent turns its trajectory into per-region statistics packets and chooses a compression level. Compression is either low-rank sketching of $G_k$ or output-aware selection in the style of Enhancing Communication Compression via Discrepancy-aware Calibration for Federated Learning. That paper ranks parameter units by how much the model output changes if they are dropped, measured on 32–64 calibration samples. Here we reuse its score as the value estimate for a packet's components.

The second piece is the scheduler. At each service opportunity it serves the class maximizing $c_i(t)\,Q_i\,\mu_i$, where $Q_i$ is the queued work of class $i$ and $\mu_i$ is its service rate. It refreshes $c(t)$ once per epoch from the server's current $G_k$.

When there are several aggregation workers, we add a dispatching layer that borrows the controlled asymmetry of CARD from Heavy-Traffic Optimal Size- and State-Aware Dispatching. CARD keeps $n-1$ servers for short jobs and isolates large jobs on one server, and that paper proves this asymmetry is heavy-traffic optimal for known sizes. Our version sends small, high-value packets to short-queue workers and full-resolution residual packets to a dedicated long worker. Because CARD needs its size thresholds calibrated in advance, we re-estimate them online from the observed packet-size distribution.

The third piece is analysis. We want a bound on the time-averaged $c$-weighted backlog in each epoch that matches the switch paper's lower bound up to a term controlled by the drift in $c(t)$ per epoch. This drift falls as $G_k$ grows, roughly as $1/t$ under persistent excitation, since $c$ is a gradient of $\mathrm{tr}(G_k^{-1})$. We then translate the backlog bound into an identification-error bound. Delivered information equals generated information minus the information still queued, so lower weighted backlog means a smaller excess error over the delay-free FNSysID rate. Finally, we plug the identified model into a simple nonlinear MPC tracking loop to check that the gains survive in closed-loop control.

Baselines

The naive reference is FNSysID exactly as published: synchronous federated averaging over the same uplink, served first-come first-served, at the same compression level. It shows what ignoring the queue costs.

The strongest scheduling competitor is the Lyapunov drift-plus-penalty device scheduler of Communication-Efficient Device Scheduling for Federated Learning Using Lyapunov Optimization. It picks client participation probabilities and transmit powers round by round, reweights updates by $1/q_n^t$, and enforces power limits through virtual queues. It reports up to an 8.5x wall-clock speedup to target accuracy over uniform random selection on CIFAR-10 with 100 nodes.

For a fair comparison we give it the same channel model and the same compression levels, and we add a real-backlog term to its drift. We tune its tradeoff parameter $V$ over the same grid size we use for our epoch length. We beat it if we reach a fixed quadrotor identification error, or a fixed MPC tracking cost, in at least 20% less wall-clock time at the error-optimal load of each method. The 20% margin is our own choice of practical significance. For FNSysID error values on the quadrotor or pendulum, there is no reported result found on Lacuna, so all identification numbers will come from our own reruns.

The event-triggered competitor adapts the determinant trigger of Communication Efficient Federated Learning for Generalized Linear Bandits. Each agent transmits when the log-determinant of its local Gram matrix grows past a threshold. That paper proves sublinear $\tilde{O}(\sqrt{T})$ communication for nonlinear-link bandits but does not model the queue. We tune its threshold under the same budget as our other parameters. For multi-worker dispatch we compare against join-the-shortest-queue, power-of-$d$, and least-work-left. On synthetic Weibull jobs at 98% load, the CARD paper reports roughly a 93% mean-response-time reduction over least-work-left.

Two ablations isolate the key ingredient. The first uses information-blind weights ($c_i$ constant), which reduces the scheduler to plain MaxWeight. The second keeps the weights but swaps the nonlinear piecewise-affine features for a single global linear model. In the linear case every region is the same, so the value of a packet barely varies, and the benefit should mostly disappear. If it does not disappear, our story about where the gain comes from is wrong.

Why not just…?

Why not just compress harder until the link is lightly loaded? This is the most serious alternative. If compression were nearly free in accuracy, operating at moderate $\rho$ would remove queueing delay and make everything here unnecessary. The discrepancy-calibration paper suggests compression is not free: at a 0.01 ratio, ViT-tiny on CIFAR-10 reaches only 29.62% accuracy with calibrated selection and 21.03% with magnitude Top-$k$. Still, that evidence comes from image classification, not system identification. Our compression sweep answers the question directly. We report the load at which each method reaches its minimum time-to-error. If that load is well below saturation for every method, we concede the point.

Why not just use event-triggered communication, which already cuts traffic? Determinant triggers fire when an agent's local information grows. In a fleet that explores the same regions at the same time, for example many drones encountering the same gust or maneuver, triggers arrive in bursts, and a queue-oblivious rule sends all of them at once. We test this with correlated-excitation scenarios and measure peak backlog. We also try a hybrid that feeds our scheduler's backlog back into the trigger threshold. If the hybrid matches our scheduler, the honest conclusion is that a queue-aware trigger is enough, and we will report it as such.

Why not just tune Lyapunov drift-plus-penalty with a real queue term? Drift-plus-penalty already handles real queues and is a strong competitor. The difference is what each method optimizes. Drift-plus-penalty minimizes a per-round penalty plus queue drift. It has no notion of which waiting packet carries the most learning value, and it does not target the cost-tilted collapse that gives a heavy-traffic lower bound. The information-blind ablation and the augmented drift-plus-penalty baseline together separate the effect of the weights from the effect of being queue-aware at all.

Why not just linearize the dynamics? The four-tank example in Data-Driven Model Predictive Control With Stability and Robustness Guarantees shows that the unconstrained data-driven controller diverges, which warns against naive linear treatments. More to the point, linearization removes the differences in packet value across regions that our weights exploit. The linear-features ablation measures how much of our gain depends on nonlinearity.

Proposed Experiments

The main experiment fixes uplink capacity and sweeps the compression level, and therefore $\rho$, from 0.5 to 0.99. We run fleets of $M\in\{16,64,256\}$ on the pendulum and the 13-state quadrotor with heterogeneous parameters. For each method we record three things: wall-clock time to reach a fixed identification error, the closed-loop MPC tracking cost after a fixed time budget, and the weighted backlog scaled by $(1-\rho)$.

The decisive check on the theory is whether this scaled backlog flattens to a constant near the predicted lower bound as $\rho\to1$ under our scheduler but grows under first-come first-served and the information-blind ablation. The decisive check on the motivation is the location of each method's error-optimal $\rho$.

A secondary experiment repeats the scheduling comparison on CIFAR-10 with 100 nodes and Dirichlet non-i.i.d. splits. There we use discrepancy scores as packet values, which places our scheduler in the regime where the 8.5x Lyapunov result was reported. It tests whether the idea transfers beyond additive sufficient statistics, where no exact error formula exists. A negative result there would confine the contribution to linearly parameterized nonlinear identification, which is still a useful and clearly bounded claim.