非同期式状態通信モデルにおける分散アルゴリズムの時間計算量評価の一手法

摘要

分散システムのモデルとして，非同期式モデルがよく用いられる．非同期式モデルでは，各プロセスの動作速度に一切の仮定を置かない．これは実際の分散システムでは，一般に計算機の処理能力は均一でなく，また，同一の計算機でも負荷などの状況により処理速度は変化するためである．しかし，非同期式モデルではプロセスの動作速度の違いによってさまざまな実行が起こりうるため，アルゴリズムの時間計算量の解析は困難である．本稿では，状態通信モデルにおいて，線形状態遷移アルゴリズムというアルゴリズムのクラスを定義し，線形状態遷移アルゴリズムに関しては，同期実行の時間計算量評価と非同期式モデルにおける最悪時時間計算量評価が一致することを示す．ここで同期実行とは，すべてのプロセスの動作速度が等しいと仮定した場合の実行である．また，この結果の適用例として，自己安定Alternatorの時間計算量の評価を行なう．