{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T19:33:53Z","timestamp":1770752033695,"version":"3.50.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,9,11]],"date-time":"2015-09-11T00:00:00Z","timestamp":1441929600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DISCMAT"},{"name":"Franco-German ANR-DFG"},{"name":"ANR French Research Council","award":["ANR-11-BS02-014"],"award-info":[{"award-number":["ANR-11-BS02-014"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2015,9,11]]},"abstract":"<jats:p>\n            This article is on broadcast and agreement in asynchronous message-passing systems made up of\n            <jats:italic>n<\/jats:italic>\n            processes, and where up to\n            <jats:italic>t<\/jats:italic>\n            processes may have a Byzantine Behavior. Its first contribution is a powerful, yet simple, all-to-all broadcast communication abstraction suited to binary values. This abstraction, which copes with up to\n            <jats:italic>t<\/jats:italic>\n            &lt;\n            <jats:italic>n<\/jats:italic>\n            \/3 Byzantine processes, allows each process to broadcast a binary value, and obtain a set of values such that (1) no value broadcast only by Byzantine processes can belong to the set of a correct process, and (2) if the set obtained by a correct process contains a single value\n            <jats:italic>v<\/jats:italic>\n            , then the set obtained by any correct process contains\n            <jats:italic>v<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            The second contribution of this article is a new round-based asynchronous consensus algorithm that copes with up to\n            <jats:italic>t<\/jats:italic>\n            &lt;\n            <jats:italic>n<\/jats:italic>\n            \/3 Byzantine processes. This algorithm is based on the previous binary broadcast abstraction and a weak common coin. In addition to being signature-free and optimal with respect to the value of\n            <jats:italic>t<\/jats:italic>\n            , this consensus algorithm has several noteworthy properties: the expected number of rounds to decide is constant; each round is composed of a constant number of communication steps and involves\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            2) messages; each message is composed of a round number plus a constant number of bits. Moreover, the algorithm tolerates message reordering by the adversary (i.e., the Byzantine processes).\n          <\/jats:p>","DOI":"10.1145\/2785953","type":"journal-article","created":{"date-parts":[[2015,9,15]],"date-time":"2015-09-15T12:09:15Z","timestamp":1442318955000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":63,"title":["Signature-Free Asynchronous Binary Byzantine Consensus with t &lt; n\/3, O(n2) Messages, and O(1) Expected Time"],"prefix":"10.1145","volume":"62","author":[{"given":"Achour","family":"Most\u00e9faoui","sequence":"first","affiliation":[{"name":"LINA, Universit\u00e9 de Nantes"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hamouma","family":"Moumen","sequence":"additional","affiliation":[{"name":"LMA, University of Bejaia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michel","family":"Raynal","sequence":"additional","affiliation":[{"name":"Institut Universitaire de France and IRISA (Universit\u00e9 de Rennes)"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,9,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1822796"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/983102"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/800221.806707"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 23rd International Symposium on Fault-Tolerant Computing (FTCS\u201993)","author":"Berman Piotr","unstructured":"Piotr Berman and Juan A. Garay. 1993. Randomized distributed agreement revisited. In Proceedings of the 23rd International Symposium on Fault-Tolerant Computing (FTCS\u201993). IEEE Computer Press, 412--419."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/800222.806743"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90054-X"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/4221.214134"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1972495"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/646766.704283"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-005-0318-0"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167105"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226647"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","unstructured":"Miguel Correia Nuno Ferreira Neves and Paulo Ver\u00edssimo. From consensus to atomic broadcast: Time-free Byzantine-resistant protocols without signatures. Comput. J. 49 1 82--96. 10.1093\/comjnl\/bxh145","DOI":"10.1093\/comjnl\/bxh145"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/42282.42283"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90033-3"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-003-0096-6"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2007.1043"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626405002131"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2005.13"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.30"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/573304"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/46.1.16"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989727.1989732"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/357172.357176"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993809"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","unstructured":"Nancy A. Lynch. 1996. Distributed Algorithms. Morgan-Kaufmann.","DOI":"10.5555\/525656"},{"key":"e_1_2_1_28_1","unstructured":"Nancy A. Lynch Michael Merritt William E. Weihl and Alan Fekete. 1993. Atomic Transactions. Morgan-Kaufmann."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2006.35"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/SRDS.2011.36"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611468"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/950620.950624"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1940234.1940253"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-25258-2_14"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25873-2_4"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322188"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.48"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/1855117"},{"key":"e_1_2_1_39_1","volume-title":"Fault-Tolerant Agreement in Synchronous Message-Passing Systems","author":"Raynal Michel","unstructured":"Michel Raynal. 2010b. Fault-Tolerant Agreement in Synchronous Message-Passing Systems. Morgan & Claypool Publishers."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/2431405"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87779-0_30"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01667080"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/800222.806744"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(84)90027-9"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2785953","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2785953","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:42:37Z","timestamp":1750225357000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2785953"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,11]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,9,11]]}},"alternative-id":["10.1145\/2785953"],"URL":"https:\/\/doi.org\/10.1145\/2785953","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9,11]]},"assertion":[{"value":"2014-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-09-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}