Paxos 运行情况详尽枚举

为了彻底理解 Basic Paxos 的运行逻辑，我们需要枚举 Proposer 在不同竞争阶段下的各种情况。

核心背景

• 集群节点：A, B, C, D, E（多数派为 3）。
• 目标：对“一个”值（Instance）达成共识。

---

情况一：完美的首次提议（无竞争）

这是最简单的情况，系统处于初始状态。

1. Prepare：Proposer 1 (N=10) 向 A, B, C 发送请求。
2. Promise：A, B, C 均返回 Promise(N=10, 空)，因为它们从未接受过任何值。
3. Accept：Proposer 1 发现反馈为空，于是发起 Accept(N=10, V="Apple")。
4. Accepted：A, B, C 接受并记录 [N_acc=10, V_acc="Apple"]。
5. 结果：“Apple” 达成共识。

---

情况二：发现“前人”的足迹（认领旧值）

前一个提议者做到一半挂了，后一个提议者必须接力。

1. 背景：Proposer 1 让 A, B 接受了 [N=5, V="Orange"]，但还没发给 C 就宕机了（共识未达成）。
2. Prepare：Proposer 2 (N=20) 启动，向 B, C, D 发送请求。
3. Promise：
   • B 返回 Promise(N=20, [N=5, V="Orange"])。
   • C, D 返回 Promise(N=20, 空)。
4. Accept：Proposer 2 发现 B 有旧值。虽然它自己想提议 “Banana”，但必须认领旧值，发起 Accept(N=20, V="Orange")。
5. 结果：“Orange” 最终达成共识。（Proposer 2 帮 Proposer 1 完成了遗愿）。

---

情况三：多值竞争（认领编号最大者）

多个提议者都在跑，系统必须收敛到其中一个。

1. 背景：
   • A 接受了 [N=5, V="Apple"]。
   • B 接受了 [N=10, V="Orange"]。
2. Prepare：Proposer 3 (N=30) 向 A, B, C 发送请求。
3. Promise：
   • A 返回 Promise(N=30, [N=5, V="Apple"])。
   • B 返回 Promise(N=30, [N=10, V="Orange"])。
   • C 返回 Promise(N=30, 空)。
4. Accept：Proposer 3 发现两个旧值，必须选编号最大的（N=10），发起 Accept(N=30, V="Orange")。
5. 结果：“Orange” 达成共识。

---

情况四：共识已达成（不可篡改性）

共识一旦达成，后来的强者也无法更改。

1. 背景：A, B, C 已经达成了 [N=10, V="Apple"] 的共识。
2. Prepare：Proposer 4 (N=100) 带着巨大的编号进来，想提议 V="Gold"。
3. Promise：A, B, C 都会反馈 [N=10, V="Apple"]。
4. Accept：Proposer 4 必须放弃 “Gold”，发起 Accept(N=100, V="Apple")。
5. 结果：共识依然是 “Apple”。Proposer 4 变成了 “Apple” 的复读机。

---

情况五：活锁（Livelock）

两个 Proposer 互相“插队”，导致系统一直无法进入第二阶段。

1. P1 发起 Prepare(N=1)，获得多数派 Promise。
2. P2 紧接着发起 Prepare(N=2)，导致 Acceptor 承诺不再理会 N=1。
3. P1 尝试发起 Accept(N=1)，被拒绝。
4. P1 气不过，发起 Prepare(N=3)，导致 Acceptor 承诺不再理会 N=2。
5. P2 尝试发起 Accept(N=2)，被拒绝…
6. 结果：系统一直在第一阶段打转。
   • 注：工程上通过“随机等待”或“选出主提议者（Multi-Paxos）”来解决。

---

总结表：Proposer 的行为准则

场景	发现旧值情况	Proposer 的最终提议值 (Value)
白纸一张	所有回复均为空	使用自己想提议的值
前有古人	回复中存在旧值	必须使用旧值中编号最大(N_acc 最大)的那个 Value。详细原因参考 为什么必须认领“编号最大”的旧值？
木已成舟	多数派已达成共识	被动成为共识值的“搬运工”，无法更改结果