Consensus in the Presence of Patial Synchrony (1988)

June 18, 2022

同期的なシステムには、プロセッサ間のメッセージの到達時間や時刻の誤差に有界がある。 非同期的なシステムには、どちらにも特定の有界はない。 表題のpartial synchronousは、同期、非同期の中間的な環境である。 到達時間や時刻の誤差の有界について、存在するが値が分からない環境と、値が分かっているがどの時刻から値が保証されるか分からない環境を意味する。

このpartial synchronousなシステム下で、Fault-stop, Ommission, Authenticated Byzantine, Byzantineの4障害において、正常に機能するために必要なプロセッサの総数\(N\)と障害を許容できるプロセッサ数\(t\)の関係を示した。 Fault stopは、正常に動作してるプロセッサがある時刻に停止し再起動できない障害をさす。 Omissionは、正常にメッセージを処理できるプロセッサにメッセージが届かず、処理し損ねたメッセージがある障害である。 Authenticated Byzantineは署名によりメッセージの改竄を検知できるビザンチン問題である。 4つの障害における\(N\)と\(t\)の関係を以下に示す。 faults

以上の関係を証明するためには、プロセッサが正常である条件を定義する必要がある。 そのため、正常性を安全性と活性の2つに分けて議論されている。 安全性は、\(t\)に含まれないプロセッサは、システムの妥当性に反する決定をせず、互いに必ず含意できることである。 活性は、\(t\)に含まれないプロセッサはある時刻において合意対象の候補を決定することである。 ある障害に対して、\(N-t\)個の任意のプロセッサが安全性と活性を満たすプロトコルを\(t\)-resilinent consensus protocolという。

論文へのリンク

画像は論文から引用されています。