| 講演名 | 2001/1/15 信頼性を最大にするκコテリーの構成法の提案 崔 銀恵, 土屋 達弘, 菊野 亨, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | κ相互排除とは分散システムで資源を同時に使用するノード数をκ個以下に抑えることを保証する問題である.この問題を解く代表的な方法としてκコテリーを用いる手法があり, 信頼性の高いκコテリーの構築が求められている.これまでに幾つかのκコテリーの構成法が提案されているが, ノード及びリンク故障の可能性がある任意のトポロジーの分散システムで信頼性を最大にするκコテリーの構成法は未だ提案されていない.本研究では, まず, 任意の分散システムで信頼性を最大にするκコテリーの構成問題を非線形0-1整数計画問題として定式化する.次に, 定式化した問題を解くために分枝限定法に基づくアルゴリズムを提案する.提案法では定式化した問題の緩和問題として導いた線形0-1整数計画問題を用いることで分枝限定木の探索空間を減らす.最後に, 提案法をプログラムとして実装し, 適用実験を通して提案法の有効性を示す. |
| 抄録(英) | The κ-mutual exclusion is the problem of guaranteeing that no more than κ computing nodes enter a critical section simultaneously in a distributed system. The use of a κ-coterie, which is a special set of node groups, is known as a robust approach to solve this problem. So far, several methods have been proposed for constructing κ-coteries that provide high availability. Although, among them, κ-majority coteries have been shown to be optimal in terms of availability for fully connected networks with completely reliable links, no construction of optimal κ-coteries has been suggested for general networks. In this paper, we propose a method for constructing optimal κ-coteries in general topology networks with unreliable nodes and links. In the proposed method, the problem of finding an optimal κ-coterie in a general network is formulated as a 0-1 integer nonlinear programming problem. To solve the formulated problem, we also propose a branch-and-bound method based on a linear programming relaxation. The feasibility of the proposed method is shown through an experiment conducted for several networks. |
| キーワード(和) | κ相互排除問題 / κコテリー / 信頼性 / 0-1整数計画問題 / 分枝限定法 |
| キーワード(英) | κ-mutual exclusion / κ-coterie / availability / 0-1 integer programming / branch-and-bound |
| 資料番号 | SS2000-36 |
| 発行日 |
| 研究会情報 | |
| 研究会 | SS |
|---|---|
| 開催期間 | 2001/1/15(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Software Science (SS) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 信頼性を最大にするκコテリーの構成法の提案 |
| サブタイトル（和） | |
| タイトル（英） | Constructing Optimal κ-Coteries in General Networks |
| サブタイトル（和） | |
| キーワード(1)（和/英） | κ相互排除問題 / κ-mutual exclusion |
| キーワード(2)（和/英） | κコテリー / κ-coterie |
| キーワード(3)（和/英） | 信頼性 / availability |
| キーワード(4)（和/英） | 0-1整数計画問題 / 0-1 integer programming |
| キーワード(5)（和/英） | 分枝限定法 / branch-and-bound |
| 第 1 著者 氏名（和/英） | 崔 銀恵 / Eunhey Choi |
| 第 1 著者 所属（和/英） | 大阪大学 大学院基礎工学研究科 情報数理系専攻 Department of Informatics and Mathematical Science Graduate School of Engineering Science, Osaka University |
| 第 2 著者 氏名（和/英） | 土屋 達弘 / Tatsuhiro Tsuchiya |
| 第 2 著者 所属（和/英） | 大阪大学 大学院基礎工学研究科 情報数理系専攻 Department of Informatics and Mathematical Science Graduate School of Engineering Science, Osaka University |
| 第 3 著者 氏名（和/英） | 菊野 亨 / Tohru Kikuno |
| 第 3 著者 所属（和/英） | 大阪大学 大学院基礎工学研究科 情報数理系専攻 Department of Informatics and Mathematical Science Graduate School of Engineering Science, Osaka University |
| 発表年月日 | 2001/1/15 |
| 資料番号 | SS2000-36 |
| 巻番号（vol） | vol.100 |
| 号番号（no） | 569 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |