ADAPTIVE AND DOUBLY-EXPEDITED ONE-STEP CONSENSUS IN BYZANTINE ASYNCHRONOUS SYSTEMS
Abstract
It is known that Byzantine consensus algorithms guarantee a one-step decision only in favorable situations, for instance when all processes propose the same value. Also, no one-step algorithm can support a two-step decision. In this paper, we present a novel generic one-step Byzantine algorithm, called DEX, that circumvents these impossibilities using the condition-based approach. Algorithm DEX has two distinguished features, adaptiveness and double-expedition property. Adaptiveness makes the algorithm sensitive only to the actual number of failures so that it provides fast termination for a large number of inputs when there are fewer failures (a common case in practice). The feature double-expedition property facilitates the two-step decision in addition to the one-step decision. To the best of our knowledge, the double-expedition property is a new concept introduced by this paper, and DEX is the first algorithm having such a feature. Besides, we show that our algorithm is optimal in terms of the number of processes for one-step consensus.
This work has been supported in part by Grant-in-Aid for Scientific Research ((C)21500013) and Young Scientists ((B)22700010) of JSPS.
References
- SIGACT News 32(2), 45 (2001). Crossref, Google Scholar
V. F. Brasileiro , Consensus in One Communication Step, Proc. of the 6th International Conference on Parallel Computing Technologies2127,LNCS (2001) pp. 42–50. Google ScholarD. Dobre and N. Suri , One-step Consensus with Zero-Degradation, Proc. of the International Conference on Dependable Systems and Networks(DSN'06) (2006) pp. 137–146. Google ScholarP. Dutta and R. Guerraoui , Fast Indulgent Consensus with Zero Degradation, Proc. of the 4-th European Dependable Computing Conference on Dependable Computing2485,LNCS (2002) pp. 191–208. Google ScholarA. Mostéfaoui , S. Rajsbaum and M. Raynal , Using Conditions to Expedite Consensus in Synchronous Distributed Systems, Proc. of the 17th international symposium on Distributed Computing(DISC'03)2848,LNCS (2003) pp. 249–263. Google ScholarT. Izumi and T. Masuzawa , One-Step Consensus Solvability, Proc. of the 22nd international symposium on Distributed Computing(DISC'06)4167,LNCS (2006) pp. 224–237. Google ScholarY. J. Song and R. V. Renesse , Bosco: One-Step Byzantine Asynchronous Consensus, Proc. of the 22nd international symposium on Distributed Computing(DISC'08)5218,LNCS (2008) pp. 438–450. Google Scholar- IEEE Transactions on Computers 55(7), 843 (2006), DOI: 10.1109/TC.2006.99. Crossref, ISI, Google Scholar
- IEEE Transactions on Computers 53(4), 453 (2004), DOI: 10.1109/TC.2004.1268403. Crossref, ISI, Google Scholar
- IEEE Transactions on Dependable and Secure Computing 2(1), 46 (2005), DOI: 10.1109/TDSC.2005.13. Crossref, ISI, Google Scholar
A. Mostefaoui , S. Rajsbaum and M. Raynal , Conditions on input vectors for consensus solvability in asynchronous distributed systems, Proc. of the thirty-third annual ACM symposium on Theory of computing (STOC'01) (2001) pp. 153–162. Google Scholar- H. Attiya and J. Welch, Distributed Computing: Fundamentals, Simulations and Advanced Topics, 2004 . Google Scholar


