| 講演抄録／キーワード |
| 講演名 |
2007-03-05 15:55
メッセージの確率的な消失を考慮した耐故障合意アルゴリズム
○泉 泰介・和田幸一（名工大） |
| 抄録 |
（和） |
コンセンサス問題は，分散システム内の各プロセスが保持する変数の値をある一つの値に合意
させる問題であり，分散システム設計の基本問題として多くの応用を持つ．我々は，停止故障
および確率的なメッセージ消失が生じる分散システムのモデルを新たに提案し，その上での
合意アルゴリズムを提案する．提案アルゴリズムは，メッセージの消失確率p が
1 − 4/sqrt(n)より小さいとき，O(f) ラウンドの最悪時期待時間計算量で合意に
達することができる．ここでn は全プロセス数で，f は停止故障プロセス数である．
メッセージ消失を考えないアルゴリズムの最悪時計算量の下界はf + 2 ラウンドで
あることが知られているため，本稿の結果は，時間計算量的に高々定数倍の
オーバヘッドで，高確率で起きるメッセージ消失に対する故障耐性が実現できることを
示している． |
| （英） |
The (uniform) consensus, which is one of fundamental and important
problems for designing fault-tolerant distributed systems, is the problem
that all processes have to agree on a common value that is proposed by
a process. In this paper, we newly introduce a distributed system model
that suffers crash faults and probabilistic omissions where each message
is omitted with a probability p, and consider consensus algrithms on the
model. We propose a consensus algorithm with O(f) worst-case expected
round complexity if p < 1 − 4/sqrt(n). Interstingly, although the
algorithm can tolerate high-probability message omission, its overhead is
not so much: Since all of exiting consensus algorithms that can not
tolerate omissions have the worst-case round complexity at least (f + 2),
our algorithm has the round complexity only a constant time as much as
existing non-omission-tolerant algorithms. |
| キーワード |
（和） |
同期式分散システム / 合意問題 / 故障耐性 / 停止故障 / メッセージ消失 / / / |
| （英） |
Synchronous Distributed System / Uniform Consensus / Fault tolerance / Crash fault / Omission fault / / / |
| 文献情報 |
信学技報, vol. 106, no. 566, COMP2006-58, pp. 59-66, 2007年3月. |
| 資料番号 |
COMP2006-58 |
| 発行日 |
2007-02-26 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|