・名古屋工業大学学術機関リポジトリは、名古屋工業大学内で生産された学術情報を電子的に収集・保存・発信するシステムです。 ・論文の著作権は、著者または出版社が保持しています。著作権法で定める権利制限規定を超える利用については、著作権者に許諾を得てください。 ・著者版フラグに「author」と記載された論文は、著者原稿となります。実際の出版社版とは、レイアウト、字句校正レベルの異同がある場合もあります。 ・Nagoya Institute of Technology Repository Sytem is built to collect, archive and offer electronically the academic information produced by Nagoya Institute of Technology. ・The copyright and related rights of the article are held by authors or publishers. The copyright owners' consents must be required to use it over the curtailment of copyrights. ・Textversion "Author " means the article is author's version. Author version may have some difference in layouts and wordings form publisher version.
(c)2010 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
It is known that Byzantine consensus algorithms guarantee one-step decision only in favorablesituations (e.g. when all processes propose the same value) and no one-step algorithm can support two-step decision. This paper presents DEX, a novel one-step Byzantine algorithm that circumvents theseimpossibilities using the condition-based approach. Algorithm DEX has two distinguished features:Adaptiveness and Double-expedition property. Adaptiveness makes it sensitive to only actual numberof failures so that it provides fast termination for more number of inputs when there are fewer failures (acommon case in practice). The double-expedition property facilitates two-step decision in addition toone-step decision by running two condition-based mechanisms in parallel. To the best of our knowledge,double-expedition property is the new concept introduced by this paper, and DEX is the ￣rst algorithmhaving such a feature. Although DEX takes four steps at worst in well-behaved runs while existingone-step algorithms take only three, it is expected to work efficiently because the worst-case does notoccur so often in practice.
This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible.Proceedings on The 40th Annual IEEE/IFIP International Conference on Dependable Systems and Networks
Doubly-Expedited One-Step Byzantine Consensus
本文_fulltext
(200.09KB)
