Auditing Federated Clients at the Mixing-Time Scale

When federated clients learn from data that arrives as a correlated stream, an honest client can look like a cheater. Examples of such streams are a robot's trajectory, a pollution sensor's hourly readings, or a reinforcement-learning agent's walk through an environment. While the stream lingers in one region of state space, the client's update points somewhere unrepresentative. Today's defenses compare each round's update against the other clients or against recent history. They therefore flag this honest client as malicious, or, in the case of weight-evolution checks, as a "free-rider": a participant that downloads the shared model but submits zero or fake updates to avoid paying for computation. The inflated honest variance has a second effect. It widens the region in which disguised free-riders and stealthy attackers can hide.

We propose to move the audit, but not the aggregation, to the time scale on which the data stream forgets its past, called the mixing time. The server keeps, for each client, a running sum of that client's updates over a window longer than the mixing time. It scores clients by peer agreement and by trajectory consistency on these window sums rather than on single rounds. The central claim is a coupling between damage and detection at this scale. An honest client's window sum converges toward the shared descent direction, so its false-positive rate falls as the window grows. A stealthy attacker can only harm the model by pushing a consistent bias across rounds, and that bias accumulates in exactly the window sum we inspect. A free-rider's window sum carries no signal at all. One cheap server-side statistic thus addresses Byzantine filtering and free-rider valuation together, and it does so specifically in the regime where the Markovian data makes per-round tests fail.

Where the gap is

Federated learning on Markovian data has been analyzed only for honest clients. Streaming Federated Learning with Markovian Data proves linear speedup for Minibatch SGD, Local SGD and Local SGD with momentum on streaming data. It shows that correlation inflates the gradient noise by a factor tied to the chain's spectral gap. Federated Reinforcement Learning: Linear Speedup Under Markovian Sampling does the same for federated temporal-difference (TD) learning and Q-learning. Both papers aggregate by plain averaging, which a single bad client can break.

The robust Markovian work does not cover the federated server setting. Byzantine-Resilient Decentralized TD Learning with Linear Function Approximation applies a trimmed mean in peer-to-peer consensus. Byzantine-Robust Online and Offline Distributed Reinforcement Learning robustifies tabular count statistics. Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Rates handles corrupted rewards for a single agent. None of the three models free-riders, and none audits parameter updates sent to a server.

On the defense side, the file contains four detectors, and each makes a per-round, i.i.d.-style assumption that Markovian data violates:

Meanwhile, Free-rider Attacks on Model Aggregation in Federated Learning shows that free-riders who add calibrated noise already pass as inliers under i.i.d. data. A Little Is Enough: Circumventing Defenses For Distributed Learning shows that attackers scaled to the honest spread defeat Krum and Bulyan. Markovian data inflates that spread. These papers motivate the proposal; none of them proposes this fix.

Core Claim

The analytical tool comes from A Multistep Lyapunov Approach for Finite-Time Analysis of Biased Stochastic Approximation. That paper shows that biased Markovian updates contract when examined over a look-ahead window longer than the mixing time, even though single steps do not.

We turn this into an audit. Let $u_i^r$ be client $i$'s update in round $r$, and let $\bar u^r$ be the robustly aggregated update. The server keeps the window sum

$$S_i^{W}(r) = \sum_{s=r-W+1}^{r} u_i^s .$$

The claim is about how two kinds of deviation scale with the window $W$, measured in rounds, relative to $\tau$, the mixing time measured in rounds. For an honest client, the deviation of $S_i^W/W$ from the population direction shrinks like $\sqrt{\tau/W}$. This rate follows from the batch-means variance of a geometrically mixing chain, whose effective sample count is $W/\tau$. For a client injecting a persistent bias $b$, the same deviation stays at $\|b\|$. The bias is the attacker's per-round effect on the model, so the attacker cannot shrink it without also shrinking the damage.

Peer agreement among honest clients therefore rises toward one as $W/\tau$ grows. The agreement of a noise-only free-rider stays near zero. Per-round tests are the special case $W=1$, where both groups are indistinguishable when $\tau$ is large.

A free-rider could try to fake agreement by replaying past aggregates. The "delta weight" attack studied by WEF-Defense does exactly this. We add a second statistic to catch it: how well lagged aggregates $\bar u^{r-1},\dots,\bar u^{r-L}$ linearly predict a client's residual $u_i^r-\bar u^r$. An honest client's residual is driven by its own chain, which the server never sees, so lagged aggregates should explain little of it. A replayer's residual is almost fully explained by them.

Research Program

The method has two time scales. Aggregation runs every round with a cheap robust rule, the coordinate-wise trimmed mean, so the model is protected from gross outliers immediately. The audit runs on the window sums.

Three questions are left open by this design, and each gets its own piece of the program.

Choosing the window. The mixing time is unknown, so $W$ is estimated online. The server compares the variance of aggregate-update window sums across a range of window lengths, using standard batch-means variance ratios. It picks the smallest $W$ at which the ratio stabilizes.

Turning scores into consequences. The two statistics are combined into a per-client score. The score sets aggregation weights in the manner of Fed-PCA. Optionally, it also sets reward tier in the manner of Aequa: Fair Model Rewards in Collaborative Learning via Slimmable Networks, which hands out sub-networks of different width according to contribution. Tiering is what makes free-riding unprofitable rather than merely detectable.

