1. Basic Paxos
1.1 经典Basic Paxos
映照到现实世界中的问题就是要保证消息可靠，需要将消息交代给多个人，
image.png
image.png
理论证明这里不再赘述
只有弄懂这套机制的正确性边界，才能在工程中灵活使用
1.2 Acceptor的承诺
- accepor可以多次接受提案，acceptor响应prepare的请求要如实上报accept_proposal和accept_value并更新min_proposal
- 如果acceptor作弊未更新min_proposal，可能出现两个proposer prepare成功并且accept成功，这样后面的accept把前面的chosen覆盖掉了
- 如果acceptor作弊未返回accept_proposal和accept_value那么可能造成已经chosen的value被重新修改
从这里可以看出Acceptor肯定不能作弊
1.3 Proposer的承诺
- Proposer Prepare阶段发现的值一定要处理，决不能视而不见
- Proposer Prepare阶段未形成majority决不能发Accept
- Proposer Prepare majority成功，未发现任何accept_value说明此时一定还未形成chosen的value
- Proposer Prepare majority成功，并发现一致的accept_value(accept_proposal相同)说明此时一定形成了chosen的value
- Proposer Prepare majority成功，发现还未一致的accept_value，此时accept未决，需要继续看其他节点
- Proposer Prepare 全部节点成功，发现majority一致的accept_value，说明此时形成了chosen的value
- Proposer Prepare 全部节点成功，未发现majority一致的accept_value，说明此时一定未形成chosen的value，可以继续提议新值，或者执行rollback
- Proposer Prepare的epoch值必须要递增唯一否则会出现严重错误
1.4 核心
要正确实现Paxos协议就要严格遵守这些正确性边界
1.5 Flexible Basic Paxos
Prepare阶段和Accept阶段要求有交集即可，不一定非要两个都是多数派，比如4副本情况
可以设置 Prepare的quorum为3 Accept的Quorum为2
也可以设置Prepare的quorum为2 Accept的Quorum为3
2 工程
2.1 multi-paxos
Multi-paxos大部分应用场景就是数据流，既然是数据流传输，其实相关优化都可以在tcp滑动窗口上找到相应点，滑动窗口中存储的就是value：
image.png
https://www.zhihu.com/question/57321934
multi-paxos组和instance的区别？性能？并行提交+并行apply
2.2 作用域
Paxos可以作用于单个对象/chunk 甚至更整个系统
2.3 asymmetric Paxos
- support seal semantics
- support rollback semantics
rollback的安全行为问题的核心在于prepare阶段是否已经能够阻挡住之前的accept形成quorum
2.4 Raft安全性
leader上任要先写一条noop的entry，但是可能部分成功
image.png
image.png
对于非对称结构(不是等价的数据副本)S1在(c)场景下不能轻易通过复制index 2的日志(比如EC模式下)
此时S1需要联系更多的节点来确认这条日志可以安全rollback
