{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T19:53:51Z","timestamp":1770753231777,"version":"3.50.0"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2016,4,29]],"date-time":"2016-04-29T00:00:00Z","timestamp":1461888000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2017,8]]},"DOI":"10.1007\/s00236-016-0269-y","type":"journal-article","created":{"date-parts":[[2016,4,29]],"date-time":"2016-04-29T15:04:32Z","timestamp":1461942272000},"page":"501-520","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["Signature-free asynchronous Byzantine systems: from multivalued to binary consensus with $$t&lt;n\/3$$ t &lt; n \/ 3 , $$O(n^2)$$ O ( n 2 ) messages, and constant time"],"prefix":"10.1007","volume":"54","author":[{"given":"Achour","family":"Most\u00e9faoui","sequence":"first","affiliation":[]},{"given":"Michel","family":"Raynal","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,4,29]]},"reference":[{"key":"269_CR1","doi-asserted-by":"crossref","unstructured":"Aguilera, M.K., Frolund, S., Hadzilacos, V., Horn, S., Toueg S.: Abortable and query-abortable objects and their efficient implementation. In: Proceedings of 26th Annual ACM Symposium on Principles of Distributed Computing (PODC\u201907), pp. 23\u201332 (2007)","DOI":"10.1145\/1281100.1281107"},{"key":"269_CR2","doi-asserted-by":"crossref","DOI":"10.1002\/0471478210","volume-title":"Distributed Computing: Fundamentals, Simulations and Advanced Topics","author":"H Attiya","year":"2004","unstructured":"Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations and Advanced Topics, 2d edn. Wiley-Interscience, New York (2004)","edition":"2d"},{"key":"269_CR3","doi-asserted-by":"crossref","unstructured":"Ben-Or M.: Another advantage of free choice: completely asynchronous agreement protocols. In: Proceedings of the 2nd ACM Symposium on Principles of Distributed Computing (PODC\u201983), pp. 27\u201330. ACM Press, New York (1983)","DOI":"10.1145\/800221.806707"},{"issue":"2","key":"269_CR4","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0890-5401(87)90054-X","volume":"75","author":"G Bracha","year":"1987","unstructured":"Bracha, G.: Asynchronous Byzantine agreement protocols. Inf. Comput. 75(2), 130\u2013143 (1987)","journal-title":"Inf. Comput."},{"issue":"4","key":"269_CR5","doi-asserted-by":"crossref","first-page":"824","DOI":"10.1145\/4221.214134","volume":"32","author":"G Bracha","year":"1985","unstructured":"Bracha, G., Toueg, S.: Asynchronous consensus and broadcast protocols. J. ACM 32(4), 824\u2013840 (1985)","journal-title":"J. ACM"},{"key":"269_CR6","doi-asserted-by":"crossref","unstructured":"Cachin, Ch., Kursawe, K., Petzold, F., Shoup, V.: Secure and efficient asynchronous broadcast protocols. In: Proceedings of the 21st Annual International Cryptology Conference (CRYPTO\u201901). LNCS, vol. 2139, pp. 524\u2013541. Springer, Berlin (2001)","DOI":"10.1007\/3-540-44647-8_31"},{"issue":"1","key":"269_CR7","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1093\/comjnl\/bxh145","volume":"49","author":"M Correia","year":"2006","unstructured":"Correia, M., Ferreira Neves, N., Verissimo, P.: From consensus to atomic broadcast: time-free Byzantine-resistant protocols without signatures. Comput. J. 49(1), 82\u201396 (2006)","journal-title":"Comput. J."},{"issue":"1","key":"269_CR8","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1109\/71.899936","volume":"12","author":"R Prisco De","year":"2001","unstructured":"De Prisco, R., Malkhi, D., Reiter, M.: On $$k$$ k -set consensus problems in asynchronous systems. Trans. Parallel Distrib. Syst. 12(1), 7\u201321 (2001)","journal-title":"Trans. Parallel Distrib. Syst."},{"key":"269_CR9","doi-asserted-by":"crossref","unstructured":"Doudou, A., Garbinato, B., Guerraoui, R., Schiper, A.: Muteness failure detectors: specification and implementation. In: Proceedings of the Third European Dependable Computing Conference (EDCC\u201999). LNC, vol. 1667, pp. 71\u201387. Springer, Berlin (1999)","DOI":"10.1007\/3-540-48254-7_7"},{"issue":"2","key":"269_CR10","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1145\/42282.42283","volume":"35","author":"C Dwork","year":"1988","unstructured":"Dwork, C., Lynch, N., Stockmeyer, L.: Consensus in the presence of partial synchrony. J. ACM 35(2), 288\u2013323 (1988)","journal-title":"J. ACM"},{"key":"269_CR11","doi-asserted-by":"crossref","unstructured":"Ezhilchelvan, P., Most\u00e9faoui, A., Raynal, M.: Randomized multivalued consensus. In: Proceedings of the 4th IEEE International Symposium Object-Oriented Real-Time Distributed Computing (ISORC\u201901), pp. 195\u2013200. IEEE Society Press, New York (2001)","DOI":"10.1109\/ISORC.2001.922837"},{"issue":"2","key":"269_CR12","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1145\/3149.214121","volume":"32","author":"MJ Fischer","year":"1985","unstructured":"Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374\u2013382 (1985)","journal-title":"J. ACM"},{"key":"269_CR13","doi-asserted-by":"crossref","unstructured":"Fitzi, M., Hirt, M.: Optimally efficient multi-valued Byzantine agreement. In: Proceedings of the 25th ACM Symposium on Principles of Distributed Computing (PODC\u201906), pp. 163\u2013168. ACM Press, New York (2006)","DOI":"10.1145\/1146381.1146407"},{"issue":"7","key":"269_CR14","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1109\/TC.2007.1043","volume":"56","author":"R Friedman","year":"2007","unstructured":"Friedman, R., Most\u00e9faoui, A., Rajsbaum, S., Raynal, M.: Distributed agreement problems and their connection with error-correcting codes. IEEE Trans. Comput. 56(7), 865\u2013875 (2007)","journal-title":"IEEE Trans. Comput."},{"issue":"1\u20132","key":"269_CR15","first-page":"162","volume":"15","author":"R Friedman","year":"2005","unstructured":"Friedman, R., Most\u00e9faoui, A., Raynal, M.: $$\\Diamond {\\cal P}_{mute}$$ \u25ca P m u t e -based consensus for asynchronous Byzantine systems. Parallel Process. Lett. 15(1\u20132), 162\u2013182 (2005)","journal-title":"Parallel Process. Lett."},{"issue":"1","key":"269_CR16","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1109\/TDSC.2005.13","volume":"2","author":"R Friedman","year":"2005","unstructured":"Friedman, R., Most\u00e9faoui, A., Raynal, M.: Simple and efficient oracle-based consensus protocols for asynchronous Byzantine systems. IEEE Trans. Dependable Secure Comput. 2(1), 46\u201356 (2005)","journal-title":"IEEE Trans. Dependable Secure Comput."},{"key":"269_CR17","doi-asserted-by":"crossref","unstructured":"Hadzilacos, V., Toueg, S.: On deterministic abortable objects. In: Proceedings of the 32th Annual ACM Symposium on Principles of Distributed Computing (PODC\u201913), pp. 4\u201312 (2013)","DOI":"10.1145\/2484239.2484241"},{"issue":"1","key":"269_CR18","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1093\/comjnl\/46.1.16","volume":"46","author":"KP Kihlstrom","year":"2003","unstructured":"Kihlstrom, K.P., Moser, L.E., Melliar-Smith, P.M.: Byzantine fault detectors for solving consensus. Comput. J. 46(1), 16\u201335 (2003)","journal-title":"Comput. J."},{"key":"269_CR19","doi-asserted-by":"crossref","unstructured":"King, V., Saia, J.: Breaking the $$O(n^2)$$ O ( n 2 ) bit barrier: scalable Byzantine agreement with an adaptive adversary. In: Proceedings of the 30th ACM Symposium on Principles of Distributed Computing (PODC\u201911), pp. 420\u2013429. ACM Press, New York (2011)","DOI":"10.1145\/1835698.1835798"},{"issue":"3","key":"269_CR20","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1145\/357172.357176","volume":"4","author":"L Lamport","year":"1982","unstructured":"Lamport, L., Shostack, R., Pease, M.: The Byzantine generals problem. ACM Trans. Program. Lang. Syst. 4(3), 382\u2013401 (1982)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"269_CR21","doi-asserted-by":"crossref","unstructured":"Liang, G., Vaidya, N.: Error-free multi-valued consensus with Byzantine failures. In: Proceeding 30th ACM Symposium on Principles of Distributed Computing (PODC\u201911), pp. 11\u201320. ACM Press, New York (2011)","DOI":"10.21236\/ADA555083"},{"key":"269_CR22","volume-title":"Distributed Algorithms","author":"NA Lynch","year":"1996","unstructured":"Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann Publications, San Francisco (1996)"},{"issue":"3","key":"269_CR23","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1109\/TDSC.2006.35","volume":"3","author":"J-Ph Martin","year":"2006","unstructured":"Martin, J-Ph, Alvisi, L.: Fast Byzantine consensus. IEEE Trans. Dependable Secure Comput. 3(3), 202\u2013215 (2006)","journal-title":"IEEE Trans. Dependable Secure Comput."},{"key":"269_CR24","doi-asserted-by":"crossref","unstructured":"Milosevic, Z., Hutle, M., Schiper, A.: On the reduction of atomic broadcast to consensus with Byzantine faults. In: Proceedings of the 30th IEEE International Symposium on Reliable Distributed Systems (SRDS\u201911), pp. 235\u2013244. IEEE Computer Press, Los Alamitos (2011)","DOI":"10.1109\/SRDS.2011.36"},{"key":"269_CR25","doi-asserted-by":"crossref","unstructured":"Most\u00e9faoui, A., Moumen, H., Raynal, M.: Signature-free asynchronous Byzantine consensus with $$t<n\/3$$ t < n \/ 3 and $$O(n^2)$$ O ( n 2 ) messages. In: Proceedings of the 33rd Annual ACM Symposium on Principles of Distributed Computing (PODC\u201914), pp. 2\u20139. ACM Press, New York (2014)","DOI":"10.1145\/2611462.2611468"},{"key":"269_CR26","doi-asserted-by":"crossref","unstructured":"Most\u00e9faoui, A., Moumen, H., Raynal, M.: Signature-free asynchronous binary Byzantine consensus with $$t<n\/3$$ t < n \/ 3 , $$O(n^2)$$ O ( n 2 ) messages, and $$O(1) $$ O ( 1 ) expected time. J. ACM 62(4), 21 (2015)","DOI":"10.1145\/2785953"},{"issue":"6","key":"269_CR27","doi-asserted-by":"crossref","first-page":"922","DOI":"10.1145\/950620.950624","volume":"50","author":"A Most\u00e9faoui","year":"2003","unstructured":"Most\u00e9faoui, A., Rajsbaum, S., Raynal, M.: Conditions on input vectors for consensus solvability in asynchronous distributed systems. J. ACM 50(6), 922\u2013954 (2003)","journal-title":"J. ACM"},{"key":"269_CR28","unstructured":"Most\u00e9faoui, A., Raynal, M.: Signature-free broadcast-based intrusion tolerance: never decide a Byzantine value. In: Proceedings of the 14th International Conference on Principles of Distributed Systems (OPODIS\u2019010). LNCS, vol. 6490, pp. 144\u2013159. Springer, Berlin (2010)"},{"key":"269_CR29","doi-asserted-by":"crossref","unstructured":"Most\u00e9faoui, A., Raynal, M.: Signature-free asynchronous Byzantine systems: from multivalued to binary consensus with $$t<n\/3$$ t < n \/ 3 , $$O(n^2)$$ O ( n 2 ) messages, and constant time. In: Proceedings of the 22nd International Colloquium on Structural Information and Communication Complexity (SIROCCO\u201915). LNCS, vol. 9439, pp. 194\u2013208. Springer, Berlin (2015)","DOI":"10.1007\/978-3-319-25258-2_14"},{"key":"269_CR30","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/S0020-0190(00)00027-2","volume":"73","author":"A Most\u00e9faoui","year":"2000","unstructured":"Most\u00e9faoui, A., Raynal, M., Tronel, F.: From binary consensus to multivalued consensus in asynchronous message-passing systems. Inf. Process. Lett. 73, 207\u2013213 (2000)","journal-title":"Inf. Process. Lett."},{"key":"269_CR31","doi-asserted-by":"crossref","unstructured":"Patra, A.: Error-free multi-valued broadcast and Byzantine agreement with optimal communication complexity. In: Proceedings of the 15th International Conference on Principles of Distributed Systems (OPODIS\u201910). LNCS, vol. 7109, pp. 34\u201349. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-25873-2_4"},{"key":"269_CR32","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1145\/322186.322188","volume":"27","author":"M Pease","year":"1980","unstructured":"Pease, M., Shostak R, R., Lamport, L.: Reaching agreement in the presence of faults. J. ACM 27, 228\u2013234 (1980)","journal-title":"J. ACM"},{"key":"269_CR33","doi-asserted-by":"crossref","unstructured":"Rabin M.: Randomized Byzantine generals. In: Proceedings of the 24th IEEE Symposium on Foundations of Computer Science (FOCS\u201983), pp. 116\u2013124. IEEE Computer Society Press, New York (1983)","DOI":"10.1109\/SFCS.1983.48"},{"key":"269_CR34","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-031-02000-1","volume-title":"Communication and Agreement Abstractions for Fault-Tolerant Asynchronous Distributed Systems","author":"M Raynal","year":"2010","unstructured":"Raynal, M.: Communication and Agreement Abstractions for Fault-Tolerant Asynchronous Distributed Systems. Morgan & Claypool, San Rafael (2010)"},{"key":"269_CR35","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-031-02001-8","volume-title":"Fault-Tolerant Agreement in Synchronous Message-Passing Systems","author":"M Raynal","year":"2010","unstructured":"Raynal, M.: Fault-Tolerant Agreement in Synchronous Message-Passing Systems. Morgan & Claypool, San Rafael (2010)"},{"key":"269_CR36","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-32027-9","volume-title":"Concurrent Programming: Algorithms, Principles and Foundations","author":"M Raynal","year":"2013","unstructured":"Raynal, M.: Concurrent Programming: Algorithms, Principles and Foundations. Springer, Berlin (2013)"},{"key":"269_CR37","doi-asserted-by":"crossref","unstructured":"Toueg, S.: Randomized Byzantine agreement. In: Proceedings of the 3rd Annual ACM Symposium on Principles of Distributed Computing (PODC\u201984), pp. 163\u2013178. ACM Press, New York (1984)","DOI":"10.1145\/800222.806744"},{"key":"269_CR38","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0020-0190(84)90027-9","volume":"18","author":"R Turpin","year":"1984","unstructured":"Turpin, R., Coan, B.A.: Extending binary Byzantine agreement to multivalued Byzantine agreement. Inf. Process. Lett. 18, 73\u201376 (1984)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"269_CR39","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1049\/iet-sen.2010.0013","volume":"5","author":"H Zhang","year":"2011","unstructured":"Zhang, H., Zhao, W., Moser, L.E., Melliar-Smith, P.M.: Design and implementation of a Byzantine fault tolerance framework for non-deterministic applications. IET Softw. 5(3), 342\u2013356 (2011)","journal-title":"IET Softw."},{"issue":"17","key":"269_CR40","doi-asserted-by":"crossref","first-page":"1005","DOI":"10.1016\/j.ipl.2009.06.004","volume":"109","author":"J Zhang","year":"2009","unstructured":"Zhang, J., Chen, W.: Bounded cost algorithms for multivalued consensus using binary consensus instances. Inf. Process. Lett. 109(17), 1005\u20131009 (2009)","journal-title":"Inf. Process. Lett."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-016-0269-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-016-0269-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-016-0269-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-016-0269-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T22:56:48Z","timestamp":1748905008000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-016-0269-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,4,29]]},"references-count":40,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2017,8]]}},"alternative-id":["269"],"URL":"https:\/\/doi.org\/10.1007\/s00236-016-0269-y","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,4,29]]}}}