| 講演名 | 2004/3/9 木ネットワークにおけるビザンチン故障耐性を有する自己安定辺彩色プロトコル 櫻井 佑輔, 大下 福仁, 増澤 利光, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 自己安定プロトコルは,分散システムが任意の初期状況から実行を開始しても,有限時間内に正しく動作することを保証するプロトコルであり,任意の一時故障に対する耐性を有する.しかし,永久故障に対する耐性は有しておらず,永久故障に対する耐性を有する自己安定プロトコルの設計開発が望まれている.本橋では,永久故障モデルとして,ビザンチン故障を対象に,木ネットワークにおいてビザンチン故障耐性を有する自己安定辺彩色プロトコルの可能性について考察する.本報告ではまず,同時に一つのプロセスしか動作しないCデーモンによるスケジュールを仮定し,システム内のノードの最大次数Δに対してΔ+1色を用いて彩色する自己安定プロトコルを提案する.このプロトコルでは故障の影響を故障ノードからの距離が2までのノードに封じ込めている.また,nをシステム内の総ノード数とするとき,Δ色を用いた辺彩色では,故障の影響が故障ノードから距離Ω(logn)のノードヘ広がることを示す.さらに,同時に複数のプロセスが動作しうるDデーモンを仮定したモデルではビザンチン故障の影響範囲が距離Ω(n)のノードに広がることを示す. |
| 抄録(英) | Self-stabilizing protocols can tolerate any type and any number of transient faults. But self-stabilizing protocols have no guarantee of their behavior against permanent faults. Thus, investigation concerning self-stabilizing protocols resilient to permanent faults is important. This paper proposes a self-stabilizing edge-coloring protocol resilient to Byzantine faults in tree networks. The protocol assumes the central daemon, and use Δ+1 colors where Δ is the maximum degree in the network. This protocol achieves fault containment with radius 2. Moreover, we prove that the containment radius becomes Ω(logn) when use only Δ colors, and prove that the containment radius becomes Ω(n) under the distributed daemon. |
| キーワード(和) | 自己安定 / 故障封じ込め / 辺彩色 / ビザンチン故障 / 木ネットワーク |
| キーワード(英) | self-stabilizing / fault containment / edge-coloring / byzantine fault / tree network |
| 資料番号 | COMP2003-91 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2004/3/9(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 木ネットワークにおけるビザンチン故障耐性を有する自己安定辺彩色プロトコル |
| サブタイトル（和） | |
| タイトル（英） | Self-Stabilizing Edge Coloring Protocol Resilient to Byzantine Faults in Tree Networks |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 自己安定 / self-stabilizing |
| キーワード(2)（和/英） | 故障封じ込め / fault containment |
| キーワード(3)（和/英） | 辺彩色 / edge-coloring |
| キーワード(4)（和/英） | ビザンチン故障 / byzantine fault |
| キーワード(5)（和/英） | 木ネットワーク / tree network |
| 第 1 著者 氏名（和/英） | 櫻井 佑輔 / Yusuke SAKURAI |
| 第 1 著者 所属（和/英） | 大阪大学大学院情報科学研究科 Graduate School of Information Science and Technology,Osaka Univercity |
| 第 2 著者 氏名（和/英） | 大下 福仁 / Fukuhito OOSHITA |
| 第 2 著者 所属（和/英） | 大阪大学大学院情報科学研究科 Graduate School of Information Science and Technology,Osaka Univercity |
| 第 3 著者 氏名（和/英） | 増澤 利光 / Toshimitsu MASUZAWA |
| 第 3 著者 所属（和/英） | 大阪大学大学院情報科学研究科 Graduate School of Information Science and Technology,Osaka Univercity |
| 発表年月日 | 2004/3/9 |
| 資料番号 | COMP2003-91 |
| 巻番号（vol） | vol.103 |
| 号番号（no） | 723 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |