タイミングと故障モデル

タイミングと故障モデルは、分散アルゴリズムがメッセージ遅延とプロセッサ速度について何を仮定できるか、およびコンポーネントがどのように故障することが許容されるかを規定します。

Definition

タイミングモデルは、メッセージ配信時間と相対プロセス速度の上限に関する仮定を固定し、故障モデルは、プロセスとチャネルが指定された動作から逸脱する可能性のある方法のセットを固定します。

Scope

このトピックでは、同期、非同期、および部分同期のタイミングモデル、クラッシュ（フェイルストップ）から省略、タイミング、そして任意（ビザンチン）の障害に至る故障の分類、および非同期システムとタイムアウトに基づく推論を橋渡しする故障検出器の抽象化について扱います。これらのモデルは、可能性と不可能性の結果が導き出される公理です。

Core questions

• アルゴリズムは遅延と速度に関してどのような制約を仮定でき、タイムアウトはそれらにどのように依存するのか？
• プロトコルはどの故障クラス（クラッシュ、省略、タイミング、ビザンチン）をマスクしなければならないのか？
• 非同期システムは、不可能性の結果を回避するために故障検出器でどのように拡張できるのか？

Key theories

部分同期

実際のシステムは完全に同期でも完全に非同期でもありません。部分同期モデルは、最終的に成立するか、または不明である遅延と速度の制約を仮定しており、これは現実的でありながら合意を解決するのに十分です。

故障モデルの階層

故障は、無害なフェイルストップクラッシュから、送受信の省略、タイミング違反、任意のビザンチン動作まで多岐にわたります。プロトコルが許容しなければならない故障の深刻さは、必要なレプリケーションファクタとメッセージの複雑さを決定します。

信頼できない故障検出器

抽象的な故障検出器は、どのプロセスがクラッシュしたかについて、誤りを含む可能性のあるヒントを提供します。合意を解決するのに十分な最も弱い検出器を特徴づけることで、非同期の厳密さと実用的なタイムアウトベースの実装が調和します。

Clinical relevance

本番システムは、タイムアウトを設定したり、レプリケーションファクタを選択したり、悪意のある参加者から防御するかどうかを決定したりするたびに、暗黙的にタイミングと故障モデルを選択しています。これらの仮定を誤ると、スプリットブレインやデータ損失のインシデントの一般的な根本原因となります。

History

非同期モデルがフォールトトレラントな合意には弱すぎることが示された後、Dwork、Lynch、Stockmeyerは1988年に部分同期を導入し、ChandraとTouegは1996年に信頼できない故障検出器を形式化しました。これらは、実用的なフォールトトレラントな合意を可能にするモデリングツールを提供しました。

Debates

タイムアウトはタイミングの仮定か、それとも故障検出器か？

ある見方では、タイムアウトは（最終的な）同期の制約を符号化するものとして扱われます。別の見方では、抽象的な故障検出器の実装として扱われます。この2つの枠組みはほぼ同等ですが、ネットワークモデルとアルゴリズムの間の異なる設計境界を強調しています。

Key figures

• Cynthia Dwork
• Nancy Lynch
• Larry Stockmeyer
• Tushar Chandra
• Sam Toueg

Seminal works

• dwork1988
• chandra1996
• lynch1996

Frequently asked questions

純粋な非同期システムでは、信頼性の高い故障検出を実装できないのはなぜですか？

メッセージ遅延に制約がない場合、任意に遅いが生きているプロセスはクラッシュしたプロセスと区別できないため、いかなる検出器も時には誤りを犯す必要があります。これが、非同期システムがタイミングの仮定または信頼できない検出器で拡張される理由です。