| 講演名 | 1993/5/27 自己安定相互排除アルゴリズムの実験的評価とその改良 梅本 成俊, 角川 裕次, 山下 雅史, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 自己安定アルゴリズム(self-stabilizingal gorithm)は任意のネットワーク状況から開始することで出来、有限時間内にある正常な状況に還移させることの出来る分散アルゴリズムである。Shlomi Dolevらは任意のネットワークトポロジで動作する自己安定相互排除アルゴリズムを提案している。[1]。このアルゴリズムはネットワーク上に生成木を生成し、その上で相互排除を行なうものである。本稿では、このアルゴリズムでの、安定化に必要な時間とネットワークポロジとの関係について実験的に評価し、二進木で良い結果が得られることを示す。更に、完全ネットワーク上で動作する自己安定二進生成木アルゴリズムを提案し、その正当性を示す。 |
| 抄録(英) | Self-stabilizing algorithms are distributed algorithms that can be staxted from any network configulation and can rearch a legitimate configulation within a finite period.Dolev et al. proposed a self-stabilizing mutual exclusion algorithm£1!which wor ks on any network topology.This algorithm consists of a spanning tree algorithm and a mutual exclusion algorithm.In this paper,we investigate the relationship between network topologies and atomic steps(period)necessary to stabilize.We show that binary trees require less atomic steps for mutual exclusion by computer simulation.Then,we propose a self-stabilizing binary spanning tree algorithm which works on complete networks and show its correctness. |
| キーワード(和) | 自己安定 / 相互排除 / ネットワーク形状 / 原子ステップ / 生成木 |
| キーワード(英) | self-stabilizing / mutual exclusion / network topology / atomic step / spanning tree |
| 資料番号 | COMP93-16,SS93-10 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1993/5/27(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 自己安定相互排除アルゴリズムの実験的評価とその改良 |
| サブタイトル（和） | |
| タイトル（英） | An Experimental Evaluation and Improvement of Self-Stabilizing Mutual Exclusion Algorithm |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 自己安定 / self-stabilizing |
| キーワード(2)（和/英） | 相互排除 / mutual exclusion |
| キーワード(3)（和/英） | ネットワーク形状 / network topology |
| キーワード(4)（和/英） | 原子ステップ / atomic step |
| キーワード(5)（和/英） | 生成木 / spanning tree |
| 第 1 著者 氏名（和/英） | 梅本 成俊 / Narutoshi Umemoto |
| 第 1 著者 所属（和/英） | 広島大学工学部 Faculty of Engineering,Hiroshima University |
| 第 2 著者 氏名（和/英） | 角川 裕次 / Hirotsugu Kakugawa |
| 第 2 著者 所属（和/英） | 広島大学工学部 Faculty of Engineering,Hiroshima University |
| 第 3 著者 氏名（和/英） | 山下 雅史 / Masafumi Yamashita |
| 第 3 著者 所属（和/英） | 広島大学工学部 Faculty of Engineering,Hiroshima University |
| 発表年月日 | 1993/5/27 |
| 資料番号 | COMP93-16,SS93-10 |
| 巻番号（vol） | vol.93 |
| 号番号（no） | 81 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |