J100 j IEICE 2002 11

非停止永久故障に 耐性を有する自己安定生成木構成プ ロト コル

浮穴 学慈

片山 喜章

増澤 利光

藤原 秀雄

A Self-Stabilizing Spanning Tree Protocol that Tolerates Non-Quiescent

Permanent Faults

Satoshige UKENA^†∗, Yoshiaki KATAYAMA^††∗∗, Toshimitsu MASUZAWA^†††, and Hideo FUJIWARA^†

あらまし ネット ワークで相互接続され た多数のプ ロセ スから 構成され る分散シ ステムに おいて ，プ ロセス故 障にかかわらず 正し く動作するプ ロト コルを設計開発することが 重要である．このような故障耐性を有するプ ロ ト コル の設 計パラダ イムとし て ，自己安定プ ロト コルが 有望視され て いる．自己安定プ ロト コルとは ，任意の ネット ワーク状況から 実行を開始し ても，解を求めて安定するプ ロト コルである．この性質から ，自己安定プ ロ ト コルは 任意の一時故障に 対する故障耐性を 有する．本論文では ，状態通信モデ ル 上で ，一時故障だけでな く， 永久故障に 対する故障耐性も 有する自己安定プ ロト コルに ついて 考察する．まず，永久故障の 新たな クラスと し て ，非停止永久故障を 定義する．そし て ，ネット ワー クの生 成木を 構成する問題に 対し ，非停止永久故障プ ロセ スが 存在し て も，問題を 解く自己安定プ ロト コルを 提案する．提案するプ ロト コル の 安定時間はたかだか n(n/2 + F )d ラウンドである．ここで，n はプロセス数，d はネットワークの最大次数，F は故障プロセスの状 態変化が 観測され るまでの時間の上界（ 定数 ）である．

キーワード 分散プ ロトコル ，自己安定，故障耐性，非停止永久故障，一時故障，生成木

1. ま え がき

ネット ワーク環境の発達にともない，ネット ワーク 上の計算機が 協調し て問題解決するための計算手続き

「 分散プ ロト コル 」の重要性が増し ている．ネット ワー ク環境（ 以下，分散シ ステム ）の利点とし て ，一部の 計算機で 障害が 起きても，残りの正常な部分でサービ スを 継続で きる 可用性（availability）が 挙げ られ る ． 分散シ ステムの可用性を十分に 引き出すためには ，故 障が 起きてもサービ スを継続できる（ 問題を解くこと が で きる ），故障耐性のある分散プ ロト コルが 重要で ある．

†奈良先端科学技術大学院大学情報科学研究科 ，生駒市

Graduate School of Information Science, Nara Institute of Science and Technology, Ikoma-shi, 630–0101 Japan

††奈良先端科学技術大学院大学情報科学セン ター ，生駒市

Information Technology Center, Nara Institute of Science and Technology, 8916–5 Takayama-cho, Ikoma-shi, 630–0101 Japan

†††

大阪大学大学院基礎工学研究科情報数理系専攻，豊中市 Department of Informatics and Mathematical Science, Grad- uate School of Engineering Science, Osaka University, 1–3 Machikaneyama-cho, Toyonaka-shi, 560–8531 Japan

∗

現在，高松大学経営学部

∗∗

現在，名古屋工業大学電子情報工学科

自己安定プ ロト コル（self-stabilizing protocol^）と は ，分散シ ステムの任意の状況からプ ロト コルの実行 を 開始し て も，やが て 解状況に 到達する（ 安定する ） 分散プ ロト コルである．この性質より，自己安定プ ロ ト コルは次の二つの特長をもつ．第₁に ，分散シ ステ ムの 初 期 化が 不 要で あ る ．第₂に ，任意の 一 時 故 障 に 耐性をもつ．一時故障とは ，メモリの値の破壊や通 信中の メッセ ージ の 改変など の 一時的な 故障で あ る ． 自己安定プ ロト コルは ，一時故障が 生じ たために 分散 シ ステムがど のよ うな状況に陥ってし まっても，計算 機がプ ロト コルの実行を継続すれば ，自動的に解状況 に 復帰し て安定する．このように 優れた性質をもつ自 己安定プ ロトコルは ，_Dijkstraによって初めて提案さ れ_[4]，現在分散プ ロト コルの研究で最も盛んに研究さ れている分野の一つである．

自己安定プ ロト コルは 一時故障に 対する高度な故障 耐性をもつ．し かし ，自己安定プ ロト コルは ，故障状 況から 再安定するまでの実行の間，再び 故障が 生じ な いことを仮定し ている．つまり，現実のシ ステムのよ うに ，一度障害を起こし た計算機が ，その後も断続的 に 障害を起こすような場合，自己安定プ ロト コルは 解

D– Vol. J85–D– No. 11 pp. 1007–1014 2002 11 1007

電子情報通信学会論文誌2002/11 Vol. J85–D–I No. 11

状況に 復帰し て安定することを保証し ない．このよ う な断続的な障害を扱うには ，永久故障の枠組みが 必要 となる．実シ ステムにおけ る永久故障に対応するため， 一時故障だけでなく，永久故障に 対する故障耐性も有 す る 自 己 安 定プ ロト コル に 関す る 研 究 も 行われ て い る_{[2], [10]}∼_[12]．本論文でも，永久故障に対する故障 耐性を有する自己安定プ ロト コルについて 考察する． プ ロセ スの永久故障とし ては ，これ までに ，ビ ザン チン 故障，停止故障など の様々な故障モデルが 考えら れている．ビ ザンチン 故障モデ ルは ，故障プ ロセ スの 動作に 仮定を設けない故障モデルであり，最も大きな 故障クラスである．一方，停止故障モデ ルは ，故障し たプ ロセ スはそれ 以降，一切動作し なくなる故障モデ ルで ある ．停止故障プ ロセ スが₁個で も 存在すると ， コンセン サス問題のような単純な問題でさえ 解けない ことが 知られている_[7]．これは ，プ ロセスが停止故障 し ていることと単に 動作が 遅いことが 有界時間で 区別 できないことによる．また，_Anagnostouら_[2]は，故 障敏感（failure-sensitive）な 問題の クラスを 定義し ， 停止故障プ ロセ スが₁個でも存在すると ，故障敏感な 問題を解く自己安定プ ロト コルが 存在し ないことを示 し た ．生成木構成問題は 故障敏感な問題のクラスに属 する．

