ヒープ順序づき木を構成する自己安定プロトコルに関する研究

長谷川 学 (9851084)


ネットワークで相互接続されたプロセスから構成される分散シ ステムにおいて, 故障耐性のあるプロトコルが重要である. 1つの有力な故障耐性プロトコルとして, 自己安定 プロトコルがある.

自己安定プロトコルとは, 任意のネットワー ク状況から実行を開始しても, 解を求めて安定するプロトコル である. この性質から, 自己安定プロトコルは任意の一時故障 に耐性がある.

本論文では, 木ネットワークにおいてプロセス間の 同期を実現する自己安定プロトコルを利用して, ヒープ順序づき木を構成する自己安定プロトコルを提案する. 提案するヒープ順序づき木を構成するプロトコルは, 安定時間 O(h), 各プロセスの領域計算量 O(log n) であり, 既知の結果 と比べ安定時間, 領域計算量と もに改善されている. ここで, h は木の高さを表す.