拜占庭将军问题

拜占庭将军问题

拜占庭将军问题（Byzantine failures），是由莱斯利·兰伯特提出的点对点通信中的基本问题。含义是在存在消息丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。因此对一致性的研究一般信道是可靠的，或不存在本问题。

起源

拜占庭将军问题

拜占庭位于现在土耳其的伊斯坦布尔，是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔，为了防御目的，因此每个军队都分隔很远，将军与将军之间只能靠信差传消息。在战争的时候，拜占庭军队内所有将军和副官必需达成一致的共识，决定是否有赢的机会才去攻打敌人的阵营。但是，在军队内有可能存有叛徒和敌军的间谍，左右将军们的决定又扰乱整体军队的秩序。在进行共识时，结果并不代表大多数人的意见。这时候，在已知有成员谋反的情况下，其余忠诚的将军在不受叛徒的影响下如何达成一致的协议，拜占庭问题就此形成。

将军问题

拜占庭将军问题是一个协议问题，拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军。问题是这些将军在地理上是分隔开来的，并且将军中存在叛徒。叛徒可以任意行动以达到以下目标：欺骗某些将军采取进攻行动；促成一个不是所有将军都同意的决定，如当将军们不希望进攻时促成进攻行动；或者迷惑某些将军，使他们无法做出决定。如果叛徒达到了这些目的之一，则任何攻击行动的结果都是注定要失败的，只有完全达成一致的努力才能获得胜利。

拜占庭容错协议必须处理这些失效，并且这些协议还要满足所要解决的问题要求的规范。这些算法通常以其弹性t作为特征，t表示算法可以应付的错误进程数。

很多经典算法问题只有在t<n/3时才有解，如拜占庭将军问题，其中n是系统中进程的总数。

失效

所谓拜占庭失效指一方向另一方发送消息，另一方没有收到，发送方也无法确认消息确实丢失的情形。

在容错的分布式计算中，拜占庭失效可以是分布式系统中算法执行过程中的任意一个错误。这些错误被统称为“崩溃失效”和“发送与遗漏是失效”。当拜占庭失效发生时，系统可能会做出任何不可预料的反应。

这些任意的失效可以粗略地分成以下几类：

进行算法的另一步时失效，即崩溃失效；

无法正确执行算法的一个步骤；

执行了任意一个非算法指定的步骤；

各个步骤由各进程执行，算法就是由这些进程执行的。一个错误的进程是在某个点出现了情况。没有出现错误的进程是正确的进程。

解决算法

拜占庭将军问题

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

为了保证上面的需求，必须满足下面两个条件：

1.每两个忠诚的将军必须收到相同的值v(i)（v(i)是第i个将军的命令）。

2.如果第i个将军是忠诚的，那么他发送的命令和每个忠诚将军收到的v(i)相同。

为了简化以上模型，我们使用一个将军发送命令给多个副官的形式来证明，发送命令的将军称为发令者，接收命令的将军为副官，那么上面的两个条件可以表述为。

IC1.所有忠诚的副官遵守相同的命令。

IC2.如果发出命令的将军是忠诚的，那么所有忠诚的副官遵守司令（发出命令的将军）的命令。

特别提示

：发送命令的每次只有一个将军，将其命令发送给n-1个副官。m代表叛国者的个数，因为将军总数为n，所以副官总数为n-1个。IC2中副官遵守实际上是指忠诚的将军能够正确收到忠诚将军的命令消息。

1、通过口头消息

通过口头消息传递达到一致，如果有m个叛国将军，则将军们的总数必须为3m+1个以上。下面是口头消息传递过程中默认的一些条件：

A1.每个被发送的消息都能够被正确的投递。

A2.信息接收者知道是谁发送的消息。

A3.能够知道缺少的消息。

A1和A2假设了两个将军之间通信没有干扰，既不会有背叛者阻碍消息的发送（截断）也不会有背叛者伪造消息的情况（伪造）。即是每个将军都可以无误地将自己的消息发送给其他每个将军。（下一节中可以不需要这个必要条件）。

定义口头消息算法OM(m)。对于所有的非负整数m，每个发令者通过OM(M)算法发送命令给n-1个副官。下面将说明OM(m)算法在最多有m个背叛者且总将军数为3m+1或者更多的情况下可以解决拜占庭将军问题。（考虑到网络应用实际环境，原文使用了收到值代替收到命令。）

算法定义一个函数：majority(com1,com2,…,comn)等于多数派命令。

OM(0)算法

（1）发令者将他的命令发送给每个副官。

（2）每个副官采用他从发令者发来的命令，或者默认使用撤退命令，如果没有收到任何命令。

OM(m)算法

（1）发令者将他的命令发送给每个副官。

（2）对于每个i，vi是每个副官i从发令者收到的命令，如果没有收到命令则为撤退命令。副官i在OM(m-1)中作为发令者将vi发送给另外n-2个副官。

