Loading article…
分散コンピューティングシステムでは、障害検出器は、ノードの障害やクラッシュの検出を担当するコンピュータアプリケーションまたはサブシステムです。[1]障害検出器は、1996年にChandraとTouegの著書「Unreliable Failure Detectors for Reliable Distributed Systems」で初めて紹介されました。この本では、障害検出器は分散システムにおけるコンセンサス（信頼性の達成）とアトミックブロードキャスト（メッセージの同じシーケンス）を改善するためのツールとして説明されています。言い換えれば、障害検出器はプロセス内のエラーを探し、システムは信頼性のレベルを維持します。実際には、障害検出器がクラッシュを発見すると、システムはミスを犯しているプロセスを禁止して、それ以上の重大なクラッシュやエラーを防ぎます。[2] [3]
21世紀では、障害検出器は分散コンピューティングシステムで広く使用され、ソフトウェアアプリケーションが正常に機能しなくなるなどのアプリケーションエラーを検出します。分散コンピューティングプロジェクト（分散コンピューティングプロジェクトの一覧を参照）がますます普及するにつれて、障害検出器の使用も重要かつ重要になります。[4] [5]
起源
信頼性の低い障害検出器
1996 年に出版された「信頼性の高い分散システムのための信頼性の低い障害検出器」の共著者である Chandra と Toueg は、信頼性の低い障害検出器を導入することで障害ノードを検出するという概念にアプローチしました。 [6]彼らは、分散コンピューティング システムにおける信頼性の低い障害検出器の動作を次のように説明しています。システム内の各プロセスがローカル障害検出器コンポーネントに入ると、各ローカルコンポーネントはシステム内のすべてのプロセスの一部を調べます。[5]さらに、各プロセスには、障害検出器によって現在疑われているプログラムも含まれている必要があります。[5]
故障検出器
Chandra と Toueg は、信頼性の低い障害検出器でも、システムによって発生したエラーを検出する上では信頼性があると主張しました。[6]彼らは、信頼性の低い障害検出器と障害検出器が同じ特性を共有しているため、信頼性の低い障害検出器をすべての形式の障害検出器に一般化しました。さらに、Chandra と Toueg は、クラッシュしたプログラムが以前に疑われていたとしても、障害検出器はシステムのクラッシュを防ぐことはできないという重要な事実を指摘しています。障害検出器の構築は、分散型コンピュータ システムのフォールト トレラントコンポーネントの開発で発生した、不可欠でありながら非常に難しい問題です。その結果、分散型コンピューティング システムでの大量の情報トランザクションのエラーを検出する必要性から、障害検出器が発明されました。[1] [3] [5]
プロパティ
障害検出器のクラスは、完全性と正確性という2つの重要な特性によって区別されます。完全性とは、障害検出器がプロセス内で最終的にクラッシュしたプログラムを見つけることを意味し、正確性とは、障害検出器がプロセス内で正しい決定を下すことを意味します。[5]
完全性の度合い
完全性の度合いは、一定期間内に障害検出器によってクラッシュしたと疑われるプロセスの数によって決まる。[5]
- 強い完全性：「すべての障害のあるプロセスは、最終的にはすべての障害のないプロセスによって永久に疑われる。」[6]
- 弱い完全性：「すべての障害のあるプロセスは、最終的には何らかの障害のないプロセスによって永久に疑われる。」[6]
精度の度合い
精度の度合いは、故障検出器が一定期間内に犯したミスの数によって決まる。[5]
- 高い精度：「プロセスがクラッシュする前に、（誰にも）プロセスが疑われることはない。」[6]
- 精度が低い：「欠陥のないプロセスが疑われることは決してない。」[6]
- 最終的な強い正確性：「最後のクラッシュが発生した時点から、混乱の初期期間の終了からしばらく経つと、欠陥のないプロセスは疑われなくなります。」[6]
- 最終的な精度の低下：「最初の混乱期間の後、欠陥のないプロセスが疑われることは決してない。」[6]
分類
故障検出器は次の8つのタイプに分類できます。[1] [7]
- 完璧な故障検出器（P）
- 最終的には完璧な故障検出器（♦P）
- 強力な故障検出器（S）
- 最終的には強力な故障検出器（♦S）
- 弱い故障検出器（W）
- 最終的には弱い故障検出器（♦W）
- 準完全な故障検出器（Q）
- 最終的には準完璧な故障検出器（♦Q）
これらの故障検出器の特性は以下の通りである。[1]
簡単に言えば、故障検出器の特性は、故障検出器が実際の故障をどれだけ速く検出するか、そして誤検出をどれだけうまく回避するかによって決まります。完璧な故障検出器はすべてのエラーを間違いなく検出しますが、弱い故障検出器はエラーをまったく検出せず、多くの間違いを犯します。[3] [8]
アプリケーション
障害検出器のプロパティを変更することで、異なるタイプの障害検出器を取得できます。[3] [6]最初の例は、障害検出器の完全性を高める方法を示し、2番目の例は、あるタイプの障害検出器を別のタイプに変更する方法を示しています。
完全性の向上
以下はイェール大学のコンピュータサイエンス学部から抜粋した例です。これは障害検出器の完全性を高めることによって機能します。[6]
当初疑う = ∅
永遠に行う：
各プロセスpについて:
私の弱検出器がpを疑う場合、pをすべてのプロセスに送信する
あるプロセスqからpを受信すると:
容疑者 := 容疑者 + p - q
上記の例から、p がクラッシュした場合、弱い検出器は最終的にそれを疑うことになります。システム内のすべての障害検出器は、障害検出器によって作成された無限ループのため、最終的に p を疑うことになります。この例は、弱い完全性障害検出器も最終的にすべてのクラッシュを疑う可能性があることも示しています。 [6]クラッシュしたプログラムの検査は完全性に依存しません。[5]
故障検出器の削減わ故障検出器へS
以下は、故障検出器W を故障検出器Sに変更するアルゴリズムを満たす正当性の議論である。[1]故障検出器Wは完全性において弱く、故障検出器S は完全性において強い。どちらも正確さにおいて弱い。[6]
- 弱い完全性を強い完全性に変換する。[1]
- 永久に正確さを保ちます。[1]
- 最終的な正確さが保たれます。[1]
上記のすべての議論が満たされる場合、弱い障害検出器Wを強い障害検出器Sに縮小することは、分散コンピューティングシステム内のアルゴリズムと一致する。 [1]
参照
参考文献
- ^ abcdefghi D.、Kshemkalyani、Ajay (2008)。分散コンピューティング：原理、アルゴリズム、システム。Singhal、Mukesh。ケンブリッジ：ケンブリッジ大学出版局。ISBN 9780521189842. OCLC 175284075.
{{cite book}}: CS1 maint: 複数の名前: 著者リスト (リンク) - ^ Aguilera, Marcos Kawazoe; Chen, Wei; Toueg, Sam (2000-04-01). 「クラッシュリカバリモデルにおける障害検出とコンセンサス」.分散コンピューティング. 13 (2): 99–125. doi :10.1007/s004460050070. hdl : 1813/7330 . ISSN 0178-2770.
- ^ abcd Fischer, Michael J.; Lynch, Nancy A.; Paterson, Michael S. (1985年4月). 「1つの障害のあるプロセスによる分散コンセンサスの不可能性」J. ACM . 32 (2): 374–382. CiteSeerX 10.1.1.13.6760 . doi :10.1145/3149.214121. ISSN 0004-5411.
- ^ Holohan, Anne; Garg, Anurag (2005-07-01). 「オンラインコラボレーション: 分散コンピューティングの例」. Journal of Computer-Mediated Communication . 10 (4): 00. doi :10.1111/j.1083-6101.2005.tb00279.x. ISSN 1083-6101.
- ^ abcdefgh Chandra, Tushar Deepak; Toueg, Sam (1996). 「信頼性の高い分散システムのための信頼性の低い障害検出器」Journal of the ACM . 第 43 巻第 2 号. 43 (2). ニューヨーク、ニューヨーク、米国: ACM: 225–267. doi :10.1145/226643.226647. hdl :1813/7192. ISBN 978-0897914390。
- ^ abcdefghijkl 「FailureDetectors」。www.cs.yale.edu 。 2017年10月23日閲覧。
- ^ Aguilera, Marcos Kawazoe; Toueg, Sam (1996-10-09). 「ランダム化と障害検出: コンセンサスを解決するハイブリッドアプローチ」.分散アルゴリズム. コンピュータサイエンスの講義ノート. 第 1151 巻. Springer, ベルリン, ハイデルベルク. pp. 29–39. CiteSeerX 10.1.1.88.1597 . doi :10.1007/3-540-61769-8_3. ISBN 978-3540617693。
- ^ Chen, Wei; Toueg, S.; Aguilera, MK (2002 年 1 月). 「障害検出器のサービス品質について」. IEEE Transactions on Computers . 51 (1): 13–32. CiteSeerX 10.1.1.461.5630 . doi :10.1109/12.980014. ISSN 0018-9340.
外部リンク
- http://www.cs.yale.edu/homes/aspnes/pinewiki/FailureDetectors.html
- http://www.cs.cornell.edu/home/sam/FDpapers.html