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等因未获知共识达成而持续发送提议:
Px广播prepare(1)A和B回应承诺,状态为A(:, 1)、B(:, 1)Px收到A和B的承诺,确认多数派后广播accept(1:'foo')- 仅
A收到该请求,状态变为A(1:'foo', 1)、B(:, 1)、C(:,) Py广播prepare(2)B、C回应承诺,状态变为A(1:'foo', 1)、B(:, 2)、C(:,2)Py收到B和C的承诺,确认多数派后广播accept(2:'bar')- 仅
B收到该请求,状态变为A(1:'foo', 1)、B(2:'bar', 2)、C(:,2) Pz广播prepare(3)A和C回应承诺,状态变为A(1:'foo', 3)、B(2:'bar', 2)、C(:,3)Pz收到A和C的承诺,确认多数派,注意到1:'foo'是已接受的最大编号值,广播accept(3:'foo')- 仅
C收到该请求,状态变为A(1:'foo', 3)、B(2:'bar', 2)、C(3:'foo', 3)——共识达成!值为'foo' Pn未获知该共识,广播prepare(4)A和B回应承诺,状态变为A(1:'foo', 4)、B(2:'bar', 4)、C(3:'foo', 3)Pn收到A和B的承诺,确认多数派,注意到2:'bar'是已接受的最大编号值,广播accept(4:'bar')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
相关产品推荐
相关产品推荐

