OM算法
拜占庭将军问题
拜占庭将军问题是经典的共识问题之一。假设有
N
N
N个拜占庭将军，每个人都指挥一个同样规模的军队，包围了一座地方城市。而拜占庭将军之间，是地理隔离的，他们之间只能通过信使送信进行交流。为了合作进攻，每个将军向其他将军送信传送消息进行投票来决定是否进攻。也就是说，每个将军会给其他
N
−
1
N-1
N−1个将军派遣信使，信使会携带一个写着“进攻”或者“撤退”的信，当将军收到的“进攻”数量大于“撤退”数量的时候，就进攻，反之撤退。
然而，敌军也不会坐以待毙，早已在将军的信使里面安插了间谍，他们通过送和原本的内容相反的信，来干扰投票。
那么，我们通过设计一个什么样的算法，来使各个将军之间达成共识呢？
口头消息传递（Oral Messaging, OM）算法
这是最初的拜占庭将军问题的解决方案，下面将以伪代码的形式讲解OM算法，注意Default是预定值， f f f是最多有 f f f个将军有故障
BEGIN OM(f):
- 指挥官将值发送给每个中尉
- f o r for for i = 1 : N − 1 i=1:N-1 i=1:N−1 d o do do
- i f if if 中尉收到了值:
- 中尉 i i i将从指挥官收到的值存储为 v i , i v_{i,i} vi,i;
- e l s e else else:
- v i , i = D e f a u l t v_{i,i}=Default vi,i=Default
- e n d end end f o r for for
- f o r for for i = 1 : N − 1 i=1:N-1 i=1:N−1 d o do do
- f o r for for j = 1 : N − 1 j=1:N-1 j=1:N−1 and j ≠ i j\neq i j=i d o do do
- i f if if 中尉收到了值:
- 中尉 i i i将从中尉 j j j收到的值存储为 v i , j v_{i,j} vi,j;
- e l s e else else:
- v i , j = D e f a u l t v_{i,j}=Default vi,j=Default
- e n d end end f o r for for
- 中尉 i i i使用majority{ v i , 1 , v i , 2 … v i , N − 1 v_{i,1},v_{i,2}…v_{i,N-1} vi,1,vi,2…vi,N−1}
- e n d end end f o r for for
当算法进行到 f = 0 f=0 f=0的时候，算法变成：文章来源：https://www.toymoban.com/news/detail-816558.html
BEGIN OM(0):
- 指挥官给每个中尉发送值：
- f o r for for i = 1 i=1 i=1: N − 1 N-1 N−1 d o do do
- i f if if 中尉 i i i收到了值
- 中尉 i i i将指挥官发送的值存为 v i , i v_{i,i} vi,i;
- e l s e else else:
- v i , i = D e f a u l t v_{i,i}=Default vi,i=Default
- 中尉使用 v i , i v_{i,i} vi,i
- e n d end end f o r for for
当 N ≥ 3 f + 1 N\geq3f+1 N≥3f+1的时候算法就可以达成共识。但是很明显，这是一个递归算法算法的复杂度是指数增长的，对于现在互联网中海量的节点而言，这个算法不现实。文章来源地址https://www.toymoban.com/news/detail-816558.html
到了这里，关于区块链安全理论与实践（Blockchain for Distributed Systems Security）阅读笔记D4——OM算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
