| 講演名 | 1998/3/23 リングネットワーク上での排他制御問題に対する故障封じ込め自己安定アルゴリズム 千星 裕, 枡田 秀夫, 辻野 嘉宏, 都倉 信樹, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 自己安定アルゴリズムとは, 任意のネットワーク状況から有限時間内にシステムが問題に対する望ましい状況(解状況)に到達し安定する分散アルゴリズムである.このため, 任意個のプロセスが一時故障が生じても, その後十分長い間故障が生じなければ, 解状況に到達するという特徴がある.しかし通常, 分散システムで同時に多数の故障が生じることは稀であると考えられる.そこで, 少数個の故障が生じた状況から効率よく解状況に到達する自己安定アルゴリズムが望まれる.本稿では, (1)動作可能なプロセスは公平に動作する, (2)一時故障はどのプロセスでも等確率で生じる, と仮定する.このとき, リングネットワーク上で排他制御問題を解き, さらに唯一のプロセスで一時故障が生じた状況から平均して定数時間で解状況に到達する自己アルゴリズムを, 2つの通信モデルのもとでそれぞれ提案する. |
| 抄録(英) | Self-stabilizing algorithms are designed to guarantee convergence into some desired stable configuration (legitimate configuration) from any initial configuration arising out of an arbitrarily large number of transient faults. However, in a well-designed system, the simultaneous occurrence of a large number of faults is rare. As one of approaches focusing on this aspects, it is desirable to design self-stabilizing algorithms that efficiently recover from small number of faults. In this paper, we present two algorithms for mutual exclusion problem on ring networks. These algorithms are not only self-stabilizing, but also converge in constant time on average from a configuration with a single transient fault into legitimate configuration, if scheduler is fair and transient fault occurs on every process with equal probability. |
| キーワード(和) | 分散アルゴリズム / 一時故障 / 自己安定 / 故障封じ込め |
| キーワード(英) | distributed algorithm / transient fault / self-stabilization / fault-containment |
| 資料番号 | |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1998/3/23(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | リングネットワーク上での排他制御問題に対する故障封じ込め自己安定アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Fault Containing Self-Stabilizing algorithms for Mutual Exclusion Problem on Ring Networks |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 分散アルゴリズム / distributed algorithm |
| キーワード(2)（和/英） | 一時故障 / transient fault |
| キーワード(3)（和/英） | 自己安定 / self-stabilization |
| キーワード(4)（和/英） | 故障封じ込め / fault-containment |
| 第 1 著者 氏名（和/英） | 千星 裕 / Yutaka Senboshi |
| 第 1 著者 所属（和/英） | 大阪大学大学院基礎工学研究科情報数理系専攻 Graduate School of Engineering Science, Osaka University |
| 第 2 著者 氏名（和/英） | 枡田 秀夫 / Hideo Masuda |
| 第 2 著者 所属（和/英） | 大阪大学大学院基礎工学研究科情報数理系専攻 Graduate School of Engineering Science, Osaka University |
| 第 3 著者 氏名（和/英） | 辻野 嘉宏 / Yoshihiro Tsujino |
| 第 3 著者 所属（和/英） | 大阪大学大学院基礎工学研究科情報数理系専攻 Graduate School of Engineering Science, Osaka University |
| 第 4 著者 氏名（和/英） | 都倉 信樹 / Nobuki Tokura |
| 第 4 著者 所属（和/英） | 大阪大学大学院基礎工学研究科情報数理系専攻 Graduate School of Engineering Science, Osaka University |
| 発表年月日 | 1998/3/23 |
| 資料番号 | |
| 巻番号（vol） | vol.97 |
| 号番号（no） | 627 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |