日本ソフトウェア科学会第 37 回大会 (2020 年度) 講演論文集

ビザンチン将軍問題におけるメッセージ内容に基づく故障の特定
藤代 康誠

長谷部 浩二ビザンチン将軍問題は，故障プロセスに影響されることなく，すべての正常プロセスが妥当かつ一致した判断をする問題である．通常，ビザンチン将軍問題では故障プロセスの特定までは要求されないが，実システムへの応用を考えると故障プロセスを可能な限り特定できることが望ましい．そこで本研究では，Lamport の提案したビザンチン将
軍問題に対するアルゴリズム OM において，可能な範囲で故障を特定する方法を示す．具体的には，故障が特定された状態を，すべての正常プロセスが故障プロセスの識別子を知っていることとして定義し，故障プロセスが送信する誤ったメッセージをもとに，グラフ理論的な考察によって故障を特定するアルゴリズムを示す．さらに，故障を特定するためには，メッセージのやり取りを通して形成される正常プロセスの間の信頼関係が連結であれば十分であることを示す．

問題を解くアルゴリズムには，署名を用いない場合，

1 研究の背景と目的耐えることのできる故障プロセスの数に限界がある

分散システムは，複数の計算機上で実行される独立ことが挙げられる．処理の過程で故障プロセスを特定したプログラムが協調することで処理を実現するシし，取り除くことができれば，より確実に合意を達成ステムである．独立したプログラムの実行単位をプすることができる．さらに，故障プロセスは，システロセスという．プロセスを協調させる上で重要な課題

ムの協調を妨げるために悪意を持って実行されるプの一つは，故障したプロセスに影響されることなく，ログラムであると考えることもできる．したがって，すべての正常なプロセスが一致した正しい判断に至故障プロセスの特定はセキュリティの観点からも重要ることである．この問題はビザンチン将軍問題と呼ばな課題といえる．

れ，この問題を解くさまざまなアルゴリズムが提案されている．

そこで本研究では，Lamport が提案したビザンチン将軍問題に対するアルゴリズム OM において，故通常，ビザンチン将軍問題では故障プロセスの特障プロセスが送信する誤った内容のメッセージをもと定までは要求されないが，実システムへの応用を考に故障を特定する方法を示す．メッセージを特定の手えると，故障プロセスを可能な限り特定できることがかりとして用いる理由は，最も厄介な故障，すなわが望ましい．その理由の一つとして，ビザンチン将軍

ちシステムの協調を妨げつつ正常なプロセスに特定∗ Fault-Detection with Content of Messages in Byzan-tine Generals Problem.
This is an unrefereed paper. Copyrights belong tothe Authors.
Kosei Fujishiro, 筑波大学情報理工学位プログラム, Master’s Program in Computer Science, University ofTsukuba.
Koji Hasebe, 筑波大学システム情報系, Faculty of Engineering, Information and Systems, University ofTsukuba.

されないよう努める故障に対しても利用できる情報であると考えられるためである．
本研究の手法で重要な役割を果たしている概念は信頼関係である．プロセス Pi が，これまでに受信したメッセージの内容から，プロセス Pj は確実に正常であると結論できるとき，Pi は Pj を信頼しているという．プロセスは，アルゴリズム OM において想定した内容と矛盾したメッセージを得たとき，それをもとに故障の可能性があるプロセスを限定し，それ以外る手法が提案されている．この手法では，各ノードがのプロセスを信頼することができる．もしこの作業にメッセージの送受信やアプリケーションの入出力に関よってすべての正常なプロセスを信頼することができする偽装できないログを記録する必要がある．これにたなら，そのプロセスは故障を特定したことになる．

対し，本研究ではそのようなログを必要としない．

さらに，この作業で故障が特定できなかったとしてその他に，本研究と同様にメッセージの内容に基も，信頼しているプロセスからは，誤った情報を送らづく手法を取る研究としては，クラッシュ故障の特定れる心配なく情報を聞き出すことができる．したがっ[2] や，フェイクニュースの発信源の特定 [5] などが挙て，信頼関係のあるプロセスどうしで情報を共有するげられる．分散システムの一般的な内容，特に第 3,4ことで故障が特定できる場合がある．そこで本研究の章で述べるシステムのモデルとビザンチン故障問題

手法は，まず各プロセスが自分の受信したメッセージの定式化は米田らの文献 [7] に基づいている．

をもとに信頼関係を形成し，次にその信頼関係に基づいて情報を共有することで故障を特定する，という 23 対象とするシステムのモデル段階のアプローチをとる．この手法を用いることで，本研究で扱う分散システムのモデルは，ネットワー

メッセージをもとに正常プロセスの間で形成される信クを介して互いにメッセージを送受信することで通信頼関係が連結であれば，プロセスどうしの情報共有にするプロセスの集合によって構成される．各プロセスよって故障が特定されることを証明する．

は固有の識別子を持ち，それらは 1, . . . , n で表され本稿の構成は次の通りである．まず，第 2 章で関連研究について述べる．第 3 章では，本研究で扱うる．ここで，n はプロセスの総数である．さらに，識別子 i を持つプロセスを Pi で表す．

分散システムのモデルについて述べる．第 4 章では，分散システムは，プロセスの処理速度，メッセージビザンチン将軍問題の定義とそれに対するアルゴリ

遅延，プロセスが持つ局所時計と実時刻の同期の程ズム OM について述べる．第 5 章では，アルゴリズ度によって，同期システムと非同期システムに分けら

ム OM において送信されるメッセージの内容をもとれる．同期システムでは，プロセスの処理速度とメッに故障を特定する方法を示す．最後に，第 6 章で結論セージ遅延に上限が存在し，プロセスの局所時計と実と今後の課題を述べる．

時刻との間に一定の関係が成り立つ．本研究では，同期システムに基づく同期ラウンドモデルを採用する．

2 関連研究同期ラウンドモデルでは，プロセスはラウンドと呼ばビザンチン将軍問題とそれに対するアルゴリズムれる単位で処理を行い，ラウンドは全プロセスで同期

OM は Lamport によって 1982 年に提案された [4]．

して実行される．具体的には，プロセスは各ラウンド

これをきっかけにビザンチン故障に耐性のあるアルゴのはじめに直前のラウンドで送信されたメッセージをリズムの研究が活発に行われるようになり，実用的なすべて受信し，その内容をもとに現在のラウンドの処アルゴリズムも提案されている [1]．このような従来理とメッセージの送信を行う．のアルゴリズムは，ビザンチン故障の影響を覆い隠せ

ビザンチン将軍問題をはじめとする合意問題では，るものの，故障の特定まではしない．この点に関連しプロセスの故障を想定する．そこで，プロセスの故障て Yumerefendi らの論文 [6] は，信頼性が求められる時の動作についても規定しておく必要がある．故障

分散システムの設計目標として説明責任と呼ばれるのモデルにはいくつか種類があるが，本研究ではビ要件を最優先事項にすべきであるとしている．説明責

ザンチン故障を仮定する．ビザンチン故障は，故障プ

任とは，システムの参加者の行動が証明可能であり，ロセスの動作に仮定を置かない故障のモデルである．

その行動を第三者が検証できるような仕組みのこと

そのため，故障プロセスは処理の途中で動作を停止しである．Haeberlen らの論文 [3] では，説明責任を満たり，正しい処理を行った場合とは異なる内容のメッたすシステムと，そのシステムにおいて故障を特定すセージを送信するなど，あらゆる動作を起こす可能性がある．本研究では，故障プロセスが送信する誤っP に値を返す再帰的なアルゴリズムである．OM のた内容のメッセージをもとに，正常プロセスが故障プ実行開始時には，引数として，m に故障プロセスのロセスを特定する方法を示す．

数 k を，P に発信者以外のすべてのプロセスの集合

その他に，メッセージに関して以下を仮定する．

を，g に発信者プロセスを，x に g が提案する値を指• 送信されたメッセージは必ず正しく届く．

