paxos算法

3

信息代号：3

1

出兵日期：（1，1）

OK

2

犀首

（1，1）

提议阶段

投票提议者

信息代号：1

NOK（1，1）

OK（1，1）

信息代号：2

韩王

OK（3，2）

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

准备阶段

楚王

投票决策者

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

（2，2）

OK（2，2）

魏王

出兵日期：（2，2）

黄歇