如何理解拜占庭将军问题?

百度百科的算法木有看懂。。
关注者
304
被浏览
31938

8 个回答

答案基于<The Byzantine Generals Problem>,

Lamport最负盛名Paxos系列, 我还没看, 不过迟早也要看的.


11位拜占庭将军去打仗, 他们各自有权力观测敌情并作出判断, 进攻或撤退, 那么怎么让他们只用传令兵达成一致呢?

一种很符合直觉的方法就是投票,

每位将军作出决定后都将结果"广播"给其余所有将军, 这样所有将军都能获得同样的11份(包括自己)结果, 取多数, 即可得到全军都同意的行为.


但如果这11位将军中有间谍呢? 假设有9位忠诚的将军, 5位判断进攻, 4位判断撤退, 还有2个间谍恶意判断撤退, 虽然结果是错误的撤退, 但这种情况完全是允许的. 因为这11位将军依然保持着状态一致性.

暂时从战争故事中抽离出来, 分布式数据库最糟糕的问题绝对不是写入或者读取失败, 而是状态不同步, 还感知不到. 这个的后果就是correctness不能保证, 那程序就没有任何意义了.

2个间谍怎么破坏状态一致性呢? 他们跟5位判断进攻的将军说, 我们支持进攻, 那么这5位将军统计发现7位支持进攻, 4位支持撤退, 将发动进攻. 又跟4位撤退的将军说, 我们支持撤退, 一统计, 5票进攻, 6票撤退, 立马撤退. 这场战争必输无疑了.

避免这种状态不同步的问题, 我称之为"广义拜占庭将军问题".


Lamport继续将这个问题规约为更小的问题,

解决广义拜占庭问题, 必须满足两个条件:

  • 对任意忠诚的将军来说, 他们看到的其余将军的决定必须是一样的, 不允许出现前文那种, 5位将军统计结果是7攻4撤, 另外4位将军是5攻6撤.
  • 所有忠诚将军的决定对于其余所有忠诚将军都是一样的. 比如, V(1)表示1号将军的决定. 那么其余所有忠诚将军的统计表上, V(1)一定是一样的. 如果这点不能保证, 说明间谍已经可以直接颠覆指挥系统了, 系统怎样都是无效的, 哪怕达成了一致.

上面的条件等价于如何让一个将军(可以是间谍, 论文叫commander)对所有接收者(lieutenant)的指令(order)保持一致? 这个我叫"狭义拜占庭将军问题".


算法分口头版和签名版,

口头版对传令兵(messager)的要求仅有,

  • 命令的内容不会被破坏, 无论来自间谍或者忠臣
  • 命令的来源一定可以判断
  • 如果有将军不发命令, 可以被感知

总的来说, 这是一个非常严苛的模型, 我觉得Lamport在发表Paxos, 或者有人实现分布式数据库的时候一定不会用这个模型.

  • 大多数的节点不可能像拜占庭将军一样有主观恶意, 除非节点已经感染了病毒, 能避免服务器宕机这类的错误就可以了.
  • 命令的来源一定可以判断在现实环境是不可能达到的, 这要求节点之间采用网卡直接连接而不是用交换机.


算法描述如下,

OM(0): 0个叛徒的case, 正确性显而易见

  1. commander发送自己的观测结果给所有lieutenant
  2. 每个lieutenant使用他们接收到来自commander的结果

OM(m): m个叛徒

  1. commander发送自己的观测结果给所有lieutenant
  2. 最难理解的递归部分: lieutenant收到来自commander的结果v后, 并不直接接受, 而是让自身成为OM(m-1)的commander继续转发v
  3. 收集所有除了自身的lieutenant在OM(m-1)作为commander时发给自身的结果<v1,v2...>, 取majority

最最核心的是OM(m)的步骤2, 为什么lieutenant不能接受commander的指令而要递归?

因为commander有可能是叛徒! 他会给不同的lieutenant不同的指令.

所以, 悲催的忠臣必须问所有别的将军, "你们收到的commander的观测结果是啥?"来取majority校验, 同时又必须告诉所有别的将军, "我收到的commander的观测结果是啥?".

