OM算法

拜占庭将军问题

拜占庭将军问题是经典的共识问题之一。假设有$N$个拜占庭将军每个人都指挥一个同样规模的军队包围了一座地方城市。而拜占庭将军之间是地理隔离的他们之间只能通过信使送信进行交流。为了合作进攻每个将军向其他将军送信传送消息进行投票来决定是否进攻。也就是说每个将军会给其他$N-1$个将军派遣信使信使会携带一个写着“进攻”或者“撤退”的信当将军收到的“进攻”数量大于“撤退”数量的时候就进攻反之撤退。
然而敌军也不会坐以待毙早已在将军的信使里面安插了间谍他们通过送和原本的内容相反的信来干扰投票。
那么我们通过设计一个什么样的算法来使各个将军之间达成共识呢

口头消息传递Oral Messaging, OM算法

这是最初的拜占庭将军问题的解决方案下面将以伪代码的形式讲解OM算法注意Default是预定值$f$是最多有$f$个将军有故障

BEGIN OM(f):

1. 指挥官将值发送给每个中尉
2. $for$ $i=1:N-1$ $do$
3.       $if$ 中尉收到了值:
4.            中尉$i$将从指挥官收到的值存储为$v_{i,i}$;
5.       $else$:
6.           $v_{i,i}=Default$
7. $end$ $for$
8. $for$ $i=1:N-1$ $do$
9.       $for$ $j=1:N-1$ and $j\ne i$ $do$
10.                  $if$ 中尉收到了值:
11.                         中尉$i$将从中尉$j$收到的值存储为$v_{i,j}$;
12.                  $else$:
13.                          $v_{i,j}=Default$
14.         $end$ $for$
15. 中尉$i$使用majority{$v_{i,1},v_{i,2}\dots v_{i,N-1}$}
16. $end$ $for$

当算法进行到$f=0$的时候算法变成

BEGIN OM(0):

1. 指挥官给每个中尉发送值
2. $for$ $i=1$:$N-1$ $do$
3.      $if$ 中尉$i$收到了值
4.            中尉$i$将指挥官发送的值存为$v_{i,i}$;
5.      $else$:
6.            $v_{i,i}=Default$
7.      中尉使用$v_{i,i}$
8. $end$ $for$

当$N\ge 3f+1$的时候算法就可以达成共识。但是很明显这是一个递归算法算法的复杂度是指数增长的对于现在互联网中海量的节点而言这个算法不现实。