{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:17:59Z","timestamp":1750220279815,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":31,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3520078","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"488-501","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Improved communication complexity of fault-tolerant consensus"],"prefix":"10.1145","author":[{"given":"Mohammad T.","family":"Hajiaghayi","sequence":"first","affiliation":[{"name":"University of Maryland, USA"}]},{"given":"Dariusz R.","family":"Kowalski","sequence":"additional","affiliation":[{"name":"Augusta University, USA"}]},{"given":"Jan","family":"Olkowski","sequence":"additional","affiliation":[{"name":"University of Maryland, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"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","first-page":"489","volume":"31","author":"Alistarh D.","unstructured":"D. Alistarh , J. Aspnes , V. King , and J. Saia , Communication-eficient randomized consensus, Distributed Comput. , 31 ( 2018 ), 489 - 501 . D. Alistarh, J. Aspnes, V. King, and J. Saia, Communication-eficient randomized consensus, Distributed Comput., 31 ( 2018 ), 489-501.","journal-title":"Communication-eficient randomized consensus, Distributed Comput."},{"key":"e_1_3_2_1_3_1","first-page":"115","volume-title":"37th International Colloquium, ICALP","author":"Alistarh D.","year":"2010","unstructured":"D. Alistarh , S. Gilbert , R. Guerraoui , M. Zadimoghaddam , How Eficient Can Gossip Be? (On the Cost of Resilient Information Exchange), Automata, Languages and Programming , 37th International Colloquium, ICALP 2010 , 115 - 126 . D. Alistarh, S. Gilbert, R. Guerraoui, M. Zadimoghaddam, How Eficient Can Gossip Be? (On the Cost of Resilient Information Exchange), Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, 115-126."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"S. Amdur S. Weber and V. Hadzilacos On the message complexity of binary agreement under crash failures Distributed Computing 5 ( 1992 ) 175-186.   S. Amdur S. Weber and V. Hadzilacos On the message complexity of binary agreement under crash failures Distributed Computing 5 ( 1992 ) 175-186.","DOI":"10.1007\/BF02277665"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"crossref","unstructured":"J. Aspnes Lower Bounds for Distributed Coin-Flipping and Randomized Consensus J. ACM 45 ( 3 ) ( 1998 ): 415-450.   J. Aspnes Lower Bounds for Distributed Coin-Flipping and Randomized Consensus J. ACM 45 ( 3 ) ( 1998 ): 415-450.","DOI":"10.1145\/278298.278304"},{"key":"e_1_3_2_1_6_1","first-page":"1024","volume":"25","author":"Aspnes J.","unstructured":"J. Aspnes and O. Waarts , Randomized Consensus in Expected (2) Operations Per Processor, SIAM J. Computing 25 ( 5 ) ( 1996 ): 1024 - 1044 . J. Aspnes and O. Waarts, Randomized Consensus in Expected (2) Operations Per Processor, SIAM J. Computing 25 ( 5 ) ( 1996 ): 1024-1044.","journal-title":"Computing"},{"key":"e_1_3_2_1_7_1","first-page":"3885","volume":"39","author":"Attiya H.","unstructured":"H. Attiya and K. Censor-Hillel , Lower Bounds for Randomized Consensus under a Weak Adversary , SIAM J. Comput. 39 ( 8 ) ( 2010 ): 3885 - 3904 . H. Attiya and K. Censor-Hillel, Lower Bounds for Randomized Consensus under a Weak Adversary, SIAM J. Comput. 39 ( 8 ) ( 2010 ): 3885-3904.","journal-title":"J. Comput."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/983102"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/277697.277733"},{"key":"e_1_3_2_1_10_1","first-page":"1262","volume":"72","author":"Chlebus B.S.","unstructured":"B.S. Chlebus , and D.R. Kowalski , Robust gossiping with an application to consensus, Journal of Computer and System Sciences , 72 ( 2006 ) 1262 - 1281 . B.S. Chlebus, and D.R. Kowalski, Robust gossiping with an application to consensus, Journal of Computer and System Sciences, 72 ( 2006 ) 1262-1281.","journal-title":"Robust gossiping with an application to consensus, Journal of Computer and System Sciences"},{"key":"e_1_3_2_1_11_1","first-page":"314","volume-title":"Proceedings of the 21st International Symposium on Distributed Computing (DISC)","author":"Chlebus B.S.","year":"2006","unstructured":"B.S. Chlebus , and D.R. Kowalski , Time and communication eficient consensus for crash failures , in Proceedings of the 21st International Symposium on Distributed Computing (DISC) , 2006 , Springer LNCS 4167 , pp. 314 - 328 . B.S. Chlebus, and D.R. Kowalski, Time and communication eficient consensus for crash failures, in Proceedings of the 21st International Symposium on Distributed Computing (DISC), 2006, Springer LNCS 4167, pp. 314-328."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1583991.1584063"},{"key":"e_1_3_2_1_13_1","first-page":"30","volume-title":"Proceedings of the 34th International Symposium on Distributed Computing (DISC)","author":"Chlebus B.S.","year":"2020","unstructured":"B.S. Chlebus , D.R. Kowalski , and J. Olkowski , Fast agreement in networks with byzantine nodes , in Proceedings of the 34th International Symposium on Distributed Computing (DISC) , 2020 , pp 30 : 1-30 : 18. B.S. Chlebus, D.R. Kowalski, and J. Olkowski, Fast agreement in networks with byzantine nodes, in Proceedings of the 34th International Symposium on Distributed Computing (DISC), 2020, pp 30 : 1-30 : 18."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1582716.1582738"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65956"},{"key":"e_1_3_2_1_16_1","first-page":"191","volume":"32","author":"Dolev D.","unstructured":"D. Dolev , and R. Reischuk , Bounds on information exchange for Byzantine agreement, Journal of the ACM , 32 ( 1985 ) 191 - 204 . D. Dolev, and R. Reischuk, Bounds on information exchange for Byzantine agreement, Journal of the ACM, 32 ( 1985 ) 191-204.","journal-title":"Bounds on information exchange for Byzantine agreement, Journal of the ACM"},{"key":"e_1_3_2_1_17_1","first-page":"1457","volume":"27","author":"Dwork C.","unstructured":"C. Dwork , J. Halpern , and O. Waarts , Performing work eficiently in the presence of faults, SIAM Journal on Computing , 27 ( 1998 ) 1457 - 1491 . C. Dwork, J. Halpern, and O. Waarts, Performing work eficiently in the presence of faults, SIAM Journal on Computing, 27 ( 1998 ) 1457-1491.","journal-title":"Performing work eficiently in the presence of faults, SIAM Journal on Computing"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"M. Fisher and N. Lynch A lower bound for the time to assure interactive consistency Information Processing Letters 14 ( 1982 ) 183-186.   M. Fisher and N. Lynch A lower bound for the time to assure interactive consistency Information Processing Letters 14 ( 1982 ) 183-186.","DOI":"10.1016\/0020-0190(82)90033-3"},{"key":"e_1_3_2_1_19_1","first-page":"374","volume":"32","author":"Fisher M.","unstructured":"M. Fisher , N. Lynch , and M. Paterson , Impossibility of distributed consensus with one faulty process, Journal of the ACM , 32 ( 1985 ) 374 - 382 . M. Fisher, N. Lynch, and M. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM, 32 ( 1985 ) 374-382.","journal-title":"Impossibility of distributed consensus with one faulty process, Journal of the ACM"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796287"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"crossref","unstructured":"C. Georgiou D.R. Kowalski and A.A. Shvartsman Eficient gossip and robust distributed computation Theoretical Computer Science 347 ( 2005 ) 130-166.   C. Georgiou D.R. Kowalski and A.A. Shvartsman Eficient gossip and robust distributed computation Theoretical Computer Science 347 ( 2005 ) 130-166.","DOI":"10.1016\/j.tcs.2005.05.019"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.78"},{"volume-title":"Proc., International Conference on Dependable Systems and Networks (DSN), ( 2001 ) 433-442","author":"Gupta I.","key":"e_1_3_2_1_23_1","unstructured":"I. Gupta , R. van Renesse , and K.P. Birman , Scalable Fault-Tolerant Aggregation in Large Process Groups , in Proc., International Conference on Dependable Systems and Networks (DSN), ( 2001 ) 433-442 . I. Gupta, R. van Renesse, and K.P. Birman, Scalable Fault-Tolerant Aggregation in Large Process Groups, in Proc., International Conference on Dependable Systems and Networks (DSN), ( 2001 ) 433-442."},{"key":"e_1_3_2_1_24_1","first-page":"41","volume":"26","author":"Hadzilacos V.","unstructured":"V. Hadzilacos , and J.Y. Halpern , Message-optimal protocols for Byzantine agreement, Mathematical Systems Theory , 26 ( 1993 ) 41 - 102 . V. Hadzilacos, and J.Y. Halpern, Message-optimal protocols for Byzantine agreement, Mathematical Systems Theory, 26 ( 1993 ) 41-102.","journal-title":"Message-optimal protocols for Byzantine agreement, Mathematical Systems Theory"},{"key":"e_1_3_2_1_25_1","first-page":"97","volume-title":"Distributed Systems","author":"Hadzilacos V.","year":"1993","unstructured":"V. Hadzilacos , and S. Toueg , Fault-tolerant broadcast and related problems , in Distributed Systems , 2 nd edition, Eddison-Wesley , 1993 , pp. 97 - 145 . V. Hadzilacos, and S. Toueg, Fault-tolerant broadcast and related problems, in Distributed Systems, 2nd edition, Eddison-Wesley, 1993, pp. 97-145.","edition":"2"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"M.T. Hajiaghayi D.R. Kowalski and J. Olkowski Improved Communication Complexity of Fault-Tolerant Consensus CoRR abs\/2203.12912 ( 2022 ).   M.T. Hajiaghayi D.R. Kowalski and J. Olkowski Improved Communication Complexity of Fault-Tolerant Consensus CoRR abs\/2203.12912 ( 2022 ).","DOI":"10.1145\/3519935.3520078"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-31277-0_2"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75142-7_26"},{"key":"e_1_3_2_1_29_1","first-page":"58","volume":"2011","author":"King Valerie","unstructured":"Valerie King , Jared Saia Breaking the O(n2) bit barrier: Scalable byzantine agreement with an adaptive adversary , J. ACM, ( 2011 ) 58 , 18 : 1-18 : 24. Valerie King, Jared Saia Breaking the O(n2) bit barrier: Scalable byzantine agreement with an adaptive adversary, J. ACM, ( 2011 ) 58, 18 : 1-18 : 24.","journal-title":"J. ACM, ("},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":"D. Peleg ( 2000 ). Distributed Computing: A Locality-Sensitive Approach. SIAM.   D. Peleg ( 2000 ). Distributed Computing: A Locality-Sensitive Approach. SIAM.","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_1_31_1","first-page":"228","volume":"27","author":"Pease M.","unstructured":"M. Pease , R. Shostak , and L. Lamport , Reaching agreement in the presence of faults, Journal of the ACM , 27 ( 1980 ) 228 - 234 . M. Pease, R. Shostak, and L. Lamport, Reaching agreement in the presence of faults, Journal of the ACM, 27 ( 1980 ) 228-234.","journal-title":"Reaching agreement in the presence of faults, Journal of the ACM"}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Rome Italy","acronym":"STOC '22"},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520078","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520078","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:16Z","timestamp":1750188676000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520078"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":31,"alternative-id":["10.1145\/3519935.3520078","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3520078","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}