生成木構成 問題は 基本的な 分散問題の 一つで あり， 経 路 情 報の 管 理や 同 報 通 信など ，様々な 応 用が 存 在 する．通常の分散アルゴ リズムの研究では ，_Gallager ら_[9]など により盛んに研究されてきた．また，自己安 定プ ロト コルにおいては ，_Dolevら_[6]や_Chenら_[3] をはじ め ，様々な研究が 行われている．なお，最適な 自己安定生成木構成プ ロト コルは ，_Aggrawalら_[1]に よって提案され た ，レジ スタ通信モデ ル 上で 安定時間

O(diam)^{のものである．}diamはネット ワークの直径

である．このプ ロト コルでは大域的なプ ロセ ス識別子 を用いている．

これ まで ，永久故障を考慮し た自己安定生成木構成 プ ロト コルは提案され ていない．本論文では ，新たに 非停止永久故障を導入することで ，状態通信モデ ルに おいて ，永久故障に 耐性を有する自己安定生成木構成 プ ロト コルを提案する．非停止永久故障は ，故障プ ロ セ スが 無限にしばしば ，故障動作により状態変化する 故障モデルである．停止を許さないという制限のもと で 最も性 質の 悪い故 障で あ ると いえ る．本論文では ， 非停止永久故障のもとで 生成木構成問題を解く自己安 定プ ロト コルを提案するが ，これは ，自己安定生成木

構成問題の可解性にとって ，停止故障が 致命的な影響 を与え ることを意味する．

本論文で 提案するプ ロト コルは ，故障プ ロセス数に 対し て制限を置いていない．し たが って ，永久故障に 対する優れた故障耐性を実現し ているといえ る．また， 大域的なプ ロセ ス 識別子は 用いな い ．その 代わ りに ， 故障し ない根プ ロセ スを仮定する．これはネット ワー クが 完全に 対称であると ，決定性プ ロト コルで問題を 解くことが 不可能なため導入し た仮定であるが ，故障 耐性の観点からは 欠点といえる．また停止故障と区別 するため ，故障プ ロセ スの状態変化が ，すべての正常 な隣接プ ロセスによって無限にしばしば 観測され ると いう仮定を設けている．提案するプ ロト コルの安定時 間はn(n/2 + F)d^である．n^{はプ ロセ ス数，}d^はネッ ト ワークの最大次数，_Fは故障プ ロセスの状態変化が 観測され るまでの時間の上界（ 定数 ）である．

本論文の構成は 以下のとおりである．2.でモデル 及 び 生成木構成問題の定義を行う．3.では ，非停止永久 故障の存在下で 生成木構成問題を解く自己安定プ ロト コルを提案し ，その 正当性を証明する．また ，提案す るプ ロトコルが 安定するまでの時間計算量を評価する． 最後に4.で 結論と今後の課題について 述べる．

2. 諸 定 義

2. 1 分散シ ステム

分散シ ステムは_n個のプ ロセ スとそれらを相互に結 ぶ通信リンクからなり，無向グラフ_{G = (V, E)}によっ て表され る．頂点集合_{V = {p0, p1}, . . . , pn−1}^{はプ ロ} セスの集合を表し ，辺集合_Eは通信リンクの集合を表 す．ここで_{(pi, pj) ∈ E}であるとき，プ ロセス_piはプ ロセス_pjに隣接するという．プ ロセ ス_piの隣接プ ロ セ スの集合を _Ni(⊂

=V )^{と 表す．pi}は ，隣接プ ロセ ス pj∈ Niを局所的なポート 番号を用いて識別する．す なわ ち，ポ ート 番号の集合
_Ni= {0, 1, . . . , |Ni| − 1} に 対し て ，₁対₁対応の関数_{Λi: Ni→N
i}によって ， 各隣接プ ロセスに対応するポート 番号が 定まっている． 本論文では ，簡単のため ，各プ ロセ スは隣接プ ロセ スの状態を直接読むことができる状態通信モデルを対 象とする．ただし 本論文で 提案するプ ロト コルは ，隣 接プ ロセ スが 共有レジ スタを用いて 通信するレジ スタ 通信モデル 上のプ ロト コルへと 容易に 変換することが できる．

各プ ロセ ス_piは 状態機械であり，状態集合_Si，状 態 遷 移 関 数_αi の 組_{(Si, αi)}で 定 義 され る ．状 態 通

信 モデ ル で は ，プ ロ セ ス _pi の 状 態 遷 移 関 数 _αi は αi: Si× (^_p

j^∈Ni^{Sj) → Si}

である

（ 注1）

． 2. 2 分散シ ステムの実行

分 散シ ステ ム 全 体の 大 域 的な 状 況は ，全プ ロセ ス の 状 態の _n 項組で 表す．つ まり，すべて の 可 能な 状 況の 集 合を _C と すると ，_{C =}



p_i∈V^{Siで あ る ．あ}

る状況_{c ∈ C}に おいてプ ロセ スの部 分集合_Q⊂

=V ^が 同 時に 動 作し ，シ ステ ムが 状 況 _cか ら 状 況 _c

′_{(∈ C)}

に 変 化し た と す る ．これ を ，_c^′ _{= σ(c)} と 表 す．こ こ で ，_{∆ = (α0}, . . . , αn−1) ^{と す る と ，}σ = (∆, Q) と 表 さ れ ，こ れ を ス テップ と 呼 ぶ ．上 記 に お い て ， c = (s0, . . . , sn−1)^，c^′ = (s^′₀, . . . , s^′_n−1) ^{と す る と ，} pi∈ Q^ならばs^′_i= αi(si; c/Ni)^{である．ここで}c/Ni

は ，状況_cからプ ロセ ス_pj

