[{"title":"Brief announcement: Be prepared when network goes bad: An asynchronous view-change protocol","quality_controlled":"1","page":"187-190","status":"public","external_id":{"arxiv":["2103.03181"],"isi":["000744439800018"]},"author":[{"last_name":"Gelashvili","first_name":"Rati","full_name":"Gelashvili, Rati"},{"last_name":"Kokoris Kogias","first_name":"Eleftherios","full_name":"Kokoris Kogias, Eleftherios","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30"},{"first_name":"Alexander","full_name":"Spiegelman, Alexander","last_name":"Spiegelman"},{"last_name":"Xiang","full_name":"Xiang, Zhuolun","first_name":"Zhuolun"}],"language":[{"iso":"eng"}],"date_created":"2021-12-16T13:20:19Z","keyword":["optimal","state machine replication","fallback","asynchrony","byzantine faults"],"conference":{"location":"Virtual, Italy","name":"PODC: Principles of Distributed Computing","end_date":"2021-07-30","start_date":"2021-07-26"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing","day":"21","_id":"10553","publication_identifier":{"isbn":["9-781-4503-8548-0"]},"doi":"10.1145/3465084.3467941","department":[{"_id":"ElKo"}],"type":"conference","citation":{"apa":"Gelashvili, R., Kokoris Kogias, E., Spiegelman, A., &#38; Xiang, Z. (2021). Brief announcement: Be prepared when network goes bad: An asynchronous view-change protocol. In <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i> (pp. 187–190). Virtual, Italy: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3465084.3467941\">https://doi.org/10.1145/3465084.3467941</a>","ista":"Gelashvili R, Kokoris Kogias E, Spiegelman A, Xiang Z. 2021. Brief announcement: Be prepared when network goes bad: An asynchronous view-change protocol. Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. PODC: Principles of Distributed Computing, 187–190.","short":"R. Gelashvili, E. Kokoris Kogias, A. Spiegelman, Z. Xiang, in:, Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2021, pp. 187–190.","mla":"Gelashvili, Rati, et al. “Brief Announcement: Be Prepared When Network Goes Bad: An Asynchronous View-Change Protocol.” <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2021, pp. 187–90, doi:<a href=\"https://doi.org/10.1145/3465084.3467941\">10.1145/3465084.3467941</a>.","ama":"Gelashvili R, Kokoris Kogias E, Spiegelman A, Xiang Z. Brief announcement: Be prepared when network goes bad: An asynchronous view-change protocol. In: <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2021:187-190. doi:<a href=\"https://doi.org/10.1145/3465084.3467941\">10.1145/3465084.3467941</a>","chicago":"Gelashvili, Rati, Eleftherios Kokoris Kogias, Alexander Spiegelman, and Zhuolun Xiang. “Brief Announcement: Be Prepared When Network Goes Bad: An Asynchronous View-Change Protocol.” In <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>, 187–90. Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3465084.3467941\">https://doi.org/10.1145/3465084.3467941</a>.","ieee":"R. Gelashvili, E. Kokoris Kogias, A. Spiegelman, and Z. Xiang, “Brief announcement: Be prepared when network goes bad: An asynchronous view-change protocol,” in <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>, Virtual, Italy, 2021, pp. 187–190."},"oa":1,"article_processing_charge":"No","publication_status":"published","oa_version":"Preprint","month":"07","isi":1,"date_updated":"2023-09-04T11:42:10Z","arxiv":1,"scopus_import":"1","abstract":[{"text":"The popularity of permissioned blockchain systems demands BFT SMR protocols that are efficient under good network conditions (synchrony) and robust under bad network conditions (asynchrony). The state-of-the-art partially synchronous BFT SMR protocols provide optimal linear communication cost per decision under synchrony and good leaders, but lose liveness under asynchrony. On the other hand, the state-of-the-art asynchronous BFT SMR protocols are live even under asynchrony, but always pay quadratic cost even under synchrony. In this paper, we propose a BFT SMR protocol that achieves the best of both worlds -- optimal linear cost per decision under good networks and leaders, optimal quadratic cost per decision under bad networks, and remains always live.","lang":"eng"}],"year":"2021","publisher":"Association for Computing Machinery","date_published":"2021-07-21T00:00:00Z","main_file_link":[{"url":"https://arxiv.org/abs/2103.03181","open_access":"1"}]},{"status":"public","intvolume":"       146","language":[{"iso":"eng"}],"external_id":{"arxiv":["1908.02743"]},"author":[{"first_name":"Thomas","full_name":"Nowak, Thomas","last_name":"Nowak"},{"full_name":"Rybicki, Joel","first_name":"Joel","last_name":"Rybicki","orcid":"0000-0002-6432-6646","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87"}],"quality_controlled":"1","title":"Byzantine approximate agreement on graphs","page":"29:1--29:17","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ec_funded":1,"volume":146,"has_accepted_license":"1","date_created":"2019-10-08T12:41:38Z","ddc":["004"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"end_date":"2019-10-18","name":"DISC: Symposium on Distributed Computing","start_date":"2019-10-14","location":"Budapest, Hungary"},"keyword":["consensus","approximate agreement","Byzantine faults","chordal graphs","lattice agreement"],"doi":"10.4230/LIPICS.DISC.2019.29","publication_identifier":{"eisbn":["978-3-95977-126-9"]},"citation":{"chicago":"Nowak, Thomas, and Joel Rybicki. “Byzantine Approximate Agreement on Graphs.” In <i>33rd International Symposium on Distributed Computing</i>, 146:29:1--29:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. <a href=\"https://doi.org/10.4230/LIPICS.DISC.2019.29\">https://doi.org/10.4230/LIPICS.DISC.2019.29</a>.","ieee":"T. Nowak and J. Rybicki, “Byzantine approximate agreement on graphs,” in <i>33rd International Symposium on Distributed Computing</i>, Budapest, Hungary, 2019, vol. 146, p. 29:1--29:17.","ista":"Nowak T, Rybicki J. 2019. Byzantine approximate agreement on graphs. 33rd International Symposium on Distributed Computing. DISC: Symposium on Distributed Computing, LIPIcs, vol. 146, 29:1--29:17.","apa":"Nowak, T., &#38; Rybicki, J. (2019). Byzantine approximate agreement on graphs. In <i>33rd International Symposium on Distributed Computing</i> (Vol. 146, p. 29:1--29:17). Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.DISC.2019.29\">https://doi.org/10.4230/LIPICS.DISC.2019.29</a>","short":"T. Nowak, J. Rybicki, in:, 33rd International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 29:1--29:17.","ama":"Nowak T, Rybicki J. Byzantine approximate agreement on graphs. In: <i>33rd International Symposium on Distributed Computing</i>. Vol 146. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:29:1--29:17. doi:<a href=\"https://doi.org/10.4230/LIPICS.DISC.2019.29\">10.4230/LIPICS.DISC.2019.29</a>","mla":"Nowak, Thomas, and Joel Rybicki. “Byzantine Approximate Agreement on Graphs.” <i>33rd International Symposium on Distributed Computing</i>, vol. 146, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 29:1--29:17, doi:<a href=\"https://doi.org/10.4230/LIPICS.DISC.2019.29\">10.4230/LIPICS.DISC.2019.29</a>."},"type":"conference","department":[{"_id":"DaAl"}],"oa":1,"publication":"33rd International Symposium on Distributed Computing","file_date_updated":"2020-07-14T12:47:44Z","_id":"6931","day":"01","date_updated":"2025-07-10T11:54:03Z","arxiv":1,"month":"11","alternative_title":["LIPIcs"],"year":"2019","abstract":[{"lang":"eng","text":"Consider a distributed system with n processors out of which f can be Byzantine faulty. In the\r\napproximate agreement task, each processor i receives an input value xi and has to decide on an\r\noutput value yi such that\r\n1. the output values are in the convex hull of the non-faulty processors’ input values,\r\n2. the output values are within distance d of each other.\r\n\r\n\r\nClassically, the values are assumed to be from an m-dimensional Euclidean space, where m ≥ 1.\r\nIn this work, we study the task in a discrete setting, where input values with some structure\r\nexpressible as a graph. Namely, the input values are vertices of a finite graph G and the goal is to\r\noutput vertices that are within distance d of each other in G, but still remain in the graph-induced\r\nconvex hull of the input values. For d = 0, the task reduces to consensus and cannot be solved with\r\na deterministic algorithm in an asynchronous system even with a single crash fault. For any d ≥ 1,\r\nwe show that the task is solvable in asynchronous systems when G is chordal and n > (ω + 1)f,\r\nwhere ω is the clique number of G. In addition, we give the first Byzantine-tolerant algorithm for a\r\nvariant of lattice agreement. For synchronous systems, we show tight resilience bounds for the exact\r\nvariants of these and related tasks over a large class of combinatorial structures."}],"scopus_import":"1","date_published":"2019-11-01T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","article_processing_charge":"No","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","call_identifier":"H2020"}],"publication_status":"published","oa_version":"Published Version","file":[{"date_updated":"2020-07-14T12:47:44Z","file_size":639378,"file_name":"LIPIcs-DISC-2019-29.pdf","checksum":"2d2202f90c6ac991e50876451627c4b5","content_type":"application/pdf","date_created":"2019-10-08T12:47:19Z","relation":"main_file","access_level":"open_access","creator":"jrybicki","file_id":"6934"}]}]