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