ℓ^{∈ Ni (0 <}= ℓ <= |N^{i| − 1)} の状態_sj

ℓ ^{を集めた|Ni|項組(sj}0, sj1, . . . , sj_|Ni|−1) を表す．一方，_{pi∈ Q/} ならば _s^′_{i= si}である．

ス ケジュール はプ ロセ スの 空で は な い 部 分 集 合の 無限系列_Q⁰_{, Q}¹_{, . . . (Q}

ℓ_⊂

=V )^{であ る ．状況 c0 と ス} ケジュー ル _Q⁰_{, Q}¹_{, . . .}が 与え ら れ た と き ，_c⁰ か ら 始 ま る ス ケジ ュー ル _Q⁰_{, Q}¹_{, . . .} に よ る シ ス テ ム の 実 行 _E は ，状 況 の 無 限 系 列 _c⁰_{, c}¹_{, . . .} で 表 され る ． ただし 各 _ℓに ついて_c

ℓ _{= (s}ℓ

0, . . . , s^ℓ_n−1) ^{と す ると ，} c^ℓ+1= σ^ℓ(c^ℓ), σ^ℓ= (∆, Q^ℓ)^{を満たす．}pi∈ Q^ℓのと き，プ ロセス_piは ステップ _σ

ℓ

において動作し たと呼 び ，_s^ℓ_{i= s|} ^ℓ+1

i ^{のとき，pi}は 状態変化し たと呼ぶ ．こ こで 実行_{E = c}⁰_{, c}¹_{, . . .}におけ る状況_c⁰を実行_E の 初期状況と呼ぶ．

本論文では自己安定プ ロトコルについて 考察するの で ，初期状況に 対し 仮定を置かない．また ，無限スケ ジュールを考え るが ，すべてのスケジ ュールが 公平で あると仮定する．すなわち，各プ ロセ スは スケジ ュー ルに 無限にしばしば 現れ るものとする．

以 下 で は ，実 行 _{E = c}⁰_{, c}¹_{, . . .} の 部 分 系 列 c^k, c^k+1, . . . , c^{k′ を，実行断片と呼び}frag(E ; k, k^′)^と 表 す．また ，frag(E ; k, ∞)^{は 接 尾 部}c^k, c^k+1, . . . ^を 表す．

2. 3 非停止永久故障

本論文では ，プ ロセ スの故障を考え る．故障プ ロセ スとは ，分散シ ステムで 定められた状態遷移関数に 従 わな い状 態遷移を 行 うプ ロセ スであ る．形式的には ， 故障プ ロセ スを以下のように定義する．

状 況_c⁰ と スケジ ュール _Q⁰_{, Q}¹_{, . . .} に 対し て ，状 況 の 無 限 系 列 _{E = c}⁰_{, c}¹_{, . . .} を 考 え る ．こ こ で ， c^ℓ= (s^ℓ₀, . . . , s^ℓ_n−1)^{と表し ，}pi∈ Q/ ^ℓならばs^ℓ+1_i = s^ℓ_i

とする ．_{pi∈ Q}

ℓ

に 対し て ，_s

ℓ+1

i = α| i(s^ℓi; c^ℓ/Ni)^の とき，_piは実行_Eのステップ _σ

ℓ

に故障動作し たとい う．実行_Eにおいて 故障動作し たプ ロセ スを故障プ ロ セ スとい う．以下では ，故障プ ロセ スの 集合を _F と 表す．

これ まで に ，様々な 故障モデ ルが 考察され て いる ． ビ ザン チン 故障は ，故障動作に 関し て何も仮定し ない 故障モデ ルであり，最も大きな故障クラスである．ま た ，停止故障は ，実行のある時点以降，状態が 変化し ない故障モデルである．停止故障プ ロセ スが 一つで も 存在すると ，コンセン サス問題のよ うな単純な問題で さえ 解けないことが 知られている_[7]．これは ，プ ロセ スが 停止故障し ていることと単に 動作が 遅いことが 有 界時間で区別できないことによる．そこで本論文では ， 停止を許さない故障のモデルとし て ，故障プ ロセ スが 無限にしばしば ，故障動作により状態変化する非停止 永久故障を導入する．非停止永久故障は ，以下のよ う に 定義され る．

［ 定義₁］（ 非停止永久故障 ）

スケジュール_Q⁰_{, Q}¹_{, . . .}に対して，状況の無限系列 E = c⁰, c¹, . . .^{を考える．ここで ，}c^ℓ= (s^ℓ₀, . . . , s^ℓ_n−1) と表し ，_{pi∈ Q/}

ℓ

ならば_s^ℓ+1_{i = s}

ℓ

i^とする．pi^に対し

て，_{pi∈ Q}

ℓ

かつ_s^ℓ+1

i ^{= α| i(s} ℓ i^{; c}

ℓ_/N

i)^かつs^ℓ+1_i = s| ^ℓ_i なる_ℓが 無限個存在するとき，_piは実行_Eにおいて

非停止永久故障し たという． _✷

本論文では ，故障プ ロセ スの故障とし て非停止永久 故障のみを考え る．ただし ，故障プ ロセ スが 無限にし ばしば ，故障動作により状態変化し たとし ても，隣接 プ ロセ スが その状態変化を観測できなければ ，この故 障プ ロセ スの故 障は 停 止故障と 同じ に なってし ま う． 例えば ，正常なプロセス_{pi∈ Nf}が₂度動作する間に， 故障プ ロセ ス_pf が_s

ℓ

f → s^ℓf^′ → s^ℓf^{′′ のよ うに 複数回}

状態遷移し たとする．_s

ℓ

f = s| ^ℓ_f^{′であっても，}s^ℓ_f = s^ℓ_f^′′ であれば ，_piは故障プ ロセ スの状態変化を観測できな い．そこで 以下では ，故障プ ロセ スの故障動作による 状態変化が 任意の正常な隣接プ ロセ スによって無限に しばしば 観測され るという仮定を設け る．ここで ，状 態変化の観測は 次のように定義され る．

［ 定義₂］（ 状態変化の観測 ）

