链客，专为开发者而生，有问必答！

此文章来自链客区块链技术问答社区，未经允许拒绝转载。

百度描述

拜占庭将军问题是一个协议问题，拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军。问题是这些将军在地理上是分隔开来的，并且将军中存在叛徒。叛徒可以任意行动以达到以下目标：欺骗某些将军采取进攻行动；促成一个不是所有将军都同意的决定，如当将军们不希望进攻时促成进攻行动；或者迷惑某些将军，使他们无法做出决定。如果叛徒达到了这些目的之一，则任何攻击行动的结果都是注定要失败的，只有完全达成一致的努力才能获得胜利。拜占庭假设是对现实世界的模型化，由于硬件错误、网络拥塞或断开以及遭到恶意攻击，计算机和网络可能出现不可预料的行为。拜占庭容错协议必须处理这些失效，并且这些协议还要满足所要解决的问题要求的规范。这些算法通常以其弹性t作为特征，t表示算法可以应付的错误进程数。很多经典算法问题只有在t小于n/3时才有解，如拜占庭将军问题，其中n是系统中进程的总数。

算法核心

主要是分布式系统中最终一致性的解决问题。算法核心在于少数人m服从多数人3m＋1这个策略。以四个将军为例OM(1) 如当将军A将信息传递给将军B，C，D。而中间是通过副官传递。且传递一定是有结果，分正确为1，错误为0。而且一次传递中错误为一处的情况下，会有两种情形：当发令者将军A的副官不是叛徒，而传递后的将军中有叛徒的情况下。则会有以下结果。A的结果正确传递到BCD。而BCD中其中一个将军下面的副官会将错误结果传递给另外两个副官。但由于最终另外两个副官的结果是正确的，所以最终以多数正确（4个1）赢过少数错误（两个0）而最终实现一致。当发令者将军A的副官是叛徒的情况下，则A向B通过副官传递的是错误信息。通过B再向C和D传达两条错误信息。但由于C和D本身接收的是正确的，且相互传递后有四条正确信息。因此最终结果还是以多数正确（4个1）赢过少数错误（两个0）而最终实现一致。

算法拓展

条件：IC1. 所有忠诚的副官遵守相同的命令 IC2. 如果发出命令的将军是忠诚的，那么所有忠诚的副官遵守司令（发出命令的将军）的命令

引理1：对于任意m 和k ，如果有超过2k+m 个将军和最多k 个背叛者，那么算法OM(m) 满足IC2

OM(m) : 证明：通过m 的归纳法证明，我们通过假设OM(m-1) 成立来证明OM(m) m>0。首先考虑发送命令的将军是忠诚的。那么将引理中k 设为m 则OM(m) 满足IC2 ，IC1 在发令将军是忠诚的情况下也满足。接着考虑m 个背叛者中有一个是发令者，那最多就只有m-1 个副官是背叛者了，又因为有3m 个将军，所以副官的总数超过3m-1，且有3m-1>3(m-1) 。因此通过归纳法假设 OM(m-1) 满足IC1 和IC2（最多3(m-1) 个将军和最多m-1 个背叛者）。那么任意两个忠诚的副官j 在OM(m-1) 获得相同命令vj，那么在OM(m) 算法中每个忠诚的副官都会收到(v1,v2,…,\v(n-1))，可知满足条件IC1 和IC2。

因此，实际上拜占庭问题即分布式问题的最终一致性方案即为少数服从多数。这一点在区块链和比特币中尤其体现出这一点。我的算法工作量大于你的时候，你必须服从我。甚至大于全部51%的时候，即为自己占用区块。