| 講演名 | 2009-10-20 ラウンドモデルからの変換による非同期コンセンサスアルゴリズムの導出(ネットワーク環境でのディペンダビリティ) 赤井 和幸, 土屋 達弘, 菊野 亨, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | コンセンサスは分散システムの耐故障実現に関わる本質的な問題である.この問題を解くためのアルゴリズムはメッセージ遅延,並行性,故障などの要因で設計・検証が困難である.この困難さを解決するために,それらを抽象化した計算モデルであるラウンドモデルがいくつか提案されている.本研究ではラウンドモデル上で記述されている2つのコンセンサスアルゴリズムを対象とし,それらを通常の非同期分散システムで動作するように変換する.これによって,ラウンドモデル上でコンセンサスアルゴリズムを設計すれば通常の非同期分散システムで動作するように変換できることを示す. |
| 抄録(英) | Consensus is a fundamental problem faced in implementing fault-tolerant distributed systems. The design and verification of algorithms to solve this problem are difficult because of message delay, concurrency, and faults inherent to distributed systems. To solve this difficulty, several round models, which are abstract computation models for distributed systems, have been developed. In this paper, we report our experience in which we converted two consensus algorithms designed for a round model into a conventional asynchronous distributed system model. This experience supports the usefulness of the two-step design method, in which an algorithm is designed based on the round model and then is translated into the conventional model. |
| キーワード(和) | 耐故障分散システム / コンセンサス問題 / ラウンドモデル |
| キーワード(英) | fault-tolerant distributed system / consensus problem / round model |
| 資料番号 | DC2009-25 |
| 発行日 |
| 研究会情報 | |
| 研究会 | DC |
|---|---|
| 開催期間 | 2009/10/13(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Dependable Computing (DC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ラウンドモデルからの変換による非同期コンセンサスアルゴリズムの導出(ネットワーク環境でのディペンダビリティ) |
| サブタイトル（和） | |
| タイトル（英） | Deriving an Asynchronous Consensus Algorithm from a Round Model-Based Algorithm |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 耐故障分散システム / fault-tolerant distributed system |
| キーワード(2)（和/英） | コンセンサス問題 / consensus problem |
| キーワード(3)（和/英） | ラウンドモデル / round model |
| 第 1 著者 氏名（和/英） | 赤井 和幸 / Kazuyuki AKAI |
| 第 1 著者 所属（和/英） | 大阪大学大学院情報科学研究科 Graduate School of Information Science and Technology, Osaka University |
| 第 2 著者 氏名（和/英） | 土屋 達弘 / Tatsuhiro TSUCHIYA |
| 第 2 著者 所属（和/英） | 大阪大学大学院情報科学研究科 Graduate School of Information Science and Technology, Osaka University |
| 第 3 著者 氏名（和/英） | 菊野 亨 / Tohru KIKUNO |
| 第 3 著者 所属（和/英） | 大阪大学大学院情報科学研究科 Graduate School of Information Science and Technology, Osaka University |
| 発表年月日 | 2009-10-20 |
| 資料番号 | DC2009-25 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | 238 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |