Paxos（コンピュータサイエンス）

Paxos は、信頼性の低い、または誤りやすいプロセッサのネットワークでコンセンサスを解決するためのプロトコルのファミリーです。コンセンサスとは、参加者のグループ間で 1 つの結果に同意するプロセスです。この問題は、参加者またはその通信に障害が発生する可能性がある場合に困難になります。^[1]

コンセンサスプロトコルは、レスリー・ランポート^[2]が提案し、フレッド・シュナイダー^[3]が調査したように、分散コンピューティングに対するステートマシンレプリケーションアプローチの基礎です。 ステートマシンレプリケーションは、アルゴリズムをフォールトトレラントな分散実装に変換する技術です。アドホックな技術では、重要な障害が解決されない場合があります。ランポートらが提案した原理的なアプローチでは、すべてのケースが安全に処理されることが保証されます。

パクソス議定書は1989年に初めて提出され、ギリシャのパクソス島で使用されていた架空の立法合意システムにちなんで名付けられました。ラムポートは、議会は「議員が議場に出入りし続けても」機能する必要があると書いています。^[4]その後、1998年に学術論文として出版されました。^[5]

Paxos プロトコル ファミリには、プロセッサの数、合意された値を学習するまでのメッセージ遅延の数、個々の参加者のアクティビティ レベル、送信されるメッセージの数、障害の種類など、さまざまなトレードオフが含まれます。非同期ネットワークでの進行を保証する決定論的フォールト トレラント コンセンサス プロトコルはありませんが ( Fischer、Lynch、Patersonの論文^{[6]で証明された}結果)、Paxos は安全性 (一貫性) を保証し、進行を妨げる可能性のある条件を引き起こすことは困難です。

Paxos は通常、耐久性が求められる場合 (たとえば、ファイルまたはデータベースを複製する場合) に使用され、耐久性のある状態の量が多くなる可能性があります。このプロトコルは、一定数のレプリカが応答しない期間中でも、処理を続行しようとします。また、永久に障害が発生したレプリカを削除したり、新しいレプリカを追加したりするメカニズムもあります。

この話題はプロトコルより前からあった。1988年、Lynch、Dwork、Stockmeyerは、広範囲の「部分同期」システムにおける合意の解決可能性を実証した。^[7] Paxosは、分散トランザクションのコンテキストで、1988年にOkiとLiskov によって初めて公開された「viewstamped replication」の合意に使用されるプロトコルと非常によく似ている。 ^[8] この先行研究にもかかわらず、Paxosは特にエレガントな形式論を提供し、フォールトトレラントな分散合意プロトコルの安全性の最も初期の証明の1つを含んでいた。

再構成可能なステートマシンは、動的なグループメンバーシップをサポートする信頼性の高いグループマルチキャストプロトコルに関する以前の研究と密接な関係があります。たとえば、 1985年と1987年にBirmanが行った仮想同期 gbcast ^{[9]プロトコルに関する研究です。しかし、gbcastは耐久性のサポートとパーティショニング障害への対処に関しては異例です。ほとんどの信頼性の高いマルチキャストプロトコルには、ステートマシンレプリケーションモデルの実装に必要なこれらの特性がありません。この点は、} Lamport、Malkhi 、Zhouの論文で詳しく説明されています。^[10]

Paxos プロトコルは、クラッシュ障害との均一な合意として形式化された問題に対する理論的なソリューションのクラスのメンバーです。この問題の下限はKeidarと Shraer によって証明されています。^[11]クラウド規模のステート マシン レプリケーション用の C++ ソフトウェア ライブラリである Derecho ^[12]は、自己管理型の仮想同期メンバーシップと統合された Paxos プロトコルを提供します。このプロトコルは Keidar と Shraer の最適性境界と一致し、最新のリモート DMA (RDMA)データセンター ハードウェアに効率的にマッピングされます (ただし、RDMA が利用できない場合は TCP を使用します)。

Paxos の説明を簡略化するために、次の仮定と定義が明示されています。適用範囲を広げる手法は文献で知られており、この記事では取り上げません。

• プロセッサは任意の速度で動作します。
• プロセッサに障害が発生する可能性があります。
• 安定したストレージを備えたプロセッサは、障害発生後にプロトコルに再参加する場合があります (クラッシュ回復障害モデルに従う)。
• プロセッサは共謀したり、嘘をついたり、プロトコルを破壊しようとしたりしません。(つまり、ビザンチン障害は発生しません。プロセスの恣意的/悪意のある動作から生じる障害を許容するソリューションについては、ビザンチン Paxos を参照してください。)

• プロセッサは他のプロセッサにメッセージを送信できます。
• メッセージは非同期で送信され、配信に時間がかかる場合があります。
• メッセージが失われたり、順序が変わったり、重複したりする可能性があります。
• メッセージは破損することなく配信されます。(つまり、ビザンチン障害は発生しません。メッセージ チャネルの恣意的/悪意のある動作によって発生する破損したメッセージを許容するソリューションについては、ビザンチン Paxos を参照してください。)

一般的に、コンセンサスアルゴリズムは、プロセッサが同時に故障した場合でも、プロセッサを使用して進行することができます。^[13]言い換えれば、故障していないプロセスの数は、故障したプロセスの数よりも厳密に大きくなければなりません。ただし、再構成を使用すると、同時にF個を超える故障が発生しない限り、合計で任意の数の故障に耐えるプロトコルを使用することができます。Paxosプロトコルの場合、これらの再構成は個別の構成として処理できます。^[14]${\displaystyle n=2F+1}$${\displaystyle F}$

安全性(「一貫性」とも呼ばれる)を保証するために、Paxos は 3 つのプロパティを定義し、障害のパターンに関係なく、最初の 2 つが常に保持されるようにします。

妥当性（または非自明性）

提案された値のみが選択され、学習される。^[15]

合意（または一貫性、安全性）

2つの異なる学習者が異なる値を学習することはできない（または、決定された値が複数存在することもできない）。^{[15] [16]}

終了（または生存）