任意の実行_{E = c}⁰_{, c}¹_{, . . .}を考える．以下を満たす 実行断片frag(E ; k, k^′) (k < k^′)が 存在すると き，ス

（ 注₁）：厳 密に は ，_piは 隣 接プ ロ セ スをポ ート 番 号で 識 別 す る ので ， αi : Si ×^

j∈_Ni^Sj′



→ Si^{（ ただし ，p}j′^{= Λ−1}i ^{(j)）で ある．}

電子情報通信学会論文誌2002/11 Vol. J85–D–I No. 11

テップ _σ

k^′−1

に おいて ，プ ロセ ス_{pj∈ Ni}がプ ロセ ス_piの状態変化を観測するとい う．

• s^ki = s| ^k_i^′−1

• pj ∈ Q^k, pj ∈ Q^k′−1, pj ∈ Q/ ^ℓ (k < ℓ <

k^′− 1) ✷

2. 4 非停止永久故障下の自己安定生成木構成問題 分散シ ステム_{G = (V, E)}において ，非停止永久故 障プ ロセ スの集合を_F とする．本論文では ，_Gから 故障プ ロセ スを取り除いた ネット ワーク_{G − F} の生 成木を構成する自己安定プ ロト コルを提案する．ここ

では ，_{G − F} の生成木を構成する自己安定プ ロトコル

を 定義する ．ただし 以下では ，プ ロセス_p0が 根とし て指定されているものとする．また ，_p0は故障し ない と 仮定し ，ネット ワー ク_{G − F} は 連結であ ると 仮定 する．

各プ ロセ ス_piは 変数_parent

i^∈
Ni∪ {⊥}^{をもつ ．} 状 況 _c に おけ る 変 数 _parenti の 値 を _parenti(c) と 表し ，T (c) = (V, A(c))^{を ，}V ^{を 頂点集合，}A(c) = {(pi, pj)|parent_i(c) = Λi(pj)}^{を有向辺集合とするグ} ラフとする_{(Λi: Ni→
Ni)}．また_{T (c) − V}^′は，部分 グ ラフ_{(V − V}^′, A(c) − (V^′× V^′))^を表す(V^′⊂_{=V )}^．

［ 定義₃］頂点の部分集合_V

′_(⊂

=V − {p^{0})が 与えら} れ たとき，_{T (c) − V}

′

が 根プ ロセ ス_p0を 根とする木 であるとは ，以下の条件を満たすことをい う．

• ^{根プ ロセス}p0^{の出次数は}0 (parent0(c) = ⊥)^．

• ^{任意の頂点}pi(∈ V − V^′− {p0})^{の出次数は}1 (parenti(c) |= ⊥)^．

