  It is a common belief that Byzantine fault-tolerant solutions for consensus
are significantly slower than their crash fault-tolerant counterparts. Indeed,
in PBFT, the most widely known Byzantine fault-tolerant consensus protocol, it
takes three message delays to decide a value, in contrast with just two in
Paxos. This motivates the search for fast Byzantine consensus algorithms that
can produce decisions after just two message delays \emph{in the common case},
e.g., under the assumption that the current leader is correct and not suspected
by correct processes. The (optimal) two-step latency comes with the cost of
lower resilience: fast Byzantine consensus requires more processes to tolerate
the same number of faults. In particular, $5f+1$ processes were claimed to be
necessary to tolerate $f$ Byzantine failures.
  In this paper, we present a fast Byzantine consensus algorithm that relies on
just $5f-1$ processes. Moreover, we show that $5f-1$ is the tight lower bound,
correcting a mistake in the earlier work. While the difference of just $2$
processes may appear insignificant for large values of $f$, it can be crucial
for systems of a smaller scale. In particular, for $f=1$, our algorithm
requires only $4$ processes, which is optimal for any (not necessarily fast)
partially synchronous Byzantine consensus algorithm.