定する．OM の結果として各プロセスに返される値• メッセージの受信者はそのメッセージの送信者が，各プロセスの決定すべき値である．具体的なアルがわかる．

• どのプロセスも他のすべてのプロセスに直接メッセージを送ることができる．

1 つ目と 2 つ目の仮定は，プロセスが利用する通信ネットワークの信頼性が十分に高く，いったん送信されたメッセージがネットワークの障害によって失われたり改ざんされたりしないことを表す．3 つ目の仮定
は，プロセスの間の通信ネットワークが完全グラフであることを表す．

ゴリズムを以下に示す．
アルゴリズム OM (0, P, g, x)

1. プロセス g が値 x を P に含まれるすべてのプロセスに送信する．

2. 各プロセス Pi ∈ P に受信した値を返す．
アルゴリズム OM (m, P, g, x), m > 0

1. プロセス g が値 x を P に含まれるすべてのプロセスに送信する．

2. 各プロセス Pi ∈ P が受信した値 yi を用いて，|P| 個の OM (m−1, P−{Pi }, Pi , yi ) を実行する．

4 ビザンチン将軍問題の概要

3. 各プロセス Pi は，ステップ 1 で 1 つの値を受

ビザンチン将軍問題は，故障プロセスに影響される

信し，ステップ 2 で |P| − 1 個の値を返されていことなく，すべての正常なプロセスが正しい判断で一る．それら合計 |P| 個の値に過半数を占める同一致する問題である．正確な定義を以下に示す．の値があればその値を，なければあらかじめ決め定義 1 (ビザンチン将軍問題). 発信者と呼ばれる特られたデフォルトの値を Pi に返す．

別なプロセス PO がある値 v0 を保持しているとする．

3 章で述べたように，ここでは同期ラウンドモデル

PO 以外のすべてのプロセス Pi は以下の条件を満たを仮定しているため，プロセスはこのアルゴリズムすように変数 wi に値をセットせよ．

が正しく実行された場合に各ラウンドで受信すべき• PO 以外の正常なプロセス Pi はいずれ必ず wiの値をセットする．
（停止性）

メッセージを予想することができる．したがって，故障プロセスがあるラウンドで送信すべきメッセージ• PO 以外の正常なプロセス Pi , Pj が wi , wj に値を送信していない場合，受信側のプロセスはそれををセットした場合，セットされた値は同じであ検出することができる．その場合は，あらかじめ決める．
（合意）られたデフォルトのメッセージを受信したと見なす．

• PO が正常ならば，PO 以外の正常なプロセスがwi にセットした値は v0 である．
（妥当性）
以降，プロセス PO は値 v0 を「提案する」といい，PO 以外のプロセス Pi が wi に値 v をセットすることこの考え方を採用することで，故障プロセス Pi の動作を，アルゴリズム OM (m, P, g, x) のステップ 1 において x とは異なる値 y を送信する，というものに限定しても一般性を失わない．

を，Pi が v を「決定する」という．
故障プロセスの数を k(< n) としたとき，n ≤ 3k

5 故障の特定のもとではビザンチン将軍問題を解くアルゴリズム

本章では，アルゴリズム OM において送受信されは存在しない．一方，n ≥ 3k + 1 の場合には，このるメッセージをもとに故障を特定する具体的な方法を問題を解くさまざまなアルゴリズムが提案されてい示す．はじめに故障プロセス数 k が 1 の場合の方法る．本研究では，Lamport が提案したアルゴリズムを示し，次にそれを一般化したアルゴリズムを示す．

OM (m, P, g, x) を考える．OM は，プロセスの集合プロセスの総数 n はアルゴリズム OM によってビザ

ンチン将軍問題を解くことができる数以上，すなわちn ≥ 3k + 1 を満たすと仮定する．

(a)𝑃"

故障の特定に至るまでの大まかな流れは次の通りである．各プロセス Pi がそれぞれ発信者となってOM (k, P, Pi , vi ) を開始し，n 個のビザンチン将軍問題を同時に解くことを考える．OM の実行過程では，プロセスの間でさまざまなメッセージが送受信され

