  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 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.
