答案基于<The Byzantine Generals Problem>,
Lamport最负盛名Paxos系列, 我还没看, 不过迟早也要看的.
11位拜占庭将军去打仗, 他们各自有权力观测敌情并作出判断, 进攻或撤退, 那么怎么让他们只用传令兵达成一致呢?
一种很符合直觉的方法就是投票,
每位将军作出决定后都将结果"广播"给其余所有将军, 这样所有将军都能获得同样的11份(包括自己)结果, 取多数, 即可得到全军都同意的行为.
但如果这11位将军中有间谍呢? 假设有9位忠诚的将军, 5位判断进攻, 4位判断撤退, 还有2个间谍恶意判断撤退, 虽然结果是错误的撤退, 但这种情况完全是允许的. 因为这11位将军依然保持着状态一致性.
暂时从战争故事中抽离出来, 分布式数据库最糟糕的问题绝对不是写入或者读取失败, 而是状态不同步, 还感知不到. 这个的后果就是correctness不能保证, 那程序就没有任何意义了.
2个间谍怎么破坏状态一致性呢? 他们跟5位判断进攻的将军说, 我们支持进攻, 那么这5位将军统计发现7位支持进攻, 4位支持撤退, 将发动进攻. 又跟4位撤退的将军说, 我们支持撤退, 一统计, 5票进攻, 6票撤退, 立马撤退. 这场战争必输无疑了.
避免这种状态不同步的问题, 我称之为"广义拜占庭将军问题".
Lamport继续将这个问题规约为更小的问题,
解决广义拜占庭问题, 必须满足两个条件:
上面的条件等价于如何让一个将军(可以是间谍, 论文叫commander)对所有接收者(lieutenant)的指令(order)保持一致? 这个我叫"狭义拜占庭将军问题".
算法分口头版和签名版,
口头版对传令兵(messager)的要求仅有,
总的来说, 这是一个非常严苛的模型, 我觉得Lamport在发表Paxos, 或者有人实现分布式数据库的时候一定不会用这个模型.
算法描述如下,
OM(0): 0个叛徒的case, 正确性显而易见
OM(m): m个叛徒
最最核心的是OM(m)的步骤2, 为什么lieutenant不能接受commander的指令而要递归?
因为commander有可能是叛徒! 他会给不同的lieutenant不同的指令.
所以, 悲催的忠臣必须问所有别的将军, "你们收到的commander的观测结果是啥?"来取majority校验, 同时又必须告诉所有别的将军, "我收到的commander的观测结果是啥?".
但该死的是, 忠臣A在告诉别的将军来自commander的观测结果的时候, 别的将军会怀疑忠臣A是不是叛徒. 别的将军判断忠臣A是忠臣的唯一的办法是询问别的忠臣A通知的忠臣, "忠臣A告诉你commander都发了啥?"
每次递归都做悲观预期即commander是个叛徒, 那么就达成了OM(m) => OM(m-1)的效果.
感觉这是说不明白了=_=, 看例子也不容易懂, 从传统CS动态规划状态转移的角度理解是最容易的.
签名版:
(未完待续)