(b)

𝑃#

𝑃$

𝑃"

𝑃%(c)

𝑃%

𝑃#

𝑃$(d)
𝑃"

る．特に故障プロセスの存在下では，OM が正常に𝑃"実行された場合とは整合しないメッセージの集合を 1つのプロセスが受信することがある．そのようなメッ

𝑃#

𝑃$

𝑃%

𝑃#

𝑃$

𝑃%

セージの集合を受信したプロセスは，故障が疑われるプロセスの範囲を絞り込むことができる．メッセージの送受信を通して故障が疑われるプロセスが 1 つに絞られるならば，故障は特定されたことになる．

図1

OM におけるメッセージの送受信関係ズムにおけるステップ 1 のときであり，メッセージの内容は提案する値 x である．

5. 1 基本的な定義と仮定
はじめに，故障が特定されている状態の定義をはっ図からわかる通り，同じプロセスの間でも複数のメッセージが送信されるため，それらが図のどの矢きりさせておく．

印に相当するのかをプロセスが区別できる必要があ

定義 2. 各プロセス Pi は，正常と判断したプロセスる．そこで，OM で送信されるメッセージには，その集合 Ri を保持しているとする．集合 Ri がすべてのメッセージがこれまでにどのプロセスに受信されての正常プロセスを含み，かつ故障プロセスを含まないきたかを表す履歴が含まれるとする．履歴はプロセス

とき，プロセス Pi は故障を特定しているという．まの列で表される．例えば，図 1(a) の P2 から P3 へのた，すべての正常プロセスが故障を特定していると矢印に相当するメッセージには，P1 からのメッセーき，故障が特定されているという．

ジが P2 を経由して送信されたことを表す列 ⟨P1 , P2 ⟩さらに，プロセスは以下の事実をあらかじめ知っていると仮定する．

が付加される．この履歴は，プロセスがメッセージを送信するタイミングで自分の識別子を履歴の末尾にA1. システムのモデルは 3 章で述べたものである．

追加することで成長していく．この情報を付加したとA2. 実行されるアルゴリズムは OM である．

しても，故障プロセスの動作を誤った値の送信に限定

A3. 故障プロセス数は k である．

してよい点は変わらない．今後，故障プロセスが誤っ今後しばらくは議論をわかりやすくするため故障プた値を送信することを，「嘘をつく」とも表現する．

ロセス数 k が 1，プロセスの総数 n が 4 の場合について説明する．

5. 2 メッセージ内容に基づく故障の特定

図 1 は，OM におけるメッセージの送受信関係を，OM の実行の中で，故障プロセスが嘘をつくタイ

OM の再起呼び出しを最初に開始する発信者ごとにミングは複数存在する．以下では例として，P2 が故示したものである．このような発信者を「おおもとの障プロセスである場合を考える．図 1 からわかる通発信者」と呼ぶ．グラフの頂点はプロセスを表し，頂り，P2 がメッセージを送信する機会は，P2 がおおも点の間を結ぶ矢印は，矢印が向かう方向へメッセージとの発信者である場合に 3 回，そうでない場合に 2 回が送信されることを表す．太い線で描かれている頂点ずつの計 9 回ある．そのそれぞれについて，P2 が嘘は，おおもとの発信者を表す．アルゴリズム OM でをつくと，他のプロセスは何を知ることができるか考メッセージが送信されるのは 4 章で示したアルゴリ

える．仮に，P1 をおおもとの発信者とする OM （図1(a)）において，P2 が P3 に対して嘘をついたとすスが持つ情報をすべて使っているとは限らないため，る．すると，P3 は P1 の提案値として決定すべき値のより詳細な議論によって，少ない嘘からでも故障が特候補を 2 通り受け取ることになる．P1 から受け取っ定できる可能性がある．もう 1 つは，プロセスどうた値を v1 ，P2 から受け取った値を v1′ (̸= v1 ) とする．

