Adaptive One-Step Byzantine Consensus

• Item type: SIG Technical Reports(1)
• 公開日: 2010-01-19
• タイトル: Adaptive One-Step Byzantine Consensus
• タイトル / 言語: en
• タイトル: Adaptive One-Step Byzantine Consensus
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Nagoya Institute of Technology
• 著者所属: Nagoya Institute of Technology
• 著者所属: Nagoya Institute of Technology
• 著者所属(英): en
• 著者所属(英): Nagoya Institute of Technology
• 著者所属(英): en
• 著者所属(英): Nagoya Institute of Technology
• 著者所属(英): en
• 著者所属(英): Nagoya Institute of Technology
• 著者名: Nazreen, Banu; Taisuke, Izumi; Koichi, Wada
• 著者名(英): Nazreen, Banu; Taisuke, Izumi; Koichi, Wada
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: It is known that Byzantine consensus algorithms guarantee one-step decision only in favorable situations (e.g. when all processes propose the same value) and no one-step algorithm can support two-step decision. In this paper, we present a novel one-step Byzantine algorithm DEX based on the condition-based approach that circumvents the above impossibilities. Algorithm DEX is adaptive in the sense that it is sensitive to only actual number of failures, and hence achieves fast termination for large number of inputs when less number of processes are faulty. In addition, it also has double-expedition property, so that it allows two-step decision in addition to one-step decision by introducing two condition-based mechanisms running concurrently. To the best of our knowl edge, double-expedition property is a new concept introduced by this paper and DEX is the first algorithm having such a feature. Even though DEX takes four steps at worst in well-behaved runs while existing algorithms takes only three, it provides fast termination for large number inputs, which makes us to expect that our algorithm works faster in average in practical situations.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: It is known that Byzantine consensus algorithms guarantee one-step decision only in favorable situations (e.g. when all processes propose the same value) and no one-step algorithm can support two-step decision. In this paper, we present a novel one-step Byzantine algorithm DEX based on the condition-based approach that circumvents the above impossibilities. Algorithm DEX is adaptive in the sense that it is sensitive to only actual number of failures, and hence achieves fast termination for large number of inputs when less number of processes are faulty. In addition, it also has double-expedition property, so that it allows two-step decision in addition to one-step decision by introducing two condition-based mechanisms running concurrently. To the best of our knowl edge, double-expedition property is a new concept introduced by this paper and DEX is the first algorithm having such a feature. Even though DEX takes four steps at worst in well-behaved runs while existing algorithms takes only three, it provides fast termination for large number inputs, which makes us to expect that our algorithm works faster in average in practical situations.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2010-AL-128, 号 2, p. 1-9, 発行日 2010-01-19
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会