Chenyu Zhang (Tianjin University), Xiulong Liu (Tianjin University), Hao Xu (Tianjin University), Haochen Ren (Tianjin University), Muhammad Shahzad (North Carolina State University), Guyue Liu (Peking University), Keqiu Li (Tianjin University)
Traditional Byzantine Fault Tolerance (BFT) consensus protocols adopt a star topology with a leader to handle all message transmission, causing performance to degrade rapidly as replicas grow. Recently, many studies have sought to improve scalability by exploring multi-layer topology (e.g., tree structures) to reduce the leader's fanout. However, these approaches either depend on a polynomial fanout to preserve fault tolerance or are constrained by the impact of topology depth on throughput, ultimately leading to only modest scalability gains. To this end, we propose Tide, the first BFT consensus that maintains robust performance as replica count grows, which is enabled by our design of logarithmic-fanout topology and high-parallel pipelining. Tide utilizes redundant connections as key insight in topology, reducing fanout without compromising resilience. Tide further introduces a novel pipelining where inter-layer interactions dynamically determine the degree of proposal parallelism, thereby decoupling throughput from topology depth. Real-world experiments with 100 cloud servers demonstrate that as the replica count scales from 100 to 1,000, state-of-the-art protocols experience a 65% to 90% decrease in throughput and a 50× increase in latency.
In contrast, Tide maintains a replica-agnostic high throughput of around 50ktps, over 5x higher than others, while its latency remains at 0.3s-0.4s.