文档介绍：起源拜占庭位于如今的土耳其的伊斯坦布尔,是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔,为了防御目的,因此每个军队都分隔很远,将军与将军之间只能靠信差传消息。在战争的时候,拜占庭军队内所有将军和副官必需达成一致的共识,决定是否有赢的机会才去攻打敌人的阵营。但是,在军队内有可能存有叛徒和敌军的间谍,左右将军们的决定又扰乱整体军队的秩序。在进行共识时,结果并不代表大多数人的意见。这时候,在已知有成员谋反的情况下,其余忠诚的将军在不受叛徒的影响下如何达成一致的协议,拜占庭问题就此形成。将军问题拜占庭将军问题是一个协议问题,拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军。问题是这些将军在地理上是分隔开来的,并且将军中存在叛徒。叛徒可以任意行动以达到以下目标:欺骗某些将军采取进攻行动;促成一个不是所有将军都同意的决定,如当将军们不希望进攻时促成进攻行动;或者迷惑某些将军,使他们无法做出决定。如果叛徒达到了这些目的之一,则任何攻击行动的结果都是注定要失败的,只有完全达成一致的努力才能获得胜利。拜占庭假设是对现实世界的模型化,由于硬件错误、网络拥塞或断开以及遭到恶意攻击,计算机和网络可能出现不可预料的行为。拜占庭容错协议必须处理这些失效,并且这些协议还要满足所要解决的问题要求的规范。这些算法通常以其弹性t作为特征,t表示算法可以应付的错误进程数。很多经典算法问题只有在t<n/3时才有解,如拜占庭将军问题,其中n是系统中进程的总数。失效所谓拜占庭失效指一方向另一方发送消息,另一方没有收到,发送方也无法确认消息确实丢失的情形。在容错的分布式计算中,拜占庭失效可以是分布式系统中算法执行过程中的任意一个错误。这些错误被统称为“崩溃失效”和“发送与遗漏是失效”。当拜占庭失效发生时,系统可能会做出任何不可预料的反应。这些任意的失效可以粗略地分成以下几类:进行算法的另一步时失效,即崩溃失效;无法正确执行算法的一个步骤;执行了任意一个非算法指定的步骤各个步骤由各进程执行,算法就是由这些进程执行的。一个错误的进程是在某个点出现了上述情况的进程。没有出现错误的进程是正确的进程。解决算法拜占庭问题的最初描述是:n个将军被分隔在不同的地方,忠诚的将军希望通过某种协议达成某个命令的一致(比如一起进攻或者一起后退)。但其中一些背叛的将军会通过发送错误的消息阻挠忠诚的将军达成命令上的一致。Lamport证明了在将军总数大于3m,背叛者为m或者更少时,忠诚的将军可以达成命令上的一致。为了保证上面的需求,必须满足下面两个条件:(i)(v(i)是第i个将军的命令),那么他发送的命令和每个忠诚将军收到的v(i)相同为了简化以上模型,我们使用一个将军发送命令给多个副官的形式来证明,发送命令的将军称为发令者,接收命令的将军为副官,那么上面的两个条件可以表述为:,那么所有忠诚的副官遵守司令(发出命令的将军)的命令特别提示:发送命令的每次只有一个将军,将其命令发送给n-1个副官。m代表叛国者的个数,因为将军总数为n,所以副官总数为n-1个。IC2中副官遵守实际上是指忠诚的将军能够正确收到忠诚将军的命令消息。通过口头消息通过口头消息传递达到一致,如果有m个叛国将军