OM 算法最難理解的地方在于 它為什么是遞歸的。

如果算法正確，其的目標(biāo)狀態(tài)是：

IC1.所有忠誠的下屬都遵守相同的命令
IC2.如果發(fā)令將軍是忠誠的，那么每個忠誠的下屬必須遵守他發(fā)出的命令

遞歸的根本目的是解決當(dāng) 發(fā)令將軍是叛徒時 忠誠副官接受命令一致性的問題（當(dāng)確定只有副官是叛徒時，似乎不需要遞歸，只要副官之間廣播一輪命令即可，但是使用遞歸解也沒問題）。

舉例：假設(shè)將軍數(shù)為 7，其中叛徒數(shù)為 2. 設(shè)發(fā)令將軍為 C，其它人為 G1 ~ G6。

算法推導(dǎo)過程：

最直觀的方式是，G1 ~ G6 直接遵守 C 的指令。但這顯然是不行的，因為 C 可能是叛徒，直接遵守會違反 1C1。

所以，我們要防發(fā)令將軍是叛徒的情況。一種直觀的方法是每個副官都看看其它各個副官都接收到了 C 發(fā)的什么命令。假設(shè)此時輪到 G1 做決策是否接受命令，它想辦法知道其它副官得到的命令是 (v2 ~ v6)。如果 C 是叛徒，也沒關(guān)系，只要 G1 采用 v1 ~ v6 中的大多數(shù)即可。其它將軍也采用 v1 ~ v6 中的大多數(shù)即可。

但是事情沒有這么簡單，因為除了發(fā)令官還有 1 個叛徒，這會造成下面的問題：

假設(shè) C 和 G6 是叛徒（注意此時出現(xiàn)了發(fā)令將軍是叛徒的情況），那么 G1 收到的結(jié)果 (v1, v2, v3, v4, v5, v6) 可能會是 (A, A, A, R, R, R)， G2 收到的可能是 (A, A, R, R, R, R)，此時 G1 和 G2 求大多數(shù)時可能會得到不一樣的結(jié)果。

那此時 G1 不能直接用 v2 ~ v6，G2 同理不能直接用 v1, v3 ~ v6，因為第二個叛徒 G6 的存在，可能導(dǎo)致每個副官接收到由 G6 發(fā)出的命令是不同的。

我們此時發(fā)現(xiàn)，這個算法 OM(2) 本身就是為了獲得一個 根據(jù) C 指令得到的 G1 ~ G6 一致值。那么我們只要以 G1 ~ G6 分別為發(fā)令將軍，遞歸的執(zhí)行一下算法 OM(1) 就可以使 G1 ~ G6 中忠誠的副官獲得全局一致的命令。

舉例，以 G1 為發(fā)令將軍 G2 ~ G6 為副官執(zhí)行 OM(1) 算法，結(jié)果是 G2 ~ G6 都獲得了相同的 G1 的命令。如果 G1 是忠誠的，那么 G2 ~ G6 獲得的命令和 G1 接收到 C 命令相同。如果 G1 是叛徒，G2 ~ G6 也至少能在內(nèi)部達(dá)成一個一致的命令。同理，分別以 G2 ~ G6 為發(fā)令將軍執(zhí)行 OM(1) 算法，最終，G1 ~ G6 每個將軍獲得的除自己之外的其它某個將軍 GX 的指令都是相同的。

最后，G1 把 OM(1) 過程得到的 G2 ~ G6 的結(jié)果求 majority，就是 v1。

為更精確的描述，下面用 python 代碼模擬上述的過程。假設(shè)有 n 個將軍，其中有 m 個叛徒，且 n > 3m。令 L 表示副官集合，c 表示發(fā)令將軍，c 不屬于 L。v 表示發(fā)令官發(fā)出的命令，取 [0, 1] 分別表示進(jìn)攻和撤退。

# -*- coding: UTF-8 -*-

import json

loyalMap = {}; # generalId to True/False map

def isLoyal(i):
    return loyalMap[i]

def majority(R):
    values = R.values()
    print "get majority from " + json.dumps(values)
    count = -1
    curVal = -1
    for v in values:
        if v == curVal:
            count += 1
        else:
            count -= 1
            if count < 0:
                curVal = v
                count += 1
    if count < 0:
        raise Exception, "No majority found"
    return curVal

# 當(dāng) len(L) > 3m 時，該算法可以返回正確結(jié)果
def OM(m, c, L, v):     # 返回以 c 為發(fā)令官，副官們采納的命令
    V = {}                      # 存放 L 中每個副官采納的 c 的命令
    if (m == 0):
        for i in L:
            V[i] = v
        return V
    T = {}               # 存放發(fā)令官 c 向每個副官發(fā)出的命令
    for i in L:
        if isLoyal(c):
            T[i] = v     # 副官 i 接收到 c 的一致的命令
        else:
            T[i] = 1-v
    R = {}               # 存放 OM m - 1 輪遞歸后每個將軍采納的命令 dict
    for i in L:
        R_i = OM(m - 1, i, L - {i}, T[i])    # 存放 OM m - 1 輪遞歸中以 i 為發(fā)令官的采納的命令 dict
        R_i[i] = T[i]
        R[i] = R_i
    RT = {}                                           # R 的轉(zhuǎn)置 dict
    for i in R:
        for j in R[i]:
            if j not in RT:
                RT[j] = {}
            RT[j][i] = R[i][j]
    for i in L:
        V[i] = majority(RT[i]);
    return V

if __name__ == '__main__':
    loyalMap = {"commander":True, "l1":True, "l2":False, "l3":True, "l4": False, "l5": True, "l6": True}
    v1 = OM(2, "commander", set(loyalMap.keys()) - {"commander"}, 1)
    print v1