Source-linked AI summary
Papaya: Practical, Private, and Scalable Federated Learning
Dzmitry Huba, John Nguyen, Kshitiz Malik, Ruiyu Zhu, Mike Rabbat, Ashkan Yousefpour, Carole-Jean Wu, Hongyuan Zhan, Pavel Ustinov, Harish Srinivas, Kaikai Wang, Anthony Shoumikhin, Jesik Min, Mani Malek
TL;DR
Synchronous federated learning struggles with heterogeneous devices, stragglers, and diminishing returns from higher concurrency. PAPAYA presents a production asynchronous system with buffered aggregation and secure infrastructure, achieving substantially faster and more communication-efficient training at scale. The paper also reports improved fairness relative to synchronous over-selection, while trusted-hardware aggregation introduces a performance cost.
Problem
Heterogeneity and larger synchronous cohorts create stragglers and diminishing scalability, limiting federated learning across massive client populations.
Method
PAPAYA implements buffered asynchronous FL with FedBuff, incremental asynchronous secure aggregation, and configurable aggregation goals for production-scale training.
Results
5× faster and 8× more communication-efficient than SyncFL, AsyncFL reached target test loss faster in high-concurrency training.
Takeaways & Limitations
AsyncFL scales better than SyncFL and avoids the model bias introduced by discarding slow-client updates through over-selection.
Takeaways & Limitations
Trusted-hardware secure aggregation trades performance for security guarantees, with host-TEE transfer time increasing with aggregation goal.
Abstract
from arXiv · showhide
Cross-device Federated Learning (FL) is a distributed learning paradigm with several challenges that differentiate it from traditional distributed learning, variability in the system characteristics on each device, and millions of clients coordinating with a central server being primary ones. Most FL systems described in the literature are synchronous - they perform a synchronized aggregation of model updates from individual clients. Scaling synchronous FL is challenging since increasing the number of clients training in parallel leads to diminishing returns in training speed, analogous to large-batch training. Moreover, stragglers hinder synchronous FL training. In this work, we outline a production asynchronous FL system design. Our work tackles the aforementioned issues, sketches of some of the system design challenges and their solutions, and touches upon principles that emerged from building a production FL system for millions of clients. Empirically, we demonstrate that asynchronous FL converges faster than synchronous FL when training across nearly one hundred million devices. In particular, in high concurrency settings, asynchronous FL is 5x faster and has nearly 8x less communication overhead than synchronous FL.
1 INTRODUCTION
Cross-device FL keeps raw data on client devices but faces heterogeneity, stragglers, and poor scaling under synchronous aggregation. PAPAYA addresses these challenges with asynchronous training and reports faster, more communication-efficient, and fairer models.
- Cross-device FL trains models across large client populations while keeping raw training data on devices.
- SyncFL aggregates client updates in rounds, so heterogeneous devices create stragglers that prolong training and reduce utilization.
- Increasing synchronous concurrency resembles large-batch training and yields diminishing reductions in wall-clock training time.
- AsyncFL aggregates updates as they arrive, decoupling client training from server updates and keeping utilization essentially at 100%.It must nevertheless handle stale updates based on older server models.
- 5× faster and 8× more communication-efficient than SyncFL, AsyncFL reached target test loss faster across millions of devices.The comparison uses wall-clock time and communication efficiency.
- 53% higher test perplexity for clients in the 99th percentile occurred with SyncFL over-selection, while AsyncFL did not introduce this bias.
2 UNDERSTANDING THE LANDSCAPE OF FEDERATED LEARNING AT-SCALE
The paper examines production-scale heterogeneity and the scaling limits of synchronous FL. Its evidence shows that stragglers inflate round times, while higher concurrency eventually trades modest speed gains for sharply greater communication costs.
- SyncFL training-time speedup plateaus as concurrency increases, limiting the benefit of larger cohorts.
- Mobile-device compute capabilities differ by an order of magnitude, and training-data volume varies widely across users.Together, these differences produce large variations in client training time.
- 21× larger average round completion time than mean client training time occurs in SyncFL with concurrency and aggregation goal set to 1000.
- Over-selection mitigates SyncFL stragglers but causes sampling bias that produces models unfair to slow-responding clients.
- 73% higher communication costs accompany only a 17% reduction in overall training time when concurrency doubles from 1300 to 2600.
3 PROPOSED DESIGN
PAPAYA implements buffered asynchronous FL with client-independent participation, incremental secure aggregation, continuous replacement, and fast model aggregation. The design targets high utilization and scalable production deployment while managing stale updates.
- FedBuff removes rounds by letting clients download, train, and upload updates asynchronously.The server updates its model after receiving the configured aggregation goal of client updates.
- FedBuff weights each update by the client’s training examples and a factor determined by update staleness.Staleness is the difference between the client’s starting model version and the server version at upload.
- AsyncFL is faster and more resource efficient than SyncFL in large-scale production settings with system and data heterogeneity.The system nevertheless requires careful design because asynchronous training introduces distinct challenges.
- Client selection avoids inter-client dependencies, while client replacement maintains close to 100% utilization after clients finish or fail.
- PAPAYA introduces incremental asynchronous secure aggregation using a Trusted Execution Environment.The protocol lets clients communicate updates securely without waiting for other clients to perform aggregation.
- AsyncFL generates up to 30× more server model updates per unit time than SyncFL.PAPAYA therefore designs for substantially higher model-aggregation throughput.
4 SYSTEM COMPONENTS
PAPAYA uses a server architecture with centralized coordination, client-facing selection, and task-specific aggregation components. Its design supports both synchronous and asynchronous FL, with component interactions adapted for scalability and straggler resilience.
- PAPAYA’s server has Coordinator, Selector, and Aggregator components, while clients run a separate runtime on end-user devices.Selectors and Aggregators can scale elastically with workload, whereas the Coordinator is centralized.
- PAPAYA differs from the Google FL stack by supporting both synchronous and asynchronous training, enabling faster convergence and straggler resilience.
- The Coordinator assigns tasks and clients, coordinates progress, and handles Aggregator failures.
- The Selector communicates directly with clients, advertises available tasks, reports client availability, and routes requests to Aggregators.
- Each task is assigned to one Aggregator, which aggregates client updates, drives client execution, and tracks whether more clients are needed.
5 SECURE AGGREGATION
PAPAYA’s asynchronous secure aggregation uses a trusted execution environment and attestation to protect client updates without requiring synchronous cohorts. It reduces host–TEE communication by sending compact random seeds while supporting incremental aggregation.
- Existing SMPC-based secure aggregation hinders asynchronous training because it requires cohort formation and inter-client communication in each round.
- Naive TEE aggregation is unscalable because host–TEE transfer grows with aggregation goal and model size.For 100 clients with 20MB models, transfer takes nearly 650 milliseconds.
- PAPAYA’s Asynchronous SecAgg uses a TEE and attestation to ensure the Trusted Secure Aggregator has not been tampered with.Client updates are protected with additive one-time-pad masking and secure virtual channels established through Diffie–Hellman key exchange.
- Asynchronous SecAgg lets clients send masked updates to an Aggregator while sending the masking seed to the TSA for incremental secure aggregation.
- O(K + m) data crosses the TSA boundary because each client sends a usually 16-byte seed that generates a model-sized mask.This replaces the O(K · m) transfer of the alternative approach.
6 SYSTEM DESIGN
PAPAYA’s system design supports asynchronous client training through client independence, rapid replacement, and fast aggregation. It maintains high utilization and handles the higher server-update frequency produced by AsyncFL.
- 6 SYSTEM DESIGN: AsyncFL requires client independence, fast client replacement, and fast model aggregation to support asynchronous training and higher utilization.
- 6.1 Client Protocol: PAPAYA’s client protocol uses selection and participation phases without inter-client dependencies, and virtual sessions prevent transient failures from causing dropout.
- 6.2 High Client Utilization: AsyncFL keeps utilization close to 100% because completed or failed clients are replaced immediately rather than waiting for a cohort round.
- 6.2 High Client Utilization: Client assignment tracks task demand and eligibility, then randomly assigns each available client to an eligible task.
- 6.3 Fast Model Aggregation: 30× more server model updates per hour are generated by AsyncFL than SyncFL at a concurrency of 2,300, motivating fast aggregation.
- 6.3 Fast Model Aggregation: PAPAYA uses persistent Aggregators, in-memory queues, and parallel aggregation across available cores to process frequent model updates efficiently.
7 EVALUATION
The evaluation compares AsyncFL with SyncFL across convergence speed, scalability, communication efficiency, straggler handling, and sampling bias. AsyncFL scales better, avoids over-selection bias, and achieves faster training with appropriate aggregation goals.
- Convergence and scalability: 5× faster speedup is achieved by AsyncFL over SyncFL at high concurrency, while the speedup gap widens from 2× to 5× as concurrency increases.The comparison measures wall-clock time to reach a target loss.
- Experimental setup: AsyncFL is evaluated against SyncFL on a language-model task using nearly 100 million Android phones.Experiments use matched client populations and repeated runs.
- Server-model step frequency: Increasing K from 100 to 1300 increases the batch size and slows convergence because the server performs model updates less frequently.Moderate K values can improve stability, while server write bandwidth limits update frequency.
- Sampling bias from over-selection: AsyncFL matches the ground-truth client distribution with D-statistic 8.8 × 10^-4, whereas SyncFL with over-selection has D-statistic 6.6 × 10^-2.The corresponding p-values are 0.98 and 0.0, respectively, indicating sampling bias from over-selection.
- Sampling bias from over-selection: AsyncFL combines fast training, high model quality, and no sampling bias, while SyncFL without over-selection is 10× slower.Over-selection causes a 6% overall model-quality drop and a 50% drop for clients with more examples.
- Understanding AsyncFL advantages: AsyncFL with K = 100 is 4.3× faster than SyncFL with over-selection at concurrency 1,300.About half of this speedup comes from smaller K and the rest from avoiding sampling bias.
8 RELATED WORK
PAPAYA is compared with production FL systems and software toolkits at similar or different scales. Its distinguishing system-level feature is support for both synchronous and asynchronous training with asynchronous secure aggregation.
- Production FL systems: GFL and AFL implement only SyncFL, whereas PAPAYA implements both SyncFL and AsyncFL.PAPAYA supports incremental client progress rather than requiring fixed synchronous rounds.
- Secure aggregation: PAPAYA uses asynchronous secure aggregation based on TEEs, while GFL uses SMPC-based synchronous secure aggregation and AFL does not report using secure aggregation.The comparison highlights differences in privacy mechanisms as well as aggregation mode.
- FL software toolkits: Clara, IBM-FL, OpenFL, and FATE are software toolkits distinct from production FL systems training across hundreds of millions of devices.The paper focuses on production-scale FL rather than general-purpose toolkit offerings.
9 CONCLUSIONS
PAPAYA presents a production asynchronous FL system that supports both synchronous and asynchronous training at scale. AsyncFL is reported as faster, more straggler resilient, and higher quality than SyncFL in high-concurrency settings.
- Conclusion: PAPAYA supports both synchronous and asynchronous federated learning in a production system designed for training at scale.The system is presented as a production asynchronous FL design with flexible support for both modes.
- Conclusion: 5× faster speedup and nearly 8× more resource conservation are achieved by asynchronous FL than synchronous FL in high-concurrency settings.The conclusion summarizes the paper’s empirical comparison of the two approaches.
SUPPLEMENTARY MATERIAL
The supplementary material describes cryptographic building blocks and a TEE-assisted asynchronous secure-aggregation protocol. The design masks client inputs while allowing the server to recover their aggregate under client availability constraints.
- Additive one-time pad: A PRNG-generated additive one-time pad avoids ciphertext expansion, while decryption complexity grows linearly with the number of additions.The protocol trades server-side decryption workload for compact ciphertexts suitable for mobile-device settings.
- Additive one-time pad: Additive one-time pads can operate over a finite Abelian group, allowing ciphertexts to occupy the same space as plaintexts.The scheme is presented as more efficient for mobile computation and bandwidth than larger-group alternatives.
- Protocol design: The secure-aggregation protocol uses trusted hardware to assist with dropped clients and reduce interdependence among clients.Clients can check in at different times and may have non-overlapping availability windows.
- Ideal functionality: The ideal functionality accepts private client vectors and reveals only their position-to-position aggregate across at least t clients.The server has no private input, and individual client inputs remain private.
- Protocol design: Clients send masked inputs to the untrusted server and demasking information to the trusted party, which instructs the server how to recover the aggregate.The server aggregates masked inputs while the trusted party aggregates masks.
B.4 Security Proof
The security proof uses simulation and hybrid experiments to show that the real protocol execution is computationally indistinguishable from the ideal functionality. The proof establishes correctness while replacing honest-client inputs and protocol views with simulated values.
- Simulation strategy: The proof constructs a simulator whose joint view is computationally indistinguishable from a real-world execution with honest clients.The simulator’s detailed construction is provided in Figure 18.
- Hybrid experiments: Hybrid0 models the real protocol, with the simulator playing honest clients using their private inputs while the adversary controls the server and corrupted clients.This hybrid is exactly the real-world protocol execution.
- Hybrid experiments: Hybrid1 replaces honest-client masked inputs with independently uniform random vectors while preserving the server’s recovered sum over corrupted and selected clients.Correctness follows because the server receives the same aggregate, and indistinguishability follows from uniform distributions over G^ℓ.
- Hybrid experiments: Hybrid2 runs the ideal functionality with real honest clients and uses its honest-input sum to construct the trusted party’s real-world message.The simulator’s outputs match the adversary’s outputs for the corresponding roles.
- Conclusion: The protocol’s real and ideal executions are computationally indistinguishable because the simulator preserves the adversary’s view across the hybrid transitions.The argument relies on the ideal functionality correctly summing honest clients’ inputs and matching role outputs.
C.2 Updating the Trusted Binary with Verifiable Logs
Verifiable logs address the update rigidity of hardcoded remote attestations by recording trusted-binary changes in an append-only, auditable structure. This lets clients and auditors verify binary history while allowing regular updates without simultaneous client updates.
- Motivation: Hardcoded remote-attestation hashes make updating the trusted binary impossible without updating clients, motivating verifiable logs.The logs record code changes for later verification.
- Log construction: A verifiable log uses an append-only Merkle tree whose root snapshots support inclusion proofs and consistency checks between log versions.These mechanisms let observers verify that records belong to the log and that snapshots remain consistent.
- Verification workflow: The server must provide an inclusion proof showing that the trusted binary used by the protocol appears in the latest log snapshot.Clients and auditors request the latest snapshot through the same API.
- Verification workflow: Logged trusted binaries cannot avoid auditing without being detected, while clients proceed only when the binary is present in the log.The argument relies on the unforgeability of the underlying secure hashes.
- Practical consequence: With sufficient public auditing, the trusted binary can be updated regularly without requiring simultaneous client-side updates.This is the practical consequence of replacing a fixed hardcoded identity check with an auditable history.
E.5 Edge Training Engine
The Papaya client combines a hosting platform with a general machine-learning framework for configurable on-device training. It separates data policy, training execution, and mobile deployment concerns.
- Client architecture: The Papaya client provides persistent data management and a general executor that supports swapping data sources, models, losses, and other ML-task components.The Example Store enforces data-use and retention policies, while the Executor abstracts model-training logic.
- Mobile implementation: The implementation uses PyTorch Mobile features including selective build and the mobile interpreter.Selective build compiles only the operators used by the client.