  The view synchronization problem lies at the heart of many Byzantine Fault
Tolerant (BFT) State Machine Replication (SMR) protocols in the partial
synchrony model, since these protocols are usually based on views. Liveness is
guaranteed if honest processors spend a sufficiently long time in the same view
during periods of synchrony, and if the leader of the view is honest. Ensuring
that these conditions occur, known as Byzantine View Synchronization (BVS), has
turned out to be the performance bottleneck of many BFT SMR protocols.
  A recent line of work has shown that, by using an appropriate view
synchronization protocol, BFT SMR protocols can achieve $O(n^2)$ communication
complexity in the worst case after GST, thereby finally matching the lower
bound established by Dolev and Reischuk in 1985. However, these protocols
suffer from two major issues:
  (1) When implemented so as to be optimistically responsive, even a single
Byzantine processor may infinitely often cause $\Omega(n\Delta)$ latency
between consecutive consensus decisions.
  (2) Even in the absence of Byzantine action, infinitely many views require
honest processors to send $\Omega(n^2)$ messages.
  Here, we present Lumiere, an optimistically responsive BVS protocol which
maintains optimal worst-case communication complexity while simultaneously
addressing the two issues above: for the first time, Lumiere enables BFT
consensus solutions in the partial synchrony setting that have $O(n^2)$
worst-case communication complexity, and that eventually always (i.e., except
for a small constant number of "warmup" decisions) have communication
complexity and latency which is linear in the number of actual faults in the
execution.
