Basic Paxos 算法流程

在 Basic Paxos 中，达成一次共识需要两个阶段。我们假设 Proposer 想要提议一个值 $V_{my}$。关于这些步骤背后的设计逻辑，可以参考 Paxos 设计哲学。

核心状态定义

• $N$ (Proposal Number)：提议编号。必须全局唯一且递增。
• $N_{max}$ (Max Seen Number)：Acceptor 记录的已承诺的最大编号。
• $[N_{acc},V_{acc}]$ (Accepted Proposal)：Acceptor 记录的已接受的提案（包括编号和值）。

---

第一阶段：Prepare (准备与锁定)

目标：Proposer 尝试“锁定”多数派 Acceptor，并查询是否已有“前人”留下的值。

1. Proposer - 发起请求 (Prepare)：

   • 生成一个新编号 $N$。
   • 向所有 Acceptor 广播 Prepare(N)。关于为什么只需多数派响应，请参考 Paxos 为什么只需与“多数派”通信？。

2. Acceptor - 做出承诺 (Promise)：

   • 条件检查：如果收到的 $N>N_{max}$：
     • 更新状态：将 $N_{max}$ 设置为 $N$。
     • 回复 Promise：返回一个回复包，包含：
       • 承诺 (Commitment)：保证以后不再接受任何编号小于 $N$ 的请求。
       • 历史反馈 (Feedback)：如果自己之前已经接受过提案，则返回该提案 $[N_{acc},V_{acc}]$；否则返回空。
   • 否则：拒绝请求（或不予理会）。

图解：Prepare 阶段的“锁定”与“反馈”

sequenceDiagram
    participant P as Proposer (N=10)
    participant A1 as Acceptor 1
    participant A2 as Acceptor 2
    participant A3 as Acceptor 3

    P->>A1: 1. Prepare(N=10)
    P->>A2: 1. Prepare(N=10)
    P->>A3: 1. Prepare(N=10)

    A1-->>P: 2. Promise(N=10, 无旧值)
    A2-->>P: 2. Promise(N=10, 已接受过 [N=5, V="Apple"])
    A3-->>P: 2. Promise(N=10, 已接受过 [N=8, V="Orange"])

    Note over A1, A3: 承诺：不再接受编号 < 10 的提议

---

第二阶段：Accept (提议与投票)

目标：Proposer 根据第一阶段收集的信息，发起真正的投票，尝试让值成为决议。

1. Proposer - 确定内容并提议 (Propose)：

   • 条件检查：如果收到的 Promise 响应超过半数（Majority）：
     • 确定 Value：
       • 如果在所有收到的回复中，有 Acceptor 返回了旧提案 $[N_{acc},V_{acc}]$：
         • Proposer 必须放弃 $V_{my}$，选择其中 $N_{acc}$ 最大的那个 $V_{acc}$ 作为本次提议的值。详细原因参考 为什么必须认领“编号最大”的旧值？。
       • 如果所有回复都为空：
         • Proposer 可以使用自己原本想提议的值 $V_{my}$。
     • 发起 Accept：向所有 Acceptor 发送 Accept(N, Value) 请求。

2. Acceptor - 接受提案 (Accept)：

   • 条件检查：如果收到的 $N\ge N_{max}$：
     • 持久化：更新状态 $[N_{acc},V_{acc}]=[N,Value]$。
     • 回复 Accepted：告知 Proposer 已接受该提案。
   • 否则：拒绝请求（因为已经承诺给了更高编号的提议者）。

图解：Accept 阶段的“认领”与“投票”

sequenceDiagram
    participant P as Proposer (N=10)
    participant A1 as Acceptor 1
    participant A2 as Acceptor 2
    participant A3 as Acceptor 3

    Note over P: 决策：收到的旧值中 N=8 最大 (来自 A3)
    Note over P: 放弃自己的 "Banana"，必须使用 "Orange"

    P->>A1: 3. Accept(N=10, V="Orange")
    P->>A2: 3. Accept(N=10, V="Orange")
    P->>A3: 3. Accept(N=10, V="Orange")

    A1-->>P: 4. Accepted(N=10, V="Orange")
    A2-->>P: 4. Accepted(N=10, V="Orange")
    A3-->>P: 4. Accepted(N=10, V="Orange")

    Note over A1, A3: 多数派达成，"Orange" 成为决议

• 逻辑核心：Proposer 必须尊重“前人”留下的足迹，通过“认领”机制确保共识的一致性。更多场景演示请参考 Paxos 运行情况详尽枚举。
• 结果：一旦多数派 Acceptor 接受了同一个值，该值就正式成为决议，不可更改。

---

关键动作定义表

动作 (中文)	动作 (英文)	执行者	核心含义
准备	Prepare	Proposer	询问 Acceptor 能否锁定，并查询历史。
承诺	Promise	Acceptor	保证不再理会小编号，并交待已接受的旧值。
提议请求	Accept Request	Proposer	带着确定的值请求投票。
接受	Accepted	Acceptor	节点正式投票支持该值，并将其记录在案。
达成共识	Chosen	全局状态	当多数派 Acceptor 都执行了 Accepted 动作，值即成为决议。