Adaptive One-Step Byzantine Consensus

概要

論文の詳細を見る
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.
一般社団法人情報処理学会の論文
2010-01-19