{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T10:53:52Z","timestamp":1774436032852,"version":"3.50.1"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,4,12]],"date-time":"2024-04-12T00:00:00Z","timestamp":1712880000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1815316 and CCF-2221980"],"award-info":[{"award-number":["CCF-1815316 and CCF-2221980"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2024,4,30]]},"abstract":"<jats:p>\n            Since the mid-1980s it has been known that Byzantine Agreement can be solved with probability 1 asynchronously, even against an omniscient, computationally unbounded adversary that can adaptively\n            <jats:italic>corrupt<\/jats:italic>\n            up to\n            <jats:italic>f &lt; n\/3<\/jats:italic>\n            parties. Moreover, the problem is insoluble with\n            <jats:italic>f \u2265 n\/3<\/jats:italic>\n            corruptions. However, Bracha\u2019s\u00a0[\n            <jats:xref ref-type=\"bibr\">13<\/jats:xref>\n            ] 1984 protocol (see also Ben-Or\u00a0[\n            <jats:xref ref-type=\"bibr\">8<\/jats:xref>\n            ]) achieved\n            <jats:italic>f &lt; n\/3<\/jats:italic>\n            resilience at the cost of\n            <jats:italic>exponential<\/jats:italic>\n            expected latency\n            <jats:italic>2<\/jats:italic>\n            <jats:sup>\n              \u0398 (\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            , a bound that has\n            <jats:italic>never<\/jats:italic>\n            been improved in this model with\n            <jats:italic>f = \u230a (n-1)\/3 \u230b<\/jats:italic>\n            corruptions.\n          <\/jats:p>\n          <jats:p>\n            In this article, we prove that Byzantine Agreement in the asynchronous, full information model can be solved with probability 1 against an adaptive adversary that can corrupt\n            <jats:italic>f &lt; n\/3<\/jats:italic>\n            parties, while incurring only\n            <jats:italic>polynomial latency with high probability<\/jats:italic>\n            . Our protocol follows an earlier polynomial latency protocol of King and Saia\u00a0[\n            <jats:xref ref-type=\"bibr\">33<\/jats:xref>\n            ,\n            <jats:xref ref-type=\"bibr\">34<\/jats:xref>\n            ], which had\n            <jats:italic>suboptimal<\/jats:italic>\n            resilience, namely\n            <jats:italic>f \u2248 n<\/jats:italic>\n            \/10\n            <jats:sup>9<\/jats:sup>\n            \u00a0[\n            <jats:xref ref-type=\"bibr\">33<\/jats:xref>\n            ,\n            <jats:xref ref-type=\"bibr\">34<\/jats:xref>\n            ].\n          <\/jats:p>\n          <jats:p>\n            Resilience\n            <jats:italic>f = (n-1)\/3<\/jats:italic>\n            is uniquely difficult, as this is the point at which the influence of the Byzantine and honest players are of roughly equal strength. The core technical problem we solve is to design a collective coin-flipping protocol that\n            <jats:italic>eventually<\/jats:italic>\n            lets us flip a coin with an unambiguous outcome. In the beginning, the influence of the Byzantine players is too powerful to overcome, and they can essentially fix the coin\u2019s behavior at will. We guarantee that after just a polynomial number of executions of the coin-flipping protocol, either (a) the Byzantine players fail to fix the behavior of the coin (thereby ending the game) or (b)\u00a0we can \u201cblacklist\u201d players such that the blacklisting rate for Byzantine players is at least as large as the blacklisting rate for good players. The blacklisting criterion is based on a simple statistical test of\n            <jats:italic>fraud detection<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/3639454","type":"journal-article","created":{"date-parts":[[2024,1,2]],"date-time":"2024-01-02T21:58:12Z","timestamp":1704232692000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection"],"prefix":"10.1145","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9799-0981","authenticated-orcid":false,"given":"Shang-En","family":"Huang","sequence":"first","affiliation":[{"name":"University of Michigan, Ann Arbor, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0495-3904","authenticated-orcid":false,"given":"Seth","family":"Pettie","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7289-5435","authenticated-orcid":false,"given":"Leqi","family":"Zhu","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, USA"}]}],"member":"320","published-online":{"date-parts":[[2024,4,12]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400804"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01303199"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/0222030"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278304"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411510"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1002\/0471478210"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3388788"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/800221.806707"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.15"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132543"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/FTCS.1993.627344"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796307182"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90054-X"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/4221.214134"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-005-0318-0"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167105"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1985.232245"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/42282.42283"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814586"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539790187084"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90033-3"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01843568"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794265232"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.30"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00120"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520015"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch165"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21923"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/1824777.1824788"},{"key":"e_1_3_3_33_2","volume-title":"Improvement and partial simulation of King & Saia\u2019s expected-polynomial-time Byzantine agreement algorithm","author":"Kimmett Ben","year":"2020","unstructured":"Ben Kimmett. 2020. Improvement and partial simulation of King & Saia\u2019s expected-polynomial-time Byzantine agreement algorithm. Master\u2019s Thesis. University of Victoria, Canada."},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2837019"},{"key":"e_1_3_3_35_2","unstructured":"Valerie King and Jared Saia. 2018. Correction to Byzantine agreement in expected polynomial time JACM 2016. arXiv:1812.10169. Retrieved from http:\/\/arxiv.org\/abs\/1812.10169"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/357172.357176"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24100-0_35"},{"key":"e_1_3_3_38_2","volume-title":"Distributed Algorithms","author":"Lynch Nancy A.","year":"1996","unstructured":"Nancy A. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann."},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322188"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.48"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376007"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1137\/0402020"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/800222.806744"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639454","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639454","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:53:37Z","timestamp":1750287217000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639454"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,12]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4,30]]}},"alternative-id":["10.1145\/3639454"],"URL":"https:\/\/doi.org\/10.1145\/3639454","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,12]]},"assertion":[{"value":"2023-01-10","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-15","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}