@inproceedings{10553,
  abstract     = {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.},
  author       = {Gelashvili, Rati and Kokoris Kogias, Eleftherios and Spiegelman, Alexander and Xiang, Zhuolun},
  booktitle    = {Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing},
  isbn         = {9-781-4503-8548-0},
  keywords     = {optimal, state machine replication, fallback, asynchrony, byzantine faults},
  location     = {Virtual, Italy},
  pages        = {187--190},
  publisher    = {Association for Computing Machinery},
  title        = {{Brief announcement: Be prepared when network goes bad: An asynchronous view-change protocol}},
  doi          = {10.1145/3465084.3467941},
  year         = {2021},
}

@inproceedings{6931,
  abstract     = {Consider a distributed system with n processors out of which f can be Byzantine faulty. In the
approximate agreement task, each processor i receives an input value xi and has to decide on an
output value yi such that
1. the output values are in the convex hull of the non-faulty processors’ input values,
2. the output values are within distance d of each other.


Classically, the values are assumed to be from an m-dimensional Euclidean space, where m ≥ 1.
In this work, we study the task in a discrete setting, where input values with some structure
expressible as a graph. Namely, the input values are vertices of a finite graph G and the goal is to
output vertices that are within distance d of each other in G, but still remain in the graph-induced
convex hull of the input values. For d = 0, the task reduces to consensus and cannot be solved with
a deterministic algorithm in an asynchronous system even with a single crash fault. For any d ≥ 1,
we show that the task is solvable in asynchronous systems when G is chordal and n > (ω + 1)f,
where ω is the clique number of G. In addition, we give the first Byzantine-tolerant algorithm for a
variant of lattice agreement. For synchronous systems, we show tight resilience bounds for the exact
variants of these and related tasks over a large class of combinatorial structures.},
  author       = {Nowak, Thomas and Rybicki, Joel},
  booktitle    = {33rd International Symposium on Distributed Computing},
  keywords     = {consensus, approximate agreement, Byzantine faults, chordal graphs, lattice agreement},
  location     = {Budapest, Hungary},
  pages        = {29:1----29:17},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Byzantine approximate agreement on graphs}},
  doi          = {10.4230/LIPICS.DISC.2019.29},
  volume       = {146},
  year         = {2019},
}