{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T17:59:26Z","timestamp":1773511166443,"version":"3.50.1"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2011,7,1]],"date-time":"2011-07-01T00:00:00Z","timestamp":1309478400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-07-1-0532"],"award-info":[{"award-number":["FA9550-07-1-0532"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-0313160"],"award-info":[{"award-number":["CCR-0313160"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["644058"],"award-info":[{"award-number":["644058"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2011,7]]},"abstract":"<jats:p>\n            We describe an algorithm for Byzantine agreement that is scalable in the sense that each processor sends only \u00d5(\u221a\n            <jats:italic>n<\/jats:italic>\n            ) bits, where\n            <jats:italic>n<\/jats:italic>\n            is the total number of processors. Our algorithm succeeds with high probability against an\n            <jats:italic>adaptive adversary<\/jats:italic>\n            , which can take over processors at any time during the protocol, up to the point of taking over arbitrarily close to a 1\/3 fraction. We assume synchronous communication but a\n            <jats:italic>rushing<\/jats:italic>\n            adversary. Moreover, our algorithm works in the presence of flooding: processors controlled by the adversary can send out any number of messages. We assume the existence of private channels between all pairs of processors but make no other cryptographic assumptions. Finally, our algorithm has latency that is polylogarithmic in\n            <jats:italic>n<\/jats:italic>\n            . To the best of our knowledge, ours is the first algorithm to solve Byzantine agreement against an adaptive adversary, while requiring\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) total bits of communication.\n          <\/jats:p>","DOI":"10.1145\/1989727.1989732","type":"journal-article","created":{"date-parts":[[2011,7,21]],"date-time":"2011-07-21T13:27:09Z","timestamp":1311254829000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":73,"title":["Breaking the\n            <i>O<\/i>\n            (\n            <i>n<\/i>\n            <sup>2<\/sup>\n            ) bit barrier"],"prefix":"10.1145","volume":"58","author":[{"given":"Valerie","family":"King","sequence":"first","affiliation":[{"name":"University of Victoria, Victoria, BC, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jared","family":"Saia","sequence":"additional","affiliation":[{"name":"University of New Mexico, Albuquerque, NM"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,7,20]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146393"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the IACR Theory of Cryptography Conference (TCC).","author":"Abraham I.","unstructured":"Abraham , I. , Dolev , D. , and Halper , J . 2008. Lower bounds on implementing robust and resilient mediators . In Proceedings of the IACR Theory of Cryptography Conference (TCC). Abraham, I., Dolev, D., and Halper, J. 2008. Lower bounds on implementing robust and resilient mediators. In Proceedings of the IACR Theory of Cryptography Conference (TCC)."},{"key":"e_1_2_1_3_1","unstructured":"Agbaria A. and Friedman R. 2003. Overcoming Byzantine Failures Using Checkpointing. Coordinated Science Laboratory Tech. rep. no. UILU-ENG-03-2228 (CRHC-03-14) University of Illinois at Urbana-Champaign.  Agbaria A. and Friedman R. 2003. Overcoming Byzantine Failures Using Checkpointing. Coordinated Science Laboratory Tech. rep. no. UILU-ENG-03-2228 (CRHC-03-14) University of Illinois at Urbana-Champaign."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2006.63"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1038\/scientificamerican0302-40"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/571637.571640"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.csi.2007.12.004"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.55"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1529974.1529992"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of 21st ACM SIGOPS Symposium on Operating Systems Principles.","author":"Clement A.","unstructured":"Clement , A. , Wong , E. , Alvisi , L. , Dahlin , M. , and Marchetti , M . 2009. Making Byzantine fault tolerant systems tolerate Byzantine faults . In Proceedings of 21st ACM SIGOPS Symposium on Operating Systems Principles. Clement, A., Wong, E., Alvisi, L., Dahlin, M., and Marchetti, M. 2009. Making Byzantine fault tolerant systems tolerate Byzantine faults. In Proceedings of 21st ACM SIGOPS Symposium on Operating Systems Principles."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of Operating Systems Design and Implementation (OSDI).","author":"Cowling J.","unstructured":"Cowling , J. , Myers , D. , Liskov , B. , Rodrigues , R. , and Shrira , L . 2005. Hq replication: A hybrid quorum protocol for byzantine fault tolerance . In Proceedings of Operating Systems Design and Implementation (OSDI). Cowling, J., Myers, D., Liskov, B., Rodrigues, R., and Shrira, L. 2005. Hq replication: A hybrid quorum protocol for byzantine fault tolerance. In Proceedings of Operating Systems Design and Implementation (OSDI)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2455.214112"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796481"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of EUROCRYPT. 307--323","author":"Garay J. A.","unstructured":"Garay , J. A. and Ostrovsky , R . 2008. Almost-everywhere secure computation . In Proceedings of EUROCRYPT. 307--323 . Garay, J. A. and Ostrovsky, R. 2008. Almost-everywhere secure computation. In Proceedings of EUROCRYPT. 307--323."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-008-0069-x"},{"key":"e_1_2_1_16_1","first-page":"2002","article-title":"On concentration of probability","volume":"11","author":"Janson S.","year":"1999","unstructured":"Janson , S. 1999 . On concentration of probability . Combinat. Probabil. Comput. 11 , 2002 . Janson, S. 1999. On concentration of probability. Combinat. Probabil. Comput. 11, 2002.","journal-title":"Combinat. Probabil. Comput."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1824777.1824788"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 19th International Heterogeneity in Computing Workshop.","author":"King V.","unstructured":"King , V. , Oluwasanmi , O. , and Saia , J . 2010. An empirical study of a scalable byzantine agreement aglrotihm . In Proceedings of the 19th International Heterogeneity in Computing Workshop. King, V., Oluwasanmi, O., and Saia, J. 2010. An empirical study of a scalable byzantine agreement aglrotihm. In Proceedings of the 19th International Heterogeneity in Computing Workshop."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the International Symposium on Distributed Computing (DISC).","author":"King V.","unstructured":"King , V. and Saia , J . 2009. From almost-everywhere to everywhere: Byzantine agreement in \u00d5(n3\/2) bits . In Proceedings of the International Symposium on Distributed Computing (DISC). King, V. and Saia, J. 2009. From almost-everywhere to everywhere: Byzantine agreement in \u00d5(n3\/2) bits. In Proceedings of the International Symposium on Distributed Computing (DISC)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109667"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.77"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1294261.1294267"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the Computer Security Foundations Workshop. 116--124","author":"Malkhi D.","unstructured":"Malkhi , D. and Reiter , M . 1997. Unreliable intrusion detection in distributed computations . In Proceedings of the Computer Security Foundations Workshop. 116--124 . Malkhi, D. and Reiter, M. 1997. Unreliable intrusion detection in distributed computations. In Proceedings of the Computer Security Foundations Workshop. 116--124."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/358746.358762"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.48"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 2nd USENIX Conference on File and Storage Technologies. 1--14","author":"Rhea S.","unstructured":"Rhea , S. , Eaton , P. , Geels , D. , Weatherspoon , H. , Zhao , B. , and Kubiatowicz , J . 2003. Pond: the OceanStore prototype . In Proceedings of the 2nd USENIX Conference on File and Storage Technologies. 1--14 . Rhea, S., Eaton, P., Geels, D., Weatherspoon, H., Zhao, B., and Kubiatowicz, J. 2003. Pond: the OceanStore prototype. In Proceedings of the 2nd USENIX Conference on File and Storage Technologies. 1--14."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/MWC.2004.1368895"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538788.1538794"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPADS.2005.104"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1989727.1989732","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1989727.1989732","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:05:54Z","timestamp":1750244754000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1989727.1989732"}},"subtitle":["Scalable byzantine agreement with an adaptive adversary"],"short-title":[],"issued":{"date-parts":[[2011,7]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,7]]}},"alternative-id":["10.1145\/1989727.1989732"],"URL":"https:\/\/doi.org\/10.1145\/1989727.1989732","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,7]]},"assertion":[{"value":"2010-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-07-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}