背景
在计算机通信实践中，有一个驰名的两军问题，讲述通信的单方通过ACK来达成共识，永远会有一个在途的ACK须要进行确认，因而无奈达成共识。
两军问题和BasicPaxos十分类似
1） 通信的各方须要达成共识；
2） 通信的各方仅须要达成一个共识；
3） 假如信道不稳固，有丢包、提早或者重放，但音讯不会被篡改。
BasicPaxos最早以希腊议会的背景来解说，但普通人不了解希腊议会的运作模式，因而看BasicPaxos的论文会比拟难了解。两军问题的背景大家更相熟，因而尝试用这个背景来演绎一下BasicPaxos。
为了配合BasicPaxos的多数派概念，把两军改为3军；同时假如了将军、顾问和通信兵的角色。
假如的3军问题
1） 1支红军在山谷里扎营，在四周的山坡上驻扎着3支蓝军；
2） 红军比任意1支蓝军都要弱小；如果1支蓝军独自作战，红军胜；如果2支或以上蓝军同时防御，蓝军胜；
3） 三支蓝军须要同步他们的防御工夫；但他们惟一的通信媒介是派通信兵步行进入山谷，在那里他们可能被俘虏，从而将信息失落；或者为了防止被俘虏，可能在山谷停留很长时间；
4） 每支军队有1个顾问负责提议防御工夫；每支军队也有1个将军批准顾问提出的防御工夫；很显著，1个顾问提出的防御工夫须要取得至多2个将军的批准才有意义；
5） 问题：是否存在一个协定，可能使得蓝军同步他们的防御工夫？
接下来以两个假如的场景来演绎BasicPaxos；顾问和将军须要遵循一些根本的规定
1） 顾问以两阶段提交（prepare/commit）的形式来发动提议，在prepare阶段须要给出一个编号；
2） 在prepare阶段产生抵触，将军以编号大小来裁决，编号大的顾问胜出；
3） 顾问在prepare阶段如果收到了将军返回的已承受防御工夫，在commit阶段必须应用这个返回的防御工夫；
两个顾问先后提议的场景
1） 顾问1发动提议，派通信兵带信给3个将军，内容为（编号1）；
2） 3个将军收到顾问1的提议，因为之前还没有保留任何编号，因而把（编号1）保留下来，防止忘记；同时让通信兵带信回去，内容为（ok）；
3） 顾问1收到至多2个将军的回复，再次派通信兵带信给3个将军，内容为（编号1，防御工夫1）；
4） 3个将军收到顾问1的工夫，把（编号1，防御工夫1）保留下来，防止忘记；同时让通信兵带信回去，内容为（Accepted）；
5） 顾问1收到至多2个将军的（Accepted）内容，确认防御工夫曾经被大家接管；
6） 顾问2发动提议，派通信兵带信给3个将军，内容为（编号2）；
7） 3个将军收到顾问2的提议，因为（编号2）比（编号1）大，因而把（编号2）保留下来，防止忘记；又因为之前曾经承受顾问1的提议，因而让通信兵带信回去，内容为（编号1，防御工夫1）；
8） 顾问2收到将军的回复，因为回复中带来了已承受的顾问1的提议内容，顾问2因而不再提出新的防御工夫，承受顾问1提出的工夫；顾问2再次派通信兵带信给3个将军，内容为（编号2，防御工夫1）；
9） 3个将军收到顾问2的工夫，把（编号2，防御工夫1）保留下来，防止忘记；同时让通信兵带信回去，内容为（Accepted）；
10） 顾问2收到至多2个将军的（Accepted）内容，确认防御工夫曾经被大家接管；
两个顾问穿插提议的场景
1） 顾问1发动提议，派通信兵带信给3个将军，内容为（编号1）；
2） 3个将军的状况如下
- 将军1和将军2收到顾问1的提议，因为还没有其余顾问提议，因而将军1和将军2把（编号1）记录下来；同时让通信兵带信回去，内容为（ok）；
- 负责告诉将军3的通信兵被抓，因而将军3没收到顾问1的提议；
3） 顾问2在同一时间也发动了提议，派通信兵带信给3个将军，内容为（编号2）；
4） 3个将军的状况如下
- 将军2和将军3收到顾问2的提议，将军2和将军3把（编号2）记录下来；将军2记录编号2，是因为编号2比之前记录的编号1大；将军3记录编号2，是因为之前没有顾问向他提议；这两个将军同时让通信兵带信回去，内容为（ok）；
- 负责告诉将军1的通信兵被抓，因而将军1没有收到顾问2的提议；
5） 顾问1收到至多2个将军的回复，再次派通信兵带信给有回答的2个将军，内容为（编号1，防御工夫1）；
6） 2个将军的状况如下
- 将军1收到了（编号1，防御工夫1），和本人保留的编号雷同，因而把（编号1，防御工夫1）保留下来；同时让通信兵带信回去，内容为（Accepted）；
- 将军2收到了（编号1，防御工夫1），因为（编号1）小于曾经保留的（编号2），因而让通信兵带信回去，内容为（Rejected，编号2）；
7） 顾问2收到至多2个将军的回复，再次派通信兵带信给有回答的2个将军，内容为（编号2，防御工夫2）；
8） 将军2和将军3收到了（编号2，防御工夫2），和本人保留的编号雷同，因而把（编号2，防御工夫2）保留下来，同时让通信兵带信回去，内容为（Accepted）；
9） 顾问2收到至多2个将军的（Accepted）内容，确认防御工夫曾经被多数派承受；
10） 顾问1只收到了1个将军的（Accepted）内容，同时收到一个（Rejected，编号2）；顾问1从新发动提议，派通信兵带信给3个将军，内容为（编号3）；
11） 3个将军的状况如下
- 将军1收到顾问1的提议，因为（编号3）大于之前保留的（编号1），因而把（编号3）保留下来；因为将军1曾经承受顾问1前一次的提议，因而让通信兵带信回去，内容为（编号1，防御工夫1）；
- 将军2收到顾问1的提议，因为（编号3）大于之前保留的（编号2），因而把（编号3）保留下来；因为将军2曾经承受顾问2的提议，因而让通信兵带信回去，内容为（编号2，防御工夫2）；
- 负责告诉将军3的通信兵被抓，因而将军3没收到顾问1的提议；
12） 顾问1收到了至多2个将军的回复，比拟两个回复的编号大小，抉择大编号对应的防御工夫作为最新的提议；顾问1再次派通信兵带信给有回答的2个将军，内容为（编号3，防御工夫2）；
13） 将军1和将军2收到了（编号3，防御工夫2），和本人保留的编号雷同，因而保留（编号3，防御工夫2），同时让通信兵带信回去，内容为（Accepted）；
14） 顾问1收到了至多2个将军的（accepted）内容，确认防御工夫曾经被多数派承受；
小结
BasicPaxos算法难了解，除了讲故事的背景不相熟之外，还有以下几点
1） 参加的各方并不是要唇枪舌剑，拼个鱼死网破；而是要单干共赢，最终达成一个共识；当大家讲起投票的时候，往往第一反馈是要唇枪舌剑，没想到是要单干共赢；很显著能够想到，在第二个场景下，如果顾问1为了逞英雄，强行要提交他提出的防御工夫1，那么最终是无奈达成一个共识的；这里的点就在于顾问1违反了规定，相当于产生了拜占庭谬误；
2） 惯例的通信协议设计，对于写操作，通常都是只返回胜利和失败的状态，不会返回更多的货色；但BasicPaxos的prepare和commit，将军除了返回胜利还是失败的状态之外，还会把之前曾经产生的一些状态带回给顾问，这个和惯例的通信协议是不同的；
3） 在两军问题的背景下，其实晓得防御工夫被至多2个将军承受的是顾问，而不是将军；在“两个顾问穿插提议的场景”下，当顾问1没有做第2次prepare之前，将军1记录的其实是一个谬误的防御工夫；实践上来说，任何一个将军在任何一个时刻都无奈判断本人不是处在将军1的场景下；因而BasicPaxos在3个蓝军组成的零碎中达成了一个共识，但并没有为每个将军明确了共识；
4） 本文的两个场景都以“两个顾问”来讲，这里的“两个顾问”可能是真的两个不同的顾问，也可能是同一个顾问因为某种原因先后做了屡次提议；对应分布式系统的场景
- 真的有两个并发的client
- 两个client一先一后；第一个client执行到某个步骤因为某种原因进行了；过了一段时间，另外一个client接着操作同一个数据
- 同一个client重试；第一次执行到某一步骤因为某种原因进行了，立刻或者稍后进行了重试
后记
写这篇文章的时候，参考了以下两篇文章：
Paxos算法细节详解(一)--通过事实世界形容算法
http://www.cnblogs.com/endsoc...
第一篇文章用了咱们脍炙人口的背景，大部分内容非常容易了解，尤其是用比特币来映射编号，十分贴切；只是对于proposer-1小姐最初的“背离”会有点违反常识。看完这个故事之后就始终在想更贴切的背景。在两军问题中，蓝军各方是要单干达成一个共识；对于顾问来说，取得了前一个顾问的提议就承受，而不再提出本人的提议是合乎逻辑的，这个和paxos也更加吻合。在理论的分布式系统中，如果遇到抵触，波及的各方也不是要唇枪舌剑争个鱼死网破，想要的只是能发现抵触，只有一方胜利、或者全副失败都无所谓，只有能保证数据统一就行。
以两军问题为背景，在提议编号上找不到适合的映射点，比拟僵硬，这一点不如第一篇文章中的故事。
Question 7: The Two Generals’ Problem of reaching consensus on when to attack is unsolvable, how come it’s possible to have consensus with Paxos?
http://bogdan.pistol.gg/2014/...
paxos最终依然无奈解决两军问题，即便是扩大到3军也是无奈解决的。在3军背景下，按paxos算法的定义，最初是达成了一个独特的防御工夫，3军中的任何一方都能够通过paxos算法读取出这个防御工夫。但3军怎么晓得在什么时候去读取、其他人是否曾经读取，这是一个和两军问题同样的问题；同时因为通信兵可能有限提早，可能局部蓝军在防御工夫之前读取到了，局部蓝军可能在防御工夫之后才读取到，所以两军最终还是无解的。第二篇参考文章中也详细描述了这些问题。所以写paxos和两军问题，不是说paxos解决了两军问题，只是借用两军问题的背景来演绎paxos。
本文转自微信后盾团队如有侵权请分割咱们删除。
OpenIMgithub开源地址：
https://github.com/OpenIMSDK/...
OpenIM官网 ：https://www.rentsoft.cn
OpenIM官方论坛：https://forum.rentsoft.cn/
更多技术文章：
开源OpenIM：高性能、可伸缩、易扩大的即时通讯架构
https://forum.rentsoft.cn/thr...
【OpenIM原创】简略轻松入门 一文解说WebRTC实现1对1音视频通信原理
https://forum.rentsoft.cn/thr...