（3）对于每个i，并且j eqi，vj是副官i从第（2）步中的副官j发送过来的命令（使用OM(m-1)算法），如果没有收到第（2）步中的副官j的命令则默认为撤退命令。最后副官i使用majority(v1,…,vn-1)得到命令。

接下来实际的考虑一个n=4，m=1的情况：

1.当副官3是背叛者，以副官2为例

第一步发令者执行算法OM(1)将自己的命令发送给三个副官，三个副官都正确地收到了命令。

第二步每个收到命令的副官都作为发令者执行算法OM(0)，将自己的命令转发给其余副官，因为副官3是背叛者，所以他给副官2传递的消息会是假消息。副官2最后根据majority函数来决定命令。

这样背叛的副官3同理也干扰不了忠诚的副官1和发令者的决定。下面看看如果发令者是背叛者。

2.发令者是背叛者，其余副官为忠诚的

第一步

：发令者向副官发送了不同的命令，实际情况中是一个攻击者向不同方发送了不同的值进行欺骗。

第二步

：副官收到命令后，摇身一变为发令者执行OM(0)向所有的副官发送命令，这样所有副官的到命令会都相同

，这样所有命令都达不到大部分。

文章接着就证明了OM(m)算法对任意m都是可以满足，首先引入一个引理（归纳法证明）：

引理1：

对于任意m和k，如果有超过2k+m个将军和最多k个背叛者，那么算法OM(m)满足IC2（回顾下IC2指的是，如果将军是忠诚的，所有的副官遵守将军命令）。

证明

：当m=0的时候，OM(0)在将军是忠诚的时候满足IC2。当m>0时，首先将军将命令传递给n-1个副官，然后每个副官对n-1个将军执行OM(m-1)算法。因为假设了n>2k+m（引理中有将军数大于2k+m），所以n-1>2k+(m-1)>=2k（即每一轮中副官总数不小于背叛者的两倍），这样每轮OM(m-k)算法中忠诚的副官收到的命令都是majority(v1,v2,...,v(n-1))，其中忠诚副官发送的命令大于或者等于一半。

接着解决拜占庭将军问题。

定理1：对于任意m，如果有超过3m个将军和最多m背叛者，算法OM(m)满足条件IC1和条件IC2。

证明：通过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。

2、通过签名消息

签名消息在除了满足口头消息A1-A3三点要求外还应该满足下面A4：

A4（a）签名不可被伪造，一旦被篡改即可发现。

（b）任何人都可以验证将军签名的可靠性。

下面定义一个类似于上面majority函数的choice来决定副官的选择：1.当集合V只包含了一个元素v，那么choice(V)=v；2.choice(o)=RETREAT。

拜占庭将军问题

初始化Vi=空集合

（1）将军签署命令并发给每个副官。

（2）对于每个副官i。

（A）如果副官i从发令者收到v:0的消息，且还没有收到其他命令序列，那么。

（i）使Vi为{v}。

（ii）发送v:0:i给其他所有副官。

（B）如果副官i收到消息v:0:j1:...:jk且v不在集合Vi中则。

（i）添加v到Vi。

（ii）如果k。

（3）对于每个副官i，当不再收到消息，则遵守命令choive(Vi)。

算法的几点说明：

算法第三步并没有说明副官如何判断没有新的消息，可以通过两个解决方法：一是要求每个副官收到消息后要么签名转发该消息，要么发送一个通知他将不发送这个消息；二是设置一个超时时间，如果在该时间段还没有收到消息，则认为不再收到消息。

算法SM(m)中，让副官签名是确认其收到了该消息（有点像来了份文件给每个领导批阅）。在SM(1)中副官收到消息就不用签字了，因为不用转发给其他副官。

定理2

：对于任意m，最多只有m个背叛者情况下，算法SM(m)解决拜占庭将军问题。

Proof：首先证明IC2，如果发令者是忠诚的，那么所有的副官一定收到相同的命令，因为签名无法篡改，且IC1也就满足了。证明IC1只用考虑发令者是背叛者的情况（重新回顾下IC1是指所有忠诚的副官执行相同的命令），IC1要求两个忠诚的副官（i，j）必须收到相同的命令集合Vi、Vj，也就是Vi中每个v都在Vj中。会存在两种情况，其一当副官i收到v令的序列后，加入到Vi，并将其发送给副官j，j将命令v保存；其二副官i收到命令v:0:j1:...:jk:i，其中有jr=j，所以由A4可知副官j也收到了该命令。

k<m。这种情况下，i发送信息v:0:j1:...:jk:i给副官j，那么j一定收到v。

k=m。发令者是背叛者，最多只有m-1个副官是背叛者。因此，最少有一个序列j1,...,jm是忠诚的。那么j一定收到这个忠诚的副官序列发来的值v所以副官j收到v。