Paxos made simple

TL;DR:

paxosは、ノードのグループを単一の値に同意または合意に達するという問題を解決するプロトコルです。

概要:

本稿では、非同期および非ビザンチンモデルのコンピュータのコレクション間でコンセンサスに達するために使用されるフォールトトレラント

コンセンサスの問題は、一つのコンピュータであるかのように物事を決定するためにコンピュータのコレクションを取得することです。 コンセンサスと他の合意問題の主な違いは、コンセンサスプロトコルはフォールトトレラントである必要があることです。 対照的に、二相コミットのようなプロトコルでは、コーディネーターがクラッシュした場合、システム全体が進行できない可能性があります。 安定したリーダーが存在する場合、リーダーはすべての操作自体に対して総順序を確立し、他のノードがそれに従うことができるため、コンセンサスは些細なも しかし、リーダーの失敗は、システムが進歩するのを妨げるでしょう。 さらに、リーダー選挙アルゴリズムが失敗した場合(ネットワークパーティションの場合に発生する可能性が高い)、複数のリーダーが存在し、合意財産に違反する可能性があります。

この論文では、エージェントの三つのクラスを定義しています。

1。提案者(値を提案するノード)2.アクセプタ(提案された値を覚えている)3.学習者(選択された値を発見する)。

次に、コンセンサスを解くための次の失敗した試みについて説明します。

1。単一のアクセプターの代理店(リーダーとして機能して下さい)。 単一障害点のために不十分です。 2.複数のアクセプターエージェント。 -アクセプタは、彼らが受け取る最初の値を受け入れる-それは大多数のアクセプタによって受け入れられた場合、値が選択されます我々は簡単に値が大多数の受け入れによって受け入れられていないケースを構築することができますので、不十分な、終了に違反しています。 3. メッセージが順不同で配信され、契約に違反する可能性があるため、複数の値が不十分であることを受け入れます。

Paxosアルゴリズム:

準備フェーズ:

提案者に対して、新しい提案番号nを選択し、準備要求(nを含む)をアクセプタにブロードキャストします。 Acceptorの場合、nと最も高い数のaccepted proposalを比較します。 Nが大きい場合、アクセプターは、その提案者と、それが受け入れた最も高い番号の提案(および提案に関連付けられた値)に従うことを約束します。

Acceptフェーズ:

提案者が大多数のアクセプターから回答を受け取った後、提案者はすべてのアクセプターにaccept要求を送信します。 Acceptメッセージには、プロポーザル番号と値(最も高い番号のプロポーザルの値、またはすべてのアクセプタが応答しない場合は任意の値)が含まれています。 最後に、accept要求が大多数のacceptorによって受け入れられた場合。 提案が選択されます(または決定されます)。

注:1.アクセプターは、失敗して回復した場合でも、受け入れた最も高い番号の提案を覚えておく必要があります。 提案者は、同じ提案番号2の別の提案を発行しようとしない限り、その提案を忘れることができます。提案番号は、グローバルに一意で単調に増加する必要があります3.”デュエリングプロポーザー問題”。

二人の提案者が同時に提案したい場合、前の提案よりも大きい数の提案を発行することにより、お互いをブロックしようとする可能性があります。 この状況は永遠に続く可能性があり、終了に違反します。 可能な解決策には、リーダーの選挙とランダムなバックオフが含まれます。質問:

質問:

1. 第3節のリーダー選挙アルゴリズムは何ですか?

2.この論文ではいくつかの最適化を紹介していますが、これらの機能がPaxos

のパフォーマンスを向上させる理由と方法については説明していません3.As 私は論文を読みましたが、Paxosは他の最適化なしで実装するには難しすぎるかコストがかかるかもしれないと感じました

4。メッセージが破損できないという仮定は強すぎるようです

5。この論文はやや不完全なようです。 1.it 上記のデュエル提案者の問題と解決策については対処していません。 2. グローバルにユニークで単調に増加するために、提案番号を選択するにはどうすればよいですか? 3.会員管理はどうですか?

コメントを残す

メールアドレスが公開されることはありません。