但该死的是, 忠臣A在告诉别的将军来自commander的观测结果的时候, 别的将军会怀疑忠臣A是不是叛徒. 别的将军判断忠臣A是忠臣的唯一的办法是询问别的忠臣A通知的忠臣, "忠臣A告诉你commander都发了啥?"

每次递归都做悲观预期即commander是个叛徒, 那么就达成了OM(m) => OM(m-1)的效果.

感觉这是说不明白了=_=, 看例子也不容易懂, 从传统CS动态规划状态转移的角度理解是最容易的.


签名版:

(未完待续)

-----------------[题外话]-----------------
有些好玩的事是提到拜占庭将军问题或者Lamport就会想起来的,所以先说点题外话。
这个问题的提出者Leslie Lamport觉得,死锁问题因为Dijkstra的哲学家就餐故事而受到了超出自己预期的关注。然后他顿悟了...
I realized that it was the story that went with it that made the problem so popular.
于是他开始编故事。拜占庭将军的故事就是Lamport在研究分布式系统容错性的时候编出的一个故事。论文发表,故事被广为传颂,Lamport也很爽。
尝到甜头之后,他在研究一致性算法的论文里以考古学家的口吻把保持分布式系统的一致性写成古希腊Paxos岛上议会临时议员们面临的问题。不过,这个故事不怎么招人受待见。至少,审稿人说Lamport把所有关于Paxos岛的内容换掉,要不就拒绝发表。当然,老爷子很不爽这些没有幽默感的人,干脆把文章贴在自己的网站(反正大家都回来膜拜,论文贴上去跟发表出去也差不多)。最后,等很多人都用Paxos实现系统的时候,文章才最终被发表。文章的发表时间(1998.03)距离完成时间(1990.01)足足差了8年。

-----------------[简单理解]-----------------
因为Lamport是分布式系统祖师爷级的人物,所以我就从分布式系统的角度来说。如果要保证分布式系统一致性和可用性,就必须处理错误节点,防止系统出现用户可以观察到的错误。
拜占庭将军问题在我看来是提出了一个错误模型即错误节点可以做任意事情(不受protocol限制),比如不响应、发送错误信息、对不同节点发送不同决定、不同错误节点联合起来干坏事等等。总之就是说,没有节点会出现比这更严重的错误。

很显然,拜占庭错误是overly pessimistic的模型,因为这种错误实际环境中比较少见。那么为什么要研究这个模型呢?其中最简单的一个原因是,如果某个一致性算法能够保证在系统出现f个拜占庭错误时保持系统一致,那么这个算法也就能够保证在出现f个任意其他错误的时候也保持系统一致。

错误模型有上限,肯定也就有一个下限(overly optimistic,没有比它还要弱的模型)。这个下限就是‘fail-stop’模型。这个模型的假设是:当一个节点出错,这个节点会停止运行,并且其他所有节点都知道这个节点发生了错误。用同样的逻辑,如果某个一致性算法不能保证在系统出现f个错误的时候保持一致,那么这个算法也就没法处理其他f个任意其他问题。

应用这些错误模型,可以对不同算法进行比较,也可以对具体算法的cost进行讨论。

-----------------[关于算法]-----------------
第一个提出解决拜占庭将军问题算法的,是Lamport于1980年发表的 Reaching agreement in the presence of faults [research.microsoft.com/]。这篇文章描述了当出现拜占庭错误的节点数(f)为1时的算法。

上面匿名用户贴的链接是Lamport与1982年发表的文章,其中描述了第一个能够处理f≥1的算法。

对这个问题的下一个进展是在1999年,是由Barbara Liskov(三位女性图灵奖获得者之一)提出。但是,具体列出这个进展之前,需要提一下拜占庭将军问题和FLP定理之间的关系。

除了错误模型,系统一致性的另一个重要方面是讨论在不同系统假设(通信异步/同步,任务完成时间有没有规定上限)下达成一致性的可能性和相应算法/协议。由于FLP(Impossibility of Distributed Consensus with One Faulty Process)决定了在异步+无响应上限的情况下不存在能够mask一个节点崩溃(强于fail-stop,节点崩溃,其他节点不知情)的有效算法。所以解决拜占庭问题的算法都会有同步假设(或者同步保证safety,或者同步保证liveness)。

[坑]

P.S.
百科上的算法我还没看,等看明白再补充。
为什么?