• T (c) − V^′において ，任意の頂点_{pi(∈ V − V}

′₎

から 根_p0に 到達可能． _✷

［ 定義₄］（ 自己安定生成木構成プ ロト コル ）

任意の故障プ ロセス集合_Fに対する，プロトコル_Aの 任意の実行_Eが次の条件を満たす接尾部frag(E ; k, ∞) をもつと き ，プ ロト コル _Aを非停止永久故障耐性を 有する自己安定生成木構成プ ロト コルとい う．

• ^{任意の状況}c^ℓ(ℓ >_{= k)}^{において ，}T (c^ℓ) − F^が 根プ ロセ ス_p0 を根とする木．

• ^{任意の 状況の 組}c^ℓ, c^ℓ′ (k <_{= ℓ <= ℓ}^′)^{に ついて ，} T (c^ℓ) − F = T (c^ℓ′) − F^． _✷

2. 5 ラ ウ ン ド

生成木を構成し て安定するまでの時間計算量を安定 時間という．非同期式分散シ ステムにおいては ，プ ロ セ スがいつ動作するかはわからない．そのままでは 時 間計算量が 評価できないため，状態通信モデルやレジ スタを 用いた 共有 メモリ通信モデ ルでは ，通常，₁単

位時間（ ラウンド ）に 各プ ロセスが 少なくとも₁回動 作するとい う仮定を設け る．本論文でも以下に定義す るラウンド 数を用いて ，安定時間を評価する．

［ 定義₅］（ ラウンド ）

任意の実行_E が 与えられたとき，

• ^第0ラウンド は ，初期状況から 始まる実行断片 において，各プ ロセスが少なくとも₁回はスケジュール に 現れ るよ うな最小の実行断片frag(E ; 0, ℓ0)^である．

• ^第k^ラウンドfrag(E ; ℓk−1, ℓk)^{が定義されたと} き，第_{k + 1}ラウンド は状況_c^ℓk から始まる実行断片 において，各プ ロセ スが 少なくとも₁回は スケジ ュー ルに現れ るような最小の実行断片_{frag(E ; ℓk, ℓk+1)}で

ある． _✷

なお， メッセージ 交換モデルでは ，類似の評価尺度 とし て理想時間計算量を用いるのが 一般的である．理 想時間計算量では，プ ロセスの動作時間は無視し ，メッ セ ージ 伝 送遅 延が たかだ か₁単 位時 間で あ ると 仮 定 する．

3. プ ロト コル

本章では ，非停止永久故障耐性を有する自己安定生 成木構成プ ロト コルを示し ，その正当性の証明と安定 時間の評価を行う．

3. 1 非停止永久故障耐性を 有する自己安定生成木 構成プ ロト コル

各正常プ ロセ ス_piの 状態遷移関数_αi は 以下で 示 され る手続き全体により表され る．つまり，正常プ ロ セ ス _piが スケジ ュールに 現れ るとき，直前の 状況に おけ る隣接プ ロセ スの状態（ 諸変数の値 ）に 従って₁ ステップ で 手続き全体が 処理され ，新たな _piの 状態 が 決められ る．

各プ ロセ ス_piは ，_piにおけ る局所的なポート 番号 の集合_Niを定数とし てもつ．また ，2. 4において定 義され た変数_parent

i（ 親へのポ ート 番号を 格納 ）に 加え ，_distiと_oldiの₂変数をもつ．変数_distiには 安定状況において根からの距離が 格納され ，変数_oldi は _piが 前回動作し たときの_parentparent

i ^{の 値を 保}

持するための変数である．

各プ ロセ スは自分が 根であるか 否かを関数_Root を 用いることで 判別できる．根以外の各プ ロセ ス_piは ， distparent_i^{及び parent}_parentiの値を前回動作し たと きの 値と比較することで ，親が 状態変化し たかど うか を観測する．親が 状態変化し たことを観測すると ，_pi は 現在の親とは 異なる隣接プ ロセ スを新たな親とし て

選ぶ ．なぜなら ，状態変化し たプ ロセ スは故障プ ロセ スである可能性があるからである．なお，新し い親を 選ぶ際には ，あらかじ め決められた順序で 繰返し 隣接 プ ロセ スを 選ぶ 関数 _RRobin を 使用す る ．これ に よ り，_piの隣接プ ロセ スに故障プ ロセスが 存在し ，無限 にしばしば 状態変化が 観測され る場合には ，故障プ ロ セ スを避けて親を選ぶことになる．

定数 _Ni 隣接プ ロセ スを表すポート 番号の集合． 変数 _disti 根からの距離．

oldi 前回の親の 親の 値を 保持するための 変 数．

関数 _Root プ ロセ スが根_p0であれば 真，根以外で あれば 偽を返す．

RRobin ^{与えられた集合}X^{からラウンド ロビン}

で集合の要素を返す．つまり_Xを順序 集合とみなし ，_ℓ回目に 呼ばれ たと き， ℓ mod |X|^{番目の要素を返す．} プ ロト コル

if (Root()) parent_i:= ⊥; disti:= 0;

else if ((oldi, disti) |= (parent_parent

i^{, distparenti+1))}

parent_i:= RRobin(Ni); (oldi, disti) := (parent_parent

i^{, distparent}i^{+ 1);}

3. 2 正 当 性

本 節で は 提 案し たプ ロト コ ルが 問 題の 解 条 件を 満 た すこ と を 示 す．問 題の 定 義に お いて 導 入し た 記 法 parent_i(c), T (c)^{に加え ，}disti(c), oldi(c)^{は ，それぞ} れ 状況_cにおけ る各プ ロセ ス_piの変数_{disti, oldi}の 値を表すものとする．

［ 補題₁］任意の実行_{E = c}⁰_{, c}¹_{, . . .}を考え る．状況 c^{kに おけ るグ ラフ}T (c^k)が 有向閉路を 含み ，有向閉 路に 正 常プ ロセ スが 含 まれ るならば ，その 有 向 閉 路 に 含 まれ る少な くと も₁個の 正 常プ ロセ スが 接尾 部 frag(E ; k, ∞)において状態変化し 親を変更する．

（ 証明 ） _{T (c}

k₎

に 含まれ る有向閉路を ，プ ロセ スの 系列を 用いて_pj

0, . . . , pj_m−1, pj_m(= pj₀)^{と 表す．た} だし ，_parent

j_ℓ^(c k_{) = Λ}

j_ℓ(pj_ℓ+1) (0 <_{= ℓ <= m − 1)} と す る ．有 向 閉 路 に 故 障プ ロ セ ス が 含 ま れ る 場 合 は ，故 障の 定 義とプ ロト コ ル より，故 障プ ロ セ ス を 親 と す る 正 常プ ロ セ ス_pjℓ は い ず れ 状 態 変 化 す る ． こ の と き ，ネット ワ ー ク _{G − F} の 連 結 性 の 仮 定 よ り_pj

ℓ ^{の 次数は2以上なので ，pj}ℓ は 親を 変更す る ．

有 向 閉 路に 含 まれ るすべ て のプ ロセ スが 正 常プ ロセ スの 場 合 ，各プ ロセ ス _{pjℓ( /}∈ F ) (0 <_{= ℓ <= m − 1)} が _c

k

以 降 状 態 変 化し な い の で あ れ ば ，各 _ℓ に つ いて _distj

ℓ^(c

k_{) = dist}

j_ℓ+1(c^k) + 1が 成 立 ．つ ま り distj0(c^k) > distj_m−1(c^k) > distj0(c^k) ^{が 成 立 す} る こ と に な り 矛 盾 す る ．し た が って ，distj_ℓ(c^k) |= distj_ℓ+1(c^k) + 1であるようなプ ロセ ス_pjℓ が 存在し ， 次に 動作するとき状態変化する．ここで ，_pj

ℓ ^の次数

が₂以上か ，または ，根である場合，_pj

ℓ^{が 親をpj}ℓ+1

以外に 変更する．_pj

ℓ ^{の次数が1}で ，か つ，根ではな い場合．_pj

ℓ ^{の 次数が1とな るのは 長さ2の有向閉路}

pj0, pj1, pj0 のと きのみで あ る．_pjℓ は _distjℓ の値の みを 変更し ，_pjℓ−1 が 親を_pj

ℓ ^{以外に 変更する．}✷

［ 補題₂］任意の実行_Eにおいて ，無限にしばしば 状 態変化するプ ロセ ス集合を_M と表す．実行_Eに接尾 部frag(E ; k, ∞)^{が 存在し ，任意の} ℓ >_{= k}^{に ついて ，} T (c^ℓ) − M ^{は 連結である．}

（ 証明 ） _{V − M} に 含 まれ るプ ロ セ スが 状 態 変 化 し ない接尾部frag(E ; k, ∞)を 考え る．背理法に より T (c^ℓ) − M (ℓ >_{= k)}^が2個 以 上の 連 結 成 分を 含 むと 仮定し ，根プ ロセ ス_p0 を 含まない連結成分の一つを Tr= (Vr, Ar)^{と 表す．補題}1^よりTr^{は 閉路を 含ま}

な い ．一 方 ，_Tr の 各プ ロ セ スの 出 次 数が₁だ か ら ， T (c^ℓ)^{に おいて ，}pi ∈ Vr ^{か つ} pj ∈ V − Vr ^{で あ る}

pi, pj^{の組のうち，}(pi, pj) ∈ A(c^ℓ)^{であるようなもの} が 存在し ，_Trが 連結成分なので_{pj∈ M} である ．_pi の次数が₂以上の場合，プ ロト コルより，いずれ_piは parent_i^{を変更するので}pi∈ M/ ^{に 矛盾する．}pi^の次

数が₁の場合，ネット ワーク_{G − F} の 連結性の 仮定 より_{pj∈ F/} であ る．プ ロト コルより_pjはいずれ_pi を親とし ，状態変化し なくなる．これは _{pj∈ M} に 矛 盾する．

し た が って _{T (c}

ℓ_{) − M}

は 連 結で あ るこ と が いえ

る． _✷

［ 補題₃］任 意の 実 行 _E に おいて ，無 限にし ば しば 状 態 変 化 す るプ ロセ ス 集 合を _M と 表 す．こ の と き F = M^{が 成立する．}

（ 証明 ） 非停止永久故障の定義より_{F ⊂}

=M^である．

V − M に 含 まれ るプ ロ セ スが 状 態 変 化し な い よ う な _E の 接 尾部frag(E ; k, ∞)を 考え ，背 理法に よ り (V − F ) ∩ M |= ∅^{と仮定する．仮定より}G − F^{は 連} 結なので ，_{pi∈ M − F} かつ_{pj∈ V − M} であるよう なプ ロセ スの組_{pi, pj ((pi, pj) ∈ E)}が 存在する ．仮 定より _piは 無限にしばしば 親を 変更するが ，プ ロト

電子情報通信学会論文誌2002/11 Vol. J85–D–I No. 11

コルより，いずれ _{V − M}に 属するプ ロセ スを親とし 状態変化し なくなることになり矛盾する．し たがって， (V − F ) ∩ M = ∅^{であることがいえ ，}F = M^がいえ

る． _✷

補題₂及び 補題₃から ，定理₁が いえ る．

［ 定理₁］任 意 の 実 行 _E に お い て ，い ず れ グ ラ フ T (c) − F ^{は 根プ ロ セ ス} p0 を 根 と す る 木 と な り 安

定する． _✷

3. 3 安 定時 間

次に 提案プ ロト コルが 安定するまでの時間計算量で ある安定時間を評価する．故障プ ロセ スの状態変化が 観測され ない間，正常なプ ロセ スが 故障プ ロセスを避 け て 木を 構成することが で きな いことは 自明であ る ． 時間計算量を評価するため ，各故障プ ロセ ス_pf に つ いて ，_pf のすべての隣接プ ロセスが_pf の状態変化を 観測するまでに 要するラウンド 数の 上界を_F と 仮定 する ．定数_F は 故障の 見つか りに くさを 示す指標と いうことができる．またネット ワークの最大次数を_d とする．

［ 補題₄］任 意の 実 行 _E に おいて ，₂個のプ ロセ ス pi, pj∈ F/ ^{を考え る．}pjが 状態変化し た直後の状況を c^{ℓとし ，}c^{ℓは 第}k(k >_{= 2)}ラウンド に 属するとする ． T (c^ℓ)^{に おいて} (pi, pj) ∈ A(c^ℓ)^{ならば ，}pi^は c^ℓ以

降第_{k + 1}ラウンド 終了までに状態変化する．

（ 証明 ） 実 行 _E に お い て ，_ℓ^′ < ℓ < ℓ^′′, pi ∈ Q^ℓ′, pi ∈ Q^{ℓ′′−1} で あ る よ う な 最 小 の 実 行 断 片 frag(E ; ℓ^′, ℓ^′′) = c^ℓ′, c^ℓ′+1, . . . , c^{ℓ′′ を 考え る ．}k >_{= 2} なので ，_{pi∈ Q}

ℓ^′

であるような_ℓ

′

は 存在する．また ， σ^{ℓ′′−1}= (∆, Q^{ℓ′′−1})^は第k^または第k + 1^ラウンド に 含まれ ることになる．

c^{ℓ′ において}pj^の親が pi^{でない場合と} pi^{であ る}

場合に 分けられ る．

• parentj^(c ℓ^′_{) = Λ}

j(pj^′) (pj^′ = p| i)^の場合． 場 合 分 け の 仮 定 よ り _{|Nj| >= 2} な の で ，補 題 の 仮 定 よ り，_parent

j^(c

ℓ−1_{) |= parent} j^(c

ℓ₎

で あ る ． parent_j(c^ℓ′) = parent_j(c^{ℓ′′−1}) = Λj(pj^′)^{と仮定する} と ，プ ロトコルより，実行断片_{frag(E ; ℓ}

′_{+ 1, ℓ}′′

− 1) に お い て ，_parentj(c

ℓ^′′′_{) = Λ}

j(pi)^{で あ る 状 況} c^ℓ′′′ (ℓ^′ < ℓ^{′′′ <}_{= ℓ}^′′− 1)が 存 在す るこ とに な る ．実行 断 片 _{frag(E ; ℓ}^′′′_{, ℓ}^′′_{− 1)}に お い て _pi は 状 態 変 化し な いので ，プ ロト コルより_pjも状態変化し ない ．つま り，_parentj(c

ℓ^′′−1_{) = Λ}

j(pi) となり矛盾する ．し た がって，_parentj(c

ℓ^′_{) |= parent} j^(c

ℓ^′′−1₎

がいえ ，_piは σ^{ℓ′′−1において ，}pjの状態変化を観測可能である．

• parentj^(c ℓ^′_{) = Λ}

j(pi)^の場合．parent_j(c^ℓ′) = parent_j(c^{ℓ′′−1}) = Λj(pi) ^{と 仮 定す る ．}pi ^は σ^{ℓ′ で} pjを 親とし てから ，_{frag(E ; ℓ}

′_{+ 1, ℓ}′′

− 1)^{に おいて} 動 作し な いの で ，_distj(c^ℓ

′) + 1 = disti(c^ℓ′+1)^{が 成} 立する ．ここで ，実行断片_{frag(E ; ℓ}^′_{, ℓ}^′′_{− 1)}に おい て ，_pj が ステップ _σ^ℓ−1 の₁回 の み 動 作し ，か つ ， ℓ = ℓ^′+ 1の場合は ，補題の仮定から_s^ℓ−1

j ^{= s|} ℓ

j^なの

で ，_distj(c

ℓ^′_{) |= dist}

j(c^ℓ′′)が 成立する ．それ 以外の 場合は_pjは_{frag(E ; ℓ}

′_{+ 1, ℓ}′′

− 1)^{で 動作し}pi^を親

と するので ，_distj(c^ℓ

′′₋₁

) = disti(c^ℓ′+1) + 1^{が 成立} し ，したが って_distj(c^ℓ

′) + 2 = distj(c^ℓ′′)^{がいえ る．} ど ちらの場合も_distj(c

ℓ^′_{) |= dist}

j(c^ℓ′′)^{が いえ る．し} たが って ，_piは_σ

ℓ^′′−1

において ，_pjの状態変化を観 測可能である．

いずれの場合も_piは_{k + 1}ラウンド 終了までに_pjの 状態変化を観測可能であり，_piは状態変化する．_✷

［ 定理₂］_{V − F} に属するプ ロセスが状態変化し なく

なるまでに要するラウンド 数は，たかだか_n(n/2+F)d である．（_dはネット ワークの最大次数 ）

（ 証明 ） 実行_E の_{V − F} が 状態変化し ない接尾部

（ 定理₁により定義可能 ）において ，各状況_cにおけ るグ ラフをT (c) − F = T^{とおく．また ，}T ^において 根_p0からの距離が _hであるプ ロセ ス集合を_Vhと表 し ，_Vhのプ ロセスが第h(n − h/2 + F)d^{ラウンド 以} 降は 状態変化し ないことを ，_hによる帰納法により証 明する．初期状況からたかだか₁ラウンド で根_{r ∈ V0} は状態変化し なくなる．

h−1

ℓ=0^Vℓに含まれ る各プ ロセ スが 状態変化し ない接 尾部 _{frag(E ; kh, ∞)}に おいて ， プ ロセ ス_{pi∈ Vh}はたか だか_d回し か 親を 変更し な い．ここで ，_piが_{ℓ (1 <= ℓ <= d)}回状態変化し た直後 の状況を_c^k

ℓ

h とする．（ 便宜上_k⁰_{h= kh}とおく ） 状況_c

k^ℓ_h

から ，_piが₁回状態変化するまでに 要す るラウンド 数はたかだか(n − h) + F^{であるが ，これ} は状況_c

k^ℓ_h

において ，_piから親をたど って得られ る経 路を，以下の₃通りの場合に分けることで証明され る．

• 経路上に 故障プ ロセ ス_{pf ∈ F} を含む場合．故 障プ ロセ ス_pf を 親とする正常プ ロセスが_pf の状態 変化を 観測し ，状態変化するまでに_F ラウンド 要す る．補題₄より，経路上の正常プ ロセ ス_pjが 状態変 化し てから ，それ を親とする正常プ ロセ ス_pj′が 状態 変化するまでたかだか₁ラウンド 要する．経路長はた かだか _{n − h}なので ，_piが 状態変化するまで ，たか だか(n − h) + F ^{ラウンド 要する．}

• ^経路上に F に 属するプ ロセ スを 含まず，経路

が 閉路に接続する場合．たかだか₁ラウンド で 閉路に 含まれ るプ ロセ スのど れかが 状態変化する．上の場合 と同様の議論により，_piが 状態変化するまで ，たかだ か_{n − h}ラウンド 要する．

• ^経路上に F に 属するプ ロセ スを 含まず，経路 の終点が _p0 であ る場合．経路上のプ ロセ スの うちた かだか₁ラウンド で 状態変化するプ ロセ スが 存在する 場合，上と同様の議論により，_piが 状態変化するまで ，

たかだか _{n − h}ラウンド 要する ．経路上のすべて の

プ ロセ スが₁ラウンド 以内に 状態変化し ない場合，経 路に 含まれ るプ ロセ ス_{pj∈ Vh−1} は 状況_c^k

0

h 以降状

態変化し ないので ，_pjを親とするプ ロセスは状況_c

k^ℓ_h

以降状態変化し ない．経路上のあるプ ロセス_pj′ が 状 態変化し ないならば ，_pj′ を親とするプ ロセ ス_pj′′は 状況_c^k

ℓ

h 以降状態変化し ない．し たが って，経路上の ど のプ ロセ スも状況_c^k

ℓ

h 以降状態変化し ないが ，_T の 定義により経路は _T に 含まれ ることになる． _✷

［ 系₁］ 提案プ ロト コルは ，非停止永久故障のもとで 生成木を構成する自己安定プ ロト コルであり，たかだ

かn(n/2 + F)dラウンド で 安定する． _✷

4. む す び

本論文では新たな故障モデルとし て非停止永久故障 を定義し た ．非停止永久故障は ，停止を許さないとい う制限の もとで 最も 性質の 悪い 故障で あ ると いえ る ． そし て ，非停止永久故障のもとで 生成木構成問題を解 く自己安定プ ロト コルを提案し た．これは ，自己安定 生成木構成問題の可解性にとって ，停止故障が 致命的 な影響を与えることを意味する．

本論文では問題を解くにあたって ，故障プ ロセ スの 状態変化が ，すべての正常な隣接プ ロセ スによって無 限にしばしば 観測され るという仮定を設けている．停 止故障と区別するためには ，故障プ ロセ スの状態変化 を無限にしばしば 観測する正常な隣接プ ロセ スが ，少 なくとも₁個は存在するという仮定が 必要である．本 論文の仮定を緩和し ，この最低限の仮定のもとで 自己 安定生成木構成問題が 解け るかど うか ，また ，そのま までは 解けない場合には ，故障プ ロセ ス数など につい てど のような制限を設ければ 問題が 解け るかを明確に することは 今後の課題である．

更に ，非停止永久故障のもとで ，生成木構成問題以 外の静的問題（ 解状況が 変化し ない問題 ）が 解け るか ど うか ，相互排除問題など の動的問題（ 解状況が 変化 す る 問 題 ）が 解け るかど うか の 考 察も 今 後の 課 題で

ある．

本論文で 提案し たプ ロト コルの安定時間はたかだか n(n/2 + F)dラウンド である．ここで ，_nはプ ロセス 数，_dはネット ワークの最大次数，_F は 故障プ ロセス の状態変化が 観測され るまでの時間の上界である．永 久故障を考慮し ない最適な自己安定生成木構成プ ロト コル_[1]の 安定時間_O(diam)と 比較すると ，安定時 間を改善できる可能性が 考えられ る．ここで_diamは ネット ワークの直径である．計算量の下界を求め ，安 定時間を改善することも今後の課題である．

謝辞 日ご ろより有用な御討論を頂いている奈良先 端科学技術大学院大学の井上美智子助教授に 深く感謝 致し ます．本研究は 一部，日本学術振興会・科学研究 費補助金・基盤研究_C（₂（ 課題番号） _12680349）の研 究助成による．

文 献

[1] S. Aggarwal and S. Kutten, “Time-optimal self- stabilizing spanning tree algorithms,” Proc. 13th Conference on the Foundations of Software Technol- ogy and Theoretical Computer Science (FSTTCS), pp.15–17, 1993.

[2] E. Anagnostou and V. Hadzilacos, “Tolerating tran- sient and permanent failures,” 7th Int. Workshop on Distributed Algorithms (LNCS725), pp.174–188, 1993.

[3] NS. Chen, HP. Yu, and ST. Huang, “A self-stabilizing algorithm for constructing spanning trees,” Infor- mation Processing Letters, vol.39, no.3, pp.147–151, 1991.

[4] E.W. Dijkstra, “Self stabilizing systems in spite of distributed control,” Commun. ACM, vol.17, pp.643– 644, 1974.

[5] S. Dolev, Self-stabilization, MIT Press, 2000. ISBN 0-262-04178-2.

[6] S. Dolev, A. Israeli, and S. Moran, “Uniform self- stabilizing leader election,” Proc. 5th Workshop on Distributed Algorithms, pp.167–180, 1991.

[7] M.J. Fischer, N.A. Lynch, and M.S. Paterson, “Im- possibility of distributed consensus with one faulty process,” Proc. 2nd. ACM SIGACT-SIGMOD Sym- posium on Principles of Database Systems, pp.1–7, 1983.

[8] E. Fromentin, M. Raynal, and F. Tronel, “On classes of problems in asynchronous distributed systems with process crashes,” Proc. 19th International Confer- ence on Distributed Computing Systems (ICDCS’99), pp.470–477, 1999.

[9] R. Gallager, P. Humblet, and P. Spira, “A distributed algorithm for minimum-weight spanning trees,” ACM Trans. Programming Languages and Systems, vol.5, no.1, pp.66–77, 1983.

電子情報通信学会論文誌2002/11 Vol. J85–D–I No. 11

[10] A. Gopal and K. Perry, “Unifying self-stabilization and fault-tolerance,” Proc. 12th Ann. ACM Symp. on Principles of Distributed Computing (PODC’92), pp.195–206, 1993.

[11] T. Masuzawa, “A fault-tolerant and self-stabilizing protocol for the topology problem,” Proc. 2nd. Work- shop on Self-Stabilizing Systems, pp.1.1–1.15, Las Vegas, NV, 1995.

[12] H. Matsui, M. Inoue, T. Masuzawa, and H. Fujiwara,

“Fault-tolerant and self-stabilizing protocols using an unreliable failure detector,” IEICE Trans. Inf. & Syst., vol.E83-D, no.10, pp.1831–1840, Oct. 2000.

（ 平成13 年 9 月 5 日受付，14 年 2 月 7 日再受付）

浮穴 学慈 （ 正員 ）

平9 阪大・理・物理卒．平 14 奈良先端 科学技術大学院大学博士後期課程了．同年 高松大学経営学部講師．分散アルゴ リズム の研究に 従事．博士（ 工学 ）．

片山 喜章 （ 正員 ）

平2 阪大・基礎工・情報卒．平 6 同大大 学院博士後期課程中退．同年奈良先端科学

技術大学院大学情報科学研究科助手．平7

同大情報科学セン ター 助手．平14 名工大 電気情報工学科講師．分散プ ロト コルなど に 関する 研究に 従事．博士（ 工学 ）．情報 処理学会会員．

増澤 利光 （ 正員 ）

昭57 阪大・基礎工・情報卒．昭 62 同大 大学院博士後期課程了．同年同大情報処理 教育セン ター助手．同大基礎工助教授を経 て ，平6 奈良先端科学技術大学院大学情報 科学研究科助教授．平12 阪大基礎工学研 究科教授，現在に 至る．平5 コーネル大客 員準教授（ 文部省在外研究員 ）．分散アルゴ リズ ム，並列アル ゴ リズム，テスト 容易化設計，テスト 容易化高位合成に 関する 研究に 従事．工博．ACM，IEEE，EATCS，情報処理学会各 会員．

藤原 秀雄 （ 正員：フェロー ） 昭44 阪大・工・電子卒．昭 49 同大大 学院博士課程了．同大・工・電子助手，明 治大・工・電子通信助教授，情報科学教授 を 経て ，現在奈 良先 端大・情報 科学 教授 ． 昭56 ウォータールー大客員助教授．昭 59 マッギル大客員準教授．論理設計論，フォー ルト ト レ ラン ス ，設 計 自動 化 ，テ スト 容 易 化設 計 ，テ スト 生 成，並列処理，計算複雑度に 関する研究に 従事．著書「Logic Testing and Design for Testability」(MIT Press) など ．大 川出版賞，IEEE Computer Society Outstanding Contribu- tion Award，IEEE Computer Society Meritorious Service Award など 受賞．情報処理学会会員．IEEE Computer Soci- ety Golden Core Member，IEEE Fellow．