第12章|第12章 拜占庭容错
在讲这个问题前，我们先回顾我们已经有的容错。我们可以使用RSM来容错，在2F+1最多可以有F个节点挂掉。
参与PAXOS的协议的机子被攻击了，或者代码写错了。这样这台机器可能会违背协议。
文章图片
image.png 拜占庭将军问题：
https://zh.wikipedia.org/wiki/%E6%8B%9C%E5%8D%A0%E5%BA%AD%E5%B0%86%E5%86%9B%E9%97%AE%E9%A2%98
拜占庭问题的目标是，共识发生在好人里，少数的坏人不可以影响好人去接受一个坏计划。
本身控制不了坏人，坏人可以不遵守好人的计划，也可以发送不同的消息
如何让好人达成一致呢？
关键是让好人得到相同的正确的消息。
文章图片
image.png 假设前面5个人，前面4个都是好的，最后一个是叛徒。如果进行投票，2个好的进攻，2个好的撤退。叛徒无论说进攻还是撤退看上去都是叛徒决定。但这个不是拜占庭将军要解决的问题。拜占庭将军问题是要让这4个好人步调不一致，有人进攻有人撤退。当好人2边结果很接近，叛徒的决定是可以影响最终结果这个无法避免。实际情况，5个人是无法当面投票的，所以他们只能互相发消息来代表自己的投票。如果都是好人，每个人都会收到别人的结果，最终他们能收到一致的结果。这个时候叛徒就出来了起作用。他可以向一部分发送进攻，一部分发送撤退。造成4个好的分裂。使得共识被破坏。
上面2个条件。每个好人都会向其他人投一致的票（一个好人不会一半投进攻，一半投撤退），并且他们投出去的票被别人看到的都是对的。同时要求通过一些交互可以把叛徒发现出来使得坏人不能发挥作用。他们可以把自己收到的票再转发一次。这个时候他们4个好人一通气发现叛徒有的说进攻有的说撤退，就能把叛徒找出来。
这个问题被转化另一个问题，
对一个人来说他是主将，其他人是副官。叛徒如果做了副官，可以在转发的时候捣乱。如果叛徒做了主将可以给不同的副官发不同的消息。
文章图片
image.png 所以在3个人的时候，有1个叛徒。是分辨不出来的，如下图。
文章图片
image.png 通信是基于可以篡改的环境3个人的时候，有1个叛徒。是分辨不出来的
那我们看4个人能不能容忍一个坏蛋。
我们看看如何做
文章图片
image.png
消息在路中不会被篡改，知道谁发的，知道消息缺席的情况。
1和2,保证叛徒不能中途截获信息。3保证坏蛋不发消息也没事。
基本思想就是转发，每个人收到消息就向剩下其他人转发。副官会收到一系列的VALUE。
我们来看一个具体例子。现在4个人，假设坏蛋是副官。
文章图片
image.png
那么大多数的是好人发的。
文章图片
image.png 如果坏蛋是CMD会如何，最优策略是发3个不一样（最可能达不成一致）
文章图片
image.png
好人经过转发，发现3个消息不一致，那么他们就知道CMD是坏人，就可以不执行了。
那么时间复杂度是多少呢？
文章图片
image.png
【第12章|第12章 拜占庭容错】复杂度会比较高。纯ORAL的方式DETECT的代价非常大。
最简单的方法是不让他篡改MESSAGE。（这里如何解读，也就是好比将军都是用自己专属的笔迹写的指令，当叛徒收到后，是无法篡改后转发给别人。所以叛徒能做的只有当自己做COMMANDER的时候，发送混乱的消息。）
在这是非对称的签名可以用上了，就达到了上述的效果。
文章图片
image.png
这样复杂度就降低了。当不存在机器挂掉的时候，只需要有2F+1个机器就可以容忍F个坏蛋。
如果在DS里有些系统被攻击，那么就可以用拜占庭问题来解决。
文章图片
image.png 又有人会捣乱，又有人会不参加，怎么在一起WORK，也就是说结合PAXOS和BFT来实现一个RSM。RSM就是初始状态一致，操作一致，结束状态就会一致。
文章图片
image.png 
文章图片
image.png 上述的分析就表示如果有坏蛋，那么PAXOS就不能用。如果消息是加密的，要解决这个问题，我们首先要限制住如果坏蛋是PRIMARY的情况，因为坏蛋是BACKUP时，由于消息是加密的，它不能做什么事情，最多只能让自己挂掉。
那么整个问题就变成如何发现错误当坏蛋是PRIMARY的时候，当有机器挂了应该怎么做？
我们首先来看下为什么PAXOS在拜占庭问题下会不WORK？
文章图片
image.png
文章图片
image.png
文章图片
image.png
文章图片
image.png 在这里既有机器会挂掉，又有机器是坏蛋，那么3f+1里需要有2F+1达成一致。
也就是说可以容忍F个坏蛋和F个机器挂掉。
文章图片
image.png 轮流做PRIMARY ， 有F+1个人达成一致可以要求替换PRIMARY。（因为最多F个坏蛋，坏蛋团结不管用）
文章图片
image.png
文章图片
image.png
文章图片
image.png
文章图片
image.png
文章图片
image.png 
文章图片
image.png 当PRIMARY 是好人，坏蛋能不能阻止PRIMARY 继续做下去？因为好人有2F+1个，即使有F个挂了，还有F+1个，那么当F个坏人都在捣乱。其他的REPLICA好人也知道有F+1的消息一致，所以知道PRIMARY是好人。
当PRIMARY时坏人，好人能不能阻止？ 当PRIMARY时坏人，有F+1个好人，会彼此交互PRIMARY给他们发的消息看是不是一致，而坏人一定不一致。而必定有至少F+1个混乱的消息。那么就知道PRIMARY是坏人。所以可以按顺序继续让下一个人来做PRIMARY。
推荐阅读
- 第6.2章（设置属性）
- 2018-02-06第三天|2018-02-06第三天 不能再了，反思到位就差改变
- 第三节|第三节 快乐和幸福（12）
- EffectiveObjective-C2.0|EffectiveObjective-C2.0 笔记 - 第二部分
- android第三方框架（五）ButterKnife
- 开学第一天（下）
- 野营记-第五章|野营记-第五章 讨伐梦魇兽
- 2018年11月19日|2018年11月19日 星期一 亲子日记第144篇
- 第326天
- 跌跌撞撞奔向你|跌跌撞撞奔向你 第四章（你补英语，我补物理）