非同期共有メモリシステムにおける ポイント競合度適応型繰り返し改名アルゴリズムに関する研究

梅谷真也 (0051012)

非同期共有メモリシステム上で， 効率良く名前の獲得と解放を繰り返し行う繰り返しM-改名アルゴリズムは， 分散アルゴリズムの分野において重要な基礎アルゴリズムである． システムに属する $N$ 個のプロセスは， 0,1,...,N-1 の範囲の相異なる名前を最初に持っている． 繰り返しM-改名アルゴリズムを実行することで， 0,1,...,M-1 の範囲の名前を新しく獲得し， その名前を使用した後に解放する． 複数のプロセスが同時に同一の名前を保持することはない．

従来の最良の繰り返しk(2k-1)-改名アルゴリズムとして， Afek らがステップ計算量 O(k^3)， 空間計算量 O(n^3N) のアルゴリズムを提案した． ここで，k はポイント競合度， n は k の上界を示す． ポイント競合度とは， 名前を獲得する際に， 同時にステップを実行したり名前を保持しているプロセスの最大数である． さらに，変数の値が非有界となるが， ステップ計算量 O(k^2 log k)， 空間計算量 O(n^3N) の繰り返し k(2k-1)-アルゴリズムも提案している． 本研究では，これら従来の繰り返しk(2k-1)-改名アルゴリズムより効率の良い， ステップ計算量 O(k^2)， 空間計算量 O(n^2N) かつ 変数の値が有界な k(2k-1)-改名アルゴリズムを実現した．