拜占庭将军问题

[TOC]

拜占庭将军错误计算机科学家莱斯利·兰伯特在《拜占庭将军问题》中提出的一个错误模型，描述了一个完全不可信的场景，除了存在故障行为，还存在恶意行为

一组拜占庭将军分别各率领一支军队共同围困一座城市。为了简化问题，将各支军队的行动策略限定为进攻或撤离两种。因为部分军队进攻部分军队撤离可能会造成灾难性后果，因此各位将军必须通过投票来达成一致策略，即所有军队一起进攻或所有军队一起撤离。因为各位将军分处城市不同方向，他们只能通过信使互相联系。在投票过程中每位将军都将自己投票给进攻还是撤退的信息通过信使分别通知其他所有将军，这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以知道共同的投票结果而决定行动策略。

系统的问题在于，可能将军中出现叛徒，他们不仅可能向较为糟糕的策略投票，还可能选择性地发送投票信息。假设有9位将军投票，其中1名叛徒。8名忠诚的将军中出现了4人投进攻，4人投撤离的情况。这时候叛徒可能故意给4名投进攻的将领送信表示投票进攻，而给4名投撤离的将领送信表示投撤离。这样一来在4名投进攻的将领看来，投票结果是5人投进攻，从而发起进攻；而在4名投撤离的将军看来则是5人投撤离。这样各支军队的一致协同就遭到了破坏。

由于将军之间需要通过信使通讯，叛变将军可能通过伪造信件来以其他将军的身份发送假投票。而即使在保证所有将军忠诚的情况下，也不能排除信使被敌人截杀，甚至被敌人间谍替换等情况。因此很难通过保证人员可靠性及通讯可靠性来解决问题。

假使那些忠诚（或是没有出错）的将军仍然能通过多数决定来决定他们的战略，便称达到了拜占庭容错。在此，票都会有一个默认值，若消息（票）没有被收到，则使用此默认值来投票。

上述的故事映射到计算机系统里，将军便成了计算机，而信差就是通信系统。虽然上述的问题涉及了电子化的决策支持与信息安全，却没办法单纯的用密码学与数字签名来解决。因为电路错误仍可能影响整个加密过程，这不是密码学与数字签名算法在解决的问题。因此计算机就有可能将错误的结果提交去，亦可能导致错误的决策。

拜占庭将军问题被认为是容错性问题中最难的问题类型之一

拜占庭将军问题很好地抽象了分布式系统面临的共识问题，理解了这个问题，对于学习其他分布式协议算法都有很好的帮助。。

拜占庭问题解决

TODO

口信消息型拜占庭问题之解

如果叛将人数为 m，将军人数不能少于 3m + 1 ，要进行 m + 1 轮协商，那么拜占庭将军问题就能解决了。m 也叫能容忍的最大叛将数。

如果有 n 位将军，那么最多能容忍 (n - 1) / 3 位叛将。

这种解法：只能容忍不到1/3的背叛。

签名消息型拜占庭问题之解

签名的作用是防止消息被叛徒修改。如果被修改可以被发现，同时也会是修改签名的叛徒身份暴露。

签名约束了叛徒的作恶行,可以容忍 n - 2 位叛徒。叛徒再多就变成只有一位忠诚的，活着全是叛徒，也就有协商的意义了。

那么投票过程怎么进行？

数字签名既可以证实内容的完整性，又可以确认内容的来源，实现不可抵赖性（Non-Repudiation）。

把收到的消息，透出给别人，如果在透出时修改了，此时签名就起作用了，

签名消息是一些常用的拜占庭容错算法（比如 PBFT）的实现基础。

在分布式计算中，不同的计算机通过通讯交换信息达成共识而按照同一套协作策略行动。但有时候，系统中的成员计算机可能出错而发送错误的信息，用于传递信息的通讯网络也可能导致信息损坏，使得网络中不同的成员关于全体协作的策略得出不同结论，从而破坏系统一致性。

拜占庭容错

拜占庭容错（Byzantine Fault Tolerance，BFT）。

拜占庭将军错误描述了一个完全不可信的场景，除了存在故障行为，还存在恶意行为。

非拜占庭容错，又叫故障容错（Crash Fault Tolerance，CFT），解决的是分布式系统中存在故障，但不存在恶意节点的共识问题，比如进程奔溃，服务器硬件故障等等。

块链技术比特币就是采用了拜占庭容错算法POW，对于这种开放式的网络环境必须使用拜占庭容错算法，因为彼此无法建立信任关系。如果是企业内部的分布式中间件，因为只需考虑故障容错，不存在恶意节点。