The Missing Sampler: distributed privacy accounting for asynchronous federated learning

The setting

Differentially private federated learning bounds what a trained model can reveal about any single client. In the distributed DP model, each client adds a share of discrete Gaussian noise to its clipped update, and secure aggregation guarantees the server only ever observes the noised sum — central-DP-level utility without central-DP-level trust. The resulting guarantee is reported as one system-wide (ε, δ) bound, computed under a quiet assumption: every client participates with the same probability in every aggregation.

Buffered asynchronous FL — the throughput-friendly design real deployments actually use — breaks exactly that assumption. The server closes each aggregation with the first K responses to arrive. Whoever is fastest gets in; whoever is slow rarely does.

The problem: under- and over-privatisation

Participation rates under latency-biased buffering are heavy-tailed: the fastest clients appear in orders of magnitude more aggregations than the slowest. But the noise each client commits is calibrated to the average participation rate, fixed before training. So fast clients spend privacy far beyond the reported budget — in our simulations, accumulating up to 97× the reported privacy loss — while slow clients contribute noise for budget they never spend.

The natural repair — track privacy loss per client and retire clients approaching their budget — cannot be left to the server: a malicious server could under-report fast clients' counts, keep them past their budget, or pick the aggregated subset adversarially. Clients cannot self-report either. The accounting has to live with a party that is neither.

The fix: a privatiser committee

Modern one-shot secure aggregation protocols already maintain a small persistent committee of nodes. We repurpose those nodes as privatisers. They observe only aggregate metadata, and they do four things the server must not be trusted to do:

• maintain per-client Gaussian-DP ledgers of actual — not assumed — participation;
• enforce retirement through a safety cap, so any spending policy provably keeps every client at ε_i ≤ ε_target;
• inject the distributed noise, chosen after the buffer is observed, so it matches real participation;
• threshold-decrypt only authorised aggregates — no budget-compliant subset, no decryption.

The same committee supplies the protocol's missing piece — the sampler. Using a public randomness beacon, it draws a uniformly random k′-of-K subset from each latency-biased buffer. From the privacy adversary's view, every buffered client now appears in the released aggregate with probability exactly k′/K, independent of identity or latency — which restores, for the first time in asynchronous DP-FL, rigorous privacy amplification by subsampling, with the buffer size as a wall-clock-versus-noise deployment knob.

Results

On CIFAR-10, AG News, and DBpedia, committee subsampling recovers up to +38 percentage points of accuracy at matched privacy budget — most of the utility DP noise had taken. The per-client ledger is not optional: even under the strongest amplification setting, standard accounting still violates the target budget by at least 1.4×. A parameter-space canary audit confirms the framework removes the disparate vulnerability that latency-biased participation induces.

Why it matters

Asynchrony is what you reach for the moment devices are heterogeneous and the slowest client cannot set the pace — that is most real deployments. If the reported ε is wrong in exactly that regime, deployed systems are making a promise they do not keep, and making it unevenly across their users. A guarantee that only holds under an idealised schedule is not a guarantee; it is a modelling assumption wearing one.