分散k-相互排除問題について

スポンサーリンク

概要

論文の詳細を見る
相互排除問題は多くのプロセスの中の1つに権利を与える問題であり、共有リソースの使用などで用いられる。コータリーと呼ばれる集合を用いて相互排除を行なう分散アルゴリズムが考えられてきた。近年、同一の共有リソースが複数個存在する場合に相当するk-相互排除問題に対し、コータリーを拡張したk-コータリーを用いた分散アルゴリズムが考察されている。本稿では、k-コータリーの新たな定義とそのk-コータリーを用いた分散k-相互排除アルゴリズムを示す。その通信計算量はコータリーの最大のコーラムの大きさを|Q|とするとO(|Q|)となる。プロセス数Nがある整数aに対してN=a^k+1>である場合には、|Q|が高々(k+1)N^k, (k+1)>となるk-コータリーを構成できる。
社団法人電子情報通信学会の論文
1993-09-24

著者

関連論文

もっと見る

スポンサーリンク