PAXOS 小记

随便敲的，看看就好（被书折腾后凭感觉写的，可能小误

PAXOS 针对 2PC 的保守策略改为少数服从多数的更为合理的策略

每个 Acceptor 可批准多个提案

每个 Proposer 有唯一的身份标记 $M_{i}$ ，以及对应的提案内容 $V_{i}$ ，用 $< M, V >$ 表示一个提案

注意提案者 $M$ 其实是会暗中附和其它人的提案内容，因此 $V$ 并不唯一，所谓的选定提案更为关注的是内容 $V$

提案超过半数即大于等于 $⌊ \frac{n}{2} ⌋ + 1$ 的 Acceptor 批准时，该提案被选定，内容由 Learner 发布

规定：

P1.Accpetor 必然批准接收到的第一个 $< M_{i}, V_{i} >$

P2.当 Accpetor 批准 $< M_{i}, V_{i} >$ 后，不会再接受 $M_{j} < M_{i}$ 的任意请求，批准的 $M_{j} > M_{i}$ 对应的 $V_{j} = V_{i}$ （解决未提交即完成选定，实际是下放到生成的时刻）

推论：

当 $< M_{i}, V_{i} >$ 被选定时，必存在一个大小大于等于 $⌊ \frac{n}{2} ⌋ + 1$ 的 Accpetor 多数集全部批准该提案

当 $< M_{i}, M_{i + 1} . . . M_{j}, V_{i} >$ 被选定时，必存在一个大小大于等于 $⌊ \frac{n}{2} ⌋ + 1$ 的 Accpetor 多数集全部批准 $M_{i}$ 到 $M_{j}$ 的任一提案

当 $< M_{i}, V_{i} >$ 产生时，多数集必满足任意其一 1.集合未曾批准过 $M_{j} < M_{i}$ 的任意提案 2.存在一个选定的 $M_{j} < M_{i}$ 的提案， $V_{j} = V_{i}$ （由超过半数得选定必有交集，并且若已存在编号小的选定，那肯定是符合 2）

当存在 $M_{j} < M_{i}$ 的提案，那 $V_{i}$ 的值一定是最大的批准的 $M_{i}$ 所对应的 $V_{i}$

因此当 $< M_{i}, M_{i + 1} . . . M_{j}, V_{i} >$ 被选定时， $M_{j + 1}$ 的 $V_{j + 1} = V_{i}$

目的：

1.尽快达成一致

2.少数服从多数

算法步骤：暂略