非同期式共有メモリシステムにおける改名アルゴリズムに関する調査

圓道浩史 (9951018)


分散アルゴリズムの分野において,改名問題に関する研究が盛んに行われている.改名問題では,システムを構成する各プロセスが新しい名前(識別子)を獲得する.改名問題は,プロセスが名前の獲得を高々一回おこなう一回改名問題と,名前の獲得と解放を繰り返し行う繰り返し改名問題に分類される.

分散アルゴリズムの中には,コンセンサスアルゴリズムやスナップショットアルゴリズムのように,ステップ計算量がプロセスの名前空間サイズに依存するものが存在する.したがって改名によってプロセスの名前空間サイズを縮小することができれば,これらの問題を解くためのステップ計算量を削減できる効果がある.

本課題研究では,改名アルゴリズムの研究における課題を明確化し,また既知のアルゴリズムのアイデアを整理することが重要であるという立場から,非同期式共有メモリシステムにおける改名アルゴリズムの調査を行った.

各アルゴリズムは改名後の名前空間サイズとステップ計算量によって評価した.特にアルゴリズムのステップ計算量が改名前の名前空間サイズに依存しないものを高速な改名アルゴリズムと呼ぶ.さらにステップ計算量が改名手続きにおいて競合するプロセスの数だけに依存するものをアダプティブな改名アルゴリズムと呼ぶ.

本発表では一回改名問題,および繰り返し改名問題に対する,高速改名アルゴリズムと,アダプティブ改名アルゴリズムの調査結果を報告する.

まず始めに非同期式共有メモリシステムと改名問題について簡単に説明し,改名のメリットについても述べる.次に一回改名問題を定義し,本課題研究で調査した高速な一回改名アルゴリズムに関して報告する.また名前空間サイズを縮小するための具体的アイデアを1つ紹介する.

次に繰り返し改名問題を定義し,高速な繰り返し改名アルゴリズムの調査結果をまとめて報告する.また繰り返し改名を行うためのアイデアを1つ紹介する最後にまとめを行う..