Server memory. Storing one vector per client costs about the same as STPA's momentum. For large models, the window sums are kept in a fixed random low-dimensional projection, following the projection defense of Shiyun Lin et al..

On the theory side, we will prove two results for linear TD learning and for strongly convex streaming least squares, extending the multistep Lyapunov argument. The first bounds the honest false-positive rate as a function of $W/\tau$. The second bounds the residual damage from any attacker who passes the audit. The second result is a deliberate weakening: we bound harm, not detection. An attacker whose window bias is small enough to pass the audit is one whose cumulative effect on the model is small.

Baselines

The naive reference point is Local SGD with momentum and plain averaging, the best honest method in Streaming Federated Learning with Markovian Data. It is run with no defense, to measure how much the attacks hurt.

The classical robust aggregators are coordinate-wise median, trimmed mean and Krum. These are the default answer to "just filter bad updates". In Local Model Poisoning Attacks to Byzantine-Robust Federated Learning, optimized attacks raised MNIST error for Krum from 0.11 to 0.75 and for median from 0.06 to 0.28. Under the attack of A Little Is Enough: Circumventing Defenses For Distributed Learning, CIFAR-10 accuracy dropped to 20.3% for Krum and 28.1% for Bulyan.

The strongest Byzantine competitor is STPA. It is the closest prior work because it also uses temporal information, and it reports about 1% MNIST test error with 34% malicious clients, where Krum exceeded 80%. Those numbers are on i.i.d. image data. For the Beijing air-quality or federated TD settings, no reported result was found on Lacuna for STPA, so we will run it ourselves.

The strongest free-rider competitors are WEF-Defense and Fed-PCA. WEF-Defense reports a defense effect 1.68x and 1.33x stronger than its baselines in IID and non-IID settings. For Fed-PCA, no reported numeric result was found on Lacuna; its Taobao result is qualitative.

Fairness is enforced in four ways:

  • Every method sees identical client streams, attack schedules and model architectures.
  • Every method gets the same hyperparameter search budget: the same number of grid points over thresholds, clipping levels and momentum.
  • Every method is given the true Byzantine count wherever it requires one.
  • Every method is given the same server memory budget, matched by projection dimension.

Beating the field means two things together. First, a lower honest-client false-positive rate and higher free-rider detection area under the curve than STPA, WEF-Defense and Fed-PCA at mixing times of at least five rounds. Second, final loss or TD error within noise of the attack-free run. A method that wins on detection but loses accuracy does not count.

Three ablations isolate the key ingredient. Setting $W=1$ reduces the method to per-round peer prediction, essentially Fed-PCA with our scoring. Fixing $W$ instead of estimating it tests the window-selection step. Removing the lagged-predictability term should expose the method to replay free-riders.

Why not just…?

Why not just loosen the thresholds of existing detectors to stop flagging honest Markovian clients? Loosening thresholds trades false positives for a wider hiding envelope. That envelope is exactly what disguised free-riders in Free-rider Attacks on Model Aggregation in Federated Learning and variance-scaled attackers in A Little Is Enough exploit. We will tune STPA's and WEF-Defense's thresholds over the full grid and plot receiver operating curves. If any threshold setting dominates the window audit across mixing times, the proposal fails.

Why not just run more local steps, or use local momentum, so each update already averages over the mixing time? This is the real threat. If the number of local steps per round greatly exceeds the mixing time, per-round updates are already near-i.i.d., and our method should reduce to existing ones. We therefore expect gains only when communication is frequent relative to mixing. Frequent communication is the regime that Federated Reinforcement Learning: Linear Speedup Under Markovian Sampling favors for speedup, and the regime of slow environmental regimes in sensing. Local momentum is also computed by the client, so an adversary controls it, as noted for STPA. We will sweep local steps against mixing time and report the crossover. If the advantage persists far past the crossover, or never appears below it, our explanation is wrong.

Why not just score clients on a clean server validation set? Data-Free Evaluation of User Contributions in Federated Learning and Incentive Design for Efficient Federated Learning in Mobile Networks: A Contract Theory Approach argue that such sets are often unavailable under privacy constraints. Local Model Poisoning Attacks to Byzantine-Robust Federated Learning found that loss-based rejection did not fully protect Krum. A static validation set also cannot represent which region of the state space each client currently occupies. We include a validation-set loss-based rejection baseline with an oracle stationary-distribution validation set, as an upper reference.

Proposed Experiments

Testbeds. We use three testbeds, in increasing order of realism:

Attacks. We test plain and Gaussian-disguised free-riders, delta-weight replay free-riders, sign flipping, the variance-scaled attack from A Little Is Enough, and the optimized local model poisoning attack. Adversary fractions run from 10% to 40%. We also test an adaptive attacker who knows our window and spreads a bias that stays just below the audit threshold.

Metrics. We report:

  • the honest false-positive rate,
  • free-rider detection area under the curve,
  • final gradient norm or TD mean-squared error relative to the attack-free run,
  • the Pearson correlation between true contribution and allocated reward, the metric Aequa reports at about 0.98 to 1.00 on static data.

Decisive checks. Three results would settle the claim. First, the honest false-positive rate of STPA and WEF-Defense should rise with mixing time, while ours stays flat once the window $W$ is estimated. Without this, the motivating gap is not real. Second, against the adaptive attacker, the excess error should be bounded by the audit threshold, as the damage-coupling theorem predicts. Third, the advantage should vanish once local steps far exceed mixing time, which confirms that the mechanism, rather than tuning, is responsible.