OM算法
拜占庭將軍問題
拜占庭將軍問題是經(jīng)典的共識問題之一。假設(shè)有
N
N
N個拜占庭將軍，每個人都指揮一個同樣規(guī)模的軍隊，包圍了一座地方城市。而拜占庭將軍之間，是地理隔離的，他們之間只能通過信使送信進行交流。為了合作進攻，每個將軍向其他將軍送信傳送消息進行投票來決定是否進攻。也就是說，每個將軍會給其他
N
?
1
N-1
N?1個將軍派遣信使，信使會攜帶一個寫著“進攻”或者“撤退”的信，當將軍收到的“進攻”數(shù)量大于“撤退”數(shù)量的時候，就進攻，反之撤退。
然而，敵軍也不會坐以待斃，早已在將軍的信使里面安插了間諜，他們通過送和原本的內(nèi)容相反的信，來干擾投票。
那么，我們通過設(shè)計一個什么樣的算法，來使各個將軍之間達成共識呢？
口頭消息傳遞（Oral Messaging, OM）算法
這是最初的拜占庭將軍問題的解決方案，下面將以偽代碼的形式講解OM算法，注意Default是預(yù)定值， f f f是最多有 f f f個將軍有故障
BEGIN OM(f):
- 指揮官將值發(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的時候，算法變成：文章來源：http://www.zghlxwxcb.cn/news/detail-816558.html
BEGIN OM(0):
- 指揮官給每個中尉發(fā)送值：
- 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將指揮官發(fā)送的值存為 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的時候算法就可以達成共識。但是很明顯，這是一個遞歸算法算法的復(fù)雜度是指數(shù)增長的，對于現(xiàn)在互聯(lián)網(wǎng)中海量的節(jié)點而言，這個算法不現(xiàn)實。文章來源地址http://www.zghlxwxcb.cn/news/detail-816558.html
到了這里，關(guān)于區(qū)塊鏈安全理論與實踐（Blockchain for Distributed Systems Security）閱讀筆記D4——OM算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
