Paper 2022/020

PACE: Fully Parallelizable BFT from Reproposable Byzantine Agreement

Haibin Zhang, Beijing Institute of Technology
Sisi Duan, Tsinghua University

The classic asynchronous Byzantine fault tolerance (BFT) framework of Ben-Or, Kemler, and Rabin (BKR) and its descendants rely on reliable broadcast (RBC) and asynchronous binary agreement (ABA). However, BKR does not allow all ABA instances to run in parallel, a well-known performance bottleneck. We propose PACE, a generic framework that removes the bottleneck, allowing fully parallelizable ABA instances. PACE is built on RBC and reproposable ABA (RABA). Different from the conventional ABA, RABA allows a replica to change its mind and vote twice. We show how to efficiently build RABA protocols from existing ABA protocols and a new ABA protocol that we introduce. We implement six new BFT protocols: three in the BKR framework, and three in the PACE framework. Via a deployment using 91 replicas on Amazon EC2 across five continents, we show that all PACE instantiations, in both failure-free and failure scenarios, significantly outperform their BKR counterparts, and prior BFT protocols such as BEAT and Dumbo, in terms of latency, throughput, latency vs. throughput, and scalability.

Note: The version only updates acknowledgement and author info.

Available format(s)
Publication info
Published elsewhere. ACM CCS
asynchronous BFT binary consensus blockchain fault tolerance
Contact author(s)
haibin @ bit edu cn
duansisi @ mail tsinghua edu cn
2022-07-03: last of 2 revisions
2022-01-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Haibin Zhang and Sisi Duan},
      title = {PACE: Fully Parallelizable BFT from Reproposable Byzantine Agreement},
      howpublished = {Cryptology ePrint Archive, Paper 2022/020},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.