World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

ADAPTIVE AND DOUBLY-EXPEDITED ONE-STEP CONSENSUS IN BYZANTINE ASYNCHRONOUS SYSTEMS

    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

    • I. Keider and S. Rajsbaum, SIGACT News 32(2), 45 (2001). CrossrefGoogle Scholar
    • V. F. Brasileiroet al., Consensus in One Communication Step, Proc. of the 6th International Conference on Parallel Computing Technologies2127, LNCS (2001) pp. 42–50. Google Scholar
    • D. 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 Scholar
    • P. 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 Scholar
    • A. 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 Scholar
    • T. 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 Scholar
    • Y. 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
    • T. Izumi and T. Masuzawa, IEEE Transactions on Computers 55(7), 843 (2006), DOI: 10.1109/TC.2006.99. Crossref, ISIGoogle Scholar
    • R. Guerraoui and M. Raynal, IEEE Transactions on Computers 53(4), 453 (2004), DOI: 10.1109/TC.2004.1268403. Crossref, ISIGoogle Scholar
    • R. Friedman, A. Mostefaoui and M. Raynal, IEEE Transactions on Dependable and Secure Computing 2(1), 46 (2005), DOI: 10.1109/TDSC.2005.13. Crossref, ISIGoogle 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