Search papers, labs, and topics across Lattice.
This paper investigates the fundamental limits of bandwidth efficiency in leader-based State Machine Replication (SMR) protocols, focusing on the data expansion rate. It proves a lower bound of approximately 2.5 for 2-round finality protocols and demonstrates that 3-round finality protocols can achieve data expansion rates arbitrarily close to 1 by using a second voting round as a recovery mechanism for aggressive erasure coding. The authors present two 3-round finality protocols, Carnot 1 and Carnot 2, that realize this approach with different trade-offs between fault tolerance and fragment dissemination overhead.
Three-round consensus protocols can shatter the bandwidth bottleneck in leader-based systems, achieving near-optimal data expansion rates by using a second round of voting to recover from aggressive erasure coding failures.
In leader-based protocols for State Machine Replication (SMR), the leader's outgoing bandwidth is a natural throughput bottleneck. Erasure coding can alleviate this by allowing the leader to send each processor a single fragment of each block, rather than a full copy. The \emph{data expansion rate}, the ratio of total data sent to payload size, determines how close throughput can get to the underlying network bandwidth. We investigate the fundamental limits and possibilities for bandwidth-efficient leader-based consensus. On the negative side, we prove that protocols with 2-round finality (one round of voting) cannot achieve a data expansion rate below approximately 2.5, a bound that is matched by existing protocols. On the positive side, we show that protocols with 3-round finality (two rounds of voting) can push the data expansion rate arbitrarily close to 1. The key insight is that the second voting round provides a recovery mechanism: leaders can attempt aggressive erasure codes and safely fall back to more conservative ones when reconstruction fails, without compromising consistency. We present two protocols with 3-round finality realising this approach. Carnot 1 assumes $n \geq 4f+1$ processors (of which at most $f$ may be Byzantine) and achieves a clean design requiring no additional fragment dissemination beyond the initial protocol messages. Carnot 2 operates under the optimal resilience assumption $n \geq 3f+1$, at the cost of additional fragment dissemination when Byzantine processors interfere. Both protocols can incorporate stable leaders and optimistic proposals to maximise throughput and minimise latency. Under favourable conditions, with correct leaders and few actual faults, both protocols allow leaders to use data expansion rates approaching 1; under adversarial conditions, leaders can revert to safe expansion rates of approximately $1.33$ and $1.5$, respectively.