しで何らかの情報交換をすることによって信頼関係をこのとき，P3 は P1 か P2 のいずれかが嘘をついて拡張するアプローチである．ここでは後者のアプローいることがわかる．実際，P1 も P2 も正常であるのチをとる．に P3 が 2 通りの値を受け取ることはない．一方で，次のアルゴリズム T C は，信頼関係を安全に推移

P1 と P2 どちらが嘘をついたのかまではわからない．

閉包に拡張する．より具体的には，どの正常プロセス

なぜなら，仮に P2 ではなく P1 が故障していて，P2も正常プロセスのみを信頼しているならば，このアルには v1′ を，P3 には v1 を送っていたとしても，P3 がゴリズムによって推移閉包に拡張された信頼関係もそP1 と P2 から受け取る値の組は P2 が嘘をついた場合の性質を保持する．そのうえ，このアルゴリズムは故と同じであり，区別がつかないからである．

障に影響されない．

さらに故障プロセス数が 1 であるという前提知識

アルゴリズム T Cから，P3 は P1 と P2 以外のプロセス，すなわち P4

1. 各プロセス Pi は，自分が信頼している各プロは確実に正常であることがわかる．したがって，P3セス Pj ∈ Ri に，Pj が信頼しているプロセスのは正常と判断したプロセスの集合 R3 に P4 を加えて集合 Rj を答えるよう要求する．要求を受けたよい．一般に Pj ∈ Ri のとき Pi は Pj を信頼していPj は，Rj を Pi に送信する．

るといい，このことを関係 R を用いて (Pi , Pj ) ∈ Rで表す．R を信頼関係と呼ぶ．

2. 直前のステップにおける要求の結果として Piが受信したすべての Rj の和集合を R′i とする．

同様の議論により，P2 がメッセージを送信する 9

各プロセス Pi は，R′i − Ri = ∅ ならば，このア回の機会すべてについて，どのタイミングで嘘をつくルゴリズムを終了する．そうでなければ，各プと，どのプロセスの間に信頼関係ができるのかを導き

ロセス Pj ∈ R′i − Ri に Rj を答えるよう要求し出すことができる．

た後，Ri に R′i の要素をすべて加える．要求を信頼関係の言葉を用いれば，故障が特定されている状態は，すべての正常プロセス Pi , Pj の間で受けた Pj は，Rj を Pi に送信する．その後，ステップ 2 をもう一度行う．

(Pi , Pj ) ∈ R が成り立つことといえる．これは，正常正常プロセスが他のプロセスに情報を要求する回数プロセスの集合を頂点とし，信頼関係 R を辺とするは高々n 回であり，同じプロセスに 2 回以上情報を要グラフが完全グラフであることともいえる．明らか

求することはないため，正常プロセスはいつか必ずこに，P2 が自分以外をおおもとの発信者とする OM にのアルゴリズムを終了できる．アルゴリズム T C において常に嘘をつけば，グラフは完全グラフとなり故関して次の定理が成り立つ．

障は特定される．

定理 1. 正常なプロセスの間で形成されている信頼関係のグラフが連結であり，かつ任意の正常プロセス

5. 3 アルゴリズム T C による信頼関係の拡張

Pi について，(Pi , Pj ) ∈ R ならば Pj は正常であると上で示した通り，故障プロセスが常に嘘をつけば故する．このとき，アルゴリズム T C を実行すること障は特定されるが，実用的な観点からは，故障プロセで故障が特定される．

スが嘘をつく回数が少なくても故障が特定できるこ

この定理は，故障を特定するためには正常プロセスとが望ましい．少ない嘘から故障を特定するためのアの間で連結な信頼関係を形成できれば十分であること

プローチは少なくとも 2 つある．1 つは，各プロセスを示している．例えば，故障プロセスを P2 とし，アが持つメッセージの集合からさらに得られる情報をルゴリズム OM の実行後に形成されている信頼関係考えるアプローチである．上で示した方法はプロセを R = {(P1 , P3 ), (P3 , P4 ), (P4 , P1 )} とする．この時

