拜占庭将军问题

参考 The Byzantine Generals Problems

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

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

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

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

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

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

IC2. 如果发出命令的将军是忠诚的,那么所有忠诚的副官遵守相同的命令

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

一、通过口头消息

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

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

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

A3. 能够知道缺少的消息

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

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

算法定义一个函数:$majority(com_1,com_2,\dots,com_n)$ 等于多数派命令。


OM(0)算法

(1)发令者将他的命令发送给每个副官。

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

OM(m)算法

(1)发令者将他的命令发送给每个副官。

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

(3)对于每个i,并且$j\neq i$,vj 是副官i 从第(2)步中的副官j 发送过来的命令(使用OM(m-1) 算法),如果没有收到第(2)步中的副官j 的命令则默认为撤退命令。最后副官i 使用majority(v_1,\dots,v_{n-1})得到命令。


继续阅读