{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:54:29Z","timestamp":1773482069559,"version":"3.50.1"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,1,8]],"date-time":"2024-01-08T00:00:00Z","timestamp":1704672000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,8]],"date-time":"2024-01-08T00:00:00Z","timestamp":1704672000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2024,3]]},"DOI":"10.1007\/s00446-023-00459-9","type":"journal-article","created":{"date-parts":[[2024,1,8]],"date-time":"2024-01-08T20:01:53Z","timestamp":1704744113000},"page":"19-33","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Expected linear round synchronization: the missing link for linear Byzantine SMR"],"prefix":"10.1007","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9092-4327","authenticated-orcid":false,"given":"Oded","family":"Naor","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6417-1250","authenticated-orcid":false,"given":"Idit","family":"Keidar","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,1,8]]},"reference":[{"issue":"2","key":"459_CR1","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)"},{"key":"459_CR2","unstructured":"Castro, M., Liskov, B.: Practical Byzantine fault tolerance. In: OSDI 99, 173\u2013186 (1999)"},{"key":"459_CR3","doi-asserted-by":"crossref","unstructured":"Gueta, G.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: 2019 49th Annual IEEE\/IFIP International Conference on Dependable Systems and Networks (DSN), pp. 568\u2013580 (2019). IEEE","DOI":"10.1109\/DSN.2019.00063"},{"key":"459_CR4","unstructured":"Baudet, M., Ching, A., Chursin, A., Danezis, G., Garillot, F., Li, Z., Malkhi, D., Naor, O., Perelman, D., Sonnino, A.: State machine replication in the libra blockchain. Technical Report, Calibra (2019)"},{"key":"459_CR5","doi-asserted-by":"crossref","unstructured":"Yin, M., Malkhi, D., Reiter\u00a0and, M., Gueta, G.G., Abraham, I.: HotStuff: BFT consensus with linearity and responsiveness. In: 38th ACM Symposium on Principles of Distributed Computing (PODC\u201919) (2019)","DOI":"10.1145\/3293611.3331591"},{"key":"459_CR6","doi-asserted-by":"crossref","unstructured":"Kotla, R., Alvisi, L., Dahlin, M., Clement, A., Wong, E.: Zyzzyva: speculative byzantine fault tolerance. In: ACM SIGOPS Operating Systems Review, vol. 41, pp. 45\u201358 (2007). ACM","DOI":"10.1145\/1323293.1294267"},{"key":"459_CR7","unstructured":"Buchman, E., Kwon, J., Milosevic, Z.: The latest gossip on BFT consensus. arXiv preprint arXiv:1807.04938 (2018)"},{"key":"459_CR8","unstructured":"Buterin, V., Griffith, V.: Casper the friendly finality gadget. arXiv preprint arXiv:1710.09437 (2017)"},{"key":"459_CR9","doi-asserted-by":"crossref","unstructured":"Gelashvili, R., Kokoris-Kogias, L., Sonnino, A., Spiegelman, A., Xiang, Z.: Jolteon and ditto: network-adaptive efficient consensus with asynchronous fallback. In: Financial Cryptography and Data Security: 26th International Conference, FC 2022, Grenada, May 2\u20136, 2022, Revised Selected Papers, pp. 296\u2013315 (2022). Springer","DOI":"10.1007\/978-3-031-18283-9_14"},{"key":"459_CR10","doi-asserted-by":"crossref","unstructured":"Dolev, D., Reischuk, R.: Bounds on information exchange for Byzantine agreement. In: Proceedings of the First ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. PODC \u201982, pp. 132\u2013140. Association for Computing Machinery, New York, NY, USA (1982)","DOI":"10.1145\/800220.806690"},{"key":"459_CR11","doi-asserted-by":"crossref","unstructured":"Naor, O., Baudet, M., Malkhi, D., Spiegelman, A.: Cogsworth: Byzantine view synchronization. In: Proceedings of the Cryptoeconomic Systems Conference (CES\u201920) (2020)","DOI":"10.21428\/58320208.08912a03"},{"key":"459_CR12","unstructured":"Naor, O., Keidar, I.: Expected linear round synchronization: the missing link for linear Byzantine SMR. In: 34th International Symposium on Distributed Computing (DISC 2020) (2020). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik"},{"key":"459_CR13","doi-asserted-by":"crossref","unstructured":"Boneh, D., Lynn, B., Shacham, H.: Short signatures from the weil pairing. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 514\u2013532 (2001). Springer","DOI":"10.1007\/3-540-45682-1_30"},{"issue":"3","key":"459_CR14","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)","journal-title":"J. Cryptol."},{"key":"459_CR15","doi-asserted-by":"crossref","unstructured":"Shoup, V.: Practical threshold signatures. In: Advances in Cryptology-EUROCRYPT 2000: International Conference on the Theory and Application of Cryptographic Techniques Bruges, Belgium, May 14\u201318, 2000 Proceedings 19, pp. 207\u2013220 (2000). Springer","DOI":"10.1007\/3-540-45539-6_15"},{"key":"459_CR16","doi-asserted-by":"crossref","unstructured":"Libert, B., Joye, M., Yung, M.: Born and raised distributively: fully distributed non-interactive adaptively-secure threshold signatures with short shares. In: Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, pp. 303\u2013312 (2014)","DOI":"10.1145\/2611462.2611498"},{"issue":"3","key":"459_CR17","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)","journal-title":"J. Cryptol."},{"key":"459_CR18","unstructured":"Loss, J., Moran, T.: Combining asynchronous and synchronous byzantine agreement: the best of both worlds. Cryptology ePrint Archive (2018)"},{"key":"459_CR19","doi-asserted-by":"crossref","unstructured":"Keidar, I., Kokoris-Kogias, E., Naor, O., Spiegelman, A.: All you need is dag. In: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, pp. 165\u2013175 (2021)","DOI":"10.1145\/3465084.3467905"},{"key":"459_CR20","doi-asserted-by":"crossref","unstructured":"Spiegelman, A., Giridharan, N., Sonnino, A., Kokoris-Kogias, L.: Bullshark: DAG BFT protocols made practical. In: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pp. 2705\u20132718 (2022)","DOI":"10.1145\/3548606.3559361"},{"key":"459_CR21","unstructured":"Keidar, I., Naor, O., Poupko, O., Shapiro, E.: Cordial miners: fast and efficient consensus for every eventuality. In: 37th International Symposium on Distributed Computing (DISC 2023) (2023). Schloss-Dagstuhl-Leibniz Zentrum f\u00fcr Informatik"},{"key":"459_CR22","doi-asserted-by":"crossref","unstructured":"Abraham, I., Malkhi, D., Spiegelman, A.: Asymptotically optimal validated asynchronous Byzantine agreement. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pp. 337\u2013346 (2019)","DOI":"10.1145\/3293611.3331612"},{"key":"459_CR23","doi-asserted-by":"crossref","unstructured":"Kokoris\u00a0Kogias, E., Malkhi, D., Spiegelman, A.: Asynchronous distributed key generation for computationally-secure randomness, consensus, and threshold signatures. In: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pp. 1751\u20131767 (2020)","DOI":"10.1145\/3372297.3423364"},{"key":"459_CR24","doi-asserted-by":"crossref","unstructured":"Das, S., Yurek, T., Xiang, Z., Miller, A., Kokoris-Kogias, L., Ren, L.: Practical asynchronous distributed key generation. In: 2022 IEEE Symposium on Security and Privacy (SP), pp. 2518\u20132534 (2022). IEEE","DOI":"10.1109\/SP46214.2022.9833584"},{"issue":"4","key":"459_CR25","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1145\/146585.146588","volume":"39","author":"A Borodin","year":"1992","unstructured":"Borodin, A., Linial, N., Saks, M.E.: An optimal on-line algorithm for metrical task system. J. ACM (JACM) 39(4), 745\u2013763 (1992)","journal-title":"J. ACM (JACM)"},{"issue":"1","key":"459_CR26","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/BF01294260","volume":"11","author":"S Ben-David","year":"1994","unstructured":"Ben-David, S., Borodin, A., Karp, R., Tardos, G., Wigderson, A.: On the power of randomization in on-line algorithms. Algorithmica 11(1), 2\u201314 (1994)","journal-title":"Algorithmica"},{"issue":"4","key":"459_CR27","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1016\/0196-6774(91)90041-V","volume":"12","author":"A Fiat","year":"1991","unstructured":"Fiat, A., Karp, R.M., Luby, M., McGeoch, L.A., Sleator, D.D., Young, N.E.: Competitive paging algorithms. J. Algorithms 12(4), 685\u2013699 (1991)","journal-title":"J. Algorithms"},{"issue":"2","key":"459_CR28","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)","journal-title":"Inf. Comput."},{"issue":"4","key":"459_CR29","first-page":"18","volume":"32","author":"L Lamport","year":"2001","unstructured":"Lamport, L.: Paxos made simple. ACM Sigact News 32(4), 18\u201325 (2001)","journal-title":"ACM Sigact News"},{"key":"459_CR30","doi-asserted-by":"crossref","unstructured":"Oki, B.M., Liskov, B.H.: Viewstamped replication: a new primary copy method to support highly-available distributed systems. In: Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, pp. 8\u201317 (1988). ACM","DOI":"10.1145\/62546.62549"},{"key":"459_CR31","doi-asserted-by":"crossref","unstructured":"Keidar, I., Dolev, D.: Efficient message ordering in dynamic networks. In: Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, pp. 68\u201376 (1996)","DOI":"10.1145\/248052.248062"},{"key":"459_CR32","doi-asserted-by":"crossref","unstructured":"Birman, K., Joseph, T.: Exploiting virtual synchrony in distributed systems. In: Proceedings of the Eleventh ACM Symposium on Operating Systems Principles, pp. 123\u2013138 (1987)","DOI":"10.1145\/37499.37515"},{"issue":"4","key":"459_CR33","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1145\/4221.4227","volume":"32","author":"B Awerbuch","year":"1985","unstructured":"Awerbuch, B.: Complexity of network synchronization. J. ACM (JACM) 32(4), 804\u2013823 (1985)","journal-title":"J. ACM (JACM)"},{"key":"459_CR34","unstructured":"Ford, B.: Threshold logical clocks for asynchronous distributed coordination and consensus. arXiv preprint arXiv:1907.07010 (2019)"},{"key":"459_CR35","doi-asserted-by":"crossref","unstructured":"Keidar, I., Shraer, A.: Timeliness, failure-detectors, and consensus performance. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Principles of Distributed Computing, pp. 169\u2013178 (2006)","DOI":"10.1145\/1146381.1146408"},{"issue":"10","key":"459_CR36","doi-asserted-by":"publisher","first-page":"1367","DOI":"10.1109\/TPDS.2008.16","volume":"19","author":"I Keidar","year":"2008","unstructured":"Keidar, I., Shraer, A.: How to choose a timing model. IEEE Trans. Parallel Distrib. Syst. 19(10), 1367\u20131380 (2008)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"459_CR37","doi-asserted-by":"crossref","unstructured":"Gafni, E.: Round-by-round fault detectors (extended abstract) unifying synchrony and asynchrony. In: Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, pp. 143\u2013152 (1998)","DOI":"10.1145\/277697.277724"},{"key":"459_CR38","unstructured":"Bravo, M., Chockler, G., Gotsman, A.: Making Byzantine consensus live. In: 34st International Symposium on Distributed Computing (DISC 2020) (2020). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik"},{"key":"459_CR39","doi-asserted-by":"crossref","unstructured":"Ramasamy, H.V., Cachin, C.: Parsimonious asynchronous Byzantine-fault-tolerant atomic broadcast. In: International Conference on Principles of Distributed Systems, pp. 88\u2013102 (2005). Springer","DOI":"10.1007\/11795490_9"},{"issue":"1","key":"459_CR40","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. ACM SIGACT News 52(1), 71\u201380 (2021)","journal-title":"ACM SIGACT News"},{"key":"459_CR41","doi-asserted-by":"crossref","unstructured":"Cohen, S., Keidar, I., Spiegelman, A.: Not a COINcidence: sub-quadratic asynchronous Byzantine agreement WHP. In: 34st International Symposium on Distributed Computing (DISC 2020) (2020). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik","DOI":"10.1145\/3382734.3405708"},{"key":"459_CR42","doi-asserted-by":"crossref","unstructured":"Blum, E., Katz, J., Liu-Zhang, C.-D., Loss, J.: Asynchronous Byzantine agreement with subquadratic communication. Cryptology ePrint Archive, Report 2020\/851 (2020)","DOI":"10.1007\/978-3-030-64375-1_13"},{"key":"459_CR43","doi-asserted-by":"crossref","unstructured":"Civit, P., Dzulfikar, M.A., Gilbert, S., Gramoli, V., Guerraoui, R., Komatovic, J., Ribeiro\u00a0Vidigueira, M.J.: Byzantine consensus is $$\\theta (n^2)$$: the Dolev-Reischuk bound is tight even in partial synchrony! Technical report, Dagstuhl Publishing (2022)","DOI":"10.21203\/rs.3.rs-2526543\/v1"},{"key":"459_CR44","unstructured":"Lewis-Pye, A.: Quadratic worst-case message complexity for state machine replication in the partial synchrony model. arXiv preprint arXiv:2201.01107 (2022)"},{"key":"459_CR45","unstructured":"Lewis-Pye, A., Abraham, I.: Fever: Optimal responsive view synchronisation. arXiv preprint arXiv:2301.09881 (2023)"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-023-00459-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-023-00459-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-023-00459-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T18:10:15Z","timestamp":1731003015000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-023-00459-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,8]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["459"],"URL":"https:\/\/doi.org\/10.1007\/s00446-023-00459-9","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,8]]},"assertion":[{"value":"24 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 November 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 January 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}