{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:30:31Z","timestamp":1750307431225,"version":"3.41.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2010,8,1]],"date-time":"2010-08-01T00:00:00Z","timestamp":1280620800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-0313160","644058"],"award-info":[{"award-number":["CCR-0313160","644058"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2010,8]]},"abstract":"<jats:p>We resolve two long-standing open problems in distributed computation by describing polylogarithmic protocols for Byzantine agreement and leader election in the asynchronous full information model with a nonadaptive malicious adversary. All past protocols for asynchronous Byzantine agreement had been exponential, and<jats:italic>no<\/jats:italic>protocol for asynchronous leader election had been known. Our protocols tolerate up to (1\/3 \u2212 \u03f5) \u22c5<jats:italic>n<\/jats:italic>faulty processors, for any positive constant \u03f5. They are Monte Carlo, succeeding with probability 1 \u2212<jats:italic>o<\/jats:italic>(1) for Byzantine agreement, and constant probability for leader election. A key technical contribution of our article is a new approach for emulating Feige's lightest bin protocol, even with adversarial message scheduling.<\/jats:p>","DOI":"10.1145\/1824777.1824788","type":"journal-article","created":{"date-parts":[[2010,9,2]],"date-time":"2010-09-02T13:14:24Z","timestamp":1283433264000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":32,"title":["Fast asynchronous Byzantine agreement and leader election with full information"],"prefix":"10.1145","volume":"6","author":[{"given":"Bruce M.","family":"Kapron","sequence":"first","affiliation":[{"name":"University of Victoria, BC, Canada"}]},{"given":"David","family":"Kempe","sequence":"additional","affiliation":[{"name":"University of Southern California, Los Angeles, CA"}]},{"given":"Valerie","family":"King","sequence":"additional","affiliation":[{"name":"University of Victoria, BC, Canada"}]},{"given":"Jared","family":"Saia","sequence":"additional","affiliation":[{"name":"University of New Mexico, Albuquerque, NM"}]},{"given":"Vishal","family":"Sanwalani","sequence":"additional","affiliation":[{"name":"University of New Mexico, Albuquerque, NM"}]}],"member":"320","published-online":{"date-parts":[[2010,9,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01303199"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278304"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250814"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400793"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/800221.806707"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-002-0083-3"},{"key":"e_1_2_1_7_1","unstructured":"Ben-Or M. and Linial N. 1989. Collective coin flipping. In Advances in Computing Research 5: Randomness and Computation S. Micali Ed. JAI Press 91--115. Ben-Or M. and Linial N. 1989. Collective coin flipping. In Advances in Computing Research 5: Randomness and Computation S. Micali Ed. JAI Press 91--115."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132543"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Berman P. and Garay J. A. 1993. Randomized distributed agreement revisited. In Digest of Papers: FTCS-23 the 23rd Annual International Symposium on Fault-Tolerant Computing. 412--419. Berman P. and Garay J. A. 1993. Randomized distributed agreement revisited. In Digest of Papers: FTCS-23 the 23rd Annual International Symposium on Fault-Tolerant Computing. 412--419.","DOI":"10.1109\/FTCS.1993.627344"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/800222.806743"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-005-0318-0"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167105"},{"key":"e_1_2_1_13_1","unstructured":"Chor B. and Dwork C. 1989. Randomization in Byzantine agreement. In Advances in Computing Research 5: Randomness and Computation S. Micali Ed. JAI Press 443--497. Chor B. and Dwork C. 1989. Randomization in Byzantine agreement. In Advances in Computing Research 5: Randomness and Computation S. Micali Ed. JAI Press 443--497."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65956"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796481"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/588058.588060"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.30"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11818175_25"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109667"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.77"},{"volume-title":"Probabilistic Methods for Algorithmic Discrete Mathematics","author":"McDiarmid C.","key":"e_1_2_1_21_1","unstructured":"McDiarmid , C. 1998. Concentration . In Probabilistic Methods for Algorithmic Discrete Mathematics , M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed, Eds. Springer , 195--247. McDiarmid, C. 1998. Concentration. In Probabilistic Methods for Algorithmic Discrete Mathematics, M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed, Eds. Springer, 195--247."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/646767.704304"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195141"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322188"},{"volume-title":"Proceedings of the 39th IEEE Symposium on Foundations of Computer Science. 576--583","author":"Russell A.","key":"e_1_2_1_25_1","unstructured":"Russell , A. and Zuckerman , D . 1998. Perfect information leader election in log&ast; n + o(1) rounds . In Proceedings of the 39th IEEE Symposium on Foundations of Computer Science. 576--583 . Russell, A. and Zuckerman, D. 1998. Perfect information leader election in log&ast; n + o(1) rounds. In Proceedings of the 39th IEEE Symposium on Foundations of Computer Science. 576--583."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0402020"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/800222.806744"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(84)90027-9"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199712)11:4%3C345::AID-RSA4%3E3.0.CO;2-Z"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1824777.1824788","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1824777.1824788","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:39:53Z","timestamp":1750246793000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1824777.1824788"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,8]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,8]]}},"alternative-id":["10.1145\/1824777.1824788"],"URL":"https:\/\/doi.org\/10.1145\/1824777.1824788","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2010,8]]},"assertion":[{"value":"2009-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-09-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}