背景

在计算机通信实践中，有一个驰名的两军问题 (two-army problem)，讲述通信的单方通过 ACK 来达成共识，永远会有一个在途的 ACK 须要进行确认，因而无奈达成共识。

两军问题和 Basic Paxos 十分类似

1）通信的各方须要达成共识；

2）通信的各方仅须要达成一个共识；

3）假如的前提是信道不稳固，有丢包、提早或者重放，但音讯不会被篡改。

Basic Paxos 最早以希腊议会的背景来解说，但普通人不了解希腊议会的运作模式，因而看 Basic Paxos 的论文会比拟难了解。两军问题的背景大家更相熟，因而尝试用这个背景来演绎一下 Basic Paxos。

为了配合 Basic Paxos 的多数派概念，把两军改为 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 收到至多 2 个将军的回复，因为回复中带来了已承受的顾问 1 的提议内容，顾问 2 因而不再提出新的防御工夫，承受顾问 1 提出的工夫；

两个顾问穿插提议的场景

1）顾问 1 发动提议，派通信兵带信给 3 个将军，内容为（编号 1）；

2）3 个将军的状况如下

a) 将军 1 和将军 2 收到顾问 1 的提议，将军 1 和将军 2 把（编号 1）记录下来，如果有其余顾问提出更小的编号，将被回绝；同时让通信兵带信回去，内容为（ok）；

b) 负责告诉将军 3 的通信兵被抓，因而将军 3 没收到顾问 1 的提议；

3）顾问 2 在同一时间也发动了提议，派通信兵带信给 3 个将军，内容为（编号 2）；

4）3 个将军的状况如下

a) 将军 2 和将军 3 收到顾问 2 的提议，将军 2 和将军 3 把（编号 2）记录下来，如果有其余顾问提出更小的编号，将被回绝；同时让通信兵带信回去，内容为（ok）；

b) 负责告诉将军 1 的通信兵被抓，因而将军 1 没收到顾问 2 的提议；

5）顾问 1 收到至多 2 个将军的回复，再次派通信兵带信给有回答的 2 个将军，内容为（编号 1，防御工夫 1）；

6）2 个将军的状况如下

a) 将军 1 收到了（编号 1，防御工夫 1），和本人保留的编号雷同，因而把（编号 1，防御工夫 1）保留下来；同时让通信兵带信回去，内容为（Accepted）；

b) 将军 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 个将军的状况如下

a) 将军 1 收到顾问 1 的提议，因为（编号 3）大于之前保留的（编号 1），因而把（编号 3）保留下来；因为将军 1 曾经承受顾问 1 前一次的提议，因而让通信兵带信回去，内容为（编号 1，防御工夫 1）；

b) 将军 2 收到顾问 1 的提议，因为（编号 3）大于之前保留的（编号 2），因而把（编号 3）保留下来；因为将军 2 曾经承受顾问 2 的提议，因而让通信兵带信回去，内容为（编号 2，防御工夫 2）；

c) 负责告诉将军 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）本文的两个场景都以“两个顾问”来讲，这里的“两个顾问”可能是真的两个不同的顾问，也可能是同一个顾问因为某种原因先后做了屡次提议；对应分布式系统的场景

a）真的有两个并发的 client

b）两个 client 一先一后；第一个 client 执行到某个步骤因为某种原因进行了；过了一段时间，另外一个 client 接着操作同一个数据

c）同一个 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…

【OpenIM 原创】开源 OpenIM：轻量、高效、实时、牢靠、低成本的音讯模型

https://forum.rentsoft.cn/thr…