Skip to main content

basic paxos

· 3 min read

basic paxos​

目的: basic paxos 目的是为了让多个副本最多只有一个值.

paxos make simple​

有一篇论文，描述了basic paxos 的证明和推导过程，描述了prepare 过程的原理

p1 每个acceptor必须有接收第一个它收到的proposal

p2 当一个proposal的value 被chosen , 那么所有后续proposal 的值等于value

p2a 当一个proposal的value 被chosen , 那么后续所有acceptor接收的值等于value

p2b 当一个proposal的value被chosen , 那么后续所有proposer issue 的proposal number 对应的值等于value

p2c 对应数字n 和值v , 当acceptor 有一个最大集合S ,这个集合满足其中一个条件: 1 没有accetor 一个大于n的值 2 issue 的v 等于这个最大集合S中proposal number 最大的值

要满足p2c: 条件1 容易判断 , 条件2: 怎么保证是小于n的最大值呢?
通过prepare 语句: 在集合S的accetor不会接受比n小的issue , 这样,当前的集合中的最大的就是被accept中小于n的最大的 proposal number

每个guarantee的原因​

P1： 为了保证只有一个proposal也能chose a value P2: 为了保证多个被chosen的proposal 都有同样的值（We can allow multiple proposals to be chosen, but we must guarantee that all chosen proposals have the same value） P2a: 为了满足p2 , 我们给出当被chosen的时候，所有acceptor都具有被chosen的value P2b:为了满足p2a,我们给出，当被chosen的时候，所有issue的值都有被chseon的value P2c:

  • 大前提
assume that some proposal with number m and value
v is chosen and show that any proposal issued with number n > m also
has value v
  • 小前提
assumption that every proposal issued with a number in m . . (n − 1) has
value v , where i . . j denotes the set of numbers from i through j

相关阅读: