锐客网

  1. 首页 > it技术 > >

拜占庭问题论文翻译

区块链

The Byzantine Generals Problem
? 可靠的计算机系统必须处理会向系统的不同部分提供冲突信息的故障组件。这种情况可以用拜占庭军队的将军和他们的部队围困在敌方城市附近来概括地表达。 将军们只能通过使者交流，他们必须商定共同的战斗计划。 但是，其中一个或多个可能是叛徒，他们会试图混淆其他人。 问题是找到一种算法来确保忠实的将军们达成共识。 结果表明，仅在口头表达的情况下，只有并且只有三分之二以上的将军忠诚时，这个问题才能解决。 所以一个叛徒可以混淆两个忠实的将军。 有了不可伪造的书面信息，这个问题对于任何数量的将军和可能的叛徒来说都是可以解决的。 然后讨论该解决方案在可靠的计算机系统中的应用。
1.引言
? 可靠的计算机系统必须能够应对一个或多个组件的故障。 发生故障的组件可能表现出一种通常被忽略的行为，即，将冲突的信息发送到系统的不同部分。 应对此类故障的问题抽象表示为拜占庭将军问题。 我们将本文的主要部分专门讨论了这个抽象问题，并通过指出如何将我们的解决方案用于实现可靠的计算机系统来进行总结。 我们假设拜占庭军队的几个师驻扎在一个敌方城市之外，每个师由其自己的将军指挥。将军只能通过使者相互沟通。 观察敌人之后，他们必须决定共同的行动计划.但是，有些将军可能是叛徒，试图阻止忠实的将军达成协议。
将军们必须有一种算法来保证:
A.所有忠实的将军都决定相同的行动计划。
? 忠实的将军都会按照算法说的去做，但是叛徒可以做他们想做的任何事情。无论叛徒做什么，该算法都必须保证条件A。忠实的将军们不仅应该达成协议，而且应该就合理的计划达成协议。因此，我们还想确保
B.少数叛徒不会使忠诚的将军们采取错误的计划。
? 条件B很难形式化，因为它需要准确说出一个不好的计划，我们不会尝试这样做。相反，我们考虑将军们如何做出决定。每个将军观察敌人并将他的观察力传达给其他人。令v（i）为第i个将军传达的信息。每个将军使用某种方法将值v（1）… v（n）组合到一个单独的行动计划中，其中n是将军的数量。条件A通过让所有将军使用相同的方法来组合信息来实现，条件B通过使用鲁棒的方法来实现。例如，如果要做出的唯一决定是进攻还是撤退，则v（i）将是通过将军 i认为哪种选择最好的决定，而最终决定可以基于其中的多数票。只有忠实的将军在两种可能性之间几乎均等地划分时，少数叛徒才会影响决策。
? 虽然这种方法可能不是满足条件 A 和 B 的唯一方法，但它是我们所知道的唯一方法。它假定将军们用一种方法彼此交流他们的信息V(i)。显而易见的方法是通过信使相互发送 v(i)。然而，这不起作用，因为满足条件 A要求每个忠诚的将军获得相同的值 v(1)…V(n)。一个叛国的将军可以给不同的将军发出不同的价值观。要满足条件 B，下列条件必须满足:
**1.每个忠诚的将军都必须获得相同的信息。**一致性
? 条件 1 意味着一个将军不一定能直接使用从第一个将军那里得到的 v(i)值，因为一个叛国的将军可以给不同的将军发送不同的值。这意味着，如果我们不小心，在满足条件 1 的情况下，我们可能会引入一种可能性，即将军们使用的 v(i)值不同于第一个将军发出的 v(i)值——即使第一个将军是忠诚的。如果要满足条件 b，我们就不能允许这种情况发生。例如，如果每一个忠诚的将军都发出“进攻”的信号，我们就不能允许少数叛徒使忠诚将军以“撤退”、“…”、“撤退”的信号为基础作出决定。因此，我们对每个 i 都有以下要求:
**2.如果第i个将军是忠诚的，那么他发送的值必须被每个忠诚的将军用作 v(i)的值。**正确性
我们可以重写条件 i 作为条件，即对于每一个 i(不管第一个将军是否忠诚)，1’。任何两个忠诚的将军使用相同的价值 v(i)。条件 1’和 2 都是由第 i 个将军发送的单个值的条件。因此，我们可以考虑限制在一个将军如何把他的信息传递给其他将军的问题上。我们用一个指挥官向他的副官们发出命令的方式来表达这个意思，得到以下的问题。
拜占庭将军问题指挥官必须向他的n-1中将下达命令
IC1. 所有忠诚的副官都遵守同样的命令。
IC2.如果指挥官是忠诚的，那么每个忠诚的中尉都会服从他发出的命令。
【拜占庭问题论文翻译】? 条件 IC1 和 IC2 称为交互式一致性条件。请注意，如果指挥官是忠诚的，那么 IC1就跟随 IC2。然而，指挥官并不需要忠诚。
? 为了解决我们最初的问题，第一位将军用一个解决方案向拜占庭将军问题发出命令，“使用 v(i)作为我的信息”，其他将军充当中尉，从而发出 v(i)的价值。
2.不可能的结果
? 拜占庭将军问题看起来简单得让人难以置信。如果将军们只能发送口头信息，那么除非三分之二以上的将军们忠诚，否则任何解决方案都不会奏效。特别是，只有三个将军，没有任何解决办法可以在一个单一的叛徒存在。口头信息的内容完全在发送者的控制之下，因此叛国的发送者可以传递任何可能的信息。这种信息对应于计算机通常互相发送的信息类型。在第四部分，我们考虑签名的，书面的协议，因此这不是真的。
? 我们现在表明，口头信息没有解决三个将军可以处理一个叛徒。为简单起见，我们考虑这样一种情况，即唯一可能的决定是“进攻”或“撤退”。让我们首先看看图

  • 司令是忠诚的
