Efficient Randomized Byzantine Fault-Tolerant Replication Based on Special Valued Coin Tossing

Junya NAKAMURA  Tadashi ARARAGI  Shigeru MASUYAMA  Toshimitsu MASUZAWA  

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

Full Text: PDF>>
Buy this Article

We propose a fast and resource-efficient agreement protocol on a request set, which is used to realize Byzantine fault tolerant server replication. Although most existing randomized protocols for Byzantine agreement exploit a modular approach, that is, a combination of agreement on a bit value and a reduction of request set values to the bit values, our protocol directly solves the multi-valued agreement problem for request sets. We introduce a novel coin tossing scheme to select a candidate of an agreed request set randomly. This coin toss allows our protocol to reduce resource consumption and to attain faster response time than the existing representative protocols.