{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T07:42:11Z","timestamp":1774942931001,"version":"3.50.1"},"reference-count":61,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,12,11]],"date-time":"2023-12-11T00:00:00Z","timestamp":1702252800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,12,11]],"date-time":"2023-12-11T00:00:00Z","timestamp":1702252800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"EPFL Lausanne"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2024,6]]},"abstract":"Abstract<\/jats:title>\n \n The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has (at least) quadratic (in the number of processes) communication complexity in the worst case: given a system with\n n<\/jats:italic>\n processes and at most\n \n \n $$f < n \/ 3$$<\/jats:tex-math>\n \n \n f<\/mml:mi>\n <<\/mml:mo>\n n<\/mml:mi>\n \/<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n failures, any solution to Byzantine consensus exchanges\n \n \n $$\\Omega \\big (n^2\\big )$$<\/jats:tex-math>\n \n \n \u03a9<\/mml:mi>\n \n (<\/mml:mo>\n <\/mml:mrow>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n words, where a word contains a constant number of values and signatures. While it has been shown that the bound is tight in synchronous environments, it is still unknown whether a consensus protocol with quadratic communication complexity can be obtained in partial synchrony where the network alternates between (1) asynchronous periods, with unbounded message delays, and (2) synchronous periods, with\n \n \n $$\\delta $$<\/jats:tex-math>\n \n \u03b4<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -bounded message delays. Until now, the most efficient known solutions for Byzantine consensus in partially synchronous settings had cubic communication complexity (e.g., HotStuff, binary DBFT). This paper closes the existing gap by introducing\n SQuad<\/jats:sc>\n , a partially synchronous Byzantine consensus protocol with\n \n \n $$O\\big (n^2\\big )$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n \n (<\/mml:mo>\n <\/mml:mrow>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n worst-case communication complexity. In addition,\n SQuad<\/jats:sc>\n is optimally-resilient (tolerating up to\n \n \n $$f < n \/ 3$$<\/jats:tex-math>\n \n \n f<\/mml:mi>\n <<\/mml:mo>\n n<\/mml:mi>\n \/<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n failures) and achieves\n \n \n $$O(f \\cdot \\delta )$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n f<\/mml:mi>\n \u00b7<\/mml:mo>\n \u03b4<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n worst-case latency complexity. The key technical contribution underlying\n SQuad<\/jats:sc>\n lies in the way we solve\n view synchronization<\/jats:italic>\n , the problem of bringing all correct processes to the same view with a correct leader for sufficiently long. Concretely, we present\n RareSync<\/jats:sc>\n , a view synchronization protocol with\n \n \n $$O\\big (n^2\\big )$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n \n (<\/mml:mo>\n <\/mml:mrow>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n communication complexity and\n \n \n $$O(f \\cdot \\delta )$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n f<\/mml:mi>\n \u00b7<\/mml:mo>\n \u03b4<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n latency complexity, which we utilize in order to obtain\n SQuad<\/jats:sc>\n .\n <\/jats:p>","DOI":"10.1007\/s00446-023-00458-w","type":"journal-article","created":{"date-parts":[[2023,12,11]],"date-time":"2023-12-11T02:02:16Z","timestamp":1702260136000},"page":"89-119","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Byzantine consensus is $$\\Theta (n^2)$$: the Dolev-Reischuk bound is tight even in partial synchrony!"],"prefix":"10.1007","volume":"37","author":[{"given":"Pierre","family":"Civit","sequence":"first","affiliation":[]},{"given":"Muhammad Ayaz","family":"Dzulfikar","sequence":"additional","affiliation":[]},{"given":"Seth","family":"Gilbert","sequence":"additional","affiliation":[]},{"given":"Vincent","family":"Gramoli","sequence":"additional","affiliation":[]},{"given":"Rachid","family":"Guerraoui","sequence":"additional","affiliation":[]},{"given":"Jovan","family":"Komatovic","sequence":"additional","affiliation":[]},{"given":"Manuel","family":"Vidigueira","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,12,11]]},"reference":[{"issue":"3","key":"458_CR1","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/357172.357176","volume":"4","author":"L Lamport","year":"1982","unstructured":"Lamport, L., Shostak, 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":"458_CR2","doi-asserted-by":"crossref","unstructured":"Crain, T., Gramoli, V., Larrea, M., Raynal, M.: DBFT: Efficient Byzantine consensus with a weak coordinator and its application to consortium blockchains. In: 17th IEEE International Symposium on Network Computing and Applications NCA, pp. 1\u201341 (2017)","DOI":"10.1109\/NCA.2018.8548057"},{"key":"458_CR3","doi-asserted-by":"publisher","unstructured":"Abraham, I., Malkhi, D., Nayak, K., Ren, L., Spiegelman, A.: Solida: a blockchain protocol based on reconfigurable byzantine consensus. In: Aspnes, J., Bessani, A., Felber, P., Leit\u00e3o, J. (eds.) 21st International Conference on Principles of Distributed Systems, OPODIS 2017, Lisbon, Portugal, 18\u201320 Dec, 2017. LIPIcs, vol. 95, pp. 25\u201312519. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.OPODIS.2017.25","DOI":"10.4230\/LIPIcs.OPODIS.2017.25"},{"key":"458_CR4","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1016\/j.future.2017.09.023","volume":"107","author":"V Gramoli","year":"2020","unstructured":"Gramoli, V.: From blockchain consensus back to Byzantine consensus. Future Gener. Comput. Syst. 107, 760\u2013769 (2020)","journal-title":"Future Gener. Comput. Syst."},{"issue":"1","key":"458_CR5","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/s10796-013-9460-7","volume":"16","author":"J Lim","year":"2014","unstructured":"Lim, J., Suh, T., Gil, J., Yu, H.: Scalable and leaderless Byzantine consensus in cloud computing environments. Inf. Syst. Front. 16(1), 19\u201334 (2014)","journal-title":"Inf. Syst. Front."},{"issue":"1","key":"458_CR6","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1145\/2455.214112","volume":"32","author":"D Dolev","year":"1985","unstructured":"Dolev, D., Reischuk, R.: Bounds on information exchange for Byzantine agreement. J. ACM (JACM) 32(1), 191\u2013204 (1985)","journal-title":"J. ACM (JACM)"},{"key":"458_CR7","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/978-1-4615-3422-8_27","volume-title":"Computer Science: Research and Applications","author":"P Berman","year":"1992","unstructured":"Berman, P., Garay, J.A., Perry, K.J.: Bit optimal distributed consensus. In: Computer Science: Research and Applications, pp. 313\u2013321. Springer, Boston (1992)"},{"key":"458_CR8","doi-asserted-by":"publisher","unstructured":"Momose, A., Ren, L.: Optimal communication complexity of authenticated Byzantine agreement. In: Gilbert, S. (ed.) 35th International Symposium on Distributed Computing, DISC 2021, 4\u20138 Oct, 2021, Freiburg, Germany (Virtual Conference). LIPIcs, vol. 209, pp. 32\u201313216. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2021.32","DOI":"10.4230\/LIPIcs.DISC.2021.32"},{"issue":"2","key":"458_CR9","doi-asserted-by":"publisher","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 (JACM) 35(2), 288\u2013323 (1988)","journal-title":"J. ACM (JACM)"},{"issue":"2","key":"458_CR10","doi-asserted-by":"publisher","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. Assoc. Comput. Mach. 32(2), 374\u2013382 (1985)","journal-title":"J. Assoc. Comput. Mach."},{"key":"458_CR11","doi-asserted-by":"publisher","unstructured":"Spiegelman, A.: In search for an optimal authenticated Byzantine agreement. In: Gilbert, S. (ed.) 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), vol. 209, pp. 38\u201313819. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2021). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2021.38. https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2021\/14840","DOI":"10.4230\/LIPIcs.DISC.2021.38"},{"issue":"1","key":"458_CR12","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1145\/3457588.3457600","volume":"52","author":"S Cohen","year":"2021","unstructured":"Cohen, S., Keidar, I., Naor, O.: Byzantine agreement with less communication: recent advances. SIGACT News 52(1), 71\u201380 (2021). https:\/\/doi.org\/10.1145\/3457588.3457600","journal-title":"SIGACT News"},{"key":"458_CR13","doi-asserted-by":"crossref","unstructured":"Yin, M., Malkhi, D., Reiter, M.K., Gueta, G.G., Abraham, I.: HotStuff: BFT consensus with linearity and responsiveness. In: Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, pp. 347\u2013356 (2019)","DOI":"10.1145\/3293611.3331591"},{"key":"458_CR14","unstructured":"The Diem Team: DiemBFT v4: State Machine Replication in the Diem Blockchain (2021). https:\/\/developers.diem.com\/papers\/diem-consensus-state-machine-replication-in-the-diem-blockchain\/2021-08-17.pdf"},{"key":"458_CR15","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1145\/571637.571640","volume":"20","author":"M Castro","year":"2002","unstructured":"Castro, M., Liskov, B.: Practical Byzantine fault tolerance. ACM Trans. Comput. Syst. 20, 359\u2013368 (2002)","journal-title":"ACM Trans. Comput. Syst."},{"key":"458_CR16","unstructured":"Buchman, E., Kwon, J., Milosevic, Z.: The latest gossip on BFT consensus, pp. 1\u201314 (2018). arXiv:1807.04938"},{"issue":"4","key":"458_CR17","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1137\/0212045","volume":"12","author":"D Dolev","year":"1983","unstructured":"Dolev, D., Strong, H.R.: Authenticated algorithms for Byzantine agreement. SIAM J. Comput. 12(4), 656\u2013666 (1983)","journal-title":"SIAM J. Comput."},{"key":"458_CR18","doi-asserted-by":"publisher","unstructured":"Abraham, I., Devadas, S., Nayak, K., Ren, L.: Brief announcement: practical synchronous byzantine consensus. In: Richa, A.W. (ed.) 31st International Symposium on Distributed Computing, DISC 2017, 16\u201320 Oct, 2017, Vienna, Austria. LIPIcs, vol. 91, pp. 41\u20131414. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2017.41","DOI":"10.4230\/LIPIcs.DISC.2017.41"},{"key":"458_CR19","doi-asserted-by":"crossref","unstructured":"Locher, T.: Fast Byzantine agreement for permissioned distributed ledgers. In: Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 371\u2013382 (2020)","DOI":"10.1145\/3350755.3400219"},{"key":"458_CR20","unstructured":"Micali, S.: Byzantine agreement, made trivial (2017). https:\/\/people.csail.mit.edu\/silvio\/Selected%20Scientific%20Papers\/Distributed%20Computation\/BYZANTYNE%20AGREEMENT%20MADE%20TRIVIAL.pdf"},{"key":"458_CR21","doi-asserted-by":"crossref","unstructured":"Ben-Or, M.: Another advantage of free choice: completely asynchronous agreement protocols. In: Proceedings of the Second Annual Symposium on Principles of Distributed Computing, pp. 27\u201330 (1983)","DOI":"10.1145\/800221.806707"},{"key":"458_CR22","doi-asserted-by":"crossref","unstructured":"Abraham, I., Malkhi, D., Spiegelman, A.: Asymptotically optimal validated asynchronous Byzantine agreement. In: Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, pp. 337\u2013346 (2019)","DOI":"10.1145\/3293611.3331612"},{"key":"458_CR23","doi-asserted-by":"crossref","unstructured":"Lu, Y., Lu, Z., Tang, Q., Wang, G.: Dumbo-MVBA: optimal multi-valued validated asynchronous byzantine agreement, revisited. In: Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, pp. 129\u2013138 (2020)","DOI":"10.1145\/3382734.3405707"},{"key":"458_CR24","doi-asserted-by":"publisher","unstructured":"Abraham, I., Chan, T.H.H., Dolev, D., Nayak, K., Pass, R., Ren, L., Shi, E.: Communication complexity of Byzantine agreement, revisited. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. PODC \u201919, pp. 317\u2013326. Association for Computing Machinery, New York, NY, USA (2019). https:\/\/doi.org\/10.1145\/3293611.3331629","DOI":"10.1145\/3293611.3331629"},{"key":"458_CR25","unstructured":"Chen, J., Gorbunov, S., Micali, S., Vlachos, G.: Algorand agreement: super fast and partition resilient Byzantine agreement. Cryptology ePrint Archive, pp. 1\u201310 (2018)"},{"key":"458_CR26","doi-asserted-by":"crossref","unstructured":"Cohen, S., Keidar, I., Spiegelman, A.: Brief announcement: not a COINcidence: sub-quadratic asynchronous Byzantine agreement WHP. In: Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, pp. 175\u2013177 (2020)","DOI":"10.1145\/3382734.3405708"},{"issue":"4","key":"458_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1989727.1989732","volume":"58","author":"V King","year":"2011","unstructured":"King, V., Saia, J.: Breaking the $$O(n^2)$$ bit barrier: scalable Byzantine agreement with an adaptive adversary. J. ACM 58(4), 1\u201324 (2011)","journal-title":"J. ACM"},{"key":"458_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2016.02.031","volume":"645","author":"B Libert","year":"2016","unstructured":"Libert, B., Joye, M., Yung, M.: Born and raised distributively: fully distributed non-interactive adaptively-secure threshold signatures with short shares. Theor. Comput. Sci. 645, 1\u201324 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"458_CR29","doi-asserted-by":"publisher","unstructured":"Abraham, I., Ben-David, N., Yandamuri, S.: Efficient and adaptively secure asynchronous binary agreement via binding crusader agreement. In: Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, vol. 1, pp. 381\u2013391 (2022). https:\/\/doi.org\/10.1145\/3519270.3538426","DOI":"10.1145\/3519270.3538426"},{"key":"458_CR30","doi-asserted-by":"publisher","first-page":"13121","DOI":"10.1145\/2785953","volume":"62","author":"A Most\u00e9faoui","year":"2015","unstructured":"Most\u00e9faoui, A., Moumen, H., Raynal, M.: Signature-free asynchronous binary Byzantine consensus with t< n\/3, O(n2) messages, and O(1) expected time. J. ACM 62, 13121 (2015). https:\/\/doi.org\/10.1145\/2785953","journal-title":"J. ACM"},{"key":"458_CR31","doi-asserted-by":"publisher","unstructured":"de Souza, L.F., Kuznetsov, P., Tonkikh, A.: Distributed randomness from approximate agreement. In: Scheideler, C. (ed.) 36th International Symposium on Distributed Computing, DISC 2022, 25\u201327 Oct, 2022, Augusta, Georgia, USA. LIPIcs, vol. 246, pp. 24\u201312421. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2022.24","DOI":"10.4230\/LIPIcs.DISC.2022.24"},{"issue":"2","key":"458_CR32","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/s00145-023-09451-9","volume":"36","author":"A Choudhury","year":"2023","unstructured":"Choudhury, A., Patra, A.: On the communication efficiency of statistically secure asynchronous MPC with optimal resilience. J. Cryptol. 36(2), 13 (2023). https:\/\/doi.org\/10.1007\/s00145-023-09451-9","journal-title":"J. Cryptol."},{"issue":"2","key":"458_CR33","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1016\/0890-5401(87)90054-X","journal-title":"Inf. Comput."},{"key":"458_CR34","doi-asserted-by":"publisher","unstructured":"Andrychowicz, M., Dziembowski, S.: PoW-based distributed cryptography with no trusted setup. In: Gennaro, R., Robshaw, M. (eds.) Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, 16\u201320 Aug, 2015, Proceedings, Part II. Lecture Notes in Computer Science, vol. 9216, pp. 379\u2013399. Springer (2015). https:\/\/doi.org\/10.1007\/978-3-662-48000-7_19","DOI":"10.1007\/978-3-662-48000-7_19"},{"key":"458_CR35","doi-asserted-by":"publisher","unstructured":"Garay, J.A., Kiayias, A., Leonardos, N., Panagiotakos, G.: Bootstrapping the blockchain, with applications to consensus and fast PKI setup. In: Abdalla, M., Dahab, R. (eds.) Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Rio de Janeiro, Brazil, 25\u201329 Mar, 2018, Proceedings, Part II. Lecture Notes in Computer Science, vol. 10770, pp. 465\u2013495. Springer (2018). https:\/\/doi.org\/10.1007\/978-3-319-76581-5_16","DOI":"10.1007\/978-3-319-76581-5_16"},{"key":"458_CR36","doi-asserted-by":"publisher","unstructured":"Abraham, I., Jovanovic, P., Maller, M., Meiklejohn, S., Stern, G., Tomescu, A.: Reaching consensus for asynchronous distributed key generation. In: Miller, A., Censor-Hillel, K., Korhonen, J.H. (eds.) PODC \u201921: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, 26\u201330 July, 2021, pp. 363\u2013373. ACM (2021). https:\/\/doi.org\/10.1145\/3465084.3467914","DOI":"10.1145\/3465084.3467914"},{"issue":"3","key":"458_CR37","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/s00145-005-0318-0","volume":"18","author":"C Cachin","year":"2005","unstructured":"Cachin, C., Kursawe, K., Shoup, V.: Random oracles in Constantinople: practical asynchronous Byzantine agreement using cryptography. J. Cryptol. 18(3), 219\u2013246 (2005). https:\/\/doi.org\/10.1007\/s00145-005-0318-0","journal-title":"J. Cryptol."},{"key":"458_CR38","doi-asserted-by":"publisher","unstructured":"Rabin, M.O.: Randomized Byzantine generals. In: 24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 7\u20139 Nov, 1983, pp. 403\u2013409. IEEE Computer Society (1983). https:\/\/doi.org\/10.1109\/SFCS.1983.48","DOI":"10.1109\/SFCS.1983.48"},{"key":"458_CR39","doi-asserted-by":"crossref","unstructured":"Gafni, E.: Round-by-round fault detectors: unifying synchrony and asynchrony. In: Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, pp. 143\u2013152 (1998)","DOI":"10.1145\/277697.277724"},{"issue":"4","key":"458_CR40","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1109\/TC.2004.1268403","volume":"53","author":"R Guerraoui","year":"2004","unstructured":"Guerraoui, R., Raynal, M.: The information structure of indulgent consensus. IEEE Trans. Comput. 53(4), 453\u2013466 (2004)","journal-title":"IEEE Trans. Comput."},{"key":"458_CR41","doi-asserted-by":"crossref","unstructured":"Keidar, I., Shraer, A.: Timeliness, failure-detectors, and consensus performance. In: Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, vol. 2006, pp. 169\u2013178 (2006)","DOI":"10.1145\/1146381.1146408"},{"key":"458_CR42","doi-asserted-by":"crossref","unstructured":"Golan Gueta, G., Abraham, I., Grossman, S., Malkhi, D., Pinkas, B., Reiter, M., Seredinschi, D.A., Tamir, O., Tomescu, A.: SBFT: a scalable and decentralized trust infrastructure. In: Proceedings - 49th Annual IEEE\/IFIP International Conference on Dependable Systems and Networks, DSN 2019, pp. 568\u2013580 (2019)","DOI":"10.1109\/DSN.2019.00063"},{"key":"458_CR43","doi-asserted-by":"crossref","unstructured":"Martin, J.P., Alvisi, L.: Fast Byzantine consensus. In: Proceedings of the International Conference on Dependable Systems and Networks, pp. 402\u2013411 (2005)","DOI":"10.1109\/DSN.2005.48"},{"key":"458_CR44","doi-asserted-by":"crossref","unstructured":"Ramasamy, H.G.V., Cachin, C.: Parsimonious asynchronous Byzantine-fault-tolerant atomic broadcast. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3974 LNCS, pp. 88\u2013102 (2006)","DOI":"10.1007\/11795490_9"},{"issue":"4","key":"458_CR45","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1658357.1658358","volume":"27","author":"R Kotla","year":"2009","unstructured":"Kotla, R., Alvisi, L., Dahlin, M., Clement, A., Wong, E.: Zyzzyva: speculative Byzantine fault tolerance. ACM Trans. Comput. Syst. 27(4), 1\u201339 (2009)","journal-title":"ACM Trans. Comput. Syst."},{"key":"458_CR46","doi-asserted-by":"crossref","unstructured":"Kuznetsov, P., Tonkikh, A., Zhang, Y.X.: Revisiting optimal resilience of fast Byzantine consensus. In: Proceedings of the Annual ACM Symposium on Principles of Distributed Computing (PODC), vol. 1, pp. 343\u2013353 (2021)","DOI":"10.1145\/3465084.3467924"},{"key":"458_CR47","doi-asserted-by":"crossref","unstructured":"Pass, R., Shi, E.: Thunderella: blockchains with optimistic instant confirmation. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10821 LNCS, pp. 3\u201333 (2018)","DOI":"10.1007\/978-3-319-78375-8_1"},{"key":"458_CR48","doi-asserted-by":"crossref","unstructured":"Naor, O., Baudet, M., Malkhi, D., Spiegelman, A.: Cogsworth: Byzantine view synchronization. Cryptoeconomic systems (2021)","DOI":"10.21428\/58320208.08912a03"},{"key":"458_CR49","unstructured":"Naor, O., Keidar, I.: Expected linear round synchronization: the missing link for linear Byzantine SMR. In: 34th International Symposium on Distributed Computing (DISC), vol. 179 (2020)"},{"key":"458_CR50","unstructured":"Bravo, M., Chockler, G., Gotsman, A.: Making Byzantine consensus live. In: 34th International Symposium on Distributed Computing (DISC), vol. 179, pp. 1\u201317 (2020)"},{"key":"458_CR51","doi-asserted-by":"crossref","unstructured":"Chandra, T., Toueg, S.: Unreliable failure detectors for reliable distributed systems. In: Proceedings of the 10th ACM Symposium on Principles of Distributed Computing, pp. 225\u2013267 (1996)","DOI":"10.1145\/226643.226647"},{"key":"458_CR52","doi-asserted-by":"crossref","unstructured":"Chandra, T.D., Hadzilacos, V., Toueg, S.: The weakest failure detector for solving consensus. In: Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, vol. 43, pp. 147\u2013158 (1992)","DOI":"10.21236\/ADA253611"},{"issue":"1","key":"458_CR53","doi-asserted-by":"publisher","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":"458_CR54","doi-asserted-by":"crossref","unstructured":"Antoniadis, K., Desjardins, A., Gramoli, V., Guerraoui, R., Zablotchi, I.: Leaderless consensus. In: Proceedings - International Conference on Distributed Computing Systems, vol. 2021, pp. 392\u2013402 (2021)","DOI":"10.1109\/ICDCS51616.2021.00045"},{"issue":"1","key":"458_CR55","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1145\/200836.200870","volume":"42","author":"D Dolev","year":"1995","unstructured":"Dolev, D., Halpern, J.Y., Simons, B., Strong, R.: Dynamic fault-tolerant clock synchronization. J. ACM (JACM) 42(1), 143\u2013185 (1995)","journal-title":"J. ACM (JACM)"},{"issue":"3","key":"458_CR56","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1145\/28869.28876","volume":"34","author":"TK Srikanth","year":"1987","unstructured":"Srikanth, T.K., Toueg, S.: Optimal clock synchronization. J. Assoc. Comput. Mach. 34(3), 71\u201386 (1987)","journal-title":"J. Assoc. Comput. Mach."},{"key":"458_CR57","unstructured":"Lewis-Pye, A.: Quadratic worst-case message complexity for State Machine Replication in the partial synchrony model (2022). arXiv arXiv:2201.01107"},{"key":"458_CR58","unstructured":"Abraham, I., Gueta, G., Malkhi, D.: Hot-stuff the linear, optimal-resilience, one-message BFT devil. CoRRarXiv:1803.05069 (2018)"},{"key":"458_CR59","unstructured":"Civit, P., Gilbert, S., Guerraoui, R., Komatovic, J., Vidigueira, M.: Strong Byzantine agreement with adaptive word complexity (2023). CoRRarXiv:2308.03524"},{"key":"458_CR60","doi-asserted-by":"publisher","unstructured":"Cohen, S., Keidar, I., Spiegelman, A.: Make every word count: adaptive Byzantine agreement with fewer words. In: Hillel, E., Palmieri, R., Rivi\u00e8re, E. (eds.) 26th International Conference on Principles of Distributed Systems, OPODIS 2022, 13\u201315 Dec, 2022, Brussels, Belgium. LIPIcs, vol. 253, pp. 18\u201311821. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPIcs.OPODIS.2022.18","DOI":"10.4230\/LIPIcs.OPODIS.2022.18"},{"key":"458_CR61","unstructured":"Civit, P., Gilbert, S., Guerraoui, R., Komatovic, J., Monti, M., Vidigueira, M.: Every bit counts in consensus (2023). arXiv preprint arXiv:2306.00431"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-023-00458-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-023-00458-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-023-00458-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,5]],"date-time":"2024-11-05T13:35:14Z","timestamp":1730813714000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-023-00458-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,11]]},"references-count":61,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["458"],"URL":"https:\/\/doi.org\/10.1007\/s00446-023-00458-w","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-2526543\/v1","asserted-by":"object"}]},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,11]]},"assertion":[{"value":"29 January 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 November 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 December 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflicts of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}