---
_id: '10553'
abstract:
- lang: eng
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.
article_processing_charge: No
author:
- first_name: Rati
full_name: Gelashvili, Rati
last_name: Gelashvili
- first_name: Eleftherios
full_name: Kokoris Kogias, Eleftherios
id: f5983044-d7ef-11ea-ac6d-fd1430a26d30
last_name: Kokoris Kogias
- first_name: Alexander
full_name: Spiegelman, Alexander
last_name: Spiegelman
- first_name: Zhuolun
full_name: Xiang, Zhuolun
last_name: Xiang
citation:
ama: 'Gelashvili R, Kokoris Kogias E, Spiegelman A, Xiang Z. Brief announcement:
Be prepared when network goes bad: An asynchronous view-change protocol. In: Proceedings
of the 2021 ACM Symposium on Principles of Distributed Computing. Association
for Computing Machinery; 2021:187-190. doi:10.1145/3465084.3467941'
apa: 'Gelashvili, R., Kokoris Kogias, E., Spiegelman, A., & Xiang, Z. (2021).
Brief announcement: Be prepared when network goes bad: An asynchronous view-change
protocol. In Proceedings of the 2021 ACM Symposium on Principles of Distributed
Computing (pp. 187–190). Virtual, Italy: Association for Computing Machinery.
https://doi.org/10.1145/3465084.3467941'
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 Proceedings of the 2021 ACM Symposium on Principles
of Distributed Computing, 187–90. Association for Computing Machinery, 2021.
https://doi.org/10.1145/3465084.3467941.'
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 Proceedings
of the 2021 ACM Symposium on Principles of Distributed Computing, Virtual,
Italy, 2021, pp. 187–190.'
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.'
mla: 'Gelashvili, Rati, et al. “Brief Announcement: Be Prepared When Network Goes
Bad: An Asynchronous View-Change Protocol.” Proceedings of the 2021 ACM Symposium
on Principles of Distributed Computing, Association for Computing Machinery,
2021, pp. 187–90, doi:10.1145/3465084.3467941.'
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.
conference:
end_date: 2021-07-30
location: Virtual, Italy
name: 'PODC: Principles of Distributed Computing'
start_date: 2021-07-26
date_created: 2021-12-16T13:20:19Z
date_published: 2021-07-21T00:00:00Z
date_updated: 2023-09-04T11:42:10Z
day: '21'
department:
- _id: ElKo
doi: 10.1145/3465084.3467941
external_id:
arxiv:
- '2103.03181'
isi:
- '000744439800018'
isi: 1
keyword:
- optimal
- state machine replication
- fallback
- asynchrony
- byzantine faults
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2103.03181
month: '07'
oa: 1
oa_version: Preprint
page: 187-190
publication: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing
publication_identifier:
isbn:
- 9-781-4503-8548-0
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Brief announcement: Be prepared when network goes bad: An asynchronous view-change
protocol'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
_id: '6931'
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."
alternative_title:
- LIPIcs
article_processing_charge: No
author:
- first_name: Thomas
full_name: Nowak, Thomas
last_name: Nowak
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
citation:
ama: 'Nowak T, Rybicki J. Byzantine approximate agreement on graphs. In: 33rd
International Symposium on Distributed Computing. Vol 146. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2019:29:1--29:17. doi:10.4230/LIPICS.DISC.2019.29'
apa: 'Nowak, T., & Rybicki, J. (2019). Byzantine approximate agreement on graphs.
In 33rd International Symposium on Distributed Computing (Vol. 146, p.
29:1--29:17). Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPICS.DISC.2019.29'
chicago: Nowak, Thomas, and Joel Rybicki. “Byzantine Approximate Agreement on Graphs.”
In 33rd International Symposium on Distributed Computing, 146:29:1--29:17.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.DISC.2019.29.
ieee: T. Nowak and J. Rybicki, “Byzantine approximate agreement on graphs,” in 33rd
International Symposium on Distributed Computing, 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: International Symposium
on Distributed Computing, LIPIcs, vol. 146, 29:1--29:17.'
mla: Nowak, Thomas, and Joel Rybicki. “Byzantine Approximate Agreement on Graphs.”
33rd International Symposium on Distributed Computing, vol. 146, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 29:1--29:17, doi:10.4230/LIPICS.DISC.2019.29.
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.
conference:
end_date: 2019-10-18
location: Budapest, Hungary
name: 'DISC: International Symposium on Distributed Computing'
start_date: 2019-10-14
date_created: 2019-10-08T12:41:38Z
date_published: 2019-01-01T00:00:00Z
date_updated: 2021-01-12T08:09:38Z
ddc:
- '004'
department:
- _id: DaAl
doi: 10.4230/LIPICS.DISC.2019.29
ec_funded: 1
external_id:
arxiv:
- '1908.02743'
file:
- access_level: open_access
checksum: 2d2202f90c6ac991e50876451627c4b5
content_type: application/pdf
creator: jrybicki
date_created: 2019-10-08T12:47:19Z
date_updated: 2020-07-14T12:47:44Z
file_id: '6934'
file_name: LIPIcs-DISC-2019-29.pdf
file_size: 639378
relation: main_file
file_date_updated: 2020-07-14T12:47:44Z
has_accepted_license: '1'
intvolume: ' 146'
keyword:
- consensus
- approximate agreement
- Byzantine faults
- chordal graphs
- lattice agreement
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
oa: 1
oa_version: Published Version
page: 29:1--29:17
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 33rd International Symposium on Distributed Computing
publication_identifier:
eisbn:
- 978-3-95977-126-9
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: 1
status: public
title: Byzantine approximate agreement on graphs
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 146
year: '2019'
...