論 文
LAシンポジ ウム（ 情報基礎理論ワークシ ョップ ）論文小特集
木ネット ワーク上のヒープ 順序構成自己安定プ ロト コル
浮穴 学慈
†長谷川 学
†片山 喜章
†増澤 利光
†藤原 秀雄
†A Self-Stabilizing Max-Heap Protocol in Tree Networks
Satoshige UKENA†, Manabu HASEGAWA†, Yoshiaki KATAYAMA†, Toshimitsu MASUZAWA†, and Hideo FUJIWARA†
あらまし ネット ワークで相互接続され たプ ロセスから 構成され る分散シ ステムに おいて ，故障耐性のあるプ ロト コルが 重要である．故障耐性を実現する有力な手法の一つに ，自己安定プ ロトコルが ある．自己安定プ ロト コルとは ，任意のネット ワーク状況から 実行を開始し ても，解を求めて安定するプ ロト コルである．この性質か ら ，自己安定プ ロト コルは任意の一時故障に 耐性が ある．本論文では ，木ネット ワークにおいてプ ロセス間の同 期を実現する自己安定プ ロト コルを利用し て ，ヒープ 順序付き木を構成する自己安定プ ロト コルを提案する．提 案するヒープ 順序付き木を構成するプ ロト コルは ，安定時間O(h)，各プロセスの領域計算量 O(K) であり，既 知の結果と比べ安定時間，領域計算量ともに 改善され ている．ここで ，h は木の高さ，Kは入力のサイズを表す．
キーワード 分散シ ステム，木ネット ワーク，自己安定プ ロト コル ，隣接間同期化，ヒープ
1. ま え がき
ネット ワークで相互接続され たプ ロセ スからなる分 散シ ステムにおいて ，プ ロセスが 協調し て問題を解く プ ロト コルの研究が 盛んに 行われている．特に ，一部 のプ ロセ スの故障にかかわらず，問題を解くことので きる故障耐性を有するプ ロトコルが 重要視されている．
通常のプ ロト コルでは ，プ ロト コル 実行開始時の分 散シ ステムの大域状況が ，あらかじ め決められた初期 状況であると仮定する．つまり，各プ ロセスは，あらか じ め決められた初期状態から実行を開始する．これに 対し ，自己安定プ ロトコル（self-stabilizing protocol） は ，プ ロト コル 実行開始時の分散シ ステムの大域状況 について 何も定めない．つまり，自己安定プ ロト コル は ，任意の大域状況から 実行を開始し ても，問題の解 を求めた状況に 安定するプ ロト コルである．この性質 から ，自己安定プ ロト コルでは ，プ ロセ スの一時的な 故障（プ ロセスの変数の値，プ ログ ラムカウンタの値 の破壊など ）により分散シ ステムがど のような大域状 況に 陥っても，故障し たプ ロセ スが 復旧すれば ，自動 的に 再び 解を求めた状況で 安定する．し たが って自己
†奈良先端科学技術大学院大学情報科学研究科 ，生駒市
Graduated School of Information Science, Nara Institute of Science and Technology, Ikoma-shi, 630–0101 Japan
安定プ ロト コルは ，長期にわたって分散シ ステムの状 況を安定に 保ち，プ ロセ スの一時的な故障に 柔軟に 対 応することが 求められ る分散シ ステムの実現に適し て いる．自己安定プ ロトコルは1974年にDijkstra [3]に よって初めて導入され た概念であるが ，一時故障に 対 し て優れた故障耐性をもつことから ，故障耐性のあ る プ ロト コルとし て注目され ，特に 近年，多くの研究が 行われている．
ヒープ は ，逐次アルゴ リズムにおいて 重要なデ ータ 構造であり，ソート や優先順序キューなど ，多くの応 用をもつ．このよ うな重要なデ ータ構造をネット ワー ク上に 分散型デ ータ構造とし て実現し ，分散シ ステム の設計・開発に利用することは有用である．そのため ， 様々なデ ータ構造に 対し ，それらをネット ワーク上に 実現するためのプ ロト コル（ 分散アルゴ リズム ）に 関 する研究が ，数多く行われている．
本 論 文で は ，木 ネット ワ ー クで ヒ ープ 順 序 付き 木 を 構成する自 己安定プ ロト コル を 提案する ．ここで ， ヒ ープ 順 序 付き 木 の 構 成と は ，各プ ロ セ スが もつ 値
（ 入力値 ）を，ヒープ 順序を満たす（ つまり，各プ ロセ スがその子プ ロセ スよりも大きい値をもつ ）ように 並 べ換え ることである．なお，本論文では 木ネット ワー クを対象とするが ，生成木を構成する自己安定プ ロト
コルを併用することにより，提案するプ ロト コルは 一 般のネット ワークに対し ても適用できる．
木ネット ワークでヒープ 順序付き木を構成する自己 安定プ ロト コルは ，Bourgonら[2]に よって 提案され ている．このプ ロト コルの安定時間は O(nh)である． ここで ，nはシ ステムのプ ロセス数，hは 木の高さで ある．また，各プ ロセ スの領域計算量は O(δK)であ る．ここで ，δはプ ロセ スの次数，Kは 入力値のサ イ ズである．
Alima [1]は ，木ネット ワー クに 対し て ，安定時間 O(h)，各プ ロセ スの領域計算量O(δ + K)のヒープ 順 序付き木を構成する自己安定プ ロト コルを提案し てい る．し かし このプ ロト コルでは 隣接プ ロセス間で1度 し か 値の比較・交換を行わず，正し くヒープ 順序付き 木を構成できない．このプ ロト コルを修正し たものを 繰返し 適用すれば ヒープ 順序付き木の構成も可能とな るが ，そのときの安定時間はO(h
2)
になってし まう． 本論文では ，安定時間O(h)，各プ ロセ スの 領域計 算量O(K)のヒープ 順序付き木を構成する自己安定プ ロト コルを提案する．これは文献[1], [2]のプ ロト コル と比べ，安定時間，領域計算量をともに改善し ている． 文献[1], [2]のプ ロト コルの安定時間が 大きいのは ，大 域的同期化プ ロト コル（ 根がシ ステム全体の調停者と なってプ ロセスを同期させ る ）を使用し ているためで ある．そこで ，本論文では ，隣接プ ロセ ス間でのみ同 期を実現する隣接間同期化プ ロト コル[4]を利用し て ， ヒープ 順序付き木を構成する自己安定プ ロト コルを設 計する．
同期化プ ロト コルは ，分散シ ステムにおいて，非同 期式シ ステムで 同期式シ ステムを模倣することを可能 にするプ ロト コルであり，幅広く研究されている[5]∼ [7]．Johnenらは ，木ネット ワー クにおいて 自己安定 隣接間同期化プ ロト コルを 提案し ている[4]．これは ， 木ネット ワークで隣接プ ロセス間の同期を実現するも のである．つまり，任意の隣接プ ロセ ス間で ，同時に 両方が 動作することなく，いずれか 一方ずつ，交互に 動作させ る仕組みを 提供する．このプ ロト コルの安定 時間は0であり，1プ ロセッサに つき1ビ ット の領域
（ 領域計算量O(1)）を必要とする．
本論文の構成は ，以下のとおりである．2.では ，分 散シ ステム，自己安定プ ロト コル ，隣接間同期化問題， ヒープ 順序付き木構成問題について定義を行う．3.で は ，隣接間同期化プ ロト コルを示す．4.では ，ヒープ 順序付き木を構成する自己安定プ ロト コルを提案する．
最後に ，5.で 本論文での結論について述べる．
2. 諸 定 義
2. 1 分散シ ステム
分 散 シ ス テ ム は ，無 向 連 結 グ ラ フ D = (V, E) で 定 義 さ れ る ．こ こ で ，V は 頂 点 の 集 合 (V = {0, 1, · · · , n − 1}と す る)，Eは 辺の 集 合と す る ．そ れぞれの頂点はプ ロセ スを表し ，辺は 双方向通信リン クを表す．本論文では ，木構造のネット ワークを扱う． ネット ワーク中で 根プ ロセ スをr，葉プ ロセ スの集合 をL，そし て内部プ ロセ ス（ 根プ ロセスは内部プ ロセ スに含めない ）の集合をIで 表す．
各プ ロセ スiの 隣接プ ロセ スの 集合を Ni と する ． 各プ ロセ スiは 隣接す るプ ロセ スを 区別で きる もの と する ．また ，隣接するプ ロセ ス数 |Ni|をプ ロセ ス iの次数とい う．各プ ロセ スiは ，木ネット ワーク上 での親と子のプ ロセ スを認識できるとし ，親プ ロセ ス をPi，子プ ロセ スの集合をCldiで 表す．し たがって Pi, Cldiから ，プ ロセスiは 根，葉，内部プ ロセ スの いずれであるかを認識できる．また，木の高さをhで 表す．
各プ ロセ スを状態遷移機械とし てモデ ル 化する．状 態を変数で 表し ，状態遷移をガ ード 付アクション（ 以 下，アクションという ）で 表す．ここで ，各プ ロセ ス は自分のもつ変数のみに 書込み可能であるとし ，また， 隣接プ ロセ スの変数の値を直接参照できる（ 状態通信 モデ ル ）ものとする．各プ ロセ スの各アクションはラ ベル 付けされており，以下のように表す．
< label > :: < guard > → < statement > iの各アクションのガ ード < guard >は ，i及び i の隣接プロセスの変数からなる論理式で表される．プロ セスiはガ ード が真の場合のみ命令文< statement > を実行する．命令文では，iのもつ変数を更新する．本 論文では ，ガ ード が 評価され ，命令文が 実行され るま でを1原子動作とする．また ，この1原子動作を1ス テップ と呼び ，ガ ード が 真の命令文の実行をアクショ ンの実行と呼ぶ．
各プ ロ セ ス i の 状 態 集 合 を Si で 表 す．分 散 シ ス テ ム 全 体 の と り 得 る 状 況 の 集 合 を C と す る と ， C = S0 × S1 × · · · × Sn−1 で あ る ．つ ま り，分 散 シ ステムの 各大域状況（ 以下単に 状況と 呼ぶ ）cは ， (s0, s1, . . . , sn−1)で 表され る．ここで ，si∈ Si(0 <= i <= n − 1)である．
電子情報通信学会論文誌2001/1 Vol. J84–D–I No. 1
プ ロト コル P は ，各プ ロセ スの 動 作を 規 定 す る ． し たが って ，プ ロト コルP を ，すべての 状況の集 合 C 上の2項 関 係 →と みな す こ とが で き る ．c ∈ C を 任 意の 状 況 ，Q⊂
=V をプ ロセ スの 任 意の 部 分 集 合 と す る ．Q に 属 す る す べ て のプ ロ セ スが ，同 時 に 1ス テップ を 行 うこ と に よ り 状 況が cか ら c
′
と な る（ つ ま り c → c
′
）と き ，c
′ = △(c, Q)
と 表 す． c = (s0, s1, . . . , sn−1), c′ = (s′0, s′1, . . . , s′n−1)とする とき，i /∈ Qのとき ，あるいは ，i ∈ Qでもそのア ク ションのガ ード が 偽のとき，si= s′iである．
プロセスの空でない部分集合の無限系列をスケジュー ル と 呼び ，Q = Q1, Q2, . . .と 表す．このと き，状況 の無限系列E = c0, c1, c2, · · ·がci+1= △(ci, Qi+1) (i >= 0)を満たすとき，Eを初期状況c0，スケジュー
ルQに 対する実行と呼ぶ．つまり，EはQ1, Q2, . . . に 属するプ ロセ スが 順に 動作するときの 状況変化を表 す系列である．本論文では ，弱公平な実行のみを 考え る．これは ，各プ ロセ スiに 対し ，あ る状況 cj以降 常にガ ード が 真でありながら ，cj以降命令文が 実行さ れないようなアクションは存在し ないことを保証する． つまり，連続し てガ ード が 真のアクションをもつとき， いつかはその命令文が 実行され ることを保証する．
本論文では ，非同期式シ ステ ムを 想定し て いるが ， 時 間 計 算 量の 評 価は ，同 期 式シ ステ ムで 用いら れ る ラウンド を用いて行う．つまり，時間計算量の評価で は ，各i(i >= 1)に 対し ，Qi= V となるスケジュール Q = Q1, Q2, · · ·に対する実行E = c0, c1, · · ·を考え ， 状況ci を 第iラウンド 終了時の状況とする．このよ うな実行E を同期式実行と呼ぶ．
2. 2 自己安定プ ロト コル
自己安定プ ロト コルは ，任意の状況から 実行を開始 し ても，問題の解を求めた状況に 安定するプ ロト コル である．この性質から ，自己安定プ ロト コルは ，プ ロ セ スの一時的な故障（プ ロセスの変数の値，プ ログ ラ ムカウン タの値の破壊 ）により，分散シ ステムがど の ような状況に陥っても，故障し たプ ロセ スが 復旧すれ ば ，やが て 再び 解を 求め た 状況で 安定す る ．つまり， 自己安定プ ロト コルは ，一時的な故障に 対する高度な 故障耐性を有する．
ここではattractorという概念を用いて ，自己安定
プ ロト コルを定義する．
［ 定義2.1］Closed Attractor
X，Y を，分散シ ステムの状況の集合Cに 対し て定 義され る述語とする ．以下の 条件を 満たすと きY は
Xに対するclosed attractorであるといい，X ⊲ Y と 表す．
（1）述語X を満たす任意の状況をc0 とする．c0 を初期状況とする，任意の実行E = c0, c1, · · ·におい て ，述語Y を満たす状況ci (i >= 0)が 存在する．
（2）述語Y を満たす任意の状況をc
′
0とする．c′0
を 初期状況とする，任意の 実行E
′ = c′
0，c′1，· · ·に お いて ，すべての状況c
′
iが 述語Y を満たす． ✷
X ⊲ Y は ，述語X を満たす任意の状況から 始まる
すべての実 行に 対し て ，シ ステ ムが 述語Y を 満たす ような状況に到達し ，いったん そのよ うな状況に 到達 すると ，その 後のすべての状 況も述語Y を満たすこ とを意味する．次に ，この概念を用いて 自己安定プ ロ ト コルを定義する．
［ 定義2.2］自己安定プ ロトコル
Pをプ ロト コル とし ，P の すべ ての 実 行の 集合を Pとする．また ，SPを 実行の集合Pに 対し て定義 され る述語とする．すべての状況の集合Cに対し て定 義され る述語Lが 存在し ，以下の 条件を 満たすとき， プ ロト コルPはSPに 対し て自己安定であるという．
（1）正当性：述語Lを満たす任意の状況を αと する．αを初期状況とする，任意の実行Eが 述語SP を満たす．
（2）閉包性・収束性：true ⊲ L．つまり，述語L が ，シ ステムのすべての状況の集合Cに対するclosed
attractorである． ✷
定 義2.2に おいて ，述 語 SP は ，分 散シ ステムに 要求され る動作を規定するものである．そこで ，述語 SP のことをプ ロト コル 要求と 呼ぶ ．また 述語Lは ， プ ロト コル 要求を満たす実行の初期状況を規定するの で ，Lを満たす状況を正当な状況と呼ぶ．
プ ロト コル 要求SP に 対す る自 己安定プ ロト コル は ，いず れ 正 当な 状 況に 到 達し ，それ 以 降の 実 行は SPを満たす．自己安定プ ロト コルの安定時間を以下 のよ うに定義する．
［ 定義2.3］安定時間
Pをプ ロト コル 要求SPに 対する自己安定プ ロト コルとする．Pの任意の実行Eにおいて ，第tラウ ンド 終了時の状況が 正当な状況のとき，Pの安定時間
はtであるという． ✷
2. 3 隣接間同期化問題
本論文では ，木ネット ワークにおいて 隣接プ ロセ ス 間の 同期を 実現する自己安定プ ロト コル を 利用する ． この自己安定プ ロト コルのプ ロト コル 要求NSは 次の
ように定義され る．
［ 定義2.4］プ ロト コル 要求NS
任意の実行をE = c0, c1, · · ·とする．任意のプ ロセ スをiとし ，iが 状況cs, ct (s < t)で ア クション を 実行し た(アクションを実行する直前の状況をcs, ct) と す る ．iが cs, · · · , ct の 間で 正 確に 1度だ け ア ク ションを実行するなら ，iの任意の隣接プ ロセ スjも cs, · · · , ct の 間で 正確に1度だけア クション を 実行す
る． ✷
これは ，プ ロトコル要求NSを満たす任意の実行E において，あるプ ロセスpが 実行する連続する二つの アクションの間に ，pに 隣接するすべてのプ ロセ スが 正確に1度だけアクションを実行することを意味する．
2. 4 ヒープ 順序付き木構成問題
本論文では ，木ネット ワークの各プ ロセ スが ，初期 状況でもつ値（ 初期値 ）を並べ換えることにより，ヒー プ 順序（ 各プ ロセ スがその子プ ロセ スよりも大きい値 を もつ ）を 構成す る自己安定プ ロト コルを 提案する ． ただし ，プ ロセスの初期値は相異なるとする．以下で ， ヒープ 順序付き木構成問題のプ ロトコル 要求HPを定 義する．
［ 定義2.5］プ ロト コル 要求HP
各プ ロセ スiは ，読出し 専用の入力変数iniと書込 み専用の出力変数outiをもつ．
実行を Eとする ．E に おいて ，ini の値が 変化し な ければ ，outiの値は 変化せず，以下の条件を満たす．
（1）{outi| i ∈ V } = {ini| i ∈ V }
（2）∀i ∈ V − {r} : outi< outPi ✷
3. 隣接間同期化プ ロト コル
木 ネット ワ ー クに おけ る 隣 接 間 同 期 化プ ロト コル N SP [4]を図1に 示す．各プ ロセスiは ，論理型変 数coliを もつ ．各プ ロセ スiは ，親プ ロセ スと 子プ ロセ スの変数colを読む．そし て ，coliと親プ ロセス のcolP
iが 異なる値であり，かつ，すべての子プ ロセ スのcolが coli と 同じ 場合のみ 動作し ，coli の 値を 反転させる．これ より，プ ロセ スとその隣接プ ロセ ス が 交互に 動作することを実現し ている．なお，根プ ロ セ スは親プ ロセ スとの比較をせず，葉プ ロセ スは子プ ロセ スとの比較をし ない点以外は ，他のプ ロセスと同 一である．
（ 定数 ） Cldi: 子の集合，Pi: 親のプ ロセ ス
（ 変数 ） coli : 論理型変数
［ 定理3.1］[4] プ ロト コル N SP は ，安定時間0,各
For the root
S1 :: ∀j ∈ Cldi : colj= coli → coli:= ¬coli
For the internal processes
S2 :: colPi = col| i ∧ (∀j ∈ Cldi: colj= coli)
→ coli:= colPi For the leaf processes
S3 :: colPi= col| i → coli:= colPi
図1 隣接間同期化自己安定プ ロト コルN SP
（プ ロセ スi）
Fig. 1 Self-stabilizing neighborhood synchronizer protocol N SP for process i.
プ ロセ スの領域計算量O(1)の隣接間同期化自己安定
プ ロト コルである． ✷
更に ，プ ロト コルN SPに対し て，次の定理が 成り 立つ．
［ 定理3.2］プ ロト コルN SP の任意の同期式実行を E と す る ．E の第 2hラウンド 終了時以降 ，各プ ロ セ スは2ラウンド に1度，正確にアクションを実行す
る． ✷
4. ヒ ープ 順 序 付き 木を 構 成す る 自 己 安 定 プ ロト コル
本章では ，木ネット ワークにおいてヒープ 順序付き 木を 構成する安定時間O(h)，各プ ロセ スの領域計算 量O(K) の 自 己 安 定プ ロト コル HPP を 提案す る ． ここで ，hは 木の 高さを ，Kは 入力値の サ イズを 表 す．このプ ロト コルは ，文献[2]のプ ロト コルの安 定
時間O(nh)，領域計算量O(δK)を改良し ている．
4. 1 プ ロト コルHPP の概略
木ネット ワーク上の各プ ロセ スが ，それぞれ 一つず つデ ータをもつとする．ヒープ 順序を実現するために は ，より大きな 値を根に 向かって移動させ ，小さな 値 は 葉に 向か って移動させれば よい ．つまり，各プ ロセ スと，その子プ ロセ スの間で値を比較し ，子プ ロセ ス のもつ値の最大値が 親プ ロセスのもつ値より大きな 場 合，その親と子プ ロセ ス間で値を交換する．これを繰 り返せば ，やが て木ネット ワーク全体でヒープ 順序を 実現できる．
こ の と き ，複 製や 損 失を 起こ すこ と な く，正し く デ ータ交換を行うために ，本プ ロト コルでは ，隣接間 同期化プ ロトコルを用いる．
各プ ロセスiの入力変数iniの値は ，プ ロト コル 実 行中は 変化し ないものとする．ヒープ 順序を実現する には ，前述し たよ うにこの値を移動させなければ なら
電子情報通信学会論文誌2001/1 Vol. J84–D–I No. 1
For the root
H1:: ∀j ∈ Cldi: colj= coli
→ HEAPIFY;
if (ri= ⊥ ∧ (∀j ∈ Cldi: changej= false)) /* heap order accomplished */ reseti:= true; RESET; changei:= true; else
reseti:= false; changei:= true; coli:= ¬coli;
For the internal processes
H2:: colPi= col| i ∧ (∀j ∈ Cldi: colj= coli)
→ if (resetPi= false)
reseti:= false; HEAPIFY;
if (ri= ⊥ ∧ (∀j ∈ Cldi: changej= false)) changei:= false;
else /* heap disorder in the subtree rooted i
*/
changei:= true; else
reseti:= true; RESET; changei:= true; coli:= colPi;
For the leaf processes H3:: colPi= col| i
→ if (resetPi= false)
reseti:= false; HEAPIFY; changei:= false; else
reseti:= true; RESET; changei:= true; coli:= colPi;
図2 プロトコル HPP （プロセス i） Fig. 2 Protocol HPP for process i.
ず，各プ ロセ ス iは その ための 作業用 変数 wi, ri を もっている．自己安定プ ロトコルでは ，初期状況に 仮 定をおかないため ，初期状況において ，作業用変数の 値がど のプ ロセ スの 入 力 変数 valの 値と も 一致し な いことや ，あるプ ロセ スの入力変数の値がど のプ ロセ スの作業変数の値とも一致し ない可能性がある．そこ で 本プ ロト コルでは ，作業用変数の値を並べ換え るこ とにより，ヒープ 順序を実現し た後，ネット ワーク全 体に リセット をかけ，各プ ロセスiの入力変数iniの 値を作業用変数にコピ ーし ，再び 作業用変数に対し て ヒープ 順序の構成を繰り返す．ヒープ 順序付き木が 構 成され ると ，各プ ロセ スiは 作業用変数の値を出力変 数outiにコピ ーする．リセット，ヒープ 順序付き木構 成は 繰り返し 実行され るが ，入力変数の値は 変化し な いので ，2回目以降では 同じ ヒープ 順序付き木が 構成 され る．し たが って ，各プ ロセ スiはoutiに 同じ 値 を書き込むことになり，outiの値は 変化し なくなる．
なお，異なるプ ロセスの入力変数iniの値は異なる ものとする（ 同じ 値がある場合，プ ロセ スの識別子と の2項組にすることにより，異なる値とみなせる ）．
RESET:
outi:= wi; wi:= ini; ri= ⊥; HEAPIFY:
For the root
maxi:= max{wj| j ∈ Cldi};
if (wi< maxi) /* a child has a bigger value */ ri:= wi; wi:= maxi; /* exchange values */ else
ri:= ⊥;
For the internal processes if (wi= wPi ∧ rPi = ⊥)|
/* parent of i picked up the value of i */ wi:= rPi; /* copy the returned value */ maxi:= max{wj| j ∈ Cldi};
if (wi< maxi) ri:= wi; wi:= maxi; else
ri:= ⊥;
For the leaf processes if (wi= wPi ∧ rPi = ⊥)|
wi:= rPi; ri:= ⊥;
図3 プロトコル HPP の手続き RESET， HEAPIFY（プロセス i）
Fig. 3 Procedure RESET, HEAPIFY for process i in protocol HPP.
4. 2 プ ロト コルHPP
ヒープ 順序付き木を構成する自己安定プ ロトコルを 図2，図3に示す．各プ ロセ スのアクションにおけ る ガ ード は ，隣接間同期化プ ロト コルのものと同じ であ る．プ ロセ スの動作は 隣接間同期化プ ロト コルの動作 を含んでおり，これによりプ ロト コル HPPは同期化 し て動作する．
次に ，アクション 中に 含まれ る定数，変数，手続き を説明する．
（ 定数 ） Pi: iの親
Cldi : iの子の集合 ini: iへの入力値
（ 値はユニークで実行中変化し ない ）
（ 変数 ）
coli : 同期機構N SP に 基づ く論理型変数 outi: 出力変数
wi: ヒープ を構築するための作業用変数 ri: 値の交換後，子へ返す値を格納する変数
changei: iを根とする部分木で 作業用変数の値の
変化の有無を示す論理型変数
reseti: 手続きRESETを行うかど うかを 示す論理型変数
（ 手続き ） RESET（ 図3）
すべ て のプ ロセ スで 作 業 用 変 数の 値 の 交 換が な く なった（ ヒープ 順序付き木が 構成され た ）ときに ，リ セット をかけるために 根プ ロセ スが 実行を開始する手 続き．各プ ロセ スiは ，作業用変数wiの値を出力変 数outiに 代入し ，入力変数ini の 値を 作業用変数に 代入する．
HEAPIFY(図3)
ヒープ 順序を実現する手続き．親プ ロセ スと子プ ロ セ ス間での値の交換を行う．各プ ロセ スiは ，すべて の子プ ロセ スの作業用変数を読み，それらの最大値を 求める．最大値が 自分の作業用変数の値より大きい場 合は ，まず 自分の作 業用変数の 値をriに 代入し ，次 に 最大値を自分の作業用変数に 代入する．なお，値の 交換が 起こらなかった 場合は ，riに 特別な 記号⊥を 代入する．子プ ロセ スは ，親プ ロセ スの作業用変数を 読み ，その 値が 自分の 作 業用変数と 同じ 値の 場 合に ， 値の交換が 起きたと認識し ，親のrの値を自分の作業 用変数に 代入する．
［ 定理4.1］プ ロトコルHPPは，安定時間O(h)，領 域計算量
（ 注1）
O(K)の自己安定ヒープ 順序付き木構成
プ ロト コルである． ✷
定理4.1の証明の概略は ，付録に 掲載する． 5. む す び
本論文では ，木ネット ワークでヒープ 順序を実現す る自己安定プ ロト コルを提案し た．このプ ロトコルは 隣接間同期化プ ロト コルを利用し て ，安定時間O(h)， 領域計算量O(K)でヒープ 順序を実現する．ここで ， hは木の高さ，Kは入力値のサイズを表す．これは既 知の結果と比べ，安定時間，領域計算量をともに 改善 し ている．
謝辞 日ご ろから 有益な御討論を頂く奈良先端科学 技術大学院大学の井上美智子助手に 感謝致し ます．本 研究の一部は ，文部省科学研究費補助金（ 特定領域研 究(B)(2)10205218），及び ，中部電力基礎技術研究所 研究助成による．
（ 注1）：定数Cld iは 分散シ ステムによって 用意され て いる定数であり， プ ロト コルの変数ではないので ，領域計算量に 含めていない．
文 献
[1] L. Alima, “Self-Stabilizing max-heap,” Proc. 4th Workshop on Self-stabilizing Systems, pp.94–101, 1999.
[2] B. Bourgon and A. Datta, “A self-stabilizing dis- tributed heap maintenance protocol,” Proc. 2nd Workshop on Self-Stabilizing Systems, pp.5.1–5.13, 1995.
[3] E. Dijkstra, “Self-stabilizing systems in spite of dis- tributed control,” CACM, vol.17, no.11, pp.643–644, 1974.
[4] C. Johnen, L. Alima, A. Datta, and S. Tixeuil, “Self- stabilizing neighborhood synchronizer in tree net- works,” Proc. ICDCS, pp.487–494, 1999.
[5] N. Lynch, Distributed Algorithms, Morgan Kauf- mann, 1996.
[6] M. Raynal and J. Helary, Synchronization and Con- trol of Distributed Systems and Programs, John Wi- ley & Sons, 1990.
[7] G. Tel, Introduction to Distributed Algorithms, Cambridge University Press, 1994.
付 録
本付録では ，定理4.1が 成り立つことを示す．以下 では ，次の表記を用いる．
d(i): プ ロセスiの深さ（ 根からの距離 ）． Acted(ci): 任意の実行E = c0, c1, . . .について ，状 況ci−1, ci (i >= 1)の間にア クション を実行し たプ ロ セ スの集合．
vari(c): 状況cにおけ る，変数variの値．
プ ロト コルHPPでは ，隣接間同期化プ ロト コルを 利用し ている．同期化プ ロトコルは ，非同期式シ ステ ムで 同期式シ ステムを模倣するためのものである．こ の同期式実行を用いてHPPの正当性を証明する．ま ず，同期式実行とし て理想実行を定義する．また ，自 己安定シ ステ ムでは 初期状況に 仮定を おか な いた め ， プ ロセ スの変数には 通常の動作からは 得られないよ う な 値が 入って いる 可能 性が あ る ．初期状況に おいて ， このような値をもつ変数が 存在し ないよ うに ，理想実 行を定義する．
［ 定義A.1］（ 理想実行 ） 実行E = c0, c1, . . .が 以下 の条件を満たすとき，E を理想実行という．
• 任意の状況c |= c0について ，
Acted(c) = {i ∈ V | d(i) mod 2 |= 0 }
∨ Acted(c) = {i ∈ V | d(i) mod 2 = 0 }が 成立． 便宜上，Acted(c0) = V − Acted(c1)と定義する．
• 初期状況c0において ，以下が 成立．
電子情報通信学会論文誌2001/1 Vol. J84–D–I No. 1
– ∀i ∈ V : reseti(c0) = false
– ∀i ∈ V : ri(c0) < wi(c0) ∨ ri(c0) = ⊥ – ∀i ∈ Acted(c0) : ri(c0) |= ⊥
=⇒ ∃j ∈ Cldi: wj(c0) = wi(c0) – ∀i /∈ Acted(c0) : ri(c0) |= ⊥ =⇒
∃j ∈ Cldi: wj(c0) = ri(c0) ∨ rj(c0) = ri(c0) ✷
次にプ ロト コルHPP の任意の実行E に対応する 理想実行を 定め る．そのために ，各プ ロセ スのE に 現れ る状態のn 項組とし て 以下で 実行断面を 定義す る．この実行断面を状況であると思えば ，実行断面の 系列において，理想実行と一致するような接尾部が 存 在する．
［ 定義A.2］ 任意の実行をE = c0, c1, . . .とする．任 意のプ ロセスi，任意の状況cjについて，以下を定義 する．
Enable(i, cj): 状況cjにおいて ，ガ ード が 真のiの アクションが 存在するかど うかを表す真偽値． LastActed(i, cj): k <= j ∧ i ∈ Acted(ck)を満たす 状況ckのうち最後のもの．
NxtActed(i, cj): k > j ∧ i ∈ Acted(ck)を 満たす 状況ckのうち最初のもの．
NxtEnable(i, cj): k >= j ∧ i ∈ Enable(i, ck)を 満 たす状況ck の うち最初のもの ． ✷
［ 定義A.3］ 任意の 実行Eに ついて ，すべ てのプ ロ セ スが 少なくとも1回アクションを 実行し た 状況をc とする．根rに関する状況の系列cr0, cr1, cr2, . . . , crt, . . . を 次の よ うに 定義する ．ただし ，便宜上c
r
−1 = cと する．
• Enable(r, crt−1) =⇒ c r
t = NxtActed(r, crt−1)
• ¬Enable(r, crt−1) =⇒ crt = NxtEnable(r, crt−1) 上記 の系 列 cr0, cr1, . . . に 対し ，実 行 断面 (σ0(c0t), . . . , σn−1(cn−1t )) (t = 0, 1, . . .)を 次の よ う に 定 義 す る ．た だ し ，c
′ = (s
0, . . . , sn−1) に 対し ， σi(c′) = siとする．
• Pi∈ Acted(cPti) =⇒ cit= NxtEnable(i, cPti)
• Pi∈ Acted(c/ Pti) =⇒ cit= LastActed(i, cPti)
［ 定義A.4］ 任意の実 行E と 任意のプ ロセ ス i ∈ V について ，以下で定義され るiの状態の系列s
i 0, si1, . . . をEのiへの射影といい，Proj(E, i)と表す．
• si0はEの初期状況におけ るiの状態．
• sijは E に おいてプ ロセ スiが j番目の ア ク ションを実行し た直後のiの状態． ✷
［ 補題A.1］ 任意の 実行Eに ついて ，次を 満た す理 想実行EIが 存在する．
各プ ロセ スi ∈ V について ， Proj(E′i, i) = Proj(EI, i) であるよ うなEの接尾部E
′
iが 存在する．
更に ，Eが 同期式実行なら ，Ei′ の初 期状況は E の 4hラウンド 以内に現れ る．
証明の 概略 定理3.2より，実行E において すべて のプ ロセスはいずれアクションを行い，Eが 同期実行 ならば 2hラウンド 以内に すべてのプ ロセ スが 少なく とも1回アクションを行う．更に ，すべてのプ ロセ ス i ∈ V に ついて reseti(c) = false が 成り立 つ状 況 c が 存在し ，Eが 同期実行ならばcは 初期状況から 2h ラウンド 以内に 現れ る．
E の 実 行 断 面 (σ0(c0t), . . . , σn−1(cn−1t ))の 中で ，根 からの 距離が hの 任意のプ ロセ スiについて ，cit が cから 到達可能であ るよ うな 実行断面が 存在する．E が 同期実行ならば c
0
t = c1t = · · · = cn−1t である． 上記の実行断面に含まれ るc
0
t, c1t, . . . , cn−1t について， Eのcit から 始まる接尾部をEi′ とし ，Proj(Ei′, i) = si0, si1, . . .と す る と ，実 行EI = c0, c1, . . . (た だ し ， cℓ = (s0ℓ, s1ℓ, . . . , sn−1ℓ ) (ℓ = 0, 1, 2, . . .) )は 理 想 実
行であり，題意を満たす． ✷
補題A.1より，プ ロト コルの正当性と時間計算量の評 価は ，理想実行についてのみ考えれば よい ．
［ 定義A.5］ 任意の理 想実行Eに おけ る任意の 状況 をcとする．値の集合Vals(c)を次のように定義する．
Vals(c) = W(c) ∪ R(c) ただし ，
– W(c) = { wi(c), i | i ∈ Acted(c) ∪ {r}
∨ wi(c) |= wPi(c) ∨ rPi(c) = ⊥} – R(c) = { rP
i(c), i | i /∈ Acted(c) ∪ {r}
∧ wi(c) = wPi(c) ∧ rPi(c) |= ⊥}
✷ 各プ ロセ スiに 対し ， v, i ∈ Vals(c)とな るvは 正確に 一つ定まる．このvをiが 状況cで もつ値と 考え る（ v, i ∈ R(c)のと き，実際には vはrPi の
値であ るが ，rPiが iに 戻す値なので ，iが もつ値を vと考える ）．この値の移動は 次のように定義する．
［ 定義A.6］（ 値vの移動 ） 任 意 の 連 続 す る 状 況 を c, c′，任意のプ ロセ スを iとし ， v, i ∈ Vals(c) とする．
v, i は 以下の v′, j ∈ Vals(c′)に 移動し たと いい ，
v, i ⇒c′ v′, j と表す．
• i /∈ Acted(c′)の場合
(a) rPi(c′) |= ⊥ ∧ wi(c′) = wPi(c′)（Piがiと値 を交換 ）の場合， v
′, j = v, Pi (b) その他の場合， v′, j = v, i
• i ∈ Acted(c′)の場合
(c) ri(c′) |= ⊥（iが 子と値を交換 ）の場合， wk(c′) = wi(c′)となるk ∈ Cldiに 対し ，
v′, j = v, k
(d) reseti(c′) = true（iがRESETを実行 ）の場 合， v′, j = ini, i
(e) その他の場合， v′, j = v, i ✷ 定義A.6において ，(c)の場合，同じ 値をもつ子が 複数存在すると v, i ⇒c′ v, k な るkが 一意に 定ま ら な い．ただし ，RESETを1度行 うとプ ロセ スの もつ 値は 相 異な るもの と な り， v, i ⇒c′ v
′, j
な る
v′, j が 一意に 定まる．
［ 定義A.7］ 任意の v, i ∈ Vals(c) に対 し Wrong( v, i , c)を次のよ うに 定義する．
Wrong( v, i , c) = { v′, j ∈ Vals(c)| v′< v
∧ “jはiの祖先”} ✷
|Wrong( v, i , c)|は ，値 v, i に 対し ヒープ 順序に 違反する値の個数である．し たが って ，すべてのプ ロ セ スiに ついて ，|Wrong( v, i , c)| = 0が 成り 立て ば ，ヒープ 順序が 実現できたことになる．以下，補題 A.2か ら 補 題A.7まで は ，∀i ∈ V : reseti = false を 満た す 状 況か ら たか だ か 2hラウンド で 作 業 用 変 数 上で の ヒ ープ 順 序が 成 立 す るこ と を 示 す．以 下で は ，Wrong( v, i , c) = { v1, i1 , v2, i2 , . . ., vt, it } に ついて ，ds = d(is) (1 <= s <= t)とおき，一般性を 失 うこと な くds > ds+1 (1 <= s <= t − 1)を 仮 定す る ．また ， v, i ⇒c′ v, j とし た と き ，上に 加え て ， Wrong( v, j , c′) = { v′1, i′1 , v′2, i′2 , . . ., v′t′, i′t′ }， d′s = d(i′s) (1 <= s <= t′) と お き ，d′s > d′s+1
(1 <= s <= t′− 1)を仮定する．
基 本 的に ，各 vs, is ∈ Wrong( v, i , c)は ，ヒ ー プ 順 序 に 違 反し な く な る ま で 並 列 的 に 葉 の 方 向 に 移 動 す る ．し かし ，ds−1 = ds+ 1 の と き ，つ ま り is−1 ∈ Cldis であるときには ，更に ，各j ∈ Cldis と その値 v
j, j
についてv
j< v
sであれば vs, is は移 動できない．状況cにおいて各 vs, is (1 <= s <= m) が並列的に移動できるような最大のmをTop( v, i , c) と 表す．形式的には 以下のように定義でき ，補題A.7 では ，hラウンド 以内にすべての値が 並列的に 移動す るようになることを示す．
［ 定義A.8］ 任意の状況c,任意の v, i ∈ Vals(c)に
ついて ，
Wrong( v, i , c) = { v1, i1 , v2, i2 , . . . , vt, it } と する．Top( v, i , c)を次のよ うに 定義する．
• Wrong( v, i , c) = ∅の場合 Top( v, i , c) = 0
• Wrong( v, i , c) |= ∅の場合
Top( v, i , c) = max({m| ∀s, 1 < s <= m <= t : ds−1>= ds+ 2} ∪ {1})
［ 補題A.2］ 任 意 の 連 続 す る 状 況 を c, c′ と し ，
v, i ⇒c′ v, j と す る ．t = |Wrong( v, i , c)|, t′ =
|Wrong( v, j , c′)|とすると ，t >= t′ ∧ dt<= d′t′ が 成
立する．
（ 証明 ） x ⇒c′yであ る値x ∈ Vals(c), y ∈ Vals(c′) について ，以下の三つの 集合を考え る．
• W0 = {(x, y)| x ∈ Wrong( v, i , c), y ∈ Wrong( v, j , c′)}
• W− = {(x, y)| x ∈ Wrong( v, i , c), y /∈ Wrong( v, j , c′)}
• W+ = {(x, y)| x /∈ Wrong( v, i , c), y ∈ Wrong( v, j , c′)}
t >= t′については|W−| >= |W+|を示せば よい．ここ で ，定義A.6より W+ の 各要 素( v′
s′, ℓ , vs′′, i′s′ )
∈ W+ (ℓ ∈ Cldi′ s′)
に 対し て ， vs, is ⇒c′ vs, ℓ (vs < vs′′, is = i′s′) で あ る ( vs, is , vs, ℓ ) ∈ W− が 存在する．(つまり，c → c
′
でvs とv
′
sが 交換され
た) W+の異なる要素に対して，対応するW−の要素 も異な るので |W−| >= |W+|が 成立．また ，dt<= d′t′
は 明らか ． ✷
補題A.2は ，値vに 対し て|Wrong( v, i , c)|が 単 調非増加であることを意味し ている．以下補題A.7ま で ，手続き HEAPIFYに よって |Wrong( v, i , c)| はいずれ 減少し ていくことを示す．
［ 補題A.3］ 任 意 の 連 続 す る 状 況 を c, c′ と し ，
v, i ⇒c′ v, j と す る ．m = Top( v, i , c) と す る と ，経路 i, . . . , im上の任意の頂点ℓについて ，次が 成り立つ．ただし ， v
ℓ, ℓ ∈ Vals(c′)とする．
vℓ, ℓ ∈ Wrong( v, j , c′) =⇒ ℓ /∈ Acted(c′)
（ 証明 ） 経路i, . . . , ℓ上のℓの子をjℓ∈ Cldℓ と お
く．背 理 法に よ り ℓ ∈ Acted(c′) と 仮 定 す る ．定 義 A.6 よ り， vℓ, ℓ ⇒c′ vℓ, ℓ の 場 合 と ∃jℓ′ ∈ Cldℓ :
vℓ, j′ℓ ⇒c′ vℓ, ℓ の場合とに 分けられ る．
• vℓ, ℓ ⇒c′ vℓ, ℓ の場合．
電子情報通信学会論文誌2001/1 Vol. J84–D–I No. 1
jℓ ∈ Acted(c/ ′)で あ り，値の 交 換が され な いので ，
vjℓ, jℓ ⇒c′ vjℓ, jℓ である．プロトコルと定義A.6よ り，v
jℓ <
= vℓが 成立．一方，補題の仮定より v
ℓ, ℓ ∈
Wrong( v, j , c′) だ か ら ，vℓ < v で あ り，ま た m の 定 義から ， vℓ, ℓ /∈ Wrong( v, i , c) ∨ vjℓ, jℓ /∈ Wrong( v, i , c)であり，v <= vℓ∨ v <= vjℓが 成立．し たが って矛盾が 生じ る．
• ∃jℓ′ ∈ Cldℓ: vℓ, jℓ′ ⇒c′ vℓ, ℓ の場合． – j′ℓ = jℓ の 場 合 ．ℓ と jℓ の 間 で 値 が 交 換 され るの で ， vjℓ, ℓ ⇒c′ vjℓ, jℓ で あ る ．プ ロト コ ル と 定 義 A.6 よ り，vjℓ < vℓ が 成 立 ．一 方 ，補 題 の 仮 定 よ り v
ℓ, ℓ ∈ Wrong( v, j , c′) だ か ら ， vℓ < v で あ り，ま た m の 定 義 か ら ， v
jℓ, ℓ /
∈ Wrong( v, i , c) ∨ vℓ, jℓ /∈ Wrong( v, i , c) で あ り，v <= vℓ∨ v <= vjℓ が 成 立 ．し たが って 矛 盾が 生 じ る．
– j′ℓ = j| ℓ の 場 合 ．ℓ と j
′
ℓ の 間 で 値 が 交 換 さ れ ，jℓ と の 間 で は 値 が 交 換 さ れ な い の で ，
vj′ℓ, ℓ ⇒c′ vjℓ′, jℓ′ , vjℓ, jℓ ⇒c′ vjℓ, jℓ である．プ ロトコルと定義A.6より，vj
′
ℓ < vℓ∧ vjℓ < vℓが成立． 一方 ，補題の 仮 定より vℓ, ℓ ∈ Wrong( v, j , c′)だ から ，v
ℓ< v
が 成立．またmの定義から ， v
j′ℓ, ℓ /
∈ Wrong( v, i , c)∨ vjℓ, jℓ /∈ Wrong( v, i , c)であり， v <= vjℓ′∨ v <= vjℓ が 成立．し たが って矛盾が 生じ る． いずれの場合も矛盾が 生じ る． ✷
［ 補題A.4］ 初 期 状 況 以 外 の 任 意 の 状 況 を c とし ， m = Top( v, i , c) と す る ．経 路 i, . . . , im 上 の
任 意 の 頂 点 ℓ に つ い て ，次 が 成 り 立 つ ．た だ し ，
vℓ, ℓ ∈ Vals(c)とする．
vℓ, ℓ ∈ Wrong( v, i , c) =⇒ ℓ /∈ Acted(c)
（ 証明の概略 ） 補題A.3と同様にし て示され る（ ただ し ，補題A.3とは mの定義が 異なることに 注意 ）．
✷
［ 系A.1］初 期 状 況 を 除 く 任 意 の 状 況 を c と し ， m = Top( v, i , c) と す る と im ∈ Acted(c)/ が 成
立する． ✷
［ 補題A.5］ 任 意 の 連 続 す る 状 況 を c, c′ と し ，
v, i ⇒c′ v, j と す る ．m = Top( v, i , c)，m′ = Top( v, j , c′)とすると ，次が 成立する．
0 < m < t ∧ im∈ Acted(c′) =⇒ dm> d′m′
（ 証明） 補題の仮定より，im+1= Pim∈ Acted(c/
′)
な ので ，定義A.6より， vm+1, im+1 ⇒c′ vm+1, im+1
と vm+1, im+1 ⇒c′ vm+1, Pim+1 の場合とに分けら れ る．
• vm+1, im+1 ⇒c′ vm+1, im+1 の場 合 ，mの 定義より， vm+1, im+1 ∈ Wrong( v, j , c′)は明らか．
• vm+1, im+1 ⇒c′ vm+1, Pim+1 の 場 合 ，
v′, Pim+1 ⇒c′ v′, im+1 とおけ る．v′ < vm+1< v なので ， v
′, i
m+1 ∈ Wrong( v, j , c′)である． いず れ の 場 合も v
′, i
m+1 ∈ Wrong( v, j , c′)で あ る ．し たが って ，あ るm
′′
に 対し て i
′
m′′ = im+1と
な り，d′
m′′ < dm が 成 立 ．また 経 路 j, . . . , im 上の
任意の 頂点ℓ ∈ Acted(c′)に ついて ，補題A.3より，
vℓ, ℓ /∈ Wrong( v, j , c′)だから ，∀s, 1 <= s <= m′′: d′s+1<= d′s− 2が 成立．ここで ，d′m′ <= d
′
m′′ だから ，
d′m′< dmが 成立する． ✷
［ 補題A.6］ 任 意 の 連 続 す る 状 況 を c, c
′
と し ，
v, i ⇒c′ v, j と す る ．m = Top( v, i , c)，m′ = Top( v, j , c′)とすると ，次が 成立する．
m = t > 0 ∧ it∈ Acted(c′) =⇒ m′= t′∧ dt< d′t′
（ 証明 ） dt= d
′
t′ つまりit= i′t′ と仮定する．補題の
仮定から ，補題A.3より v
′
t′, i′t′ /∈ Wrong( v, j , c′) が 成立 ．これ は ，t
′
の 定 義に 矛盾す る ．し たが って ， dt= d| ′t′が 成り立ち，補題A.2より，dt<= d′t′だから
dt< d′t′ が 成り立つ．同時に ，補題A.3よりm′= t′
が 成り立つ． ✷
［ 補題A.7］ 任意の 理想 実行をE と す る ．任意の ℓ (0 <= ℓ <= h),任意の v, i ∈ Vals(c)に 対し て ，初期 状況から2h − ℓラウンド 以内に|Wrong( v, i , c)| <= ℓ が 成立する．
（ 証明の概略 ） 補題A.2，A.5，系A.1より，hラウ ンド 以内に|Wrong( v, i , c)| = Top( v, i , c)を 満た す状況cに 到達することが いえ る．し たが って ，補題 A.6，系A.1より，状況cからh − ℓラウンド 以内に
|Wrong( v, i , c)| <= ℓを満たすことを 帰納的に 示すこ
とができる． ✷
［ 補題A.8］ 任意の理想実行Eについて，たかだか8h ラウンド で
• ∀i ∈ V : outi< outPi
• {ini| i ∈ V } = {outi| i ∈ V } が 成立し ，以降の任意の状況で 成立する．
（ 証明 ） 補題A.7より，2hラウンド 以内に ，初期状
