>

字数 1.1k 阅读 12 评论 6

Byzantine failures

拜占庭将军问题又称为“拜占庭失败”，是由 Leslie Lamport 提出的点对点通信中的基本问题，论文原文

拜占庭问题的最初描述是：N 个将军被分隔在不同的地方，忠诚的将军希望通过某种协议达成某个命令的一致（比如一起进攻或者一起后退）。但其中一些背叛的将军会通过发送错误的消息阻挠忠诚的将军达成命令上的一致。Lamport 证明了在将军总数大于 3m，背叛者为 m 或者更少时，忠诚的将军可以达成命令上的一致。

拜占庭将军问题本质是一个协议问题，问题的起源是拜占庭帝国军队的将军们准备攻击某一支敌军，但是他们必须达到全体一致的是否攻击的决定。由于这些将军在地理上是分隔开来的，因而他们必须通过信使来传递彼此的决定，而将军中存在叛徒，叛徒采取行动来欺骗某些将军采取进攻行动或者促成一个不是所有将军都同意的决定，从而导致最终行动失败，因为只有只有完全达成一致的行动才能获得胜利。

拜占庭失败对应于通信中的表现就是：消息可能丢失、重复，甚至内容损坏或者篡改（非拜占庭模型允许消息的丢失或者重复，但是不会出现内容损坏篡改的情况）。
因此，拜占庭模型的含义是在存在消息丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。

拜占庭假设是对现实世界的模型化，由于硬件错误、网络拥塞或断开以及遭到恶意攻击，计算机和网络可能出现不可预料的行为。拜占庭容错协议必须处理这些失效，并且这些协议还要满足所要解决的问题要求的规范。这些算法通常以其弹性 t 作为特征，t 表示算法可以应付的错误进程数。

算法演绎

假设多股军队计划同时攻打某城池，这些军队的 commander 被一个将军领导，但其中一个或几个可能是叛徒，所以如果想获得胜利，就一定要让忠诚的 commander 同时发动进攻，但叛徒会用错误的信息扰乱进攻时间，避免的方式就是所有的 commander 共同交换信息，以判定叛徒；

该算法的目标是：
1。忠诚的 commander 遵守同样的命令
2。如果将军也是忠诚的，所有忠诚的commander遵守该将军发布的命令

算法的需求：
1。如果存在 3m＋1 个 unit，则可容错1个 unit 的 byzantine failure
2。至少 m＋1 轮的消息传递
3。所有 unit 同步

算法的假设：
1。不会丢失消息
2。消息接收者知道谁是发送者
3。消息丢失可被探测

算法开始：
1。将军的命令被送到每个 commander
2。每个接收者使用该命令或使用 retreat 状态

算法进行；
1。将军的命令被发布到每个节点
2。每个接收者使用该命令或使用retreat状态（如未收到任何命令），每个接受者如将军般向其他n－2个commander继续转发命令（不发给自己和消息来源）
3。重复以上过程；最后得到命令集合｛vi…..vj｝

如为了容一个错，使用4个节点：

unit2 将向节点3，4继续转发命令，同时也收到节点3，4转发的命令，节点2在{v1 v31 v41}使用少数服从多数的方式获取最终命令；
对于获得一个共识的消息数量：3＋23＝9条
则对于4个节点或许4个共识而言，消息数量是 49＝36条；

对于一个能容2个错的7节点系统来说
获取一个共识的消息数量：6＋6＊（5＋5*4）＝156条
消息总数：7 * 156


##### 参考： http://baike.baidu.com/item/%E6%8B%9C%E5%8D%A0%E5%BA%AD%E5%B0%86%E5%86%9B%E9%97%AE%E9%A2%98 http://www.2cto.com/os/201312/268181.html