点では故障は特定されていない．それどころか，どのプロセスも故障を特定できていない．しかし，この信頼関係は定理 1 の仮定を満たしているため，この状態でアルゴリズム T C を実行すれば故障が特定できる．

5. 4 故障を特定する一般的なアルゴリズム
この節では，前節で示した故障の特定方法を一般化し，アルゴリズムとして示す．故障を特定するアルゴリズムを DetectFault と呼ぶことにする．故障プロセス数を k ，プロセスの総数を n(≥ 3k + 1) とし，その他の仮定は前節までと同様とする．DetectFault を実行するタイミングは，各プロセスをおおもとの発信者とする n 個の OM がすべて終了した直後である．各プロセスは OM において受信したメッセージをすべて保持しているとする．メッセージは値 v とプロセスの有限列 h の組 (v, h) で表される．v は OM における提案値であり，h はこれまでにそのメッセージを受信したプロセスの履歴である．提案値が取りうる値

1: procedure FormReliance
2:S←∅

3:

for all j ∈ {1, . . . , n} do4:for all (v, h), (v ′ , h′ ) ∈ Mij do
if v ̸= v ′ then5:

S ← S ∪ {branch(h, h′ )}6:

end if

7:
8:

end for9:

end for10:

Ri ← {Pi }11:

for all S1 , . . . , Sk ∈ S do

13:

if ∀l, m ∈ {1, . . . , k}, Sl ∩ Sm = ∅ then∪Ri ← Ri ∪ (P − kl=1 Sl ))14:

end if

12:

15:

end for

16: end procedure
図2

アルゴリズム FormRelianceの集合を V とし，プロセスの有限列の集合を H とする．プロセス Pi が OM において受信したメッセー
ジの集合を Mi ⊆ V × H で表す．DetectFault は次の 2 段階からなるアルゴリズムである．

1. 各プロセス Pi はメッセージの集合 Mi をもとにいくつかのプロセスを信頼する．

もとの発信者とするメッセージの集合である．
ここでの基本的な考え方は，おおもとの発信者が等しく，値が異なる 2 つのメッセージからは，故障プロセスを少なくとも 1 つ含むプロセスの集合が導ける，というものである．例えば，(0, ⟨P1 , P2 ⟩) と (1, ⟨P1 ⟩)2. アルゴリズム T C によって信頼関係を拡張する．という 2 つのメッセージからは，前述の議論によりこのうち，第 2 段階のアルゴリズム T C については

P1 , P2 の少なくとも一方が故障していると結論づけら

前節で説明した通りである．なお，定理 1 の結果は故れる．また，(0, ⟨P1 , P2 ⟩) と (1, ⟨P1 , P2 , P3 ⟩) からは，障プロセスの数に依存しないため，k が 2 以上であっP2 , P3 の少なくとも一方が故障していると結論づけても成り立つ．以下では第 1 段階で各 Pi が実行するられる．ここで P1 が故障の候補とならない理由は，アルゴリズムに焦点を当てる．このアルゴリズムをOM における 2 つのメッセージの成り立ちによる．具FormReliance と呼ぶ．

体的には，2 つのメッセージは，P1 から P2 に送信さFormReliance の処理内容を図 2 に示す．このアルれたメッセージを P2 が複製し，別々のプロセスに送ゴリズムではプロセスどうしの通信は行われず，プロ信することで初めて履歴の異なる 2 つのメッセージとセスの内部で逐次的に処理が実行される．2 行目からなる．したがって，2 つのメッセージの値が異なって9 行目までの処理では，メッセージの集合 Mi を用いいるならば，それは履歴における P2 以降のプロセスて故障プロセスを少なくとも 1 つ含むプロセスの集が嘘をついたためである．一般に OM において，お合をいくつか求め，それらを集合 S ⊆ 2 の要素としおもとの発信者が等しく，値が異なる 2 つのメッセーて追加している．ここで，P = {P1 , . . . , Pn } である．

ジが得られているとき，2 つの履歴の分岐点となるプ

4 行目の集合 Mij は，Mi に含まれるメッセージのうロセス以降のプロセスの集合は故障プロセスを少なく