値Cが提案された場合、最終的に学習者Lは何らかの値を学習することになる（十分な数のプロセッサが故障していない限り）。^[16]

Paxos は終了することが保証されていないため、活性特性を持たないことに注意してください。これは、一貫性プロトコルは安全性、活性、フォールトトレランスのうち 2 つしか持たないというフィッシャー・リンチ・パターソン不可能性結果 (FLP) ^[6]によってサポートされています。Paxos のポイントはフォールトトレランスを確保することであり、安全性を保証するため、活性を保証することはできません。

Paxosのほとんどの展開では、参加している各プロセスは、提案者、受け入れ者、学習者の3つの役割を果たします。^[17] これにより、正確性を犠牲にすることなく、メッセージの複雑さが大幅に軽減されます。

Paxosでは、クライアントはリーダーにコマンドを送信します。通常の操作では、リーダーはクライアントのコマンドを受信し、新しいコマンド番号を割り当て、一連のアクセプタプロセスにメッセージを送信してコンセンサスアルゴリズムのインスタンスを開始します^。 [ ${\displaystyle i}$${\displaystyle i}$^16]

役割を統合することで、プロトコルはデータベースコミュニティに典型的な効率的なクライアント・マスター・レプリカスタイルの展開に「縮小」されます。^[18] Paxosプロトコル（統合された役割を持つ実装を含む）の利点は、その安全性のプロパティが保証されることです。

一般的な実装のメッセージ フローは、「Multi-Paxos」セクションで説明されています。

このプロトコルは、Paxos ファミリーの中で最も基本的なものです。基本的な Paxos プロトコルの各「インスタンス」(または「実行」) は、単一の出力値を決定します。プロトコルは、複数のラウンドで進行します。成功したラウンドには、フェーズ 1 (パートaとbに分かれています) とフェーズ 2 (パートaとbに分かれています) の 2 つのフェーズがあります。フェーズの説明については、以下を参照してください。非同期モデルを想定していることに留意してください。つまり、たとえば、プロセッサが 1 つのフェーズにあるときに、別のプロセッサが別のフェーズにある場合があります。

Proposer は Prepare と呼ばれるメッセージを作成します。メッセージは一意の番号nで識別されます。この番号は、この Proposer によって Prepare メッセージで以前に使用されたどの番号よりも大きくなければなりません。n は提案される値ではなく、単に Proposer によるこの初期メッセージの一意の識別子であることに注意してください。実際、Prepare メッセージには提案された値 (多くの場合、vで示されます) が含まれている必要はありません。

プロポーザーは、少なくともクォーラムのアクセプタを選択し^{[方法? ] 、} nを含む Prepare メッセージをそれらのアクセプタに送信します。プロポーザーは、クォーラムを構成するのに十分な数のアクセプタと通信できない場合は、Paxos を開始しないでください。

アクセプタは、いずれかのプロポーザからの準備メッセージを待機します。アクセプタが準備メッセージを受信すると、そのメッセージの識別番号nを調べる必要があります。次の 2 つのケースがあります。

1. nが、アクセプターが（任意のプロポーザーから）受信した以前のすべての提案番号よりも大きい場合、アクセプターは、 n 以下の番号の今後のすべての提案を無視することを示すメッセージ（ Promise と呼ばれる）を提案者に返す必要があります。Promiseには、アクセプターが以前に受け入れたプロポーザルの中で最も大きい番号と、対応する受け入れ値を含める必要があります。
2. n がAcceptor が以前に受信した提案番号以下の場合、 Acceptor は応答する必要はなく、提案を無視できます。ただし、最適化のために、拒否または否定応答( NAK ) を送信すると、応答によって Proposer に、提案nで合意を形成する試みを停止できることが通知されます。

提案者がアクセプタのクォーラムから Promise を受け取った場合、提案に値vを設定する必要があります。以前に提案を受け入れたアクセプタがいる場合、その値は提案者に送信されます。提案者は提案の値vを、アクセプタが報告した提案番号の最大値に関連付けられた値 (ここではzと呼びます) に設定する必要があります。この時点でどのアクセプタも提案を受け入れていない場合、提案者は最初に提案したかった値 (たとえばx )を選択できます。^[19]

提案者は、提案に選択した値 v と提案番号n (以前にアクセプターに送信された準備メッセージに含まれていた番号と同じ) を含むAcceptメッセージ(n, v)を、アクセプターのクォーラムに送信します。したがって、Acceptメッセージは(n, v=z)か、以前にどのアクセプターも値を受け入れなかった場合は(n, v=x)のいずれかになります。

このAcceptメッセージは、「この提案を承認してください」という「リクエスト」として解釈される必要があります。

アクセプターがプロポーザーからAccept メッセージ(n, v)を受信した場合、 nより大きい識別子を持つ提案のみを検討することを (Paxos プロトコルのフェーズ 1b で) すでに約束していない場合にのみ、アクセプターはそれを受け入れなければなりません。

アクセプターが (フェーズ 1b で) nより大きい識別子を持つ提案のみを検討することをまだ約束していない場合、アクセプターは(受信したばかりのAcceptメッセージの)値v を(プロトコルの) 受け入れられた値として登録し、提案者とすべての学習者 (通常は提案者自身) にAcceptedメッセージを送信する必要があります。学習者は、最初の Accept メッセージを受信しただけではく、大多数のアクセプターから Accepted メッセージを受信した後でのみ、決定された値を学習します。

それ以外の場合は、Accept メッセージまたは要求を無視できます。

合意は、アクセプターの過半数が（同じ値ではなく）同じ識別子番号を受け入れたときに達成されることに注意してください。各識別子はプロポーザーに固有であり、識別子ごとに 1 つの値しか提案できないため、同じ識別子を受け入れるすべてのアクセプターは同じ値を受け入れます。これらの事実により、正確性に影響を与えないいくつかの直感に反するシナリオが発生します。アクセプターは複数の値を受け入れることができ、値は（異なる識別子を持つ）アクセプター間で過半数に達しても後で変更される可能性があり、アクセプターは識別子が過半数に達した後も提案を受け入れ続ける可能性があります。ただし、Paxos プロトコルは、合意が永続的であり、選択された値が不変であることを保証します。

