The Carnot Bound: Limits and Possibilities for Bandwidth-Efficient Consensus
This addresses bandwidth efficiency in distributed systems for applications requiring high-throughput consensus, offering incremental improvements with new protocol designs.
The paper tackles the throughput bottleneck in leader-based consensus protocols by investigating fundamental limits on data expansion rate, proving that 2-round finality protocols cannot achieve a rate below approximately 2.5, and showing that 3-round finality protocols can push it arbitrarily close to 1, with protocols achieving rates as low as 1.33 or 1.5 under adversarial conditions.
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.