リングネットワーク上での排他制御問題に対する 故障封じ込め自己安定アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 1998-03-23
• タイトル: リングネットワーク上での排他制御問題に対する 故障封じ込め自己安定アルゴリズム
• タイトル / 言語: en
• タイトル: Fault Containing Self - Stabilizing Algorithms for Mutual Exclusion Problem on Ring Networks
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 大阪大学大学院基礎工学研究科情報数理系専攻
• 著者所属: 大阪大学大学院基礎工学研究科情報数理系専攻
• 著者所属: 大阪大学大学院基礎工学研究科情報数理系専攻
• 著者所属: 大阪大学大学院基礎工学研究科情報数理系専攻
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering Science, Osaka University
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering Science, Osaka University
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering Science, Osaka University
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering Science, Osaka University
• 著者名: 千星裕; 桝田, 秀夫; 辻野, 嘉宏; 都倉, 信樹
• 著者名(英): Yutaka, Senboshi; Hideo, Masuda; Yoshihiro, Tsujino; Nobuki, Tokura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 自己安定アルゴリズムとは，任意のネットワーク状況から有限時間内にシステムが問題に対する望ましい状況 （解状況） に到達し安定する分散アルゴリズムである．このため，任意個のプロセスが一時故障が生じても，その後十分長い間故障が生じなければ，解状況に到達するという特徴がある．しかし通常，分散システムで同時に多数の故障が生じることは稀であると考えられる．そこで，少数個の故障が生じた状況から効率よく解状況に到達する自己安定アルゴリズムが望まれる．本稿では，(） 動作可能なプロセスは公平に動作する，(） 一時故障はどのプロセスでも等確率で生じる，と仮定する．このとき，リングネットワーク上で排他制御問題を解き，さらに唯一つのプロセスで一時故障が生じた状況から平均して定数時間で解状況に到達する自己安定アルゴリズムを，2つの通信モデルのもとでそれぞれ提案する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Self-Stabilizing algorithms are designed to guarantee convergence into some desired stable configuration (legitimate configuration) from any initial configurations 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 aspect, 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 a transient fault occurs on every process with equal probability.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10485570
• 書誌情報: 情報処理学会研究報告プログラミング（PRO）; 巻 1998, 号 30(1997-PRO-018), p. 113-120, 発行日 1998-03-23
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会