スイムプロトコル

スケーラブル弱一貫性感染型プロセスグループメンバーシップ（SWIM）プロトコルは、分散システムで使用される「アウトソーシングされたハートビート」^{[ 1 ]}に基づくグループメンバーシッププロトコルであり、2002年にAbhinandan Das、Indranil Gupta、およびAshish Motivalaによって初めて導入されました。^{[ 2 ] [ 3 ]}これは、障害検出とグループメンバーシップの伝播を組み合わせたハイブリッドアルゴリズムです。

このプロトコルは、障害検出コンポーネントと情報伝達コンポーネントの2つのコンポーネントから構成されています。

故障検出コンポーネントは、以下のように機能します。

1. T'時間単位ごとに、各ノード (${\displaystyle N_{1}}$）ランダムな他のノードにpingを送信します（${\displaystyle N_{2}}$）会員名簿に記載されています。
2. もし${\displaystyle N_{1}}$から応答を受け取ります${\displaystyle N_{2}}$、${\displaystyle N_{2}}$健康になることを決意し、${\displaystyle N_{1}}$「最後に連絡が取れた」タイムスタンプを更新します${\displaystyle N_{2}}$現在時刻である。
3. もし${\displaystyle N_{1}}$応答を受け取らない、${\displaystyle N_{1}}$リスト上の他のkノードと連絡を取る(${\displaystyle \{N_{3},...,N_{3+k}\}}$）そして、pingを実行するように要求します。${\displaystyle N_{2}}$。
4. T'単位時間経過後：応答がない場合は、${\displaystyle N_{1}}$マーク${\displaystyle N_{2}}$失敗した。

普及コンポーネントは以下のように機能します。

• その上${\displaystyle N_{1}}$障害ノードの検出${\displaystyle N_{2}}$、${\displaystyle N_{1}}$障害が発生したノードに関する情報を含むマルチキャストメッセージを、メンバーシップリストに登録されている他のノードに送信する。
• ノードがグループに参加／離脱するための自発的な要求もマルチキャスト経由で送信されます。

このプロトコルは以下の保証を提供する。

• 高い完全性：完全な完全性が保証されます（例えば、グループ内のいずれかのノードのクラッシュ障害は、最終的にすべての稼働中のノードによって検出されます）。
• 検出時間：検出時間（ノード障害発生から検出までの時間）の期待値は${\displaystyle T'{\dot {}}{\frac {1}{1-e^{-q_{f}}}}}$、 どこ${\displaystyle T'}$はプロトコル期間の長さであり、$q_f$は、グループ内の故障していないノードの割合です。^{[ 3 ]}

オリジナルの SWIM 論文では、プロトコルをより堅牢にするための以下の拡張機能がリストされています。^{[ 2 ]}

• 疑わしいノード：pingメッセージに応答しないノードは、最初は障害としてマークされません。代わりに、「疑わしい」ノードとしてマークされます。疑わしいノードを検出したノードは、このメカニズムを含む他のすべてのノードにマルチキャストメッセージを送信します。疑わしいノードがタイムアウトしきい値より前にpingに応答した場合、マルチキャスト経由で「生存」メッセージが送信され、ノードから「疑わしい」ラベルが削除されます。
• 感染型拡散：マルチキャストを介してノード障害情報を伝播する代わりに、プロトコルメッセージはノードの生存状態を判断するために使用されるpingメッセージに便乗して送信されます。これはゴシップ拡散に相当します。
• ラウンドロビン方式によるプローブ対象の選択：プロトコルの各タイムステップでプローブ対象ノードをランダムに選択する代わりに、各ノードがラウンドロビン方式でプローブ対象を選択するようにプロトコルが変更されました。これにより、平均検出時間を低下させることなく、プロトコルの最悪ケースにおける検出時間を制限できます。

• 故障検出器
• クラッシュ（コンピューター）