複数の Proposer が競合するPrepareメッセージを送信した場合、または Proposer が Quorum の応答 ( PromiseまたはAccepted )を受信しなかった場合、ラウンドは失敗します。このような場合は、より高い提案番号で別のラウンドを開始する必要があります。

Paxos の提案者は「私はリーダーです」（または、たとえば「提案者 X がリーダーです」）と提案できることに注意してください。^[20] Paxos の合意と有効性の保証により、クォーラムによって承認された場合、提案者は他のすべてのノードに対してリーダーとして認識されます。これは、リーダーであると信じているノードが 1 つあり、常にリーダーとして認識されているノードが 1 つあるため、リーダー選挙 のニーズを満たします^{[21] 。}

次の図は、Basic Paxos プロトコルの適用例/状況をいくつか表したものです。いくつかの例では、Basic Paxos プロトコルが分散システムの特定の (冗長) コンポーネントの障害にどのように対処するかを示しています。

初めて提案が行われたとき、 Promiseメッセージで返される値は「null」であることに注意してください (このラウンドでは Acceptor が以前に値を受け入れていないため)。

下の図には、クライアントが 1 つ、プロポーザが 1 つ、アクセプタが 3 つ (つまり、クォーラム サイズは 3)、学習者が 2 つ (2 本の縦線で表されます) あります。この図は、最初のラウンドが成功した場合 (つまり、ネットワーク内のプロセスが失敗しない) を表しています。

ここで、V は (Va、Vb、Vc) の最後です。

最も単純なエラー ケースは、アクセプターの障害 (アクセプターのクォーラムがまだ有効な場合) と冗長ラーナーの障害です。これらのケースでは、プロトコルは「回復」を必要としません (つまり、成功します)。以下に示すように (次の 2 つの図/ケース)、追加のラウンドやメッセージは必要ありません。

次の図では、クォーラム内のアクセプタの 1 つが失敗したため、クォーラム サイズは 2 になります。この場合、基本 Paxos プロトコルは引き続き成功します。

クライアント 提案者 受諾者 学習者
   | | | | | | |
   X-------->| | | | | | リクエスト
   | X--------->|->|->| | | 準備(1)
   | | | | ! | | !! 失敗!!
   | |<---------X--X | | Promise(1,{Va, Vb, null})
   | X--------->|->| | | 承認!(1,V)
   | |<---------X--X--------->|->| 承認済み(1,V)
   |<---------------------------------X--X レスポンス
   | | | | | |

次のケースでは、(冗長な) 学習者の 1 つが失敗しますが、基本的な Paxos プロトコルは依然として成功します。

クライアント 提案者 受諾者 学習者
   | | | | | | |
   X-------->| | | | | | リクエスト
   | X--------->|->|->| | | 準備(1)
   | |<---------X--X--X | | プロミス(1,{Va,Vb,Vc})
   | X--------->|->|->| | | 承認!(1,V)
   | |<---------X--X--X------>|->| 承認済み(1,V)
   | | | | | | !! 失敗!!
   |<---------------------------------X レスポンス
   | | | | | |

この場合、提案者は値を提案した後、合意に達する前に失敗します。具体的には、受け入れメッセージの途中で失敗するため、クォーラムの 1 つの受け入れ者だけが値を受け取ります。その間に、新しいリーダー (提案者) が選出されます (ただし、詳細は示されていません)。この場合、2 ラウンドがあることに注意してください (ラウンドは上から下へ垂直に進みます)。

クライアント 提案者 受諾者 学習者
   | | | | | | |
   X----->| | | | | | リクエスト
   | X------------>|->|->| | | 準備(1)
   | |<------------X--X--X | | プロミス(1,{Va, Vb, Vc})
   | | | | | | |
   | | | | | | | !! 放送中にリーダーが失敗!!
   | X------------>| | | | | 承認!(1,V)
   | ! | | | | |
   | | | | | | | !! 新しいリーダー!!
   | X--------->|->|->| | | 準備(2)
   | |<---------X--X--X | | Promise(2,{V, null, null})
   | X--------->|->|->| | | 承認!(2,V)
   | |<---------X--X--X------>|->| 承認済み(2,V)
   |<---------------------------------X--X レスポンス
   | | | | | | |

最も複雑なケースは、複数の提案者が自分はリーダーだと思っている場合です。たとえば、現在のリーダーが失敗して後で回復したとしても、他の提案者がすでに新しいリーダーを再選択している場合があります。回復したリーダーはまだこれを学習しておらず、現在のリーダーと競合する 1 ラウンドを開始しようとします。下の図では、4 つの失敗したラウンドが示されていますが、(図の下部に示されているように) もっと多くのラウンドがある可能性があります。

クライアント 提案者 受諾者 学習者
   | | | | | | |
   X----->| | | | | | リクエスト
   | X------------>|->|->| | | 準備(1)
   | |<------------X--X--X | | Promise(1,{null,null,null})
   | ! | | | | | !! リーダーは失敗しました
   | | | | | | | !! 新しいリーダー (最後の番号が 1 だったことを知っている)
   | X--------->|->|->| | | 準備(2)
   | |<---------X--X--X | | Promise(2,{null,null,null})
   | | | | | | | | !! オールドリーダーが回復
   | | | | | | | | !! オールドリーダーが2回トライ、拒否
   | X------------>|->|->| | | 準備(2)
   | |<------------X--X--X | | ナック(2)
   | | | | | | | | !! オールドリーダーが3回挑戦
   | X------------>|->|->| | | 準備(3)
   | |<------------X--X--X | | Promise(3,{null,null,null})
   | | | | | | | | !! 新リーダーが提案、却下
   | | X--------->|->|->| | | 承認!(2,Va)
   | | |<---------X--X--X | | ナック(3)
   | | | | | | | | !! 新リーダーが4に挑戦
   | | X--------->|->|->| | | 準備(4)
   | | |<---------X--X--X | | Promise(4,{null,null,null})
   | | | | | | | | !! オールドリーダーが提案、却下
   | X------------>|->|->| | | 承認!(3,Vb)
   | |<------------X--X--X | | ナック(4)
   | | | | | | | | ...などなど...

