Dumbo-NG: Fast Asynchronous BFT Consensus with Throughput-Oblivious Latency - Yuan Lu
Channel: ConsensusLab
Date: 2023-06-14

Yingzi Gao (Institute of Software, Chinese Academy of Sciences), Yuan Lu (Institute of Software, Chinese Academy of Sciences), Zhenliang Lu (The University of Sydney), Qiang Tang (The University of Sydney), Jing Xu (Institute of Software, Chinese Academy of Sciences), Zhenfeng Zhang (Institute of Software, Chinese Academy of Sciences)

Despite recent progresses of practical asynchronous BFT consensus, the state-of-the-art designs still suffer from suboptimal performance. Particularly, to obtain maximum throughput, existing protocols require each participating node to broadcast a huge batch of transactions, which dramatically sacrifices latency. Worse still, the broadcasts of f slowest nodes might never be agreed to output and thus can be censored (where f is the number of faults). Implementable mitigation to the threat either uses computationally costly threshold encryption or incurs communication blow-up by letting the honest nodes to broadcast redundant transactions, thus causing further efficiency issues. We present Dumbo-NG, a novel practical asynchronous BFT consensus (atomic broadcast) to solve all those remaining practical issues. Its technical core is a non-trivial direct reduction from asynchronous atomic broadcast to multi-valued validated Byzantine agreement (MVBA) with quality property (which is to ensure the output is from honest nodes with at least 1/2 probability). Most interestingly, the new protocol structure empowers completely concurrent execution of transaction dissemination and asynchronous agreement. This brings about two benefits: (i) the throughput-latency tension is resolved to approach peak throughput with minimal increase in latency; (ii) all transactions broadcasted by honest nodes can be agreed to output rapidly, thus conquering the censorship threat with no extra cost. We implement Dumbo-NG with using the current fastest MVBA protocol with quality (GLL+22, NDSS'22) and compare it to state-of-the-art asynchronous BFT including Dumbo (CCS'20) and Speeding-Dumbo (NDSS'22). Along the way, we apply the techniques from Speeding-Dumbo to DispersedLedger (NSDI'22) and obtain sDumbo-DL an improved DispersedLedger variant for comprehensive comparison. Extensive experiments (over up to 64 AWS EC2 nodes across 16 AWS regions) reveal: Dumbo-NG realizes a peak throughput 4-8x over Dumbo, 2-4x over Speeding-Dumbo, and 2-3x over sDumbo-DL (for varying scales); More importantly, Dumbo-NG's latency, which is lowest among all tested protocols, can almost remain stable when throughput grows.

ConsensusDays 23 Session 2.2- Performance and Scalability
Site: https://research.protocol.ai/sites/consensusday23/
Playlist: https://www.youtube.com/playlist?list=PLxN6L-h3wFfsRKLCj4I8xKeKjy9OL-EY6