You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

Paxos为何能保证共识达成后不变更?我的反例是否存在问题?

单法令Paxos共识稳定性的困惑与反例

我一直在研究单法令Paxos(主要参考《Paxos简化版》),但对接受者达成的共识是否能保证达成后不再变更感到困惑。根据James Aspnes的笔记:

假设某个值v最终被编号为n的提议由多数派T接受,那么我们可以通过对提议编号的归纳证明,所有编号更高的提议(即使更早提出)都将具有相同的值。

但我认为找到了一个反例,具体过程如下(可直接跳至步骤12查看核心状态):

符号说明

采用《Lamport的Paxos简化版论文中的矛盾》中的符号:X(n:v, m)表示接受者X已接受的最大编号提议为n:v(n为提议编号,v为值),m是接受者X已回应的编号最大的prepare请求。

反例过程

假设有3个接受者A、B、C,提议者Px等因未获知共识达成而持续发送提议:

  1. Px广播prepare(1)
  2. A和B回应承诺,状态为A(:, 1)、B(:, 1)
  3. Px收到A和B的承诺,确认多数派后广播accept(1:'foo')
  4. 仅A收到该请求,状态变为A(1:'foo', 1)、B(:, 1)、C(:,)
  5. Py广播prepare(2)
  6. B、C回应承诺,状态变为A(1:'foo', 1)、B(:, 2)、C(:,2)
  7. Py收到B和C的承诺,确认多数派后广播accept(2:'bar')
  8. 仅B收到该请求,状态变为A(1:'foo', 1)、B(2:'bar', 2)、C(:,2)
  9. Pz广播prepare(3)
  10. A和C回应承诺,状态变为A(1:'foo', 3)、B(2:'bar', 2)、C(:,3)
  11. Pz收到A和C的承诺,确认多数派,注意到1:'foo'是已接受的最大编号值,广播accept(3:'foo')
  12. 仅C收到该请求,状态变为A(1:'foo', 3)、B(2:'bar', 2)、C(3:'foo', 3)——共识达成!值为'foo'
  13. Pn未获知该共识,广播prepare(4)
  14. A和B回应承诺,状态变为A(1:'foo', 4)、B(2:'bar', 4)、C(3:'foo', 3)
  15. Pn收到A和B的承诺,确认多数派,注意到2:'bar'是已接受的最大编号值,广播accept(4:'bar')
  16. A收到该请求,状态变为A(4:'bar', 4)、B(4:'bar', 4)、C(3:'foo', 3)——共识达成!值为'bar'

补充说明

步骤4、8、12并非意味着其他节点故障,仅表示提议者的消息传递延迟,不属于2N+1个节点中超过N个崩溃的情况。

《Lamport的Paxos简化版论文中的矛盾》的高赞回答指出,提议者仅向做出承诺的接受者发送accept消息,且接受者接受值时会更新maxBal,我的反例满足这两个条件,但共识却出现了翻转,我是否遗漏了什么?


内容的提问来源于stack exchange,提问作者kyou

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.08.11 17:20:27