| 講演名 | 2005/6/10 1ステップ分散合意問題の可解性について(ディペンダブルソフトウェアとネットワーク及び一般) 泉 泰介, 増澤 利光, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 分散合意問題は, 分散システム内の各プロセスが保持する変数の値をある一つの値に合意させる問題であり, 分散システム設計の基本問題として多くの応用を持つ.一般に、故障耐性を有する任意の分散合意アルゴリズムは少なくとも2通信ステップが必要であることが知られているが, その一方で, ある特別な入力集合(e.g.全プロセスが初期状態で同じ値を保持する)に含まれる入力に対し, 1通信ステップで合意に至るようなアルゴリズムが存在することも知られている。本稿では, 1通信ステップで合意に至ることが可能であるような入力集合が満たすべき条件について, 適応的Condition-basedアプローチの手法に基づいて考察する.適応的Condition-basedアプローチとは, 可能な入力の集合をある階層的な区分により順位付けし, 入力の順位に応じた何らかの性能保証をするようなアルゴリズムを設計する手法である.本稿では, ある与えられた順位付けに対して, 順位kの入力については高々k個の停止故障が生じても1通信ステップで合意に至ることを保証するアルゴリズムを考える.また, そのようなアルゴリズムが存在するための, 順位付けが満たすべき必要十分条件を示す.さらに, この条件を満たす具体的な順位付けの例を挙げる.例として挙げた順位付けに対するアルゴリズムは, 従来のアルゴリズムに比べ, より多くの入力に対して1ステップで合意に至ることが可能である. |
| 抄録(英) | While any fault-tolerant asynchronous consensus algorithm requires two communication steps even in failure-free executions, it is known that we can construct the algorithm terminating in one step for some good inputs (e.g. all processes propose a same value). In this paper, we present the necessary and sufficient constraint for the set of inputs for which we can construct the asynchronous consensus algorithm terminating in one step. Our investigation is based on the notion of the condition-based approach: it introduces conditions on input vectors to specify subsets of all possible input vectors and condition-based algorithms can circumvent some impossibility if the actual input vector satisfy a particular condition. More interestingly, conditions treated in this paper are adaptive. That is, we consider hierarchical sequences of conditions whose k-th condition is the set of input vector for which the consensus can be solved in one step even if at most k processes crash. The necessary and sufficient constraint we propose in this paper is one for such condition sequences. In addition, we present several instances of the sufficient condition sequences. Compared with existing constraint for inputs (i.e. all processes propose a same value), all of these instances are more relaxed. |
| キーワード(和) | 分散合意問題 / 故障耐性停止故障 / Condition-basedアプローチ |
| キーワード(英) | Uniform consensus / Fault tolerance / Crash fault / Condition-based approach |
| 資料番号 | DC2005-8 |
| 発行日 |
| 研究会情報 | |
| 研究会 | DC |
|---|---|
| 開催期間 | 2005/6/10(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Dependable Computing (DC) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 1ステップ分散合意問題の可解性について(ディペンダブルソフトウェアとネットワーク及び一般) |
| サブタイトル（和） | |
| タイトル（英） | On Solvability of One-Step Consensus |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 分散合意問題 / Uniform consensus |
| キーワード(2)（和/英） | 故障耐性停止故障 / Fault tolerance |
| キーワード(3)（和/英） | Condition-basedアプローチ / Crash fault |
| 第 1 著者 氏名（和/英） | 泉 泰介 / Taisuke IZUMI |
| 第 1 著者 所属（和/英） | 大阪大学大学院情報科学研究科 Graduate School of Information Science and Technology, Osaka University |
| 第 2 著者 氏名（和/英） | 増澤 利光 / Toshimitsu MASUZAWA |
| 第 2 著者 所属（和/英） | 大阪大学大学院情報科学研究科 Graduate School of Information Science and Technology, Osaka University |
| 発表年月日 | 2005/6/10 |
| 資料番号 | DC2005-8 |
| 巻番号（vol） | vol.105 |
| 号番号（no） | 123 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |