{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,7]],"date-time":"2025-12-07T13:09:30Z","timestamp":1765112970649,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,7,17]],"date-time":"2022-07-17T00:00:00Z","timestamp":1658016000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,7,17]],"date-time":"2022-07-17T00:00:00Z","timestamp":1658016000000},"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":[[2023,3]]},"DOI":"10.1007\/s00446-022-00428-8","type":"journal-article","created":{"date-parts":[[2022,7,17]],"date-time":"2022-07-17T06:02:34Z","timestamp":1658037754000},"page":"3-28","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Communication complexity of byzantine agreement, revisited"],"prefix":"10.1007","volume":"36","author":[{"given":"Ittai","family":"Abraham","sequence":"first","affiliation":[]},{"given":"T.-H. Hubert","family":"Chan","sequence":"additional","affiliation":[]},{"given":"Danny","family":"Dolev","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5675-263X","authenticated-orcid":false,"given":"Kartik","family":"Nayak","sequence":"additional","affiliation":[]},{"given":"Rafael","family":"Pass","sequence":"additional","affiliation":[]},{"given":"Ling","family":"Ren","sequence":"additional","affiliation":[]},{"given":"Elaine","family":"Shi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,7,17]]},"reference":[{"key":"428_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Devadas, S., Dolev, D., Nayak, K., Ren, L.: Synchronous byzantine agreement with expected $$O(1)$$ rounds, expected $$O(n^2)$$ communication, and optimal resilience. In: Financial Crypto (2019)","DOI":"10.1007\/978-3-030-32101-7_20"},{"key":"428_CR2","doi-asserted-by":"publisher","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. Wiley, New York (2004)"},{"key":"428_CR3","doi-asserted-by":"crossref","unstructured":"Ben-Or, M.: Another advantage of free choice (extended abstract): completely asynchronous agreement protocols. In: PODC (1983)","DOI":"10.1145\/800221.806707"},{"key":"428_CR4","unstructured":"Bhangale, A., Liu-Zhang, C.D., Loss, J., Nayak, K.: Efficient adaptively-secure byzantine agreement for long messages. Cryptology ePrint Archive, Report 2021\/1403 (2021). https:\/\/ia.cr\/2021\/1403"},{"key":"428_CR5","doi-asserted-by":"crossref","unstructured":"Bitansky, N.: Verifiable random functions from non-interactive witness-indistinguishable proofs. In: Theory of Cryptography, pp. 567\u2013594 (2017)","DOI":"10.1007\/978-3-319-70503-3_19"},{"key":"428_CR6","doi-asserted-by":"publisher","unstructured":"Blum, E., Katz, J., Liu-Zhang, C., Loss, J.: Asynchronous byzantine agreement with subquadratic communication. In: R.\u00a0Pass, K.\u00a0Pietrzak (eds.) Theory of Cryptography\u201418th International Conference, TCC 2020, Durham, NC, USA, November 16-19, 2020, Proceedings, Part I, Lecture Notes in Computer Science, vol. 12550, pp. 353\u2013380. Springer (2020). https:\/\/doi.org\/10.1007\/978-3-030-64375-1_13","DOI":"10.1007\/978-3-030-64375-1_13"},{"key":"428_CR7","doi-asserted-by":"crossref","unstructured":"Cachin, C., Kursawe, K., Petzold, F., Shoup, V.: Secure and efficient asynchronous broadcast protocols. In: Annual International Cryptology Conference, pp. 524\u2013541. Springer (2001)","DOI":"10.1007\/3-540-44647-8_31"},{"key":"428_CR8","doi-asserted-by":"crossref","unstructured":"Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: FOCS (2001)","DOI":"10.1109\/SFCS.2001.959888"},{"key":"428_CR9","unstructured":"Castro, M., Liskov, B.: Practical byzantine fault tolerance. In: OSDI (1999)"},{"key":"428_CR10","doi-asserted-by":"crossref","unstructured":"Chandran, N., Chongchitmate, W., Garay, J.A., Goldwasser, S., Ostrovsky, R., Zikas, V.: The hidden graph model: communication locality and optimal resiliency with adaptive faults. In: ITCS (2015)","DOI":"10.1145\/2688073.2688102"},{"key":"428_CR11","unstructured":"Chen, J., Gorbunov, S., Micali, S., Vlachos, G.: Algorand agreement: super fast and partition resilient byzantine agreement. Cryptology ePrint Archive, Report 2018\/377 (2018). https:\/\/ia.cr\/2018\/377"},{"key":"428_CR12","unstructured":"Chen, J., Micali, S.: Algorand: the efficient and democratic ledger. arXiv:1607.01341 (2016)"},{"key":"428_CR13","doi-asserted-by":"crossref","unstructured":"Cohen, R., Coretti, S., Garay, J., Zikas, V.: Probabilistic termination and composability of cryptographic protocols. In: the 36th Annual International Cryptology Conference on Advances in Cryptology\u2014RYPTO 2016, pp. 240\u2013269. Springer (2016)","DOI":"10.1007\/978-3-662-53015-3_9"},{"key":"428_CR14","doi-asserted-by":"publisher","unstructured":"Cohen, S., Keidar, I., Spiegelman, A.: Brief announcement: Not a coincidence: Sub-quadratic asynchronous byzantine agreement whp. In: Proceedings of the 39th Symposium on Principles of Distributed Computing, PODC\u201920, pp. 175\u2013177. Association for Computing Machinery, New York, NY, USA (2020). https:\/\/doi.org\/10.1145\/3382734.3405708","DOI":"10.1145\/3382734.3405708"},{"key":"428_CR15","doi-asserted-by":"crossref","unstructured":"David, B.M., Gazi, P., Kiayias, A., Russell, A.: Ouroboros praos: an adaptively-secure, semi-synchronous proof-of-stake blockchain. In: Eurocrypt (2018)","DOI":"10.1007\/978-3-319-78375-8_3"},{"issue":"1","key":"428_CR16","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 32(1), 191\u2013204 (1985)","journal-title":"J. ACM"},{"issue":"4","key":"428_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":"428_CR18","unstructured":"Dryja, T., Liu, Q.C., Narula, N.: A lower bound for byzantine agreement and consensus for adaptive adversaries using vdfs. CoRR. arXiv:2004.01939 (2020)"},{"key":"428_CR19","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 35, 288\u2013323 (1988)","journal-title":"J. ACM"},{"key":"428_CR20","doi-asserted-by":"crossref","unstructured":"Feldman, P., Micali, S.: Optimal algorithms for byzantine agreement. In: Proceedings of the twentieth annual ACM symposium on Theory of computing, pp. 148\u2013161. ACM (1988)","DOI":"10.1145\/62212.62225"},{"key":"428_CR21","doi-asserted-by":"crossref","unstructured":"Fischer, M.J., Lynch, N.A., Merritt, M.: Easy impossibility proofs for distributed consensus problems. In: PODC (1985)","DOI":"10.1145\/323596.323602"},{"key":"428_CR22","unstructured":"Fitzi, M.: Generalized communication and security models in byzantine agreement. Ph.D. thesis, ETH Zurich (2002)"},{"key":"428_CR23","doi-asserted-by":"crossref","unstructured":"Garay, J.A., Katz, J., Kumaresan, R., Zhou, H.S.: Adaptively secure broadcast, revisited. In: Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC\u201911, pp. 179\u2013186. ACM, New York, NY, USA (2011)","DOI":"10.1145\/1993806.1993832"},{"key":"428_CR24","doi-asserted-by":"crossref","unstructured":"Garay, J.A., Kiayias, A., Leonardos, N.: The bitcoin backbone protocol: analysis and applications. In: Eurocrypt (2015)","DOI":"10.1007\/978-3-662-46803-6_10"},{"key":"428_CR25","doi-asserted-by":"crossref","unstructured":"Goyal, R., Hohenberger, S., Koppula, V., Waters, B.: A generic approach to constructing and proving verifiable random functions. In: TCC, vol. 10678, pp. 537\u2013566. Springer (2017)","DOI":"10.1007\/978-3-319-70503-3_18"},{"issue":"3","key":"428_CR26","doi-asserted-by":"publisher","first-page":"11:1","DOI":"10.1145\/2220357.2220358","volume":"59","author":"J Groth","year":"2012","unstructured":"Groth, J., Ostrovsky, R., Sahai, A.: New techniques for noninteractive zero-knowledge. J. ACM 59(3), 11:1-11:35 (2012). https:\/\/doi.org\/10.1145\/2220357.2220358","journal-title":"J. ACM"},{"key":"428_CR27","doi-asserted-by":"crossref","unstructured":"Hirt, M., Zikas, V.: Adaptively secure broadcast. In: EUROCRYPT, vol. 6110, pp. 466\u2013485. Springer (2010)","DOI":"10.1007\/978-3-642-13190-5_24"},{"issue":"2","key":"428_CR28","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.jcss.2008.08.001","volume":"75","author":"J Katz","year":"2009","unstructured":"Katz, J., Koo, C.Y.: On expected constant-round protocols for byzantine agreement. J. Comput. Syst. Sci. 75(2), 91\u2013112 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"428_CR29","doi-asserted-by":"publisher","first-page":"18: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), 18:1-18:24 (2011)","journal-title":"J. ACM"},{"key":"428_CR30","doi-asserted-by":"crossref","unstructured":"King, V., Saia, J., Sanwalani, V., Vee, E.: Scalable leader election. In: SODA (2006)","DOI":"10.1145\/1109557.1109667"},{"issue":"3","key":"428_CR31","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1145\/2402.322398","volume":"30","author":"L Lamport","year":"1983","unstructured":"Lamport, L.: The weak byzantine generals problem. J. ACM 30(3), 668\u2013676 (1983)","journal-title":"J. ACM"},{"issue":"3","key":"428_CR32","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":"428_CR33","unstructured":"Micali, S., Vadhan, S., Rabin, M.: Verifiable random functions. In: FOCS (1999)"},{"key":"428_CR34","unstructured":"Nakamoto, S.: Bitcoin: A peer-to-peer electronic cash system (2008)"},{"key":"428_CR35","doi-asserted-by":"crossref","unstructured":"Rabin, M.O.: Randomized byzantine generals. In: Proceedings of the 24th Annual Symposium on Foundations of Computer Science, pp. 403\u2013409. IEEE (1983)","DOI":"10.1109\/SFCS.1983.48"},{"key":"428_CR36","unstructured":"Tsimos, G., Loss, J., Papamanthou, C.: Gossiping for communication-efficient broadcast. Cryptology ePrint Archive, Report 2020\/894 (2020). https:\/\/ia.cr\/2020\/894"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-022-00428-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-022-00428-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-022-00428-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,4]],"date-time":"2023-03-04T09:04:34Z","timestamp":1677920674000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-022-00428-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,17]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["428"],"URL":"https:\/\/doi.org\/10.1007\/s00446-022-00428-8","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2022,7,17]]},"assertion":[{"value":"15 November 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 May 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 July 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}