| 講演名 | 2003/10/20 Vidyasankarのグループk-排他アルゴリズムの高速化 高村 政孝, アルトマン トム, 五十嵐 善英, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 一般化された相互排他問題にk-排他問題やグループ相互排他問題がある。後者はJoungによって提案された問題であり、これまでに様々なグループ相互排他アルゴリズムが提案されてきた。最近、Vidyasankarによって、k-排他問題とグループ相互排他問題を組み合わせた、k-グループ排他問題が提案された。グループ相互排他問題では、会議室は一つしかなく、同じ興味を持った哲学者同士は平行してその会議室で開催されている討論会に参加することができるが、興味が異なる哲学者同士が並行してその会議室に入ることはできないという制限がある。グループk-排他問題では、利用できる会議室の数はkである。Vidyasankarが考案したアルゴリズムは、多重書き込み/多重読み出し共有変数モデルモデル上で動く、Petersonのn-プロセスアルゴリズムの簡単な拡張である。本論文では、このVidyasankarのアルゴリズムの改良を行い、trying regionでの待ち時間の上限を、n(n-k)c+O(n^3(n-k))lから(n-k)c+O(n(n-k)^2)lに減らした。ここでnはプロセスの数(哲学者の数でもある)、lは二つの連続する原子ステップ間の時間の上限、cは哲学者が討論会に参加する時間の上限を表す。 |
| 抄録(英) | The k-exclusion problem is a natural generalization of the mutual exclusion problem. Group mutual exclusion is also an interesting generalization of mutual exclusion. The latter problem was introduced by Joung, and some algorithms for the problem have been propoed by incorporating mutual exclusin algorithms. Recently Vidyasankar introduced a combined problem of k-exclusion and group mutual exclusion, called the group k-exclusion problem, which occurs in a situation where philosophers with the same interest can attend a forum in a meeting room, but not by philosophers with a different interest in the same meeting room, and up to k meeting rooms are available. Vidyasankar's algorithm is a simple modification of the n-process algorithm by Peterson for the mutual exclusion problem in the asynchronous multi-writer / multi-reader shared memory model. We propose an improvement to Vidyasanker's algorithm. By our modifications we can accelerate the original algorithm. Waiting times in the trying region of the original algorithm and our algorithm are bounded by n(n-k)c+O(n^3(n-k))l and (n-k)c+O(n(n-k)^2)l, respectively, where n is the number of processed, l is upper bound on the time between successive two atomic steps, and c is an upper bound on the time that any philosopher spends in a forum. |
| キーワード(和) | 分散アルゴリズム / グループ相互排他 / k-排他 / ロックアウト回避 / 相互排他 / 共有変数 |
| キーワード(英) | distributed algorithms / group mutual exclusion / k-exclusion / lockout avoidance / mutual exclusion / shared memory |
| 資料番号 | COMP2003-47 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2003/10/20(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | Vidyasankarのグループk-排他アルゴリズムの高速化 |
| サブタイトル（和） | |
| タイトル（英） | Speedup of Vidyasankar's Algorithm for the Group k-Exclusion Problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 分散アルゴリズム / distributed algorithms |
| キーワード(2)（和/英） | グループ相互排他 / group mutual exclusion |
| キーワード(3)（和/英） | k-排他 / k-exclusion |
| キーワード(4)（和/英） | ロックアウト回避 / lockout avoidance |
| キーワード(5)（和/英） | 相互排他 / mutual exclusion |
| キーワード(6)（和/英） | 共有変数 / shared memory |
| 第 1 著者 氏名（和/英） | 高村 政孝 / Masataka TAKAMURA |
| 第 1 著者 所属（和/英） | 群馬大学工学部情報工学科 Department of Computer Science, Gunma University |
| 第 2 著者 氏名（和/英） | アルトマン トム / Tom ALTMAN |
| 第 2 著者 所属（和/英） | / 群馬大学工学部情報工学科 Department of Computer Science and Engineering, University of Colorado at Denver |
| 第 3 著者 氏名（和/英） | 五十嵐 善英 / Yoshihide IGARASHI |
| 第 3 著者 所属（和/英） | Department of Computer Science, Gunma University |
| 発表年月日 | 2003/10/20 |
| 資料番号 | COMP2003-47 |
| 巻番号（vol） | vol.103 |
| 号番号（no） | 394 |
| ページ範囲 | pp.- |
| ページ数 | 7 |
| 発行日 | |