什么是拜占庭将军问题?

经常听到说某某区块链使用算法解决了拜占庭将军问题,什么是拜占庭将军问题呢?
已邀请:

空投将军

赞同来自:

拜占庭将军问题,英文叫Byzantine Generals Problem,不是真实存在的历史事件,而是由图灵奖得主莱斯利·兰伯特(Leslie Lamport)和他的两位同事于1982年在其论文中提出的一个点对点通信问题。

设定的场景是:在拜占庭时代,有个非常坚固的城堡,同时被十个独立邻邦环伺,单独攻城必败,需要一半以上的将军一同攻城才可以破城。十位将军分别各率领一支军队同时攻城,在制定作战计划时,需要信使来传达消息,在撤退还是进攻问题上达成一致。但是如果其中有将军叛变,他们的作战计划将会无法达成共识,攻城计划也必然失败。

Leslie Lamport 证明,当叛变者不超过1/3 时,拜占庭将军们能达成一致的共识。否则无法保证一定能达成行动一致。但是在古老的时代,交通不发达,沟通需要很大的成本,古时候不是信使,就是飞鸽传书,十位将军各有各的攻城计划,要达成一次不知道需要多少次这样的传递。

这样如此往复达成协议很难,其实即使达成了协议也是口头协议,消息的来源,可信度,有没有被传递者篡改。拜占庭城堡经历了千年也没有被这十位将军攻破,这也是历史难题“拜占庭将军问题”。当然,从技术上理解,拜占庭将军问题是分布式系统容错性问题。

分布式系统容错性问题

在分布式计算中,不同的计算机通过通讯交换信息达成共识而按照同一套协作策略行动。但有时候,系统中的成员计算机可能出错而发送错误的信息,用于传递信息的通讯网络也可能导致信息损坏,使得网络中不同的成员关于全体协作的策略得出不同结论,从而破坏系统一致性,拜占庭将军问题被认为是容错性问题中最难的问题类型之一。

比特币创始人中本聪利用互联网传输的信息及时性的特性,引入时间戳可以明确知道最初的发言人,还提出了工作量(POW)认证的方法,实际进展可以及时同步,以及引入挖矿机制,多劳多得,拜占庭将军问题自然迎刃而解。

要回复问题请先登录注册