{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T10:58:17Z","timestamp":1778065097915,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":48,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"BSF-NSF Grant","award":["2020643"],"award-info":[{"award-number":["2020643"]}]},{"name":"ISF Grant","award":["1774\\\/20"],"award-info":[{"award-number":["1774\\\/20"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649736","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"411-422","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Optimal Load-Balanced Scalable Distributed Agreement"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0405-9651","authenticated-orcid":false,"given":"Yuval","family":"Gelles","sequence":"first","affiliation":[{"name":"Hebrew University, Jerusalem, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1647-2112","authenticated-orcid":false,"given":"Ilan","family":"Komargodski","sequence":"additional","affiliation":[{"name":"Hebrew University, Jerusalem, Israel \/ NTT Research, Sunnyvale, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331629"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Zuzana Beerliov\u00e1-Trub\u00edniov\u00e1 and Martin Hirt. 2008. Perfectly-Secure MPC with Linear Communication Complexity. In Theory of Cryptography TCC. 213\u2013230.","DOI":"10.1007\/978-3-540-78524-8_13"},{"key":"e_1_3_2_1_3_1","volume-title":"Randomness-Efficient Oblivious Sampling. In 35th Annual Symposium on Foundations of Computer Science, FOCS. IEEE Computer Society, 276\u2013287","author":"Bellare Mihir","year":"1994","unstructured":"Mihir Bellare and John Rompel. 1994. Randomness-Efficient Oblivious Sampling. In 35th Annual Symposium on Foundations of Computer Science, FOCS. IEEE Computer Society, 276\u2013287."},{"key":"e_1_3_2_1_4_1","volume-title":"Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC. 1\u201310","author":"Ben-Or Michael","year":"1988","unstructured":"Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. 1988. Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract). In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC. 1\u201310."},{"key":"e_1_3_2_1_5_1","volume-title":"Asynchronous Byzantine Agreement with Subquadratic Communication. In Theory of Cryptography Conference, TCC. 353\u2013380","author":"Blum Erica","year":"2020","unstructured":"Erica Blum, Jonathan Katz, Chen-Da Liu-Zhang, and Julian Loss. 2020. Asynchronous Byzantine Agreement with Subquadratic Communication. In Theory of Cryptography Conference, TCC. 353\u2013380."},{"key":"e_1_3_2_1_6_1","volume-title":"10th International Workshop, WDAG. 40\u201355","author":"Borderding Malte","year":"1996","unstructured":"Malte Borderding. 1996. Levels of Authentication in Distributed Agreement. In Distributed Algorithms, 10th International Workshop, WDAG. 40\u201355."},{"key":"e_1_3_2_1_7_1","volume-title":"Deepesh Data, and Pavel Hub\u00e1cek","author":"Boyle Elette","year":"2018","unstructured":"Elette Boyle, Ran Cohen, Deepesh Data, and Pavel Hub\u00e1cek. 2018. Must the Communication Graph of MPC Protocols be an Expander? In Advances in Cryptology - CRYPTO. 243\u2013272."},{"key":"e_1_3_2_1_8_1","volume-title":"ACM Symposium on Principles of Distributed Computing, PODC. 319\u2013330","author":"Boyle Elette","year":"2021","unstructured":"Elette Boyle, Ran Cohen, and Aarushi Goel. 2021. Breaking the O(\u221a n)-Bit Barrier: Byzantine Agreement with Polylog Bits Per Party. In ACM Symposium on Principles of Distributed Computing, PODC. 319\u2013330."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_21"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2484243"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Ignacio Cascudo Ronald Cramer Chaoping Xing and Chen Yuan. 2018. Amortized Complexity of Information-Theoretically Secure MPC Revisited. In Advances in Cryptology - CRYPTO. 395\u2013426.","DOI":"10.1007\/978-3-319-96878-0_14"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/296806.296824"},{"key":"e_1_3_2_1_13_1","first-page":"1","article-title":"MPC for MPC: Secure Computation on a Massively Parallel Computing Architecture. In 11th Innovations in Theoretical Computer Science Conference","volume":"75","author":"Hubert Chan T.-H.","year":"2020","unstructured":"T.-H. Hubert Chan, Kai-Min Chung, Wei-Kai Lin, and Elaine Shi. 2020. MPC for MPC: Secure Computation on a Massively Parallel Computing Architecture. In 11th Innovations in Theoretical Computer Science Conference, ITCS. 75:1\u201375:52.","journal-title":"ITCS."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48184-2_43"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.02.001"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Koji Chida Daniel Genkin Koki Hamada Dai Ikarashi Ryo Kikuchi Yehuda Lindell and Ariel Nof. 2018. Fast Large-Scale Honest-Majority MPC for Malicious Adversaries. In Advances in Cryptology - CRYPTO. 34\u201364.","DOI":"10.1007\/978-3-319-96878-0_2"},{"key":"e_1_3_2_1_17_1","first-page":"1","article-title":"Not a COINcidence: Sub-Quadratic Asynchronous Byzantine Agreement WHP. In 34th International Symposium on Distributed Computing","volume":"25","author":"Cohen Shir","year":"2020","unstructured":"Shir Cohen, Idit Keidar, and Alexander Spiegelman. 2020. Not a COINcidence: Sub-Quadratic Asynchronous Byzantine Agreement WHP. In 34th International Symposium on Distributed Computing, DISC. 25:1\u201325:17.","journal-title":"DISC."},{"key":"e_1_3_2_1_18_1","volume-title":"Advances in Cryptology -","author":"Damg\u00e5rd Ivan","unstructured":"Ivan Damg\u00e5rd and Yuval Ishai. 2006. Scalable Secure Multiparty Computation. In Advances in Cryptology - CRYPTO. Springer, 501\u2013520."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Ivan Damg\u00e5rd Yuval Ishai and Mikkel Kr\u00f8igaard. 2010. Perfectly Secure Multiparty Computation and the Computational Overhead of Cryptography. In Advances in Cryptology - EUROCRYPT. 445\u2013465.","DOI":"10.1007\/978-3-642-13190-5_23"},{"key":"e_1_3_2_1_20_1","volume-title":"Jesper Buus Nielsen, and Adam D. Smith","author":"Damg\u00e5rd Ivan","year":"2008","unstructured":"Ivan Damg\u00e5rd, Yuval Ishai, Mikkel Kr\u00f8igaard, Jesper Buus Nielsen, and Adam D. Smith. 2008. Scalable Multiparty Computation with Nearly Optimal Work and Resilience. In Advances in Cryptology - CRYPTO. 241\u2013261."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Ivan Damg\u00e5rd and Jesper Buus Nielsen. 2007. Scalable and Unconditionally Secure Multiparty Computation. In Advances in Cryptology - CRYPTO. 572\u2013590.","DOI":"10.1007\/978-3-540-74143-5_32"},{"key":"e_1_3_2_1_22_1","volume-title":"8th Student Conference. 64","author":"Dani Varsha","year":"2012","unstructured":"Varsha Dani, Valerie King, Mahnush Movahedi, and Jared Saia. 2012. Breaking the O(mn) Bit Barrier: Secure Multiparty Computation with a Static Adversary. In 8th Student Conference. 64."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-016-0284-9"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212045"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/42282.42283"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217061"},{"key":"e_1_3_2_1_27_1","first-page":"1","article-title":"Scalable Distributed Agreement from LWE","volume":"46","author":"Fernando Rex","year":"2024","unstructured":"Rex Fernando, Yuval Gelles, and Ilan Komargodski. 2024. Scalable Distributed Agreement from LWE: Byzantine Agreement, Broadcast, and Leader Election. In ITCS. 46:1\u201346:23.","journal-title":"Byzantine Agreement, Broadcast, and Leader Election. In ITCS."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01843568"},{"key":"e_1_3_2_1_29_1","first-page":"1","article-title":"Brief Announcement: Scalable Agreement Protocols with Optimal Optimistic Efficiency","volume":"42","author":"Gelles Yuval","year":"2023","unstructured":"Yuval Gelles and Ilan Komargodski. 2023. Brief Announcement: Scalable Agreement Protocols with Optimal Optimistic Efficiency. In DISC. 42:1\u201342:6.","journal-title":"DISC."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Yuval Gelles and Ilan Komargodski. 2023. Optimal Load-Balanced Scalable Distributed Agreement. IACR Cryptol. ePrint Arch. 1139.","DOI":"10.1145\/3618260.3649736"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591861"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132757"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794268765"},{"key":"e_1_3_2_1_34_1","volume-title":"Proceedings of the 19th Annual ACM Symposium on Theory of Computing, STOC. 218\u2013229","author":"Goldreich Oded","year":"1987","unstructured":"Oded Goldreich, Silvio Micali, and Avi Wigderson. 1987. How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, STOC. 218\u2013229."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","unstructured":"Venkatesan Guruswami Christopher Umans and Salil Vadhan. 2009. Unbalanced Expanders and Randomness Extractors from Parvaresh\u2013Vardy Codes. In J. ACM. https:\/\/doi.org\/10.1145\/1538902.1538904 10.1145\/1538902.1538904","DOI":"10.1145\/1538902.1538904"},{"key":"e_1_3_2_1_36_1","volume-title":"Maurer","author":"Hirt Martin","year":"2001","unstructured":"Martin Hirt and Ueli M. Maurer. 2001. Robustness for Free in Unconditional Multi-party Computation. In Advances in Cryptology - CRYPTO. 101\u2013118."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-008-0069-x"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Yuval Ishai Eyal Kushilevitz Manoj Prabhakaran Amit Sahai and Ching-Hua Yu. 2016. Secure Protocol Transformations. In Advances in Cryptology - CRYPTO. 430\u2013458.","DOI":"10.1007\/978-3-662-53008-5_15"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Yuval Ishai Manoj Prabhakaran and Amit Sahai. 2009. Secure Arithmetic Computation with No Honest Majority. In Theory of Cryptography TCC. 294\u2013314.","DOI":"10.1007\/978-3-642-00457-5_18"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Howard J. Karloff Siddharth Suri and Sergei Vassilvitskii. 2010. A Model of Computation for MapReduce. In SODA.","DOI":"10.1137\/1.9781611973075.76"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Valerie King Steven Lonargan Jared Saia and Amitabh Trehan. 2011. Load Balanced Scalable Byzantine Agreement through Quorum Building with Full Information. In Distributed Computing and Networking - ICDCN. 203\u2013214.","DOI":"10.1007\/978-3-642-17679-1_18"},{"key":"e_1_3_2_1_42_1","volume-title":"23rd International Symposium, DISC. 464\u2013478","author":"King Valerie","year":"2009","unstructured":"Valerie King and Jared Saia. 2009. From Almost Everywhere to Everywhere: Byzantine Agreement with ~ O(n^3\/2) Bits. In Distributed Computing, 23rd International Symposium, DISC. 464\u2013478."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989727.1989732"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109667"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/357172.357176"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322188"},{"key":"e_1_3_2_1_47_1","volume-title":"Proceedings of the 21st Annual ACM Symposium on Theory of Computing, STOC. 73\u201385","author":"Rabin Tal","year":"1989","unstructured":"Tal Rabin and Michael Ben-Or. 1989. Verifiable Secret Sharing and Multiparty Protocols with Honest Majority (Extended Abstract). In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, STOC. 73\u201385."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"crossref","unstructured":"David Zuckerman. 1997. Randomness-Optimal Oblivious Sampling. In Random Struct. Algorithms. 345\u2013367.","DOI":"10.1002\/(SICI)1098-2418(199712)11:4<345::AID-RSA4>3.3.CO;2-7"}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","location":"Vancouver BC Canada","acronym":"STOC '24","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649736","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649736","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:52Z","timestamp":1750291432000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649736"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":48,"alternative-id":["10.1145\/3618260.3649736","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649736","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}