咱们都知道，诸葛亮第一次北伐是最或许成功的，魏国没有防备，还策反了陇西，陇西有很多的马匹能够配备蜀国骑兵，可惜街亭一丢，那边就守不住了
当时我不在，只能作诗一首~
假如穿越曩昔，我将会向丞相献上一计，别说街亭，直接拿下长安，先看地图
从延安，洛阳，策反魏国州长，让他们出动戎行。然后再结盟孙权，让他从久攻不下的合肥调来800精兵从襄阳进攻，让魏延从宝鸡出动戎行，自己带领大军从汉中进发
五路进犯，光围都能把长安围死
可是这个时分你或许会说：天方夜谭，且不说孙权，你怎么能确保洛阳和延安的兵听你的，而不是反贼？
这个呢，就需要咱们今天要讲的问题，也称为【拜占庭将军问题】，多节点场景，没有中心化的协调，并且其间或许呈现不可靠结点的情况下，怎么确保咱们举动的统一性？
咱们先约好一些一致：
- 一个丞相发送指令，四个将军接收
- 一切人都或许是反贼
- 反贼回复的指令和丞相的相反
现在咱们模拟一个场景，必须要五路进发才能够打下长安，其间有反贼。当主路——也便是诸葛亮的那一路发出“进攻”指令时，其他四路的将军会收到，同时会向其他三路求证，假如进攻指令数过半数，就会进攻。可是反贼会回复其他将军【撤退】指令
假如反贼过多，导致【撤退】指令过多，一切的将军都不会出动，丞相只能自己北伐了
-
那么此时忠反比多少才适宜呢？
关键在于，即使有反贼存在，只需忠臣数量足够多，就能够确保最终的决议计划是正确的。 这是由于反贼无法破坏一切将军之间的通信，因此忠臣能够经过相互交流，确认反贼的存在并扫除他们的虚伪音讯。最终的决议计划取决于忠臣的数量，通常情况下，当忠臣数量超过总将军数量的三分之二时，算法能够确保正确性。
-
那么为什么是三分之二呢？不是更多或许更少？
假定发指令的是丞相，其他为将军，总数为n, 反贼数为m，
其间每一个将军做判别的依据是接受到的指令取大都，
每个将军自己在判别时，只会考虑其他将军和丞相的指令，扫除自己，所以此时有n – 1个指令，那么会呈现 m 个假指令和n – m – 1 个真指令
只需确保 n – m – 1 > m，也便是 n > 2m + 1即可
这是基本情况，当n = 3, m = 1时，满足n > 2m + 1，可是忠臣只会收到一个真指令和一个假指令，无法判别丞相或许另一个将军谁是反贼，所以为了确保取
n > 3m，也便是忠臣占2/3大都
下面是一个简略的Java代码示例，演示了怎么处理这个问题。
假定有6个将军，其间两个是反贼。每个将军都有一个仅有的ID和一个决议计划（attack或retreat）。这些将军之间经过音讯传递来达成一致。
import java.util.Arrays;
import java.util.Random;
public class ByzantineGenerals {
private static final int NUM_GENERALS = 6;
private static final int REPEAT = 5;
static int traitor;
static int traitor2;
public static void main(String[] args) {
String[] orders = new String[NUM_GENERALS]; // 指令调集
for (int p = 0; p < REPEAT; p++) {
traitor = new Random().nextInt(NUM_GENERALS - 1);
traitor2 = new Random().nextInt(NUM_GENERALS);
if (traitor == traitor2) traitor2 += 1;
for (int i = 0; i < NUM_GENERALS; i++) {
orders[i] = (i == traitor || i == traitor2) ? "retreat" : "attack";
}
System.out.println("orders" + Arrays.toString(orders));
boolean finalDecision = computeFinalDecision(orders);
System.out.println("Final decision: " + (finalDecision ? "attack" : "retreat"));
System.out.println();
}
}
private static boolean computeFinalDecision(String[] orders) {
boolean[] decisions = new boolean[NUM_GENERALS];
for (int i = 0; i < NUM_GENERALS; i++) {
if (i == traitor || i == traitor2) {
decisions[i] = (new Random().nextBoolean());
} else {
boolean[] receivedOrders = new boolean[NUM_GENERALS - 1];
int index = 0;
for (int j = 0; j < NUM_GENERALS; j++) {
if (j != i) {
receivedOrders[index++] = (orders[j].equals("attack")); // 每一位将军收集指令
}
}
decisions[i] = computeDecision(receivedOrders);
}
}
return computeDecision(decisions);
}
private static boolean computeDecision(boolean[] decisions) {
// Compute the majority decision
int numTrue = 0;
int numFalse = 0;
for (boolean decision : decisions) {
if (decision) {
numTrue++;
} else {
numFalse++;
}
}
return (numTrue > numFalse);
}
}
在上面的示例代码中，咱们模拟了一个有6个将军的场景，并随机指定两个将军为反贼。每个将军都有一个决议计划，进犯或撤退。假如将军是反贼，他将发送虚伪的指令，不然，将军将发送他真正的指令。在每个将军之间进行音讯传递后，每个将军都会收到其他将军发送的指令。假如将军是反贼，他或许会给每个将军发送不同的指令，而忠臣将发送相同的指令。最终，每个将军都会将他们收到的指令和自己的指令一起计算出一个最终的决议计划，并将它们合并成一个一起的决议计划。
在计算决议计划的过程中，咱们运用了一个简略的投票算法。咱们将每个将军的决议计划转换为一个布尔值（attack为true，retreat为false），然后计算出这些布尔值中呈现次数最多的值。假如attack呈现的次数比retreat多，则咱们最终的决议计划为attack，不然为retreat。
输出之一如下
orders[retreat, retreat, attack, attack, attack, attack]
Final decision: attack
orders[attack, attack, retreat, retreat, attack, attack]
Final decision: attack
orders[attack, attack, attack, retreat, retreat, attack]
Final decision: attack
orders[attack, attack, retreat, attack, retreat, attack]
Final decision: attack
orders[retreat, attack, attack, attack, attack, retreat]
Final decision: attack
能够看到在6个将军2个反贼下是契合 n > 2m + 1的场景，所以咱们都是进攻
在n = 3， m = 1时，n > 2m + 1需要替换为 n > 3m
稳妥起见取 n > 3m即可
同时，假如诸葛亮运用我的计谋，五路取长安，那么完全能够兴复汉室，还于旧都。剩下的只需要处理这一计谋上面的两朵小乌云即可
- 怎么防止孙权背刺
- 怎么策反魏国两个地方的戎行
