拜占庭将军-分布式领域的幽灵

【拜占庭将军-分布式领域的幽灵】拜占庭将军问题(Byzantine Generals Problem),是由莱斯利·兰波特在其同名论文中提出的分布式对等网络通信容错问题。

在分布式计算中,不同的计算机通过通讯交换信息达成共识而按照同一套协作策略行动。但有时候,系统中的成员计算机可能出错而发送错误的信息,用于传递信息的通讯网络也可能导致信息损坏,使得网络中不同的成员关于全体协作的策略得出不同结论,从而破坏系统一致性。拜占庭将军问题被认为是容错性问题中最难的问题类型之一。
也被称为“拜占庭容错”、“拜占庭将军问题”。
拜占庭将军问题是Leslie Lamport(2013年的图灵讲得住)用来为描述分布式系统一致性问题(Distributed Consensus)在论文中抽象出来一个著名的例子。
这个例子大意是这样的:
拜占庭帝国想要进攻一个强大的敌人,为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国,但也足以抵御5支常规拜占庭军队的同时袭击。这10支军队在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算,除非有至少6支军队(一半以上)同时袭击才能攻下敌国。他们分散在敌国的四周,依靠通信兵骑马相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是,他们不确定他们中是否有叛徒,叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下,拜占庭将军们才能保证有多于6支军队在同一时间一起发起进攻,从而赢取战斗。
拜占庭将军问题中并不去考虑通信兵是否会被截获或无法传达信息等问题,即消息传递的信道绝无问题。Lamport已经证明了在消息可能丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。所以,在研究拜占庭将军问题的时候,已经假定了信道是没有问题的.
此系统的名字叫做拜占庭将军问题。从描述中,可以显然知道,将军们需要通过少数服从多数的算法在分布式的场景下进行投票决议一个一致性的决定去执行。
在拜占庭将军问题中,默认是认为信使是不会被截获并且消息会传递到的。更多的情况中,将军中可能会出现叛徒、信使会被截获冒充、消息无法到达。而叛徒或信使冒充会恶意地向其他将军投票,给不同将军展示不同的投票结果,从而破坏了将军们执行的一致性。而此类错误则称为拜占庭错误。
如果系统能处理拜占庭将军错误正常运行的话,则称系统拥有拜占庭容错「Byzantine fault tolerance」,简称为BFT。

    推荐阅读