我们以历史资料为例简单介绍下paxos算法:战国中期,秦国商鞅变法后迅速崛起对外扩张,在函谷关外拉开大军,准备全面入侵山东国家,山东诸国惶惶不可终日,此时公孙衍犀首游说列国,并先后出任魏国韩国赵国等多个国相,提议欲抵抗秦国必须结成同盟,合纵方可破秦。最终有三个国家魏国,楚国,韩国集兵于函谷关外,各占一个山头准备攻打秦国。但是任意一个国家和秦国对抗必败,必须在三个国家中至少有两个国家达成一致,同时进攻。每个国家有主帅(魏王,楚王,韩王)和参谋(魏相犀首,春申君黄歇,韩太子),参谋给出的进攻时间必须得到魏楚韩中任意两个国家的同意,才可决议,但是派出信使有可能被秦国密探捕获,而导致信息丢失。所以达成一致的进攻时间是个难题,就有了下面的paxos算法决议,虽然根据此算法,三国进攻时间最终达成了一致,但是还是被秦张仪以连横之策大败盟军于函谷之外,这都是后话,不在我们算法涉及范围之内。
两个原则:
1:参谋提出提议,分两阶段,第一准备阶段,第二提交提议阶段。
2:决策者始终保存最大编号的信息,编号较小的会拒绝
20170921102047455.png
- 参谋犀首派出信使给魏楚韩(序号为1),魏王楚王收到信息,由于信使被捕,韩王未收到信息。
- 魏王楚王收到信息后,派信使告诉参谋犀首已经收到信息,等待具体指示。
- 同时参谋黄歇也派出信使送信给魏楚韩(序号为2),魏王未收到,楚怀王,韩王收到信息.
- 楚王韩王收到信息后派信使告诉参谋黄歇,信息已收到,等待具体指示。
- 参谋犀首收到信息后,派信使告诉魏楚王,具体进攻时间为下月1号。
- 魏王收到后,觉得可以,派信使告诉参谋犀首,1号进攻方案认可。
- 楚王收到后,因为他保存的最新等待指示的信号是2,所以告诉犀首,1号进攻方案不认可,正在等待最新指示为2的信息。
- 参谋黄歇派出信使告诉楚王韩王,进攻时间为下月2号。
- 楚王收到后和自己保存的信号对比,发现一致,则告诉参谋黄歇,2号方案认可。同时韩王也表示认可。
- 参谋犀首得到的方案不是一半以上(魏王认可,楚王不认可,韩王未知),所以重新发起一次投票。
- 因为第7步,已经被告知,最新指示的代号已经是2了,1已经是过去时了。所以派出信使,说最新指示代号升级为3了。
- 魏王收到信息后,告诉参谋犀首,我上次已经同意了你的进攻时间,是否更改,等待最新指示。
- 楚王收到信息后,告诉参谋犀首,最新指示代号3已收到,我目前同意的进攻时间是2号,等待你的最新指示。
- 参谋犀首收到回信后,下发具体作战时间。因为11步已经被告知,最新时间已经更改为2号了。所以犀首这次派出信使携带信息为“最新代号3,作战时间2号”。
- 魏王收到后,按最新指示执行,和自己保存的指示代号对比,发现一致,回复犀首,同意
- 楚王收到后,和自己保存的代号做对比,发现也一致,回复犀首,同意2号进攻
- 这样一次决策就达成一致了,半数以上同意2号进攻。