知识卡片

多数派交集保安全

普通读书笔记卡 · 1725.a

内容

Paxos 要求 proposer 从多数 acceptor 获取 prepare 响应,再向多数发送 accept;任意两个多数派必然相交,使后来的提议能继承已接受的最高编号值。发散:安全性藏在集合交叉里,而不是藏在某台永远正确的机器里。

参考来源

- 位置:《分布式系统与一致性》第10章《共识算法Paxos》算法阶段描述及"例子3"(源文件:_epub-src/OEBPS/Text/chapter14.xhtml) - 结论依据:原文英文原始条文"A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors"及"the proposer receives a response...from a majority of acceptors, then it sends an accept request..."定义了两轮均需多数;随后"例子3"具体演示了proposer2的多数派{acceptor3,4,5}与proposer1的多数派{acceptor1,2,3}在acceptor3处重合,导致acceptor3回复已接受的{1.1,X},proposer2因此放弃自己原本要提议的值Y改为提议X,正是多数派交集使新提议继承旧值的机制体现。 - 原始内容:A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors...If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors,then it sends an accept request...for a proposal numbered n with a value v,where v is the value of the highest-numbered proposal among the responses...acceptor3已经接受了提议{1.1,X},因此会回复PM(1.5,{1.1,X})……proposer2……会构建一个新的提议,提议编号为1.5,但是值不会使用Y……而是会选择{1.1,X}这个收到的提议中的值X。