Partially synchronous system

概要

• 一般的な分散システムはほぼこれ
• ほとんどの時間はSynchronous Systemとして振る舞うが、例外としてAsynchronous Systemとして振る舞う
  • 通常、タイムアウトを使ってプロセスがクラッシュしたと結論づける (この結論は誤りである可能性があるが、そういう誤ったクラッシュ検知に耐えられるFault toleranceが求められる)

モデル

• 2種類のモデルがある
  • メッセージの遅延上限$\delta$とプロセッサのクロックのズレ$\varphi$は存在するが事前にわからないとするモデル
    • コンセンサスアルゴリズム等を設計するうえでは、$\delta$と$\varphi$の値にかかわらず上手く動くものを設計しないといけない
  • $\delta$, $\varphi$は既知であるが、ある未知の時間$T$(Global Stabilization Time)からのズレである、とするモデル
    • GSTを経過後に、進行を保証する
    • コンセンサスアルゴリズム等を設計するうえでは、$T$の値にかかわらず上手く動くものを設計しないといけない

論文

• Consensus in the Presence of Partial Synchrony