Leslie Lamportによって作成されたPaxosアルゴリズムは、信頼できない通信およびノードの障害に直面しても、分散ノードのグループが合意に達することができるように設計された分散コンセンサスアルゴリズムです。断層耐性システムの構築に特に役立ちます。

#####仮定：

1. **非同期通信**：ノード間のメッセージには固定配信時間があると想定されていませんが、最終的には配信されます。
2. **非ビザンチン障害**：Paxosは、ノードがクラッシュして応答を停止できるが、任意の動作または悪意のある動作を示さないと仮定します。
3. **有限数のノード**：アルゴリズムは、コンセンサスプロセスに参加する固定数のノードを想定しています。

#####安全性と活性の特性：

1. **安全**：Paxosアルゴリズムは、最大で1つの値がコンセンサス決定のために選択されることを保証します。値が選択されている場合、異なる値を選択しようとするその後の試みは失敗します。
2. ** livension **：アルゴリズムは、故障していないノードの大部分が値を提案した場合、最終的にはこれらの値の1つが選択されることを保証します。ただし、Paxosは特定のネットワークまたはノードの障害に直面しても強力なlivension保証を提供しないことに注意することが重要です。

##### Paxosアルゴリズムは、提案者、アクセプター、学習者の3つの主な役割で構成されています。アルゴリズムの高レベルの説明は次のとおりです。

1. **提案者**コンセンサスプロセスを開始し、一意の識別子（数）とアクセプターに提案された価値を含む提案を送信します。
2. ** Acceptors **提案を受け取り、2フェーズプロセスに従ってください：準備フェーズと受け入れフェーズ。

    - 準備フェーズの準備：アクセプターは、一意の識別子を含む提案を受け取ります。識別子が以前の識別子よりも高い場合、識別子が低い場合に将来の提案を受け入れないことを約束し、受け入れた最高の提案を含む提案者にメッセージを送り返します（もしあれば）。

    - 受け入れ段階：提案に対して（異なるアクセプターから）回答の過半数を受け取ると、提案者は、受信した回答（または受け取っていない場合）から最高の識別子に関連付けられた値を選択し、受け入れリクエストを送信します。選択された値と提案識別子を備えたアクセプター。アクセプターは受け入れリクエストを受け取り、より高い数の提案を約束していない場合、リクエストを受け入れ、学習者に決定を伝えます。

3. **学習者**コンセンサスのために選択された価値を学ぶためのアクセプターの決定を監視します。学習者が、アクセプターの大部分が提案を受け入れたことを検出すると、価値が選択されたと安全に想定できます。

Paxosには、さまざまなシナリオでの効率とスケーラビリティを改善するために設計されたマルチパクソや高速Paxosなど、いくつかのバリエーションと最適化があります。
The Paxos algorithm, created by Leslie Lamport, is a distributed consensus algorithm designed to ensure that a group of distributed nodes can reach an agreement, even in the face of unreliable communication and node failures. It is particularly useful for building fault-tolerant systems.

##### Assumptions:

1. **Asynchronous communication**: Messages between nodes are not assumed to have a fixed delivery time, but they eventually get delivered.
2. **Non-Byzantine faults**: Paxos assumes that nodes can crash and stop responding but do not exhibit arbitrary or malicious behavior.
3. **Finite number of nodes**: The algorithm assumes a fixed number of nodes participating in the consensus process.

##### Safety and Liveness properties:

1. **Safety**: The Paxos algorithm guarantees that at most one value will be chosen for a consensus decision. If a value has been chosen, any subsequent attempts to choose a different value will be unsuccessful.
2. **Liveness**: The algorithm ensures that if a majority of non-faulty nodes propose a value, eventually, one of these values will be chosen. However, it's important to note that Paxos does not provide strong liveness guarantees in the face of certain network or node failures.

##### The Paxos algorithm consists of three main roles: proposers, acceptors, and learners. The high-level description of the algorithm is as follows:

1. **Proposers** initiate the consensus process by sending a proposal with a unique identifier (number) and a proposed value to the acceptors.
2. **Acceptors** receive proposals and follow a two-phase process: the Prepare phase and the Accept phase.

   - Prepare phase: An acceptor receives a proposal with a unique identifier. If the identifier is higher than any previous identifier it has seen, it promises not to accept any future proposals with lower identifiers and sends a message back to the proposer containing the highest proposal it has accepted (if any).

   - Accept phase: Upon receiving a majority of responses (from different acceptors) for its proposal, the proposer selects the value associated with the highest identifier from the received responses (or its own value, if none were received) and sends an accept request to the acceptors with the chosen value and the proposal identifier. An acceptor receives the accept request and, if it has not promised to any higher-numbered proposal, it accepts the request and communicates the decision to the learners.

3. **Learners** monitor the acceptors' decisions to learn the chosen value for consensus. Once a learner detects that a majority of acceptors have accepted a proposal, it can safely assume that the value has been chosen.

Paxos has several variations and optimizations, such as Multi-Paxos and Fast Paxos, designed to improve its efficiency and scalability in different scenarios.