ち，履歴が Pj から始まるもの，すなわち Pj をおおとも 1 つ含む．6 行目の関数 branch : H × H → 2PP

は 2 つのメッセージの履歴を入力として，履歴のでは，システムが同期システムであることや，プロ分岐点となるプロセス以降のプロセスの集合をセスが故障プロセスの数を知っていることなどを仮返す．例えば，h = ⟨P1 , P2 , P4 ⟩, h′ = ⟨P1 , P2 , P3 ⟩定しているが，実際のシステムではこれらの仮定が′の とき branch(h, h ) = {P2 , P3 , P4 } で あ り，h =⟨P1 , P2 , ⟩, h′′= ⟨P1 , P3 ⟩ の と き branch(h, h ) ={P1 , P2 , P3 } である．

成り立たない場面が多いと考えられる．したがって，より弱い仮定のもとでも手法を適用できるようにする必要がある．また，現状ではプロセスが自分の持っ10 行目以降の処理では，集合 S を用いて信頼できている情報から信頼関係を形成する際の推論についるプロセスを求める．はじめに 10 行目で自分自身をては十分検討されていない．プロセスの推論方法を改信頼する．11 行目以降では，S の要素，すなわち故障良することで，同じ情報からより強い結論を導ける可プロセスを少なくとも 1 つ含むことがわかっているプ

能性がある．この課題に対しては，充足可能性問題にロセスの集合を k 個選ぶ．選ばれた集合を S1 , . . . , Skよる定式化や認識論理を用いた分析など数理論理学とする．それらがどの 2 つも共通部分を持たないならを用いた手法が有効であると考えられる．

ば，前提知識 A3 により S1 , . . . , Sk はちょうど 1 つずつ故障プロセスを含む．さらに，S1 , . . . , Sk のどの参 考 文 献

1 つにも属さないプロセスは確実に正常である．した[1] Castro, M. and Liskov, B.: Practical Byzantine
Fault Tolerance, Proceedings of the Third Symposium on Operating Systems Design and Implementation, OSDI 99, USA, USENIX Association, 1999,
pp. 173–186.
[2] Fujishiro, K. and Hasebe, K.: Robustness andFailure Detection in Epistemic Gossip Protocols,
ICFEM 2020, (to appear).
[3] Haeberlen, A., Kouznetsov, P., and Druschel,P.: PeerReview: Practical accountability for distributed systems, ACM SIGOPS operating systems
review, Vol. 41, No. 6(2007), pp. 175–188.
[4] Lamport, L., Shostak, R., and Pease, M.: The
Byzantine Generals Problem, ACM Transactions
on Programming Languages and Systems, Vol. 4,No. 3(1982), pp. 382–401.
[5] van den Berg, L.: Unreliable Gossip, Master’s thesis, Universiteit van Amsterdam, 2018.
[6] Yumerefendi, A. R. and Chase, J. S.: The Roleof Accountability in Dependable Distributed Systems, Proceedings of the First Conference on Hot
Topics in System Dependability, HotDep 05, USA,USENIX Association, 2005, pp. 3.
[7] 米田友洋, 梶原誠司, 土屋達弘: ディペンダブルシス
テム, 共立出版, 2005.

がって，そのようなプロセスを Ri に追加する．これにより，すべての正常プロセスは正常プロセスだけを信頼する．

6 結論と今後の課題
本研究では，アルゴリズム OM において送受信されるメッセージをもとに故障を特定する方法を示し，それを具体的なアルゴリズムで記述した．さらに，本研究の方法で故障を特定するためには，メッセージをもとに形成される正常プロセス間の信頼関係が連結であれば十分であることを示した．本研究の方法を応用することで，一般的な分散システムのアルゴリズムにおいて故障が特定できるかどうかを検証する仕組
みや，故障を可能な限り漏れなく特定するアルゴリズムの設計などが可能になると考えられる．
今後の課題としては，提案手法をより広い範囲で適用できるように改良することが挙げられる．現状