次のケースでは、1 つの Proposer が失敗する前に 1 つの Acceptor による値 V1 の受け入れを達成します。新しい Proposer は、V1 を受け入れたことのない Acceptor を準備し、V2 を提案できるようにします。その後、V2 は、最初に V1 を受け入れた Acceptor を含むすべての Acceptor によって受け入れられます。

提案者 受容者 学習者
 | | | | | | |
 X--------->|->|->| | | 準備(1)
 |<---------X--X--X | | Promise(1,{null,null,null})
 x--------->| | | | | 承認!(1,V1)
 | | X------------->|->| 承認済み(1,V1)
 ! | | | | | | !! 失敗!!
    | | | | | |
    X--------->|->| | | 準備(2)
    |<---------X--X | | Promise(2,{null,null})
    X------>|->|->| | | 承認!(2,V2)
    |<------X--X--X------>|->| 承認済み(2,V2)
    | | | | | |

次のケースでは、1 つの Proposer が失敗する前に 1 つの Acceptor の値 V1 の受け入れを達成します。新しい Proposer は、V1 を受け入れたことのない Acceptor を準備し、V2 を提案できるようにします。この Proposer は、失敗する前に 1 つの Acceptor に V2 を受け入れさせることができます。新しい Proposer は、V1 を受け入れた Acceptor を含む多数派を見つけ、それを提案する必要があります。Proposer は、失敗する前に 2 つの Acceptor にそれを受け入れさせることに成功します。この時点で、3 つの Acceptor が V1 を受け入れていますが、同じ識別子ではありません。最後に、新しい Proposer は、受け入れられた最大の識別子を見たことがない多数派を準備します。その多数派で最大の識別子に関連付けられている値は V2 であるため、それを提案する必要があります。次に、この Proposer はすべての Acceptor に V2 を受け入れさせ、コンセンサスを達成します。

  提案者 受容者 学習者
 | | | | | | | | | | |
 X--------------->|->|->|->|->| | | 準備(1)
 |<--------------X--X--X--X--X | | Promise(1,{null,null,null,null,null})
 x--------------->| | | | | | | 承認!(1,V1)
 | | | | X------------------>|->| 承認済み(1,V1)
 ! | | | | | | | | | | | !! 失敗!!
    | | | | | | | | | |
    X--------------->|->|->|->| | | 準備(2)
    |<--------------X--X--X--X | | Promise(2,{null,null,null,null})
    X-------------->| | | | | | 承認!(2,V2)
    | | | | X--------------->|->| 承認(2,V2)
    ! | | | | | | | | | | !! 失敗!!
       | | | | | | | | |
       X--------->|---->|->|->| | | 準備(3)
       |<---------X-----X--X--X | | Promise(3,{V1,null,null,null})
       X--------------->|->| | | | 承認!(3,V1)
       | | | | X--X--------->|->| 承認(3,V1)
       ! | | | | | | | | !! 失敗!!
          | | | | | | | |
          X------>|->|------->| | | 準備(4)
          |<------X--X--|--|--X | | プロミス(4,{V1(1),V2(2),null})
          X------>|->|->|->|->| | | 承認!(4,V2)
          | X--X--X--X--X------>|->| 承認済み(4,V2)

次のケースでは、1 人の提案者が失敗する前に 2 人の受容者から値 V1 の受容を獲得します。新しい提案者が別のラウンドを開始できますが、その提案者が V1 を受容した受容者を少なくとも 1 人含まない過半数を準備することは不可能です。そのため、提案者が既存のコンセンサスを確認できない場合でも、提案者の唯一の選択肢は、すでに合意されている値を提案することです。新しい提案者は、プロセスを再開するために継続的に識別子を増やすことができますが、コンセンサスを変更することはできません。

提案者 受容者 学習者
 | | | | | | |
 X--------->|->|->| | | 準備(1)
 |<---------X--X--X | | Promise(1,{null,null,null})
 x--------->|->| | | | 承認!(1,V1)
 | | X--X--------->|->| 承認済み(1,V1)
 ! | | | | | | !! 失敗!!
    | | | | | |
    X--------->|->| | | 準備(2)
    |<---------X--X | | プロミス(2,{V1,null})
    X------>|->|->| | | 承認!(2,V1)
    |<------X--X--X------>|->| 承認済み(2,V1)
    | | | | | |

Paxos の一般的な展開では、分散ステート マシンへのコマンドとして機能する合意された値の連続ストリームが必要です。各コマンドが Basic Paxos プロトコルの単一インスタンスの結果である場合、かなりのオーバーヘッドが発生します。

リーダーが比較的安定している場合、フェーズ 1 は不要になります。したがって、同じリーダーを持つプロトコルの将来のインスタンスでは、フェーズ 1 をスキップできます。

これを実現するために、各ラウンドで同じリーダーによって増分される各値とともにラウンド番号Iが含まれます。Multi-Paxos は、障害のないメッセージ遅延 (提案から学習まで) を 4 遅延から 2 遅延に削減します。

次の図では、初期リーダー (提案者) を持つ基本 Paxos プロトコルのインスタンス (または「実行」) が 1 つだけ表示されています。マルチ Paxos は、基本 Paxos プロトコルの複数のインスタンスから構成されていることに注意してください。

クライアント 提案者 受諾者 学習者
   | | | | | | | --- 最初のリクエスト ---
   X-------->| | | | | | リクエスト
   | X--------->|->|->| | | 準備(N)
   | |<---------X--X--X | | Promise(N,I,{Va,Vb,Vc})
   | X--------->|->|->| | | 承認!(N,I,V)
   | |<---------X--X--X------>|->| 承認済み(N,I,V)
   |<---------------------------------X--X レスポンス
   | | | | | | |

ここで、V は (Va、Vb、Vc) の最後です。

