paxos算法简单入门

我们以历史资料为例简单介绍下paxos算法：战国中期，秦国商鞅变法后迅速崛起对外扩张，在函谷关外拉开大军，准备全面入侵山东国家，山东诸国惶惶不可终日，此时公孙衍犀首游说列国，并先后出任魏国韩国赵国等多个国相，提议欲抵抗秦国必须结成同盟，合纵方可破秦。最终有三个国家魏国，楚国，韩国集兵于函谷关外，各占一个山头准备攻打秦国。但是任意一个国家和秦国对抗必败，必须在三个国家中至少有两个国家达成一致，同时进攻。每个国家有主帅(魏王，楚王，韩王)和参谋(魏相犀首，春申君黄歇，韩太子)，参谋给出的进攻时间必须得到魏楚韩中任意两个国家的同意，才可决议，但是派出信使有可能被秦国密探捕获，而导致信息丢失。所以达成一致的进攻时间是个难题，就有了下面的paxos算法决议，虽然根据此算法，三国进攻时间最终达成了一致，但是还是被秦张仪以连横之策大败盟军于函谷之外，这都是后话，不在我们算法涉及范围之内。

两个原则：
1：参谋提出提议，分两阶段，第一准备阶段，第二提交提议阶段。
2：决策者始终保存最大编号的信息，编号较小的会拒绝

20170921102047455.png

1. 参谋犀首派出信使给魏楚韩（序号为1），魏王楚王收到信息，由于信使被捕，韩王未收到信息。
2. 魏王楚王收到信息后，派信使告诉参谋犀首已经收到信息，等待具体指示。
3. 同时参谋黄歇也派出信使送信给魏楚韩（序号为2），魏王未收到，楚怀王，韩王收到信息.
4. 楚王韩王收到信息后派信使告诉参谋黄歇，信息已收到，等待具体指示。
5. 参谋犀首收到信息后，派信使告诉魏楚王，具体进攻时间为下月1号。
6. 魏王收到后，觉得可以，派信使告诉参谋犀首，1号进攻方案认可。
7. 楚王收到后，因为他保存的最新等待指示的信号是2，所以告诉犀首，1号进攻方案不认可，正在等待最新指示为2的信息。
8. 参谋黄歇派出信使告诉楚王韩王，进攻时间为下月2号。
9. 楚王收到后和自己保存的信号对比，发现一致，则告诉参谋黄歇，2号方案认可。同时韩王也表示认可。
10. 参谋犀首得到的方案不是一半以上（魏王认可，楚王不认可，韩王未知），所以重新发起一次投票。
11. 因为第7步，已经被告知，最新指示的代号已经是2了，1已经是过去时了。所以派出信使，说最新指示代号升级为3了。
12. 魏王收到信息后，告诉参谋犀首，我上次已经同意了你的进攻时间，是否更改，等待最新指示。
13. 楚王收到信息后，告诉参谋犀首，最新指示代号3已收到，我目前同意的进攻时间是2号，等待你的最新指示。
14. 参谋犀首收到回信后，下发具体作战时间。因为11步已经被告知，最新时间已经更改为2号了。所以犀首这次派出信使携带信息为“最新代号3，作战时间2号”。
15. 魏王收到后，按最新指示执行，和自己保存的指示代号对比，发现一致，回复犀首，同意
16. 楚王收到后，和自己保存的代号做对比，发现也一致，回复犀首，同意2号进攻

17. 这样一次决策就达成一致了，半数以上同意2号进攻。