Vidyasankarのグループk-排他アルゴリズムの高速化
スポンサーリンク
概要
- 論文の詳細を見る
一般化された相互排他問題に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は哲学者が討論会に参加する時間の上限を表す。
- 2003-10-20
著者
-
高村 政孝
群馬大学工学部情報工学科
-
アルトマン トム
Department of Computer Science and Engineering, University of Colorado at Denver
-
五十嵐 善英
群馬大学工学部情報工学科
-
アルトマン トム
Department Of Computer Science And Engineering University Of Colorado At Denver
-
トム アルトマン
Department Of Computer Science University Of Colorado
関連論文
- Vidyasankarのグループk-排他アルゴリズムの高速化
- Vidyasankar のグループκ-排他アルゴリズムの高速化
- 6.考える課題実行時の事象関連電位の計量 : ハノイの塔を使用して(一般セッション 認知・情報)
- チャンネルネットワークにおける安全なメッセージ分配
- 一般化した独立全域木と高信頼性ブロードキャスト
- ビザンチン故障のあるスターグラフ上のブロードキャスティング
- 故障のあるスターネットワーク上の最適なブロードキャスティング(並列・分散)
- 故障のあるスターネットワーク上の最適なブロードキャスティング(並列・分散)
- ローテータグラフにおけるノンアダプティブな耐故障ファイル転送
- ハイパーリングのハイパーキューブへの埋め込み