  The Narwhal system is a state-of-the-art Byzantine fault-tolerant scalable
architecture that involves constructing a directed acyclic graph (DAG) of
messages among a set of validators in a Blockchain network. Bullshark is a
zero-overhead consensus protocol on top of the Narwhal's DAG that can order
over 100k transactions per second. Unfortunately, the high throughput of
Bullshark comes with a latency price due to the DAG construction, increasing
the latency compared to the state-of-the-art leader-based BFT consensus
protocols.
  We introduce Shoal, a protocol-agnostic framework for enhancing Narwhal-based
consensus. By incorporating leader reputation and pipelining support for the
first time, Shoal significantly reduces latency. Moreover, the combination of
properties of the DAG construction and the leader reputation mechanism enables
the elimination of timeouts in all but extremely uncommon scenarios in
practice, a property we name Prevalent Responsiveness" (it strictly subsumes
the established and often desired Optimistic Responsiveness property for BFT
protocols).
  We integrated Shoal instantiated with Bullshark, the fastest existing
Narwhal-based consensus protocol, in an open-source Blockchain project and
provide experimental evaluations demonstrating up to 40% latency reduction in
the failure-free executions, and up-to 80% reduction in executions with
failures against the vanilla Bullshark implementation.
