  In this paper, we challenge the conventional approach of state machine
replication systems to design deterministic agreement protocols in the
eventually synchronous communication model. We first prove that no such
protocol can guarantee bounded communication cost before the global
stabilization time and propose a different approach that hopes for the best
(synchrony) but prepares for the worst (asynchrony). Accordingly, we design an
optimistic byzantine agreement protocol that first tries an efficient
deterministic algorithm that relies on synchrony for termination only, and
then, only if an agreement was not reached due to asynchrony, the protocol uses
a randomized asynchronous protocol for fallback that guarantees termination
with probability 1.
  We formally prove that our protocol achieves optimal communication complexity
under all network conditions and failure scenarios. We first prove a lower
bound of $\Omega(ft+ t)$ for synchronous deterministic byzantine agreement
protocols, where $t$ is the failure threshold, and $f$ is the actual number of
failures. Then, we present a tight upper bound and use it for the synchronous
part of the optimistic protocol. Finally, for the asynchronous fallback, we use
a variant of the (optimal) VABA protocol, which we reconstruct to safely
combine it with the synchronous part.
  We believe that our adaptive to failures synchronous byzantine agreement
protocol has an independent interest since it is the first protocol we are
aware of which communication complexity optimally depends on the actual number
of failures.
