{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T23:58:26Z","timestamp":1790812706953,"version":"4.1.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2016,3,20]],"date-time":"2016-03-20T00:00:00Z","timestamp":1458432000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100009059","name":"PIMS","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100009059","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Simons Institute Berkeley"},{"name":"NSF CAREER","award":["0644058 and NSF CCR-0313160"],"award-info":[{"award-number":["0644058 and NSF CCR-0313160"]}]},{"name":"Princeton IAS"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2016,5,4]]},"abstract":"<jats:p>\n            We address the problem of Byzantine agreement, to bring processors to agreement on a bit in the presence of a\n            <jats:italic>strong<\/jats:italic>\n            adversary. This adversary has full information of the state of all processors, the ability to control message scheduling in an asynchronous model, and the ability to control the behavior of a constant fraction of processors that it may choose to corrupt adaptively.\n          <\/jats:p>\n          <jats:p>In 1983, Ben-Or proposed an algorithm for solving this problem with expected exponential communication time. In this article, we improve that result to require expected polynomial communication time and computation time. Like Ben-Or\u2019s algorithm, our algorithm uses coinflips from individual processors to repeatedly try to generate a fair global coin. We introduce a method that uses spectral analysis to identify processors that have thwarted this goal by flipping biased coins.<\/jats:p>","DOI":"10.1145\/2837019","type":"journal-article","created":{"date-parts":[[2016,3,21]],"date-time":"2016-03-21T18:56:20Z","timestamp":1458586580000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":27,"title":["Byzantine Agreement in Expected Polynomial Time"],"prefix":"10.1145","volume":"63","author":[{"given":"Valerie","family":"King","sequence":"first","affiliation":[{"name":"University of Victoria, Victoria, B.C. Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jared","family":"Saia","sequence":"additional","affiliation":[{"name":"University of New Mexico, Albuquerque, NM"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,3,20]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 33rd Annual ACM Symposium on Theory of Computing. ACM, 611--618","author":"Achlioptas D.","unstructured":"D. Achlioptas and F. McSherry . 2001. Fast computation of low rank matrix approximations . In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing. ACM, 611--618 . D. Achlioptas and F. McSherry. 2001. Fast computation of low rank matrix approximations. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing. ACM, 611--618."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 594--598","author":"Alon N.","unstructured":"N. Alon , M. Krivelevich , and B. Sudakov . 1998. Finding a large hidden clique in a random graph . In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 594--598 . N. Alon, M. Krivelevich, and B. Sudakov. 1998. Finding a large hidden clique in a random graph. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 594--598."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278304"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-002-0081-5"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90021-6"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"H. Attiya and K. Censor. 2008. Lower bounds for randomized consensus under a weak adversary. In Principles of Distributed Computing (PODC). 315--324.  H. Attiya and K. Censor. 2008. Lower bounds for randomized consensus under a weak adversary. In Principles of Distributed Computing (PODC). 315--324.","DOI":"10.1145\/1400751.1400793"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/983102"},{"key":"e_1_2_1_8_1","volume-title":"Symposium on Theory of Computing (STOC\u201901)","author":"Azar Y.","unstructured":"Y. Azar , A. Fiat , A. Karlin , F. McSherry , and J. Saia . 2001. Spectral analysis of data . In Symposium on Theory of Computing (STOC\u201901) . ACM, 619--626. Y. Azar, A. Fiat, A. Karlin, F. McSherry, and J. Saia. 2001. Spectral analysis of data. In Symposium on Theory of Computing (STOC\u201901). ACM, 619--626."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/800221.806707"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-002-0083-3"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the ACM Symposium on Theory of Computing (STOC\u201906)","author":"Ben-Or M.","unstructured":"M. Ben-Or , E. Pavlov , and V. Vaikuntanathan . 2006. Byzantine agreement in the full-information model in O (log n) rounds . In Proceedings of the ACM Symposium on Theory of Computing (STOC\u201906) . M. Ben-Or, E. Pavlov, and V. Vaikuntanathan. 2006. Byzantine agreement in the full-information model in O (log n) rounds. In Proceedings of the ACM Symposium on Theory of Computing (STOC\u201906)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"G. Bracha. 1984. An asynchronous [(n-1)\/3]-resilient consensus protocol. In PODC. 154--162.  G. Bracha. 1984. An asynchronous [(n-1)\/3]-resilient consensus protocol. In PODC. 154--162.","DOI":"10.1145\/800222.806743"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90054-X"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90054-X"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-005-0318-0"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC\u201993)","author":"Canetti R.","unstructured":"R. Canetti and T. Rabin . 1993. Fast asynchronous Byzantine agreement with optimal resilience . In Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC\u201993) . R. Canetti and T. Rabin. 1993. Fast asynchronous Byzantine agreement with optimal resilience. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC\u201993)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.781636"},{"key":"e_1_2_1_18_1","first-page":"443","article-title":"Randomization in byzantine agreement","volume":"5","author":"Chor B.","year":"1989","unstructured":"B. Chor and C. Dwork . 1989 . Randomization in byzantine agreement . Advances in Computing Research 5 (1989), 443 -- 498 . B. Chor and C. Dwork. 1989. Randomization in byzantine agreement. Advances in Computing Research 5 (1989), 443--498.","journal-title":"Advances in Computing Research"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"P. Feldman and S. Micali. 1985. Byzantine agreement in constant expected time (and trusting no one). In FOCS. 267--276.  P. Feldman and S. Micali. 1985. Byzantine agreement in constant expected time (and trusting no one). In FOCS. 267--276.","DOI":"10.1109\/SFCS.1985.14"},{"key":"e_1_2_1_20_1","volume-title":"An Introduction to Probability Theory","author":"Feller W.","unstructured":"W. Feller . 1968. An Introduction to Probability Theory , Vol. 1 ( 3 rd ed.). Wiley , New York, NY . W. Feller. 1968. An Introduction to Probability Theory, Vol. 1 (3rd ed.). Wiley, New York, NY.","edition":"3"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 13th International Conference on World Wide Web. ACM, 403--412","author":"Guha R.","unstructured":"R. Guha , R. Kumar , P. Raghavan , and A. Tomkins . 2004. Propagation of trust and distrust . In Proceedings of the 13th International Conference on World Wide Web. ACM, 403--412 . R. Guha, R. Kumar, P. Raghavan, and A. Tomkins. 2004. Propagation of trust and distrust. In Proceedings of the 13th International Conference on World Wide Web. ACM, 403--412."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030402"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 12th International Conference on World Wide Web. ACM, 640--651","author":"Kamvar S. D.","unstructured":"S. D. Kamvar , M. T. Schlosser , and H. Garcia-Molina . 2003. The eigentrust algorithm for reputation management in p2p networks . In Proceedings of the 12th International Conference on World Wide Web. ACM, 640--651 . S. D. Kamvar, M. T. Schlosser, and H. Garcia-Molina. 2003. The eigentrust algorithm for reputation management in p2p networks. In Proceedings of the 12th International Conference on World Wide Web. ACM, 640--651."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1824777.1824788"},{"key":"e_1_2_1_26_1","unstructured":"A. Karlin and A. Yao. 1984. Probabilistic lower bounds for byzantine agreement and clock synchronization. (1984). Unpublished manuscript.  A. Karlin and A. Yao. 1984. Probabilistic lower bounds for byzantine agreement and clock synchronization. (1984). Unpublished manuscript."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the ACM Symposium on Theory of Computing (STOC\u201913)","author":"King V.","unstructured":"V. King and J. Saia . 2013. Byzantine agreement in polynomial expected time . In Proceedings of the ACM Symposium on Theory of Computing (STOC\u201913) . ACM, 401--410. V. King and J. Saia. 2013. Byzantine agreement in polynomial expected time. In Proceedings of the ACM Symposium on Theory of Computing (STOC\u201913). ACM, 401--410."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics.","author":"King V.","unstructured":"V. King and J. Saia . 2014. Faster agreement via a spectral method for detecting malicious behavior . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics. V. King and J. Saia. 2014. Faster agreement via a spectral method for detecting malicious behavior. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324140"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00103-K"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/357172.357176"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24100-0_35"},{"key":"e_1_2_1_33_1","unstructured":"N. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann.  N. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90019-B"},{"key":"e_1_2_1_35_1","unstructured":"L. Page S. Brin R. Motwani and T. Winograd. 1998. The PageRank citation ranking: bringing order to the web. Stanford University Technical Report. http:\/\/ilpubs.stanford.edu:8090\/422\/1\/1999-66.pdf.  L. Page S. Brin R. Motwani and T. Winograd. 1998. The PageRank citation ranking: bringing order to the web. Stanford University Technical Report. http:\/\/ilpubs.stanford.edu:8090\/422\/1\/1999-66.pdf."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.1318566"},{"key":"e_1_2_1_37_1","volume-title":"Algorithms and Models for the Web-Graph","author":"Zhang H.","unstructured":"H. Zhang , A. Goel , R. Govindan , K. Mason , and B. Van Roy . 2004. Making eigenvector-based reputation systems robust to collusion . In Algorithms and Models for the Web-Graph . Springer , 92--104. H. Zhang, A. Goel, R. Govindan, K. Mason, and B. Van Roy. 2004. Making eigenvector-based reputation systems robust to collusion. In Algorithms and Models for the Web-Graph. Springer, 92--104."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2837019","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2837019","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:48:41Z","timestamp":1750225721000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2837019"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,3,20]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,5,4]]}},"alternative-id":["10.1145\/2837019"],"URL":"https:\/\/doi.org\/10.1145\/2837019","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,3,20]]},"assertion":[{"value":"2014-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-03-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}