  We introduce FnF-BFT, a parallel-leader byzantine fault-tolerant
state-machine replication protocol for the partially synchronous model with
theoretical performance bounds during synchrony. By allowing all replicas to
act as leaders and propose requests independently, FnF-BFT parallelizes the
execution of requests. Leader parallelization distributes the load over the
entire network -- increasing throughput by overcoming the single-leader
bottleneck. We further use historical data to ensure that well-performing
replicas are in command. FnF-BFT's communication complexity is linear in the
number of replicas during synchrony and thus competitive with state-of-the-art
protocols. Finally, with FnF-BFT, we introduce a BFT protocol with performance
guarantees in stable network conditions under truly byzantine attacks.
  A prototype implementation of \prot outperforms (state-of-the-art) HotStuff's
throughput, especially as replicas increase, showcasing \prot's significantly
improved scaling capabilities.