この場合、基本 Paxos プロトコルの後続のインスタンス ( I+1で表される) は同じリーダーを使用するため、Prepare および Promise サブフェーズで構成されるフェーズ 1 (基本 Paxos プロトコルの後続のインスタンス) はスキップされます。リーダーは安定している必要があることに注意してください。つまり、クラッシュしたり変更されたりしてはいけません。

クライアント 提案者 受諾者 学習者
   | | | | | | | --- 次のリクエスト ---
   X-------->| | | | | | リクエスト
   | X--------->|->|->| | | 承認!(N,I+1,W)
   | |<---------X--X--X------>|->| 承認済み(N,I+1,W)
   |<---------------------------------X--X レスポンス
   | | | | | | |

Multi-Paxos の一般的な展開では、提案者、受け入れ者、学習者の役割を「サーバー」に集約します。つまり、最終的には「クライアント」と「サーバー」のみになります。

次の図は、提案者、受け入れ者、学習者の役割が「サーバー」と呼ばれる単一の役割にまとめられた、基本的な Paxos プロトコルの最初の「インスタンス」を表しています。

クライアント サーバー
   | | | | --- 最初のリクエスト ---
   X-------->| | | リクエスト
   | X->|->| 準備(N)
   | |<-X--X プロミス(N, I, {Va, Vb})
   | X->|->| 承認!(N, I, Vn)
   | X<>X<>X 承認済み(N, I)
   |<--------X | | レスポンス
   | | | |

基本 Paxos プロトコルの後続のインスタンスでは、基本 Paxos プロトコルの前のインスタンスと同じリーダーを使用して、フェーズ 1 をスキップできます。

クライアント サーバー
   X-------->| | | リクエスト
   | X->|->| 受け入れる!(N,I+1,W)
   | X<>X<>X 承認済み(N,I+1)
   |<--------X | | レスポンス
   | | | |

交換されるメッセージの数を減らしたり、プロトコルのパフォーマンスを向上させるなど、さまざまな最適化を実行できます。これらの最適化のいくつかを以下に報告します。

「値が選択されたことを他の学習者に知らせる単一の識別学習者を用意することで、余分なメッセージ遅延を犠牲にしてメッセージを節約できます。その後、アクセプタは、識別学習者にのみAcceptedメッセージを送信します。ほとんどのアプリケーションでは、リーダーと識別学習者の役割は同じプロセッサによって実行されます。^[22]

「リーダーは、PrepareおよびAccept!メッセージをアクセプタの定足数にのみ送信できます。その定足数内のすべてのアクセプタが動作しており、リーダーおよび学習者と通信できる限り、定足数に含まれていないアクセプタは何もする必要はありません。」^[22]

「アクセプターはどの値が選ばれるかを気にしません。単にPrepareとAccept!メッセージに応答して、失敗しても1つの値だけが選ばれるようにするだけです。しかし、アクセプターがどの値が選ばれたかを知った場合、その値を安定したストレージに保存し、そこに保存した他の情報を消去することができます。アクセプターが後でPrepareまたはAccept!メッセージを受信した場合、Phase1bまたはPhase2bアクションを実行する代わりに、リーダーに選択された値を通知するだけで済みます。^[22]

「リーダーは、値 v を送信する代わりに、Accept!メッセージで v のハッシュを一部のアクセプターに送信できます。学習者は、アクセプターのクォーラムから v またはそのハッシュのAcceptedメッセージを受信し、それらのメッセージの少なくとも 1 つにハッシュではなく v が含まれている場合、v が選択されたことを学習します。ただし、リーダーは、 v の実際の値を伝えずに、Phase2a アクションで使用する必要がある値 v のハッシュを伝えるPromiseメッセージを受信する可能性があります。その場合、リーダーは、v を知っているプロセスと通信するまで、Phase2a アクションを実行できません。」^[22]

「提案者は、すべてのコーディネータではなく、リーダーにのみ提案を送信できます。ただし、これには、リーダー選択アルゴリズムの結果を提案者にブロードキャストする必要があり、コストがかかる可能性があります。したがって、提案者が提案をすべてのコーディネータに送信できるようにした方がよい場合があります。（その場合、コーディネータ自身だけがリーダーが誰であるかを知る必要があります。）^[15]

「各アクセプターが各学習者にAcceptedメッセージを送信する代わりに、アクセプターはリーダーにAcceptedメッセージを送信し、リーダーは値が選択されたときに学習者に通知することができます。ただし、これにより余分なメッセージ遅延が発生します。」^[15]

「最後に、フェーズ1はラウンド1では不要であることに注意してください。ラウンド1のリーダーは、提案された値を含むAccept!メッセージを送信することでラウンドを開始できます。」 ^[15]

Cheap Paxos は Basic Paxos を拡張し、各障害の後に動的に再構成することで、F+1 個のメイン プロセッサと F 個の補助プロセッサで F 個の障害を許容します。

プロセッサ要件の削減は、活性を犠牲にして行われます。短時間に多くのメイン プロセッサに障害が発生した場合、補助プロセッサがシステムを再構成するまでシステムは停止する必要があります。安定期間中、補助プロセッサはプロトコルに関与しません。

「プロセッサ p と q の 2 つしかない場合、一方のプロセッサはもう一方のプロセッサの障害と通信媒体の障害を区別できません。3 番目のプロセッサが必要です。ただし、その 3 番目のプロセッサはコマンドのシーケンスの選択に参加する必要はありません。p または q が失敗した場合にのみアクションを実行し、その後は p または q のいずれかが単独でシステムを操作し続ける間は何も行いません。したがって、3 番目のプロセッサは小型/低速/安価なプロセッサ、または主に他のタスク専用のプロセッサにすることができます。」^[22]

3 つのメイン アクセプタ、1 つの補助アクセプタ、およびクォーラム サイズ 3 を伴う例で、1 つのメイン プロセッサの障害とその後の再構成を示します。

            { アクセプター }
