オブリビアス敵対スケジューラ下でのMRSWレジスタを用いた乱択合意アルゴリズム

中島 悟(1251077)


本研究では, Multi-Reader Single-Writer(MRSW) レジスタモデル上で 、オブリビアス敵対スケジューラ下での乱択合意アルゴリズムを提案する. 乱択合意アルゴリズムを1-ε(0<ε<1)の確率で合意をとるConciliatorアルゴリズム と合意がとれたことを検出するAdopt-Commitオブジェクトの二つを用いて実現する 手法が知られている. 本研究では, ConciliatorアルゴリズムとAdopt-Commitオブジェクトを 実現するアルゴリズムのそれぞれに対して, MRSWレジスタを用いた新規手法を提案し, 乱択合意アルゴリズムの提案を行う.

提案したAdopt-Commitオブジェクトの実現アルゴリズムは, Multi-Reader Multi-Writer (MRMW) レジスタモデルに対して提案された既存手法に比べ,時間計算量を改善する. もう一方の提案したConciliatorアルゴリズムでは, 時間計算量の上界に関する解析では, 既存手法と漸近的に等しいことを証明した. さらに, 提案したConciliatorアルゴリズムに対しては, 計算機実験により, 既存手法より時間計算量が優れていることを確認した. また, Conciliatorアルゴリズム中で用いる確率に対して, 同アルゴリズムを計算機でシミュレーションした際に得られる 最適な確率を利用する手法を提案している. 最適な確率を使用することでより少ない時間計算量でConciliatorアルゴリズムが実現できることを, 計算機実験により, 評価確認した.

二つの提案アルゴリズムから構成される乱択合意アルゴリズムは, 時間計算量の解析では, アルゴリズムの初期値の値域の大きさがある値を超える場合, 既存手法よりも時間計算量が優れていることを証明した. 計算機実験においては, 実験結果から, 提案したConciliatorアルゴリズムが既存手法よりも時間計算量が優れていることがわかったため, 提案している乱択合意アルゴリズムに対しても, 既存手法よりも時間計算量が優れていることがわかる.