| 講演名 | 2001/9/7 単方向リングにおける分散資源割当アルゴリズム 佐々木 淳, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本稿では, 同等の資源がネットワーク上に分散してk個存在するときに, 各プロセスが資源を指定することなく, 優先度が高いk個のプロセスにひとつずつ資源を割り当てる資源割当問題を考え, 単方向リング上で時間最適なアルゴリズムを与える.従来の分散環境における資源割当問題では, k-相互排除問題と哲学者の飲酒の問題の二つが主に考えられているが, 本稿で扱う問題はこれらに含まれていない.この問題に対し, 本稿では, 静的な状況で一回の割当を厳密に最適な時間複雑度で実現するアルゴリズムを構築した.さらに, 動的な状況におけるアルゴリズムも示す. |
| 抄録(英) | We designed a time-optimal algorithm for a variant of a k-mutual exclusion in a unidirectional ring. Our problem is that none of the processes specifies the resource that it requires and each resource is assigned to a process with a higher priority than that of unassigned processes without overlapping when there are k resources with the same ability in the network. There are two major conventional resource allocation problems with multiple resources in a distributed context, the k-mutual exclusion problem and the drinking philosophers problem. However, these problems do not include ours. In this paper, we report our design of a strictly time-optimal algorithm in a static situation, which we extended to cope with a dynamic situation. |
| キーワード(和) | 分散アルゴリズム / k-selection / k-相互排除 / 時間複雑度 / 単方向リング / 資源割当 |
| キーワード(英) | distributed algorithm / k-selection / k-mutural exclusion / time complexity / unidirectional ring / resource allocation |
| 資料番号 | COMP2001-34 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2001/9/7(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 単方向リングにおける分散資源割当アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | A Distributed Resource Allocation Algorithm in a Unidirectional Ring |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 分散アルゴリズム / distributed algorithm |
| キーワード(2)（和/英） | k-selection / k-selection |
| キーワード(3)（和/英） | k-相互排除 / k-mutural exclusion |
| キーワード(4)（和/英） | 時間複雑度 / time complexity |
| キーワード(5)（和/英） | 単方向リング / unidirectional ring |
| キーワード(6)（和/英） | 資源割当 / resource allocation |
| 第 1 著者 氏名（和/英） | 佐々木 淳 / Atsushi Sasaki |
| 第 1 著者 所属（和/英） | 日本電信電話株式会社NTTコミュニケーション科学基礎研究所 NTT Communication Science Laboratories, NTT Corporation |
| 発表年月日 | 2001/9/7 |
| 資料番号 | COMP2001-34 |
| 巻番号（vol） | vol.101 |
| 号番号（no） | 307 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |