非同期共有メモリシステムにおける適応型繰り返し改名アルゴリズム

概要

論文の詳細を見る
本論文では, 非同期共有メモリシステム上で, 効率良く名前の獲得と解放を繰り返し行う分散アルゴリズム(改名アルゴリズム)を提案する.N個のプロセスは1, 2, ・・・, Nの範囲の一意な名前を最初に持っているが, M-改名アルゴリズムを実行することで, 新しく1, 2, ・・・, Mの範囲の一意な名前を獲得する.従来の最良のO(k^2)-改名アルゴリズムとして, Afekらがステップ計算量O(k^3), 空間計算量O(n^3N)のアルゴリズムを提案した[1].ここで, kはポイント競合度と呼ばれ, 名前を獲得する際に, 同時にステップを実行したり名前を保持しているプロセスの数の最大値を示す.また, nはkの上界である.さらに, 変数の値が非有界となるが, ステップ計算量O(k^2logk), 空間計算量O(n^3N)のアルゴリズムも提案されている[1].本論文ではこれら従来の改名アルゴリズムより効率の良い, ステップ計算量O(k^2), 空間計算量O(n^2N)のO(k^2)-改名アルゴリズムを提案する.
一般社団法人情報処理学会の論文
2001-09-25