提案者 メイン 補助学習者
| | | | | | -- フェーズ 2 --
X----------->|->|->| | | 承認!(N,I,V)
| | | ! | | --- 失敗! ---
|<-----------X--X--------------->| 承認済み(N,I,V)
| | | | | -- 障害が検出されました (2 つのみ受け入れられました) --
X----------->|->|------->| | Accept!(N,I,V) (再送信、Aux を含む)
|<-----------X--X--------X------>| 承認済み(N,I,V)
| | | | | -- 再構成: クォーラム = 2 --
X----------->|->| | | Accept!(N,I+1,W) (補助は参加しません)
|<-----------X--X--------------->| 承認済み(N,I+1,W)
| | | | |

Fast Paxos は、エンドツーエンドのメッセージ遅延を削減するために Basic Paxos を一般化します。Basic Paxos では、クライアント要求から学習までのメッセージ遅延は 3 メッセージ遅延です。Fast Paxos では 2 メッセージ遅延が許容されますが、(1) システムが最大f の障害を許容するために3f+1アクセプタで構成されること(従来の 2f+1 ではなく)、および (2) クライアントが要求を複数の宛先に送信することが必要です。

直感的に、リーダーが提案する価値がない場合、クライアントはAccept!メッセージをアクセプターに直接送信できます。アクセプターは Basic Paxos と同様に応答し、リーダーにAcceptedメッセージを送信し、すべての学習者はクライアントから学習者への 2 つのメッセージ遅延を実現します。

リーダーが衝突を検出した場合、通常どおり受け入れられる新しいラウンドのAccept!メッセージを送信して衝突を解決します。この調整された回復手法では、クライアントから学習者へのメッセージ遅延が 4 回必要になります。

最終的な最適化は、リーダーが事前に回復手法を指定し、アクセプターが衝突回復を自ら実行できるようにしたときに発生します。したがって、非調整衝突回復は 3 回のメッセージ遅延で発生する可能性があります (すべての学習者がアクセプターでもある場合は、2 回のメッセージ遅延のみ)。

クライアント リーダー 受容者 学習者
   | | | | | | | |
   | X--------->|->|->|->| | | 任意(N,I,回復)
   | | | | | | | |
   X------------------->|->|->|->| | | 承認!(N,I,W)
   | |<---------X--X--X--X------>|->| 承認済み(N,I,W)
   |<------------------------------------X--X レスポンス(W)
   | | | | | | | |

協調回復による提案の競合。注: プロトコルでは、ドロップされたクライアント要求の処理方法は指定されません。

クライアント リーダー 受容者 学習者
 | | | | | | | | |
 | | | | | | | | |
 | | | | | | | | | !! 同時に競合する提案
 | | | | | | | | | !! 異なる順序で受信されました
 | | | | | | | | | !! アクセプターによる
 | X--------------?|-?|-?|-?| | | 承認!(N,I,V)
 X-----------------?|-?|-?|-?| | | 承認!(N,I,W)
 | | | | | | | | |
 | | | | | | | | | !! アクセプタは価値について意見が一致しない
 | | |<-------X--X->|->|----->|->| 承認済み(N,I,V)
 | | |<-------|<-|<-X--X----->|->| 承認済み(N,I,W)
 | | | | | | | | |
 | | | | | | | | | !! 衝突を検出して回復
 | | X------->|->|->|->| | | 承認!(N+1,I,W)
 | | |<-------X--X--X--X----->|->| 承認済み(N+1,I,W)
 |<---------------------------------X--X レスポンス(W)
 | | | | | | | | |

矛盾する提案と調整されていない回復。

クライアント リーダー 受容者 学習者
 | | | | | | | | |
 | | X------->|->|->|->| | | 任意(N,I,回復)
 | | | | | | | | |
 | | | | | | | | | !! 同時に競合する提案
 | | | | | | | | | !! 異なる順序で受信されました
 | | | | | | | | | !! アクセプターによる
 | X--------------?|-?|-?|-?| | | 承認!(N,I,V)
 X-----------------?|-?|-?|-?| | | 承認!(N,I,W)
 | | | | | | | | |
 | | | | | | | | | !! アクセプタは価値について意見が一致しない
 | | |<-------X--X->|->|----->|->| 承認済み(N,I,V)
 | | |<-------|<-|<-X--X----->|->| 承認済み(N,I,W)
 | | | | | | | | |
 | | | | | | | | | !! 衝突を検出して回復
 | | |<-------X--X--X--X----->|->| 承認済み(N+1,I,W)
 |<---------------------------------X--X レスポンス(W)
 | | | | | | | | |

(受け入れ側/学習側の役割を統合)

クライアント サーバー
 | | | | | |
 | | X->|->|->| 任意(N,I,回復)
 | | | | | |
 | | | | | | !! 同時に競合する提案
 | | | | | | !! 異なる順序で受信されました
 | | | | | | !! サーバーによる
 | X--------?|-?|-?|-?| 承認!(N,I,V)
 X-----------?|-?|-?|-?| 承認!(N,I,W)
 | | | | | |
 | | | | | | !! サーバー間で値に相違あり
 | | X<>X->|->| 承認済み(N,I,V)
 | | |<-|<-X<>X 承認済み(N,I,W)
 | | | | | |
 | | | | | | !! 衝突を検出して回復
 | | X<>X<>X<>X 承認済み(N+1,I,W)
 |<-----------X--X--X--X レスポンス(W)
 | | | | | |

一般化コンセンサスは、複製されたステートマシンの操作とそれを実装するコンセンサスプロトコルとの関係を調査します。^[16]主な発見は、競合する提案が任意の順序で適用される場合の Paxos の最適化です。つまり、提案された操作がステートマシンの交換可能な操作である場合です。このような場合、競合する操作は両方とも受け入れられ、競合を解決して拒否された操作を再提案するために必要な遅延を回避できます。

この概念はさらに、可換操作のシーケンスがどんどん増えていくという形で一般化され、そのうちのいくつかは安定していることが分かっています (したがって実行できます)。プロトコルはこれらのシーケンスを追跡し、1 つのシーケンスのすべての提案された操作が安定していることを確認してから、それらと可換でない操作が安定できるようにします。

