| 講演名 | 2004/4/9 Timed Uniform Consensus Protocol Tolerating Crash and Timing Faults 泉 泰介, 齋藤 明紀, 増澤 利光, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | コンセンサス問題は,分散システム内の各プロセスが保持する変数の値をある一つの値に合意させる問題であり,分散システム設計の基本問題として多くの応用を持つ.本稿では,コンセンサス問題の一種であるΔ-時限一様コンセンサス問題を,停止故障およびタイミング故障の存在するシステム上で考える.Δ-時限コンセンサスとは,正常なプロセスの合意がある一定時間Δ内に終了することを保証するコンセンサス問題であり,一様コンセンサスとは故障プロセスが異なる値に合意することを許容しないコンセンサス問題である.本稿で提案するプロトコルは,f_t+1プロセスの正常プロセスがシステム内に存在することが保証されているとき,f_tプロセスのタイミング故障に対して耐性を有する.また,f_t+1プロセスが停止故障を起こさないことが保証されているとき,提案するアルゴリズムは,(時限でない)一様コンセンサス問題を解く.故障数に応じて保証する特性が変わる点で,提案するプロトコルは適応的である.本稿では,さらに耐故障性の上限についても考察を行なう.具体的には,高々f_tプロセスが正常なシステムでは,f_tプロセスのタイミング故障に対して耐性を有する時限一様コンセンサスプロトコルは存在しないこと,および,f_tプロセスのタイミング故障に対して耐性を有するいかなる時限一様コンセンサスプロトコルも,停止しないプロセスが高々f_t+1個未満存在するシステムにおいて一様コンセンサスを解くことができないことを示す.このことは,本稿で提案するプロトコルが,耐故障性および適応性の点で最適であることを意味する. |
| 抄録(英) | Δ-timed uniform consensus is a stronger variant of the traditional consensus and it satisfies the following additional property : The correct process terminates its execution within a constant time Δ(Δ-timeliness), and no two processes decide differently (Uniformity). In this paper, we consider the Δ-timed uniform consensus problem in presence of f_t crash processes and f_c timing-faulty processes. This paper proposes a Δ-timed uniform consensus algorithms. The proposed algorithm is adaptive in the following sense : It solves the Δ-timed uniform consensus when at least f_t+1 correct processes exist in the system. If the system has less than f_t+1 correct processes, the algorithm cannot solve the Δ-timed uniform consensus. However, as long as f_t+1 processes are alive, the algorithm solves (non-timed) uniform consensus. We also investigate the maximum number of faulty processes that can be tolerated. We show that any Δ-timed uniform consensus algorithm tolerating up to f_t timing-faulty processes requires that the system has at least f_t+1 correct processes. This impossibility result implies that the proposed algorithm attains the maximal resilience about the number of faulty processes. We also show that any Δ-timed uniform consensus algorithm tolerating up to f_t timing-faulty processes cannot solve the (non-timed) uniform consensus when the system has less than f_t+1 non-crashed processes. This impossibility result implies that our algorithm attains the maximum adaptiveness. |
| キーワード(和) | 時限一様コンセンサス / 故障耐性タイミング故障 / 停止故障 |
| キーワード(英) | Timed uniform consensus / Fault tolerance / Timing fault / Crash fault |
| 資料番号 | CPSY2004-7,DC2004-7 |
| 発行日 |
| 研究会情報 | |
| 研究会 | DC |
|---|---|
| 開催期間 | 2004/4/9(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Dependable Computing (DC) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | Timed Uniform Consensus Protocol Tolerating Crash and Timing Faults |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 時限一様コンセンサス / Timed uniform consensus |
| キーワード(2)（和/英） | 故障耐性タイミング故障 / Fault tolerance |
| キーワード(3)（和/英） | 停止故障 / Timing fault |
| 第 1 著者 氏名（和/英） | 泉 泰介 / Taisuke IZUMI |
| 第 1 著者 所属（和/英） | 大阪大学大学院情報科学研究科 Graduate School of Information Science and Technology, Osaka University |
| 第 2 著者 氏名（和/英） | 齋藤 明紀 / Akinori SAITOH |
| 第 2 著者 所属（和/英） | 大阪大学大学院情報科学研究科 Graduate School of Information Science and Technology, Osaka University |
| 第 3 著者 氏名（和/英） | 増澤 利光 / Toshimitsu MASUZAWA |
| 第 3 著者 所属（和/英） | 大阪大学大学院情報科学研究科 Graduate School of Information Science and Technology, Osaka University |
| 発表年月日 | 2004/4/9 |
| 資料番号 | CPSY2004-7,DC2004-7 |
| 巻番号（vol） | vol.104 |
| 号番号（no） | 13 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |