Turbo-Aggregate: Breaking the Quadratic Aggregation Barrier in Secure Federated Learning
Abstract
Federated learning is a distributed framework for training machine learning models over the data residing at mobile devices, while protecting the privacy of individual users. A major bottleneck in scaling federated learning to a large number of users is the overhead of secure model aggregation across many users. In particular, the overhead of the state-of-the-art protocols for secure model aggregation grows quadratically with the number of users. In this article, we propose the first secure aggregation framework, named Turbo-Aggregate, that in a network with N users achieves a secure aggregation overhead of O(NlogN), as opposed to O(N2), while tolerating up to a user dropout rate of 50%. Turbo-Aggregate employs a multi-group circular strategy for efficient model aggregation, and leverages additive secret sharing and novel coding techniques for injecting aggregation redundancy in order to handle user dropouts while guaranteeing user privacy. We experimentally demonstrate that Turbo-Aggregate achieves a total running time that grows almost linear in the number of users, and provides up to 40× speedup over the state-of-the-art protocols with up to N=200 users. Our experiments also demonstrate the impact of model size and bandwidth on the performance of Turbo-Aggregate.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Turbo-Aggregate's total running time is multiple times faster than the benchmarks, up to 40 times as reported by the experiments.
“the total running time is multiple times faster than the benchmarks (i.e., up to 40 times reported by the experiments).”
From Federated learning for smart healthcare: A survey (2023) · cites this paper as [58]
Turbo-Aggregate tolerates up to 50% dropping-out rate.
“up to 50% dropping-out rate can be tolerated by Turbo-Aggregate”
From Federated learning for smart healthcare: A survey (2023) · cites this paper as [58]
Turbo-Aggregate reduces aggregation overhead from O(N^2) to O(N log N), where N is the number of IoMT devices joining the FL process.
“the aggregation overhead is significantly reduced from O( 𝑁 2 ) to O( 𝑁 log ( 𝑁 )) with 𝑁 being the number of IoMT devices joining int the FL process”
From Federated learning for smart healthcare: A survey (2023) · cites this paper as [58]
Cites
New directions in cryptography
Diffie, W., & Hellman, M. (1976) · IEEE Transactions on Information Theory · doi:10.1109/tit.1976.1055638 · Cited by 14,713 · see citing works
Communication-Efficient Learning of Deep Networks from Decentralized Data
McMahan, H. B., Moore, E., Ramage, D., Hampson, S., & Arcas, B. A. Y. (2016) · arXiv · doi:10.48550/arxiv.1602.05629 · Cited by 14,215 · see citing works
Elements of Information Theory
Cover, T. M., & Thomas, J. A. (2005) · doi:10.1002/047174882x · Cited by 13,791 · see citing works
Shamir, A. (1979) · Communications of the ACM · doi:10.1145/359168.359176 · Cited by 13,756 · see citing works
Calibrating Noise to Sensitivity in Private Data Analysis
Dwork, C., McSherry, F., Nissim, K., & Smith, A. (2006) · Lecture Notes in Computer Science · doi:10.1007/11681878_14 · Cited by 7,272 · see citing works
Probability Inequalities for sums of Bounded Random Variables
Hoeffding, W. (1994) · Springer series in statistics · doi:10.1007/978-1-4612-0865-5_26 · Cited by 6,683 · see citing works
Federated learning: Challenges, methods, and future directions
Li, T., Sahu, A. K., Talwalkar, A., & Smith, V. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.2975749 · Cited by 6,210 · see citing works
Probability Inequalities for Sums of Bounded Random Variables
Hoeffding, W. (1963) · Journal of the American Statistical Association · doi:10.1080/01621459.1963.10500830 · Cited by 4,869 · see citing works
Practical Secure Aggregation for Privacy-Preserving Machine Learning
Bonawitz, K., Ivanov, V., Kreuter, B., Marcedone, A., McMahan, H. B., Patel, S., Ramage, D., Segal, A., & Seth, K. (2017) · Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3133956.3133982 · Cited by 3,956 · see citing works
Federated Learning: Strategies for Improving Communication Efficiency
Konečný, J., McMahan, H. B., Yu, F. X., Richtárik, P., Suresh, A. T., & Bacon, D. (2016) · arXiv · doi:10.48550/arxiv.1610.05492 · Cited by 3,766 · see citing works
Protocols for secure computations
Yao, A. C. (1982) · 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982) · doi:10.1109/sfcs.1982.38 · Cited by 3,306 · see citing works
Protocols for secure computations
Yao, A. C.-C. (1982) · 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982) · doi:10.1109/sfcs.1982.88 · Cited by 2,693 · see citing works
Completeness theorems for non-cryptographic fault-tolerant distributed computation
Ben-Or, M., & Wigderson, A. (1988) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/62212.62213 · Cited by 2,529 · see citing works
Federated Learning With Differential Privacy: Algorithms and Performance Analysis
Wei, K., Li, J., Ding, M., Ma, C., Yang, H. H., Farokhi, F., Jin, S., Quek, T. Q. S., & Vincent Poor, H. (2020) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2020.2988575 · Cited by 2,400 · see citing works
A fully homomorphic encryption scheme
Boneh, D., & Gentry, C. (2009) · Cited by 2,359 · see citing works
Zhu, L., & Han, S. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-63076-8_2 · Cited by 1,906 · see citing works
On the Convergence of FedAvg on Non-IID Data
Li, X., Huang, K., Yang, W., Wang, S., & Zhang, Z. (2019) · arXiv · doi:10.48550/arxiv.1907.02189 · Cited by 1,575 · see citing works
Multiparty Computation from Somewhat Homomorphic Encryption
Damgård, I., Pastro, V., Smart, N., & Zakarias, S. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-32009-5_38 · Cited by 1,331 · see citing works
Differentially Private Federated Learning: A Client Level Perspective
Geyer, R. C., Klein, T., & Nabi, M. (2017) · arXiv · doi:10.48550/arxiv.1712.07557 · Cited by 1,052 · see citing works
Beyond Inferring Class Representatives: User-Level Privacy Leakage From Federated Learning
Wang, Z., Song, M., Zhang, Z., Song, Y., Wang, Q., & Qi, H. (2019) · IEEE INFOCOM 2019 - IEEE Conference on Computer Communications · doi:10.1109/infocom.2019.8737416 · Cited by 881 · see citing works
Learning Differentially Private Recurrent Language Models
McMahan, H. B., Ramage, D., Talwar, K., & Zhang, L. (2017) · arXiv · doi:10.48550/arxiv.1710.06963 · Cited by 849 · see citing works
Lian, X., Zhang, C., Zhang, H., Hsieh, C., Zhang, W., & Liu, J. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1705.09056 · Cited by 843 · see citing works
Inverting Gradients -- How easy is it to break privacy in federated learning?Preprint
Geiping, J., Bauermeister, H., Dröge, H., & Moeller, M. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2003.14053 · Cited by 749 · see citing works
Analyzing Federated Learning through an Adversarial Lens
Bhagoji, A. N., Chakraborty, S., Mittal, P., & Calo, S. (2018) · arXiv · doi:10.48550/arxiv.1811.12470 · Cited by 703 · see citing works
Secret-Sharing Schemes: A Survey
Beimel, A. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-20901-7_2 · Cited by 680 · see citing works
Agnostic Federated LearningPreprint
Mohri, M., Sivek, G., & Suresh, A. T. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1902.00146 · Cited by 619 · see citing works
Differentially private aggregation of distributed time-series with transformation and encryption
Rastogi, V., & Nath, S. (2010) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/1807167.1807247 · Cited by 536 · see citing works
FedML: A Research Library and Benchmark for Federated Machine LearningPreprint
He, C., Li, S., So, J., Zeng, X., Zhang, M., Wang, H., Wang, X., Vepakomma, P., Singh, A., Qiu, H., et al. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2007.13518 · Cited by 504 · see citing works
Self-citationFair Resource Allocation in Federated Learning
Li, T., Sanjabi, M., Beirami, A., & Smith, V. (2019) · arXiv · doi:10.48550/arxiv.1905.10497 · Cited by 475 · see citing works
Practical Secure Aggregation for Federated Learning on User-Held DataPreprint
Bonawitz, K., Ivanov, V., Kreuter, B., Marcedone, A., McMahan, H. B., Patel, S., Ramage, D., Segal, A., & Seth, K. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1611.04482 · Cited by 468 · see citing works
Dalcín, L., Paz, R. R., & Storti, M. A. (2005) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2005.03.010 · Cited by 418 · see citing works
I Have a DREAM! (DiffeRentially privatE smArt Metering)
Ács, G., & Castelluccia, C. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-24178-9_9 · Cited by 388 · see citing works
Can You Really Backdoor Federated Learning?
Sun, Z., Kairouz, P., Suresh, A. T., & McMahan, H. B. (2019) · arXiv · doi:10.48550/arxiv.1911.07963 · Cited by 348 · see citing works
A Pragmatic Introduction to Secure Multi-Party Computation
Evans, D., Kolesnikov, V., & Rosulek, M. (2018) · Foundations and Trends® in Privacy and Security · doi:10.1561/3300000019 · Cited by 334 · see citing works
Lagrange Coded Computing: Optimal Design for Resiliency, Security and PrivacyPreprint
Yu, Q., Li, S., Raviv, N., Kalan, S. M. M., Soltanolkotabi, M., & Avestimehr, S. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1806.00939 · Cited by 325 · see citing works
Byzantine-Resilient Secure Federated Learning
So, J., Guler, B., & Avestimehr, A. S. (2021) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2020.3041404 · Cited by 313 · see citing works
Self-citationScalable Bias-Resistant Distributed Randomness
Syta, E., Jovanovic, P., Kogias, E. K., Gailly, N., Gasser, L., Khoffi, I., Fischer, M. J., & Ford, B. (2017) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.2017.45 · Cited by 300 · see citing works
(2010) · Cited by 291 · see citing works
On the Convergence of FedAvg on Non-IID Data
Li, X., Huang, K., Yang, W., Wang, S., & Zhang, Z. (2020) · International Conference on Learning Representations · Cited by 275 · see citing works
Perfectly-Secure MPC with Linear Communication Complexity
Beerliová-Trubíniová, Z., & Hirt, M. (2008) · Springer eBooks · doi:10.1007/978-3-540-78524-8_13 · Cited by 220 · see citing works
Fast Polynomial Factorization and Modular Composition
Kedlaya, K. S., & Umans, C. (2011) · SIAM Journal on Computing · doi:10.1137/08073408x · Cited by 218 · see citing works
Analyzing Federated Learning through an Adversarial Lens
Bhagoji, A. N., Chakraborty, S., Mittal, P., & Calo, S. B. (2019) · International Conference on Machine Learning · Cited by 188 · see citing works
Secure Computation on the Web: Computing without Simultaneous Interaction
Halevi, S., Lindell, Y., & Benny Pinkas, B. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-22792-9_8 · Cited by 149 · see citing works
Peer-to-peer Federated Learning on Graphs
Lalitha, A., Kilinc, O. C., Javidi, T., & Koushanfar, F. (2019) · arXiv · doi:10.48550/arxiv.1901.11173 · Cited by 146 · see citing works
LAGRANGE CODED COMPUTING: OPTIMAL DESIGN FOR RESILIENCY, SECURITY, AND PRIVACY
Avestimehr, S., Kalan, M. M., Raviv, N., Soltanolkotabi, M., Li, S., & Yu, Q. (2019) · International Conference on Artificial Intelligence and Statistics · Cited by 130 · see citing works
CodedPrivateML: A Fast and Privacy-Preserving Framework for Distributed Machine Learning
So, J., Güler, B., & Avestimehr, A. S. (2021) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2021.3053220 · Cited by 126 · see citing works
Self-citationFair Resource Allocation in Federated Learning
Li, T., Sanjabi, M., Beirami, A., & Smith, V. (2020) · International Conference on Learning Representations · Cited by 120 · see citing works
Pipe-SGD: A Decentralized Pipelined SGD Framework for Distributed Deep Net TrainingPreprint
Li, Y., Yu, M.-C., Li, S.-Z., Avestimehr, A., Kim, N., & Schwing, A. (2018) · Neural Information Processing Systems · doi:10.48550/arxiv.1811.03619 · Cited by 112 · see citing works
Self-citationCOLA: Decentralized Linear LearningPreprint
He, L., Bian, A., & Jaggi, M. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1808.04883 · Cited by 94 · see citing works
Federated Learning with Autotuned Communication-Efficient Secure Aggregation
Bonawitz, K., Salehi, F., Konečný, J., McMahan, H. B., & Gruteser, M. (2019) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/ieeeconf44664.2019.9049066 · Cited by 83 · see citing works
Semi-Cyclic Stochastic Gradient Descent
Eichner, H., Koren, T., McMahan, H. B., Srebro, N., & Talwar, K. (2019) · arXiv · doi:10.48550/arxiv.1904.10120 · Cited by 66 · see citing works
Central Server Free Federated Learning over Single-sided Trust Social Networks
He, C., Tan, C., Tang, H., Qiu, S., & Liu, J. (2019) · arXiv · doi:10.48550/arxiv.1910.04956 · Cited by 60 · see citing works
Private and Dynamic Time-Series Data Aggregation with Trust Relaxation
Leontiadis, I., Elkhiyaoui, K., & Molva, R. A. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-12280-9_20 · Cited by 49 · see citing works
Edge-Assisted Hierarchical Federated Learning with Non-IID DataPreprint
Liu, L., Zhang, J., Song, S., & Letaief, K. B. (2019) · arXiv (Cornell University) · Cited by 47 · see citing works
A Scalable Approach for Privacy-Preserving Collaborative Machine LearningPreprint
So, J., Güler, B., & Avestimehr, S. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2011.01963 · Cited by 29 · see citing works
Self-citationGroup Knowledge Transfer: Collaborative Training of Large CNNs on the Edge.Preprint
He, C., Annavaram, M., & Avestimehr, S. (2020) · arXiv (Cornell University) · Cited by 18 · see citing works
Applied Federated Learning: Improving Google Keyboard Query Suggestions
Yang, T., Andrew, G., Eichner, H., Sun, H., Li, W., Kong, N., Ramage, D., & Beaufays, F. (2018) · arXiv · doi:10.48550/arxiv.1812.02903
Flagged first, then by citations
Cited by
Sorted by citations
Federated learning for smart healthcare: A survey
Nguyen, D. C., Pham, Q.-V., Pathirana, P. N., Ding, M., Seneviratne, A., Lin, Z., Dobre, O., & Hwang, W.-J. (2023) · ACM Computing Surveys · doi:10.1145/3501296 · Cited by 827 · see citing works
Federated Learning: A Survey on Enabling Technologies, Protocols, and Applications
Aledhari, M., Razzak, R., Parizi, R. M., & Saeed, F. (2020) · IEEE Access · doi:10.1109/access.2020.3013541 · Cited by 733 · see citing works
Biscotti: A blockchain system for private and secure federated learning
Shayan, M., Fung, C., Yoon, C. J. M., & Beschastnikh, I. (2021) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2020.3044223 · Cited by 354 · see citing works
Byzantine-Resilient Secure Federated Learning
So, J., Guler, B., & Avestimehr, A. S. (2021) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2020.3041404 · Cited by 313 · see citing works
Self-citationFederated learning for secure IoMT-applications in smart healthcare systems: A comprehensive review
Rani, S., Kataria, A., Kumar, S., & Tiwari, P. (2023) · Knowledge-Based Systems · doi:10.1016/j.knosys.2023.110658 · Cited by 228 · see citing works
EPPDA: An Efficient Privacy-Preserving Data Aggregation Federated Learning Scheme
Song, J., Wang, W., Gadekallu, T. R., Cao, J., & Liu, Y. (2023) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2022.3153519 · Cited by 150 · see citing works
Reviewing Federated Machine Learning and Its Use in Diseases Prediction
Moshawrab, M., Adda, M., Bouzouane, A., Ibrahim, H., & Raad, A. (2023) · Sensors · doi:10.3390/s23042112 · Cited by 114 · see citing works
Novikova, E., Fomichov, D., Kholod, I., & Filippov, E. (2022) · Sensors · doi:10.3390/s22082983 · Cited by 24 · see citing works
- Authors
- So, J., Guler, B., & Avestimehr, A. S.
- Affiliations
- University of Southern California (US)
- Venue
- IEEE Journal on Selected Areas in Information Theory
- Published
- 2021-03
- Volume
- 2
- Issue
- 1
- Pages
- 479-489
- ISSN
- 2641-8770 (ISSN-L)
- OpenAlex
- W3013310637
- Cited by
- 318
- References
- 57
- Citations by year
- 2026: 46 · 2025: 57 · 2024: 61 · 2023: 65 · 2022: 54 · 2021: 26 · 2020: 9
- FWCI
- 18.13
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- Locations
- IEEE Journal on Selected Areas in Information Theory (publishedVersion)
- Funders
- Defense Advanced Research Projects Agency (HR001117C0053)
- Army Research Office (W911NF1810400)
- NSF (CCF-1703575, CCF-1763673)
- Office of Naval Research (N00014-16-1-2189)
- Intel
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
- Physical Sciences › Computer Science › Artificial Intelligence › Cryptography and Data Security
- Physical Sciences › Computer Science › Information Systems › Cloud Data Security Solutions
- Keywords
- federated learning, additive secret sharing, privacy-preserving data aggregation
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