一般化された Paxos を説明するために、以下の例では、同時に実行される 2 つのクライアントと、2 つの異なるレジスタ A と B に対する読み取り/書き込み操作を実装する複製されたステート マシン間のメッセージ フローを示します。

ご了承くださいこの表では、非可換な演算を示します。

可能な操作のシーケンス:

<1:読み取り(A)、2:読み取り(B)、3:書き込み(B)、4:読み取り(B)、5:読み取り(A)、6:書き込み(A)>

5:Read(A)はおよび と可換3:Write(B)なので4:Read(B)、前の順序と同等の 1 つの可能な順列は次のようになります。

<1:読み取り(A)、2:読み取り(B)、5:読み取り(A)、3:書き込み(B)、4:読み取り(B)、6:書き込み(A)>

実際には、通勤は、操作が同時に提案された場合にのみ発生します。

応答は示されていません。注：メッセージの略語はプロトコルの特性により以前のメッセージフローと異なります。詳細については^{[23]を参照してください。}

クライアント リーダー 受容者 学習者
 | | | | | | | | !! 新リーダーがラウンドを開始
 | | X----->|->|->| | | 準備(N)
 | | |<-----X- X- X | | Promise(N,null)
 | | X----->|->|->| | | Phase2Start(N,null)
 | | | | | | | |
 | | | | | | | | !! 同時通勤提案
 | X------- ?|-----?|-?|-?| | | 提案(ReadA)
 X-----------?|-----?|-?|-?| | | 提案(ReadB)
 | | X------X-------------->|->| 承認されました(N,<ReadA,ReadB>)
 | | |<--------X--X-------->|->| 承認済み(N,<ReadB,ReadA>)
 | | | | | | | |
 | | | | | | | | !! 矛盾なし、どちらも受け入れ
 | | | | | | | | 安定 = <ReadA、ReadB>
 | | | | | | | |
 | | | | | | | | !! 同時に競合する提案
 X-----------?|-----?|-?|-?| | | 提案(<WriteB,ReadA>)
 | X--------?|-----?|-?|-?| | | 提案(ReadB)
 | | | | | | | |
 | | X------X-------------->|->| 受け入れられました(N、<WriteB、ReadA> . <ReadB>)
 | | |<--------X--X-------->|->| 承認されました(N,<ReadB> . <WriteB,ReadA>)
 | | | | | | | |
 | | | | | | | | !! 競合が検出されました。リーダーが選択します
 | | | | | | | | 交換順序:
 | | | | | | | | V = <読み取りA、書き込みB、読み取りB>
 | | | | | | | |
 | | X----->|->|->| | | フェーズ2開始(N+1,V)
 | | |<-----X- X- X-------->|->| 承認(N+1,V)
 | | | | | | | | 安定 = <ReadA、ReadB> 。
 | | | | | | | | <読み取りA、書き込みB、読み取りB>
 | | | | | | | |
 | | | | | | | | !! さらに矛盾する提案
 X-----------?|-----?|-?|-?| | | 提案(WriteA)
 | X--------?|-----?|-?|-?| | | 提案(ReadA)
 | | | | | | | |
 | | X------X-------------->|->| 承認されました(N+1,<WriteA> . <ReadA>)
 | | |<--------X- X-------->|->| 承認されました(N+1,<ReadA> . <WriteA>)
 | | | | | | | |
 | | | | | | | | !! リーダーが順序を選択します:
 | | | | | | | | W = <書き込みA、読み取りA>
 | | | | | | | |
 | | X----->|->|->| | | フェーズ2開始(N+2,W)
 | | |<-----X- X- X-------->|->| 承認(N+2,W)
 | | | | | | | | 安定 = <ReadA、ReadB> 。
 | | | | | | | | <ReadA、WriteB、ReadB> 。
 | | | | | | | | <書き込みA、読み取りA>
 | | | | | | | |

上記のメッセージ フローは、ネットワークの自発的な順序付けが失敗した場合に、Generalized Paxos が操作セマンティクスを活用して衝突を回避できることを示しています。これにより、プロトコルは実際には Fast Paxos よりも高速になります。ただし、衝突が発生すると、Generalized Paxos は回復するために 2 回の追加ラウンド トリップを必要とします。この状況は、上記のスキーマの WriteB および ReadB 操作で示されています。

一般的に、このようなラウンドトリップは避けられず、1ラウンド中に複数のコマンドが受け入れられるという事実から生じます。これにより、競合が頻繁に発生する場合、プロトコルはPaxosよりも高価になります。回復時間を改善するために、一般化Paxosの2つの可能な改良が可能であることが期待されます。^[24]

• まず、コーディネーターがアクセプターのすべてのクォーラムの一部である場合 (ラウンド N は中心化されていると言われる)、ラウンド N での衝突からラウンド N+1 で回復するために、コーディネーターはフェーズ 1 をスキップし、ラウンド N 中に最後に受け入れたシーケンスをフェーズ 2 で提案します。これにより、回復のコストが 1 回の往復に削減されます。
• 第二に、ラウンド N と N+1 の両方がユニークで同一の中心クォーラムを使用する場合、アクセプタはラウンド N で衝突を検出すると、ラウンド N+1 で (i) コーディネータがラウンド N で受け入れたシーケンスと (ii) ラウンド N で受け入れた最大の非競合プレフィックスの両方をサフィックスするシーケンスを自発的に提案します。たとえば、コーディネータとアクセプタがラウンド N でそれぞれ <WriteB, ReadB> と <ReadB, ReadA> を受け入れた場合、アクセプタはラウンド N+1 で <WriteB, ReadB, ReadA> を自発的に受け入れます。このバリエーションでは、回復コストは 1 つのメッセージ遅延であり、明らかに最適です。ここで、ラウンドでユニークなクォーラムを使用することで生存性が損なわれないことに注目してください。これは、このクォーラム内の任意のプロセスが次のラウンドの準備フェーズの読み取りクォーラムであるという事実に由来します。^[25]

Paxosは、嘘、メッセージの捏造、他の参加者との共謀、選択的な不参加など、参加者の恣意的な失敗をサポートするように拡張することもできます。これらのタイプの失敗は、Lamportによって普及した解決策にちなんでビザンチン失敗と呼ばれます。 ^[26]