拜占庭问题论文翻译
文章图片
? 图1 中的场景，在这个场景中，指挥官是忠诚的，并且发出了一个“攻击”命令，但是中尉2 是一个叛徒，并且向中尉 1 报告他收到了一个“撤退”命令。为了满足IC2 (所有忠诚的副官都遵守同样的命令)的要求，中尉 1 必须服从进攻命令。
  • 司令是叛徒
拜占庭问题论文翻译
文章图片
? 现在考虑另一个场景，如图 2 所示，其中指挥官是一个叛徒，向中尉 1 发出一个“攻 击”命令，向中尉 2 发出一个“撤退”命令。中尉 1 不知道谁是叛徒，他不能告诉什么信息的指挥官实际上发送给中尉 2。因此，这两张图片中的场景在中尉 1 看来完全相同。如果叛徒一贯说谎，那么中尉 1 就没有办法区分这两种情况，所以他必须服从“攻击”命令在他们两个。因此，每当中尉一号接到指挥官的“攻击”命令时，他必须服从。
? 然而，一个类似的论点表明，如果中尉 2 接到指挥官的“撤退”命令，那么他必须服从命令，即使中尉 1 告诉他指挥官说“进攻”。因此，在图 2 的场景中，中尉 2 必须服从“撤退”命令，而中尉 1 服从“攻击”命令，因此违反了条件 IC1。因此，三个将军在一个叛徒面前工作是没有解决办法的。
? 这个论点可能看起来令人信服，但是我们强烈建议读者对这种非严格的推理非常怀疑。虽然这个结果确实是正确的，但我们已经看到了同样似是而非的无效结果的“证明”.我们知道在计算机科学或数学中，没有一个领域的非正式推理比这类算法的研究更容易导致错误。为了严格证明可以处理单个叛逆者的三通解是不可能的，我们请读者参考[3]。
? 利用这个结果，我们可以证明少于 3m+1 个将军的解决方案不能应付 m个 叛徒。更确切地说，三个或更多的将军不存在这样的解决方案，因为这个问题对两个将军来说是微不足道的。
? 解一组 3m 或更少的问题，然后用它构造一个拜占庭将军问题的三通解，这是我们知道不可能的。为了避免两种算法之间的混淆，我们称假设解的将军为阿尔巴尼亚将军，构造解的将军为拜占庭将军。因此，从允许 300 万或更少的阿尔巴尼亚将军对付 300 万叛徒的算法出发，我们构造了一个允许三个拜占庭将军对付一个叛徒的解决方案。
? 通过让拜占庭的每一位将军模拟大约三分之一的阿尔巴尼亚将军，得到三个一般解，这样每一位拜占庭将军模拟的阿尔巴尼亚将军最多不超过万人。拜占庭指挥官模拟阿尔巴尼亚指挥官和最多 m-1 阿尔巴尼亚中尉，两个拜占庭中尉模拟最多m 阿尔巴尼亚中尉。因为只有一个拜占庭将军可以成为叛徒，而且他假装最多亿阿尔巴尼亚人，最多亿阿尔巴尼亚将军是叛徒。因此，假定的解决办法保证了 IC1 和IC2 对阿尔巴尼亚将军们适用。通过 IC1，所有的阿尔巴尼亚中尉被忠诚的拜赞廷中尉模仿，服从同样的命令，这是他必须服从的命令。阿尔巴尼亚将军解的 IC1 和IC2 条件是否暗示了拜占庭将军解的相应条件是很容易验证的，因此我们构造了所需的不可能解。
? 有人可能会认为，解决拜占庭将军问题贸易协定的困难源于达成确切协议的要求。我们现在通过表明达成近似协议与达成确切协议同样困难来证明情况并非如此。让我们假设，将军们不是试图商定一个精确的作战计划，而是必须商定一个大约的进攻时间。更确切地说，我们假设指挥官命令进攻的时间，我们要求保持以下两个条件：
? IC1’. 所有忠诚的副官在 10 分钟内互相攻击。
? IC2’.如果指挥官是忠诚的，那么每个忠诚的中尉都会在指挥官命令的 10 分钟内发动攻击。
(我们假设命令是在攻击前一天发出和处理的，接收命令的时间与此无关——只是命令中给出的攻击时间有关。)
? 像拜占庭将军问题一样，这个问题是无法解决的，除非超过三分之二的将军是忠诚的。我们首先证明了这一点，如果对付一个叛徒的三个将军有一个解决方案，那么我们就可以构造一个对付一个叛徒的拜占庭将军问题的三个通用解决方案。假设指挥官希望发出“进攻”或“撤退”的命令。他通过发送 1:00 的攻击时间命令攻击，并使用假定的算法发送 2:00 的攻击时间命令撤退。每个中尉使用以下程序获得他的命令。
? (1) 在收到指挥官的攻击时间后，一名中尉做了以下事情之一:
? (a) 如果时间是 1:10 或更早，然后攻击。
? (b) 如果时间是 1:50 或更晚，那么就撤退。
? ?否则，继续步骤(2)。IC2`
? (2) 问问另一个中尉，他在第(1)步做了什么决定。
? (a)如果另一个中尉做出了决定，那么就做出和他一样的决定。
? (b) 否则，就撤退。
? 根据 IC2’，如果指挥官是忠诚的，那么忠诚的中尉将在步骤(1)中获得正确的顺序，因此 IC2 是满意的。如果指挥官是忠诚的，那么 IC1 就跟随 IC2，所以我们只需要在指挥官是叛徒的假设下证明 IC1。因为最多只有一个叛徒，这意味着两个副手都是忠诚的。因此，如果一个中尉决定第(1)步进攻，那么另一个中尉不能决定第(1)步撤退。因此，要么他们都会在步骤(1)中做出相同的决定，要么他们中至少有一个会推迟到步骤(2)再做决定。在这种情况下，很容易看到它们都得到了相同的决定，因此 IC1 是满意的。因此，我们构建了一个拜占庭将军问题的三通解决方案来处理一个叛徒，这是不可能的。因此，我们不能有一个三通用的算法来维护 ICI’和 IC2’的存在一个叛徒。
现在可以用一般模拟法证明少于 3m+1 的解决方案不能对付 m 个叛徒。这个证明与原始拜占庭将军问题的证明相似，由读者自己去证明。
3.口头信息的解决方案
? 我们在上面展示了一个用口头信息来对付拜占庭将军问题叛徒的解决方案，必须至少有 3 百万+1 个将军。我们现在给出了一个对 3 百万+1 或更多的将军有效的解决方案。然而，我们首先确切地说明“口头信息”是什么意思。每个将军都应该执行一些算法，包括向其他将军发送消息，我们假设一个忠诚的将军正确地执行他的算法。定义口头信息体现在我们对将军信息系统的下列假设中:
A1. 每条发送的信息都被正确传递。 A2. 信息的接收者知道是谁发送的。 A3. 可以检测到消息的缺失。

假设 A1 和 A2 防止叛徒干扰其他两位将军之间的通讯，因为通过 A1 他不能干扰他们发送的信息，通过 A2 他不能通过引入虚假信息来混淆他们之间的交流。假设 A3 将挫败一个试图仅仅通过不发送信息来阻止一个决定的叛徒。这些假设的实际应用将在第 6 节中讨论。
? 本节和下面的算法要求每个通用程序都能够直接向其他通用程序发送消息。在第 5节中，我们描述了不具备这一要求的算法。叛国指挥官可以决定不下达任何命令。由于中尉们必须服从一些命令，在这种情况下，他们需要一些默认命令来服从。我们让 retreat 是这个默认顺序。
? 我们归纳性地定义了所有非负整数的口头协议算法 OM(m)，通过这些算法，指挥官可以向 n-1 中尉发送命令。我们证明 OM(m)在最多 m 叛徒面前解决 3m+1 或更多的将军的拜占庭将军问题。我们发现用“获得一个值”而不是“服从一个值”来描述这个算法更方便排序".
该算法假设函数 majority 具有如下性质:如果大多数值 vi = v，则 majority(V1,…,Vn)=v .(实际上，它假定了一系列这样的函数——每个 n )对于函数majority(V1,…Vn)的值有两个自然的选择:
1. 如果大多数值中存在vi，否则为 retreat; 2. 假设它们来自一个有序集合,选择中位数 vi 。

下面的算法只需要上述的majority（）性质。
Algorithm OM(0).
(1) 指挥官把他的价值传递给每个中尉。 (2) 每个中尉使用他从指挥官那里得到的价值，或者如果他没有得到价值就使用 RETREAT。

Algorithm OM(m), m > O
(1) 指挥官把他的价值传递给每个中尉。 (2)对每一个中尉i,令vi为中尉i收到的命令，如果没有收到则使用撤退。中尉i作为算法OM(m-1) 的指挥官，发送vi给余下的n-2个将领。 (3)对每一个 i和j(i！=j),令vj为第二步（2）将领i从将领j获得的信息，如果没有收到则使用撤退。将领i使用majority（v1 ,…,vn-1）的值作为最终命令值。

? 为了理解这个算法是如何工作的，我们考虑 m=1，n=4 的情况。图 3 展示了当指挥官发送值v 而中尉 3 是叛徒时，中尉 2 接收到的消息。在 OM(1)的第一步中，指挥官向所有三名中尉发送 v。在第二步中，Lieutenant1 使用平凡算法 OM(0)将值 v 发送给 Lieutenant2。同样在第二个步骤中，叛变的中尉 3 给中尉 2 一些其他的值 x。在步骤 3 中，中尉 2 然后有 v1=v2 和v3=x，所以他得到正确的value v = majority ( v , v, x) .值 v=majorty(v，v，x)。证明过程https://www.jianshu.com/p/538e6c9fac81
? 接下来，我们看看如果指挥官是叛徒会发生什么。图 4 显示了如果一个叛变的指挥官将三个任意值 x、y 和 z 发送给三个中尉，中尉们所接收到的值。每个中尉得到v1 = x, v2 = y, and v3 = z, 因此在步骤(3)中它们都得到相同的值majority(x，y，z)，不管这三个值 x，y 和 z 是否相等。
图3：副官是叛徒
第一步：司令向每个副官发送他的值vvv给每个副官；
第二步：副官1执行OM(0)，作为司令向副官2发送v；由于副官3是叛徒，其执行OM(0)向副官2发送了不同的值，假设为x；
第三步：副官2拥有的行动值集为{v1,v2,v3}={v,v,x}，采用majority函数，副官2采取的行动v=majority{v1,v2,v3}
同理，副官1采取的行动指令也是v，即满足拜占庭将军问题一致性条件IC1和IC2。
拜占庭问题论文翻译
文章图片
图4：将军是叛徒
第一步：司令为了阻止忠诚副官达成一致，分别向三位副官发送值{x,y,z}{x, y, z}{x,y,z};
第二步：每个副官从司令收到的值作为自己的值，并执行OM(0)向其他副官发送；
第三步：在第三步中，每个副官拥有的值集均为{x,y,z}{x, y, z}{x,y,z}，因此，副官执行行动函数majority得到的结果是一样的。
由于三位忠诚的将军采取同样的行动，满足拜占庭将军一致性条件IC1。
**从m=1, n=4的例子可以看出，OM(m)算法能够处理拜占庭将军问题。递归算法 OM(m)调用算法 OM(m-1)的 n-1 个独立执行，每个执行都调用 OM(m-2)等的 n- 2 个执行。**这意味着，对于 m>1，一个中尉会给彼此发送许多不同的信息。必须有某种方法来区分这些不同的信息。读者可以验证，如果每个中尉 i 在步骤(2)中将数字 i 前缀为他发送的值 vi，那么所有的模糊性都消除了。随着递归的“展开”，算法 OM(m-k)将被调用(n-1)…(n-k)次，以发送一个以 k 中尉的数字序列为前缀的值。
**为了证明算法OM(m)，**对任意的m,的正确性。首先证明以下引理。
Lemma1. 对任意的m和k,如果将军个数大于2k+m，有最多k个叛徒，算法 OM(m)满足IC2 。
证明：针对m的取值情况进行分析。
1.m= 0，忠诚的将军只要服从将军的命令就可以了，引理成立。
2.假设m-1，m>0,时算法满足IC2，证明对m 成立。（归纳法）
算法第一步（1），忠诚的司令发送值v给n-1个将领。第二步（2），每一个忠诚的将领调用算法OM(m-1)。
n>2k+m => n-1>2k+(m -1)>2k，多数的将领是忠诚的，每一个忠诚的将领得到一个vi=v 从n-1个值i中，在第三步majority(v1,…,vn-1)=v，满足IC2.
证明算法成立的定理1：
Theorem1.对任意的m,在人数大于3m，有m个叛徒的情况下，算法OM(m)满足条件IC1和条件IC2。
证明：针对m的取值情况进行分析。
1.m= 0，定理成立。
2.假设m-1，m>0,时成立，证明对m 成立。（归纳法）
在司令忠诚的情况下，令m=k,根据引理1可知，IC2成立从而IC1成立。
所以只需要证明司令是叛徒的情况。有最多m个叛徒，司令为其中一个，所以还有m-1个将领是叛徒。人数大于3m,所以将领人数大于3m-1。
3m-1>3(m-1)
使用归纳假设法证明OM(m-1)满足条件CI1和CI2。因此，在第三步，对每一个j,任意两个忠诚的将军获得相同的值vj。从而任意两个忠诚的将军获得相同的值 在函数majority(v1,…,v**n-1)在第三步，IC1的证。
4.带签名信息的解决方案
正如我们在图 1 和图 2 中看到的场景，正是叛徒撒谎的能力使得拜占庭将军问题变得如此困难。如果我们能够限制这种能力，问题就会变得更容易解决。一种方法是允许将军们发送不可伪造的签名信息。更确切地说，我们在 A1-A3以下假设:
A4 (a) 忠诚的将军的签名是不能伪造的，并且可以检测到他签名信息内容的任何变更。 (b) 任何人都可以核实将军签字的真实性。 请注意，我们对叛国将军的签名不做任何假设。特别是，我们允许另一个叛徒伪造他的签名，从而允许叛徒之间相互勾结。

现在，我们已经介绍了签名信息，我们以前的论点，即四个将军必须处理一个叛徒不再成立。事实上，确实存在三个通用解决方案。我们现在给出了一个算法，可以处理任意数量的将军的万叛徒。(如果少于 m+2 个将军，问题就是空洞的。)
在我们的算法中，指挥官向每个副官发送一个签名命令。然后每个中尉在命令上签名，并将其发送给其他中尉，中尉再加上他们的签名，然后再发送给其他人，如此类推。这意味着中尉必须有效地接收一条签名信息，复制几份，并签名和发送这些副本。如何获得这些副本并不重要; 一条消息可能是复印的，或者每条消息可能由一堆相同的消息组成，这些消息根据需要进行了签名和分发。
算法定义一个选择函数choice,其在一个集合命令信息中选出一个，如下：
1.如果集合V只有一个值v,Choice(V) = v。 2.choice(?) = RETREAT(撤退)。空集情况下。

? 可以注意到，可选择中值为函数的值。
定义
x:i 表示被将军i签名的值x ，则v:j:i 表示值v被将军j签名以后，然后又被将军i签名。令将军0号为命令的发送者。在算法里每一个将领i都有一个集合Vi ,集合里面包括他收到的被其他将军签名的信息。
算法SM(m).
初始化 Vi =?.
(1)司令发送其签名信息v:0给每一个将领。
(2)对每一个将领i ：
(A)如果将领 i 收到从司令v:0，且其Vi =?。 其操作如下：
? (i)他令其Vi ={v}；
? (ii)他发送v:0：i给每一个其他的将领.
? (B)如果将领 i 收到信息v:0：j1:…:jk ,且v?Vi，则：
? (i)他将v加入自己的集合Vi；
? (ii)如果k<m,则其发送v:0：j1:…:jk:i 给其他的将领?j1，…，jk。
(3)对每一个将领i ：当将领i 不再收到信息后，其遵守choice(Vi)
注意，在第二步中，副官i将忽略任意值已经在Vi出现的消息。通过对k的归纳，对于每个副官序列j1,…,jk , 且k 举例： m=1, n=3
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AXBM88Aw-1587040554637)(https://hongery.github.io/images/bft/bft4.png)]
在第(1)步，司令发送发送“attack”给副官1并发送“retreat”给副官2；
在第(2)步，每个副官将收到两个命令值，即V1=V2={"attack","retreat"}
在第(3)步，两个忠诚的副官执行choice(Vi得到的结果也是一样的。
因此，当司令叛徒时，算法满足条件IC1。
当司令是忠诚的时，叛徒副官无法篡改司令的命令，因此忠诚的副官的行动值集Vi只有一个元素，即司令发送的命令。因此，SM(m)算法满足条件IC1和IC2。
定理2.对任意的m，在至多m个叛徒的情况下，算法SM(m)解决拜占庭问题。
证明，在司令是忠诚的情况下，没有信息可被篡改。显然成立。
在司令是叛徒的情况下，需要证明IC1成立，则任意两个忠诚的将领i和j将遵循第三步获得的一致的命令。所以必须证明 将领i和j在第二步将相同的命令信息放进自己的集合。情况分析,可得有以下两种情况，如果将军i获得信息v,他把信息发送给将军j。如果将军i获得信息v：0：j1:…:jk ，且j在签名当中，则j已经把值v放进自己的集合。如果j不在签名当中,分析两种情况：
1.k

证明结束。
5.通讯路径缺失
? 到目前为止，我们假设一个将军可以直接向其他所有将军发送消息。我们现在移除这个假设。相反，我们认为物理障碍对谁可以向谁发送信息设置了一些限制。我们认为将军构成一个简单的 2 个有限无向图 g 的节点，其中两个节点之间的弧表示这两个将军可以发送消息
2 一个简单图是这样一个图，其中最多有一条弧连接任意两个节点，每条弧连接两个不同的节点。
接下来 对算法OM(m)和SM(m)进行拓展，G 为全联通图。
首先对算法OM(m)进行拓展，给出以下定义：
定义1.
(a)节点集合{i1 ,…,ip}为节点i的正则邻接集，满足：
(i)每一个i j都邻接点 i
(ii)对任意的将军 k （k 和 i 不相等），则有路径 γj,k ,从 ij 到 k 无需通过 i，且任意两条路径 γj,k 除了节点 k 没 有共同节点。
(b)图 G 是 p正则的 ，如果每个节点的正则集都有 p 个不同的节点。
如图所示，图六是 3-正则图，每个节点有三个度（三条边）。
图七 不是 3-正则图 ，中间节点有四条边。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fRvdNybD-1587040554654)(https://hongery.github.io/images/bft/bft5.png)]
拓展的OM(m,p)算法
m个叛徒 ，G 为 3-正则图。（注意到， 3m-正则图 必至少含有 3m +1 个节点 ）。对任意的正整数 m , p 。且将军通信情况构成 p-正则图。通过分析 m 如下：
算法 OM(m,p).
(0)选择司令（commander）的正则邻接集 N (含有 p 个 将领)。p为3
(1) 司令将信息发送给集合 N 里的每一个将领。
(2)对每一个 i ∈ N ，令 vi 为 将领 i 收到的从司令发过来的命令，或者没有收到信息则默认为 撤退 （RETREAT）。将领 i 按照以下规则将 vi 发送给其他将领 k：
(A) 如果 m = 1 通过路径 γj,k 发送信息，路径存在定义1由(a)(ii)保证.
(B)如果 m > 1 ,则 将领 i扮演司令的角色在OM(m-1,p-1)，图由去掉原先的司令构成。
(3)对 每一个 k ，和 i ∈ N ， k ≠ i 。令 vi 为将领 k 从 i （i 在第二步（2））） 收到的信息，或者 RETREAT 如 果没有收到信息。将领 k 使用 函数值 majority(vi，… ,v ~i p~), N = {i1 ，… , ip }.
接下来证明 在至多 m 个叛徒的情况下 ，OM(m,3m) 解决拜占庭将军问题 。首先对引理1 进行拓展（见 一）。
定理2：
Lemma 2 .对任意的 m >0 和任意的 p ≥ 2k + m ，如果至多有 k 个叛徒 ，算法 OM(m,p)满足条件IC2(见一)。
证明
? 当 m = 1, 注意到 一个将领获得的值 majority(v1，… ,v p) 中，每一个 vi 的命令发送者是通过不相交的路径发送的信息。且至多有 k 个叛徒. 在 p ≥ 2k + m 的情况下知道 忠诚将军的人数超过半数。当将军是忠诚的情况下，算法保证IC2 从而的证。运用归纳法可得对 m -1, m >1 .引理成立。
继续证明…
定理 3：
Theorem 3. 对任意的 m >0 和对任意的 p ≥ 3m ,在至多 m 叛徒的情况下 ，算法OM(m,p) 解决拜占庭问题。
证明。根据引理2，令 k = m ,可知算法满足IC2，在司令是忠诚的情况下。现在只需要证明司令为叛徒的情况。假设所有忠诚的将领再第三步（3）要获得一致的值 v i 集合.
? 如果 m = 1,则所有将领都是忠诚的，成立。
? 如果 m >1 ,简单的归纳 p ≥ 3m 可得 p -1 ≥ 3 (m -1) ，算法成立。
? 证毕。
算法假设图G 为3-正则 ，是一个条件很强的连通假设。事实上当总共有3m +1人时，3 m-正则意味着全连通，算法OM(m,3m) 可推出 OM(m）。可以看出，拓展算法 SM(m) 只需要更弱的连通条件。
? 分析多少连通条件能解决拜占庭问题。IC2 要求 忠诚的将领服从忠诚的司令，这要求他们之间要能够通信。特别地，当每一条信息都会通过一个叛徒中转的时候，不能保证将领能获得司令的信息。类似的，如果两个将领只能通过有叛徒的路径通信则IC1无法保证。
拜占庭将军的弱连通假设为，忠诚将军构成的G 的子图要互相连接。在这个条件下，总人数为 n ，不管叛徒的个数，算法 SM(n-2)成立。
接下来证明更加普遍的结果。定义一个图的半径为最小的数 d ,任意两个节点相连至多需要 d 条边。
定理4.
Theorem4. 对任意的 m 和 d ,如果有 m 个叛徒且 忠诚将军构成的子图有直径 d, 则 SM(m + d - 1) 解决拜占庭问题。
证明和定理2的证明类似（略）。
推论.如果忠诚将军构成的子图是连接的，则 SM(n - 2)可解决拜占庭问题。
证明，令 d 为忠诚将军构成的图的直径。且已知 d 小于 节点数，所以忠诚将军的人数大于d ，叛徒人数少于 n - d 。令 m = n - d -1 可的证。
可靠的系统大多使用多数票方法保证可靠性，其使用多个处理器得出一致的结果，然后使用多数票表决的方法得到单个值。
使用多数票方法是基于假设不出错的处理器将得到一致的结果。这在它们获得一致的输入时成立。其基于假设出错的处理器不会得到一致的错误结果。但是也有很多其他的情况，无法获得一致的输入，比如出错的程序发送不同的值给其他处理器。比如获取时钟值的时候，很难保证两个处理器获取相同的值等等。所以给出以下前提条件：
1.所有无故障的处理器使用相同的输入。（可以获得相同的输出）
2.如果只输入单元无故障，那么所有无故障的处理器要使用其提供的值作为输入。
这里，司令是作为 输入值的提供者，将领是处理器，忠诚为无故障。
6.可靠的系统
? 除了使用本质上可靠的电路元件，我们知道实现一个可靠的计算机系统的唯一方法是使用几个不同的“处理器”来计算相同的结果，然后对它们的输出进行多数表决，以获得一个单一的值。(投票可以在系统内进行，也可以由输出的用户在外部进行。)无论是使用冗余电路来防止单个芯片故障的可靠计算机，还是使用冗余计算站点来防止单个站点被核攻击破坏的弹道导弹防御系统，都是如此。唯一的区别在于复制的“处理器”的大小。
使用多数表决来实现可靠性是基于所有非故障处理器将产生相同的输出的假设。只要它们都使用相同的输入，这就是正确的。然而，任何单个输入数据都来自单个物理元件——例如，来自可靠计算机中的其他电路，或者来自导弹防御系统中的某个雷达站点——和一个故障定位元件，可以为不同的处理器提供不同的值。此外，不同的处理器可以获得不同的值，甚至从一个非故障的输入单元，如果他们读取的值，而它正在变化。例如，如果两个处理器在时钟前进时读取时钟，那么一个处理器可能获得旧时间，另一个处理器获得新时间。这只能通过与时钟推进同步读操作来防止。可靠的制度，必须满足以下两个条件:
  1. 所有非故障处理器必须使用相同的输入值(因此它们产生相同的输出)。
  2. 如果输入单元是非故障的，那么所有非故障进程都使用它提供的值作为输入(因此它们产生正确的输出)。
这些只是我们的交互式一致性条件 IC1 和 IC2，其中“指挥官”是产生输入的单位，“中尉”是程序，“忠诚”意味着没有错误。
? 尝试用“硬件”解决方案来规避这个问题是很诱人的。例如，可以尝试通过让所有处理器都从相同的线路读取输入值来确保所有处理器获得相同的输入值。然而，一个错误的输入单元可以沿着线路发送一个边际信号----这个信号可以被某些处理器解释为 0，而其他处理器可以解释为 1。没有办法保证不同的处理器将从一个可能出错的输入设备获得相同的值，除非让处理器相互通信来解决拜占庭将军问题。
? 当然，有故障的输入设备可能提供无意义的输入值。一个拜占庭将军解决方案所能做的就是保证所有处理器使用相同的输入值。如果输入是重要的，那么应该有几个独立的输入设备提供冗余值。例如，在导弹防御系统中应该有冗余雷达和冗余处理站点。然而，冗余输入不能实现可靠性，仍然需要确保非故障处理器使用冗余数据产生相同的输出。
? 如果输入设备是非故障的，但是由于它在值变化时被读取而给出不同的值，我们仍然希望非故障处理器获得一个合理的输入值。可以证明，如果多数函数和选择函数都是中值函数，那么我们的算法具有这样的性质，即非故障处理器获得的值在输入单元提供的值范围之内。因此，只要输入单元产生合理的值范围，非故障处理器将获得合理的值。
? 我们已经给出了几种解决方案，但是它们都是用拜占庭式的将军而不是用计算系统来表述的。我们现在研究如何将这些解决方案应用于可靠的计算系统。当然，用处理器实现“通用”算法是没有问题的。问题在于实现满足 A1-A3(算法 SM(m)的 A1-A4 假设)假设的消息传递系统。我们现在按顺序考虑这些假设。
A 1。假设 A1 指出，没有错误的处理器发送的每条消息都是正确的。
在实际系统中，通信线路可能会失灵。对于口信算法 OM(m)和 OM(m，p)，连接两个处理器的通信线路的故障与其中一个处理器的故障是无法区分的。因此，我们只能保证这些算法将工作在存在多达亿故障，无论是处理器或通信线路故障。(当然，连接到同一个处理器的多条通信线路的故障相当于单个处理器的故障。)如果我们假设失败的通信线路不会导致伪造有符号消息——我们将在下面看到这个假设是相当合理的，那么我们的有符号消息算法 SM(m)对通信线路失败不敏感。更准确地说，定理 4 即使在通信线路故障的情况下仍然有效。失败的通信线路与简单地删除通信线路具有同样的效果——它降低了处理器图形的连接性。
A 2。假设 A2 指出，处理器可以确定它所接收的任何消息的发出者。
实际上需要的是有故障的处理器不能模拟一个没有故障的处理器。在实践中，这意味着进程间通信是通过固定的线路而不是通过某些报文交换网络进行的。(如果使用交换网络，那么必须考虑有故障的网络节点，然后拜占庭将军问题节点再次出现。)请注意，如果假设A4 并且所有消息都有签名，则不需要假设 A2，因为模拟另一个处理器将意味着伪造其消息。
A 3。假设 A3 要求可以检测到消息的缺失。
消息的缺失只能通过其未能在某个固定时间内到达来检测——换句话说，通过使用某种超时限制。使用超时来满足 A3 需要两个假设:
  1. 生成和传输消息所需的最长时间是固定的。
  2. 发送方和接收方都有时钟，这些时钟在某个固定的最大误差范围内同步。
第一个假设的必要性是相当明显的，因为接受者必须知道他需要等多久才能收到消息。(生成时间是处理器在接收到生成消息所需的所有输入之后发送消息所需的时间。)第二个假设的必要性就不那么明显了。然而，可以证明这个假设或者一个等价的假设对于解决拜占庭将军问题问题是必要的。更确切地说，假设我们允许算法，将军们只在下列情况下采取行动:
  1. 在某个固定的初始时间(所有的将军都一样)。
  2. 在收到信息后。
  3. 当一段随机选择的时间过去时。(也就是说，一个普通人可以将计时器设置为一个随机值，并在计时器结束时行动。)
{这产生了我们可以想象到的最一般的算法类别，它们不允许构造同步的时钟。)可以证明，如果消息可以任意快速地传递，即使存在消息传递延迟的上界，这种算法也不能解决拜占庭将军问题问题。而且，即使我们限制叛徒，只允许他们不正确的行为是不发送信息，也不可能有解决办法。这个结果的证明超出了本文的范围。请注意，在传输延迟上设置一个下限和一个上限，将使处理器通过来回发送消息来实现时钟。
? 以上两个假设使得检测未发送的消息变得容易。假设/z 是最大的消息生成和传输延迟，并且假设没有故障的处理器的时钟在任何时候最多相差 t。然后，任何非故障进程应该开始在其时钟上按时间 t 生成的消息将在接收方时钟上的时间 t+#+t 到达其目的地。因此，如果接收者到那时还没有接收到消息，那么它可能假设消息没有被发送。(如果它晚一点到达，那么发送者一定是错误的，因此我们的算法的正确性并不取决于发送的消息。)通过对输入处理器发送其值的时间进行 fLxing，可以计算出处理器在自己的时钟上必须等待每条消息的时间。例如，在算法 SM(m)中，处理器必须等到对于任何有+ k(# +~) 签名的消息，其中 To 是指挥官开始执行算法的时间(在他的时钟上)。没有两个时钟以完全相同的速率运行，所以无论最初处理器的时钟同步得多么精确，它们最终会偏离得任意远，除非它们周期性地重新同步。因此，我们面临的问题是，即使有些处理器出现故障，也要保持处理器的时钟同步到某个固定的数量。这是一个和拜占庭将军问题本身一样困难的问题。时钟同步问题的解决方案与我国拜占庭式的解决方案密切相关。它们将在未来的论文中加以描述。
A 4。假设 A4 要求处理器能够以这样一种方式对其消息进行签名，即不能伪造没有错误的处理器签名。
签名是由进程 i 从数据项 m 生成的一段冗余信息 Si(m)。由 i 签名的消息由一对(m，Si(m))组成。满足部分(a)和(b)对于 A4，Si 函数必须具有以下两个性质:
? (a)如果处理器 i 是非故障的，那么没有故障的处理器可以生成 Si(m)。
? (b)给定 M 和 X，任何过程都可以确定 ifX 等于 Si(m)。
属性(a)永远不能得到保证，因为 Si(m)只是一个数据项，故障处理器可能生成任何数据项。然而，我们可以使违反它的概率小到我们所希望的程度，从而使系统如我们所希望的那样可靠。如何做到这一点取决于我们预期会遇到的故障类型。有两个令人感兴趣的案例:
1.随机故障。通过使Si 成为一个适当的“随机化”函数，我们可以使处理器中的一个随机故障产生正确签名的概率本质上等于它通过一个随机选择过程产生正确签名的概率**——即可能签名数目的倒数。下面是一个实现这一点的方法。假设消息被编码为小于 p 的正整数，其中 p 是 2 的幂。设 Si(m)等于 m Ki mod p，其中 Ki 是小于 p 的一个随机选择的奇数。如果另一个处理器的内存中没有 Ki，那么它为单个(非零)消息 m 生成正确签名 m*Ki 的概率应该是 l/p:它通过随机选择生成正确签名 mKi *的概率。(**注意，如果处理器可以通过一些简单的程序获得 Ki，那么在计算时用Ki 代替 k，可能会有更大的可能性出现处理器错误地伪造 i 的签名 Sj(M).)律政司(m))
2.恶意情报。如果错误的处理器被恶意的智能引导*----例如，如果一个完美的处理器被一个试图破坏系统的人操作**----那么信号函数* Si 的构造就成了一个密码学问题。我们建议读者参阅[1]和[4]来讨论如何解决这个问题。
请注意，如果进程已经看到签名，则很容易生成签名 Si(m)。因此，重要的是，相同的消息永远不必被签名两次。这意味着，当重复使用 SM(m)分发一个值序列时，序列号应该附加到值上以保证唯一性。
7.结论
? 在各种假设下，我们已经向拜占庭将军问题提出了几种解决方案，并展示了如何使用它们来实现可靠的计算机系统。这些解决方案在时间量和所需的消息数量上都很昂贵。算法 OM(m)和 SM(m)都要求消息路径的长度达到 m+1。换句话说，每个中尉可能不得不等待来自指挥官的信息，然后通过其他名中尉转发。费舍尔和林奇已经证明，这对任何可以对付万叛徒的解决方案都是正确的，所以我们的解决方案在这方面是最佳的。对于不完全连通的图，我们的算法需要长度为 m+d 的消息路径，其中 d 是忠诚将军子图的直径。我们认为这也是最佳选择。
? 算法 OM(m)和 SM(m)包括发送到(n-1)(n-2)…。(n-m-1)信息。通过组合消息，必然可以减少所需的单独消息的数量。也许还可以减少传输的信息量，但这一点尚未得到详细研究。但是，我们预计仍然需要大量的消息。
? 在任意故障的情况下实现可靠性是一个困难的问题，其解决方案似乎本身就代价高昂。降低成本的唯一方法是对可能发生的故障类型进行假设。例如，通常假设计算机可能无法响应，但是绝不会错误响应。然而，当需要极高的可靠性时，这样的假设是不可能做出的，并且需要一个拜占庭将军解决方案的全部费用。

    推荐阅读


    上一篇：图神经网络|MPNN（message passing neural networks）

    下一篇：【个人笔记】2020-8-22 Night