| 講演名 | 1998/5/28 コーラム方式の分散相互排除における同意に必要な最大遅延の最適化 土屋 達弘, 菊野 亨, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 分散相互排除問題とは分散システムを構成する複数のノードの内, 高々1つのノードにのみ特権を与える問題であり, 分散システムにおける最も基本的かつ重要な問題として知られている.この問題を解く一般的な方法として, コテリーと呼ばれる特殊なノード集合の集合を用いる方法がある.コテリーを構成する各ノード集合はコーラムと呼ばれる.この方法では, あるコーラムに属するすべてのノードから同意を得た場合にのみノードは特権を得ることができる.同意を達成するためにはノード間での通信が必要であり, その際に発生する遅延は用いられるコテリーに依存する.従って, 高い性能の実現には予め遅延の小さいコテリーを求めておくことが前提となる.本研究では, 同意に必要な遅延の最悪値を最小にするコテリーを多項式時間で求めるアルゴリズムを提案する.従来知られているアルゴリズムは, ツリー, あるいは, リングといった特殊な形状のシステムだけを対象にしていた.これに対して, 提案するアルゴリズムは全く異なる手法を用いており, 任意の形状のシステムに適用可能である. |
| 抄録(英) | The use of quorums is a well-known approach to achieving distributed mutual exclusion. This approach works based on a coterie, a special set of node groups such that any pair of node groups shares at least one common node. Each node group in a coterie is called a quorum. Mutual exclusion is ensured by imposing each node to get consensus from all nodes in at least one of the quorums before it enters a critical section. In such a quorum-based mutual exclusion scheme, the delay for reaching consensus depends critically on the coterie adopted, thus finding a coterie with small delay is very important for achieving good performance. We propose two polynomial-time algorithms to find max-delay optimal coteries, i.e., coteries that minimize the maximum delay for reaching consensus. Unlike previous algorithms, the proposed algorithms can be applied to systems with arbitrary topologies. |
| キーワード(和) | 分散相互排除 / コーラム / 通信遅延 / コテリー / 分散システム |
| キーワード(英) | distributed mutual exclusion / quorum / communication delay / coterie / distributed system |
| 資料番号 | |
| 発行日 |
| 研究会情報 | |
| 研究会 | SS |
|---|---|
| 開催期間 | 1998/5/28(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Software Science (SS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | コーラム方式の分散相互排除における同意に必要な最大遅延の最適化 |
| サブタイトル（和） | |
| タイトル（英） | Minimizing the Maximum Delay for Reaching Consensus in Quorum-Based Mutual Exclusion Schemes |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 分散相互排除 / distributed mutual exclusion |
| キーワード(2)（和/英） | コーラム / quorum |
| キーワード(3)（和/英） | 通信遅延 / communication delay |
| キーワード(4)（和/英） | コテリー / coterie |
| キーワード(5)（和/英） | 分散システム / distributed system |
| 第 1 著者 氏名（和/英） | 土屋 達弘 / Tatsuhiro Tsuchiya |
| 第 1 著者 所属（和/英） | 大阪大学大学院基礎工学研究科情報数理系専攻 Department of Informatics and Mathematical Science Graduate School of Engineering Science, Osaka University |
| 第 2 著者 氏名（和/英） | 菊野 亨 / Tohru Kikuno |
| 第 2 著者 所属（和/英） | 大阪大学大学院基礎工学研究科情報数理系専攻 Department of Informatics and Mathematical Science Graduate School of Engineering Science, Osaka University |
| 発表年月日 | 1998/5/28 |
| 資料番号 | |
| 巻番号（vol） | vol.98 |
| 号番号（no） | 85 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |