A Method of Parallelizing Consensuses for Accelerating Byzantine Fault Tolerance

Junya NAKAMURA  Tadashi ARARAGI  Toshimitsu MASUZAWA  Shigeru MASUYAMA  

IEICE TRANSACTIONS on Information and Systems   Vol.E97-D   No.1   pp.53-64
Publication Date: 2014/01/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E97.D.53
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Dependable Computing
Byzantine fault tolerance,  asynchronous distributed system,  agreement,  consensus,  state machine replication,  

Full Text: PDF>>
Buy this Article

We propose a new method that accelerates asynchronous Byzantine Fault Tolerant (BFT) protocols designed on the principle of state machine replication. State machine replication protocols ensure consistency among replicas by applying operations in the same order to all of them. A naive way to determine the application order of the operations is to repeatedly execute the BFT consensus to determine the next executed operation, but this may introduce inefficiency caused by waiting for the completion of the previous execution of the consensus protocol. To reduce this inefficiency, our method allows parallel execution of the consensuses while keeping consistency of the consensus results at the replicas. In this paper, we also prove the correctness of our method and experimentally compare it with the existing method in terms of latency and throughput. The evaluation results show that our method makes a BFT protocol three or four times faster than the existing one when some machines or message transmissions are delayed.