| 講演名 | 2005-12-22 故障数制限付きリーダー選挙問題に対する故障検知器 小野 廣隆, / 山下 雅史, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 完全な非同期分散システムにおいては, 一つでも故障プロセスがあると, 合意問題等が解けないことが知られている. 故障検知器は, (必ずしも完全に非同期ではない)非同期分散システム上での故障検知を抽象化であり, ある問題を解くために必要な(最弱な)故障検知器の能力を解析することは, その問題の「難しさ」を理解する上で重要となる. 本論文では, プロセスの故障数に制限がある条件化でのリーダー選挙問題について考察を行う. 故障数に制限がない場合, リーダー選挙問題を解くのに必要な故障検知器のクラスはPであることが知られている. 本論文では, 故障プロセス数が半数未満の場合, Pよりも真に弱いクラスの故障検知器を用いることによりリーダー選挙問題が解けることを示す. これにより, リーダー選挙問題は故障プロセス数において難易度のギャップがあることが導かれる. |
| 抄録(英) | Determining the "weakest" failure detectors is a central topic in asynchronous fault-tolerant distributed system, and indeed the weakest failure detectors have been proposed for several fundamental problems such as Consensus, Non-Blocking Atomic Commit, and Leader Election. We consider failure detectors to solve the leader election problem with f faulty processes, under the assumption that future never affect the output of a failure detector. Sabel et. al. showed the weakest failure detector for the leader election is P, perfect failure detector, with any number of faulty processes under some restricted conditions, and Delporte-Gallet et.al. showed the result holds under more realistic constraints. In this paper, we propose a new failure detector class M to solve the leader election with less than [n/2] faulty processes, and show that M is strictly weaker than P. That is, there is a hardness gap of the leader election with respect to the number of faulty processes. |
| キーワード(和) | 非同期分散システム / 故障検知器 / リーダー選挙 |
| キーワード(英) | Asynchronous Distributed System / Failure Detectors / Leader Election |
| 資料番号 | COMP2005-55 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2005/12/15(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 故障数制限付きリーダー選挙問題に対する故障検知器 |
| サブタイトル（和） | |
| タイトル（英） | Failure Detectors for the Leader Election with Bounded Faulty Processes |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 非同期分散システム / Asynchronous Distributed System |
| キーワード(2)（和/英） | 故障検知器 / Failure Detectors |
| キーワード(3)（和/英） | リーダー選挙 / Leader Election |
| 第 1 著者 氏名（和/英） | 小野 廣隆 / Hirotaka ONO |
| 第 1 著者 所属（和/英） | 九州大学大学院システム情報科学研究院 Department of Computer Science and Communication Engineering, Graduate School of Information Science and Electrical Engineering, Kyusyu University |
| 第 2 著者 氏名（和/英） | / 山下 雅史 / Sung-Hoon PARK |
| 第 2 著者 所属（和/英） | / 九州大学大学院システム情報科学研究院 School of Electrical and Computer Engineering, Chungbuk National University |
| 発表年月日 | 2005-12-22 |
| 資料番号 | COMP2005-55 |
| 巻番号（vol） | vol.105 |
| 号番号（no） | 499 |
| ページ範囲 | pp.- |
| ページ数 | 5 |
| 発行日 | |