Who Leaks When Training Doesn't Wait: Straggler-Concentrated Gradient Leakage and a Cohort-Floor Fix

Federated learning trains one shared model across many devices. Each device sends only model updates, never its raw data. Prior work has shown those updates can be inverted back into training images: an attacker optimizes a fake input until its gradient matches the observed one. It has also shown that ordinary training habits blunt this attack. Averaging over many examples, running several local steps, and summing updates from many clients all blur the signal. Every one of those findings was measured with synchronous training, where the server waits for every device each round.

Real deployments rarely wait, because the slowest device, the "straggler," sets the pace. Servers therefore accept updates asynchronously, aggregate the first $K$ arrivals, or give each device a fixed time budget. We argue that these speed fixes quietly remove the blurring that protected users, and they remove it unevenly. A slow device under a time budget finishes fewer local steps. Its update tends to arrive alone, or in a small group, after the fast devices have moved on. Gradient leakage should therefore concentrate on the slowest clients, who are often the poorest-connected users. This proposal sets out to measure that effect and to fix it with a simple server rule.

Core Claim

The empirical claim is that under straggler mitigation, a client's privacy risk is set by two quantities. One is the size of the group its update is released with, which we call the release cohort. The other is the number of local steps it completed. Both shrink as the client gets slower. Against an honest-but-curious server, meaning one that follows the protocol but tries to learn from what it sees, staleness offers no hiding place: the server knows which model version it sent each client.

The method claim is that a cohort-floor aggregation rule restores a uniform privacy guarantee. Under this rule, no update is released into the global model until at least $m$ client contributions have been pooled. Late arrivals wait for the next pool instead of being dropped. Added noise is topped up according to how many clients actually contributed. This should match synchronous privacy at near-asynchronous speed, and it should beat both worst-case local noise and dropping stragglers.

Prior Work and Its Role

Several papers motivate the leakage side and supply our attacks.

All of these assume synchronous rounds. Our premise is that the protective factors they identify are exactly what straggler mitigation strips from slow clients.

Two papers supply the systems methods we reuse.

Neither paper considers privacy. On the privacy side, Gradient-Leakage Resilient Federated Learning supplies per-example clipping with a decaying clip threshold, evaluated only in synchronous training. Beyond Inferring Class Representatives shows that a server tracking one client across rounds can recover that user's personal features. This motivates our concern that isolated straggler updates are exactly what such an attacker wants.

The closest work is Lightweight Federated Learning with Differential Privacy and Straggler Resilience, which we treat as the main competitor. It pairs individual noise with pairwise noise that cancels when all clients report. When stragglers drop out, the uncanceled pairwise terms remain in the aggregate, and the paper tunes noise variances to the observed straggler distribution. It reports privacy only as a differential-privacy budget plus accuracy, never with inversion attacks. It also requires clients to coordinate with each other.

Our design differs in three ways. It is server-side only. It sets a floor on cohort size rather than relying on noise cancellation. It is evaluated by direct per-client attack.

FedVS achieves exact, straggler-tolerant private aggregation through coded secret sharing. However, it works in the vertical setting, where clients hold different features of the same users. It also requires replacing standard activations with polynomial ones, so it does not transfer to standard horizontal training with ReLU networks.

Research Program

Audit. The first part measures who leaks. We simulate federated training in which each client's runtime is drawn from three kinds of delay distributions:

  • independent heavy-tailed delays,
  • delays tied to a device-hardware tier,
  • delays correlated with the client's label distribution.

The label-correlated case captures the data bias that Gradient Coding warns about. We run each delay setting under four aggregation schemes: synchronous, fully asynchronous, fastest-$K$, and time-budgeted local training. Every client update observed by the server is attacked with three methods: gradient matching, generator-prior inversion, and normalization-statistic matching. We record reconstruction quality as a function of three quantities: the client's speed percentile, its realized cohort size, and its completed local steps.

We also settle the open question of whether staleness obscures data, by giving the attacker either the true model version the client used or only the current model. If staleness helps at all, it helps only against the second, weaker attacker.

Mechanism. The second part builds the cohort-floor rule. The server holds incoming updates in a buffer and releases an aggregate only once at least $m$ distinct clients have contributed. Each held update is first shrunk using the Gap-Aware staleness factor $g_i \ge 1$. This factor is computed from the version history the server already stores, so it needs no client data. The shrunk update $u_i/g_i$ is then clipped to norm $C$.

Because shrinking happens before clipping and the shrink factor depends only on public information, each update's contribution is still bounded by $C$. This sidesteps the concern that data-dependent staleness weights break fixed-sensitivity privacy accounting. The released aggregate is

$$\tilde{U} = \sum_{i \in S} \mathrm{clip}_C\!\left(u_i / g_i\right) + \mathcal{N}\!\left(0,\ \sigma^2 C^2 \max\!\left(1, \tfrac{m}{|S|}\right)^{0}\mathbf{I}\right)_{\text{top-up}},$$

where $S$ is the set of clients pooled in the release ($|S| \ge m$ by construction) and $\sigma$ is the noise multiplier. In practice the "top-up" works as follows when noise is distributed across clients. Each client adds noise with standard deviation $\sigma C/\sqrt{m}$, so that any $m$ clients together supply the full noise. The server adds the missing share only when the trusted aggregation path supplied less than that. Privacy is tracked with the Moments Accountant, the standard bookkeeping tool for repeated noisy releases.

Analysis. We will prove that every released aggregate meets the same per-round guarantee regardless of a client's speed. We will then bound how much extra waiting the floor causes as a function of $m$ and the delay distribution. Following the error-per-second view of Slow and Stale Gradients Can Win the Race, this waiting is the real price of the floor.

Baselines

The naive reference point is fully asynchronous aggregation with no noise. It gives the fastest wall-clock progress and, we expect, the worst leakage concentrated on stragglers. A second reference point is synchronous training without noise. It shows the blurring that was "lost," and the file reports its CIFAR-10 accuracy as 93.37% with undefended reconstruction LPIPS of 0.45 (Evaluating Gradient Inversion). LPIPS is a learned image-similarity score where higher values mean a less faithful reconstruction.

The strongest heuristic defense is the combination of 90% gradient pruning, Intra-InstaHide, and batch size 32 from the same paper. It reached LPIPS 0.73 at 86.10% CIFAR-10 accuracy under synchronous training. We rerun it under each straggler regime. Beating it means matching or exceeding LPIPS 0.73 on the slowest decile of clients while keeping accuracy above 86.10%.

The strongest formal competitor is LightDP-FL (Lightweight Federated Learning with Differential Privacy and Straggler Resilience). The file reports only a relative figure: more than 15% higher CIFAR-10 accuracy than vanilla local differential privacy. No absolute accuracy for it is reported on Lacuna, so we reimplement it and calibrate it to the same privacy budget. Fed-CDP with decay (Gradient-Leakage Resilient Federated Learning) is run under the same delay traces. Its reported synchronous result is 97.48% on MNIST against a 97.98% non-private baseline.

All methods share the same data splits, model, delay traces, privacy budget, and hyperparameter tuning budget, which is a fixed number of trials over the clip threshold and learning rate. Beating LightDP-FL means three things together: equal or higher accuracy at equal privacy budget and equal wall-clock time, plus lower worst-decile inversion quality.

Ablations remove one ingredient at a time:

  • the cohort floor (setting $m=1$),
  • the noise top-up,
  • the ordering of shrinking before clipping (clipping first, then shrinking).

They also include "drop stragglers" fastest-$K$ training at a $K$ equal to $m$. This isolates whether pooling late arrivals, rather than discarding them, matters for accuracy on minority data.

Why not just…?

Why not just use fastest-$K$ aggregation with a large $K$, which also guarantees a cohort size? This is the most serious alternative, and it may match our privacy numbers. It fixes the cohort size by throwing away late updates. When slowness correlates with labels or hardware tier, the model then never learns from slow clients. Gradient Coding reports a worse holdout AUC (area under the ROC curve) when stragglers are ignored. The fastest-$K$ ablation under label-correlated delays decides this question. If its accuracy on slow-client classes matches the cohort floor, we will concede that the floor adds nothing beyond retaining data.

Why not just give every client enough local noise to be private on its own? This works, but at a large utility cost. LightDP-FL reports beating vanilla local differential privacy by more than 15% CIFAR-10 accuracy. Under asynchrony, the local noise also compounds with staleness error. We include this method at matched privacy budget to show the size of the gap.

Why not just increase local batch size so every update is blurry? Larger batches help against pixel-space attacks. However, Gradient Inversion with Generative Image Prior recovers batch-32 images at quality comparable to batch-4 pixel attacks. Larger batches also lengthen slow devices' runtimes, which makes them even more likely to arrive alone. The audit includes a batch-size sweep to test this directly.

Why not just rely on staleness to hide the data? An honest-but-curious server stores every model version it has sent, so it can attack with the correct one. The audit's true-version versus current-version comparison will quantify how little obscuring remains against the server. Any protection staleness provides should show up only against outside eavesdroppers.

Proposed Experiments

The main testbed is CIFAR-10 with ResNet-18 across 100 clients. To get images large enough for generator-prior attacks, we add FFHQ faces at 32×32, which has a published generator-prior inversion setup. Following Do Gradient Inversion Attacks Make Federated Learning Unsafe? and Shadow defense, we add ChestXRay as a sensitive medical domain. Leakage is reported as LPIPS, PSNR, SSIM, and image identifiability precision, broken out by client speed decile. Utility is reported as test accuracy (F1 for ChestXRay) against wall-clock time, at matched privacy budgets. For calibration, the generator-prior attack's reported ImageNet 64×64 reconstruction PSNR is 15.58 dB, against 13.78 dB for pixel attacks.

Four checks decide the outcome. First, does reconstruction quality rise monotonically with client slowness under asynchronous and time-budgeted training, but stay flat under synchronous training? If not, the core empirical claim fails. Second, under the cohort floor, does the slowest decile's leakage fall to the level of the synchronous median? Third, how much wall-clock time does the floor cost relative to fully asynchronous training, and how does that cost scale with $m$ and with tail heaviness? Fourth, does reordering shrinking before clipping make any measurable difference to accuracy? If it does not, the accounting-safe ordering costs nothing and should be adopted by default.