カストロとリスコフによって導入されたビザンチンパクソス^[27]は、知識を配布し、他のプロセッサの動作を検証する追加のメッセージ（検証）を追加します。

クライアント 提案者 受諾者 学習者
   | | | | | | |
   X-------->| | | | | | リクエスト
   | X--------->|->|->| | | 承認!(N,I,V)
   | | X<>X<>X | | 検証(N,I,V) - 放送
   | |<---------X--X--X------>|->| 承認済み(N,V)
   |<---------------------------------X--X レスポンス(V)
   | | | | | | |

MartinとAlvisiによって導入されたFast Byzantine Paxos ^[28]では、クライアントがアクセプタに直接コマンドを送信するため、この余分な遅延がなくなります。

Fast Byzantine Paxos のAcceptedメッセージはすべての Acceptor とすべての Learner に送信されますが、Fast Paxos はAcceptedメッセージを Learner にのみ送信することに注意してください。

クライアント アクセプタ 学習者
   | | | | | |
   X----->|->|->| | | 承認!(N,I,V)
   | X<>X<>X------>|->| 承認済み(N,I,V) - 放送
   |<-------------------X--X レスポンス(V)
   | | | | | |

失敗のシナリオはどちらのプロトコルでも同じです。各学習者は、異なるアクセプターから F+1 個の同一メッセージを受信するのを待ちます。これが発生しない場合は、アクセプター自身もそれを認識し (ブロードキャスト ラウンドで互いのメッセージを交換しているため)、正しいアクセプターは合意した値を再ブロードキャストします。

クライアント アクセプタ 学習者
   | | | ! | | !! アクセプタの 1 つに障害があります
   X----->|->|->! | | 受け入れる!(N,I,V)
   | X<>X<>X------>|->| 承認済み(N,I,{V,W}) - 放送
   | | | ! | | !! 学習者は2つの異なるコマンドを受け取ります
   | | | ! | | !! アクセプタがエラーに気づき、選択を修正
   | X<>X<>X------>|->| 承認済み(N,I,V) - 放送
   |<-------------------X--X レスポンス(V)
   | | | ! | |

リモート DMA ( RDMA )をサポートする非常に高速で信頼性の高いデータセンター ネットワークの出現により、ネットワーク インターフェイス カードとネットワーク ルーターが信頼性とネットワーク層の輻輳制御を提供し、ホスト CPU を他のタスクに解放するハードウェア オフロードを活用するように Paxos を最適化することに大きな関心が寄せられています。Derecho C++ Paxos ライブラリは、このオプションを探求するオープン ソースの Paxos 実装です。^[12]

Derecho は、完全なシャットダウン/再起動シーケンス全体にわたってデータ耐久性を備えた従来の Paxos と、メモリ内レプリケーションおよびステートマシン同期用の垂直 Paxos (アトミック マルチキャスト) の両方を提供します。Derecho が採用している Paxos プロトコルは、非同期データ ストリーミングを最大化し、リーダーのクリティカル パス上の他の遅延源を除去するように適応する必要がありました。そうすることで、Derecho は完全な双方向 RDMA データ レートを維持できます。対照的に、従来の Paxos プロトコルは、メッセージ送信操作をネイティブ RDMA 操作にマッピングするだけで RDMA ネットワークに移行できますが、そうするとクリティカル パスにラウンドトリップ遅延が残ります。高速 RDMA ネットワークでは、小さな遅延でも、潜在的な帯域幅を最大限に活用できないほど大きくなる可能性があります。

• Googleは、障害発生時にレプリカの一貫性を保つために、 Chubby分散ロックサービスでPaxosアルゴリズムを使用しています。 ^{[29] Chubbyは、現在Google Analyticsやその他の製品で実稼働している}Bigtable で使用されています。
• Google Spannerと Megastore は内部で Paxos アルゴリズムを使用します。
• OpenReplica レプリケーション サービスは、Paxos を使用して、ユーザーがフォールト トレラント オブジェクトを作成できるオープン アクセス システムのレプリカを維持します。同時ラウンドによる高いパフォーマンスと、動的なメンバーシップ変更による柔軟性を実現します。
• IBMはIBM SANボリュームコントローラ製品でPaxosアルゴリズムを使用して、クラスタが提供するストレージ仮想化サービスの構成と制御コンポーネントを実行するために使用される汎用フォールトトレラント仮想マシンを実装していると思われます。 ^[30]
• マイクロソフトは、BingのAutopilotクラスタ管理サービスとWindows ServerフェールオーバークラスタリングでPaxosを使用しています。^[31]
• WANdiscoはDConEアクティブ-アクティブレプリケーション技術内にPaxosを実装しました。^[32]
• XtreemFSは、ファイルデータとメタデータのフォールトトレラントかつ一貫性のあるレプリケーションを実現するために、Paxosベースのリースネゴシエーションアルゴリズムを使用しています。 ^[33]
• Heroku は、一貫性のある分散データ ストアとして Paxos を実装した Doozerd を使用します。
• Ceph は、どの OSD が稼働していてクラスター内にあるかを合意するために、モニター プロセスの一部として Paxos を使用します。
• MariaDB Xpand分散SQLデータベースは、分散トランザクションの解決にPaxosを使用します。^[34]
• Neo4j HA グラフ データベースは Paxos を実装し、Apache ZooKeeper v1.9 を置き換えます。
• Apache Cassandra NoSQLデータベースは軽量トランザクション機能のためだけにPaxosを使用します。^[35]
• ScyllaDB NoSQLデータベースは軽量トランザクションにPaxosを使用しています。^[36]
• Amazon Elastic Container ServicesはPaxosを使用してクラスターの状態を一貫して維持します。^[37]
• Amazon DynamoDBはリーダー選出とコンセンサスにPaxosアルゴリズムを使用しています。^[38]

• 二人の将軍の問題
• チャンドラ・トゥエグ合意アルゴリズム
• ステートマシン
• ラフト