你怎么知道我已经知道了,拜占庭将军问题

A、B
两人有事需要面谈,他们要用短信的方式约定明天的见面时间和地点。不过,两人的时间都非常宝贵,只有确信对方能够出席时,自己才会到场。A
给 B 发短信说,“我们明天 10:00 在 XX
大厦见吧”。不过,短信发丢了是常有的事情。为了确信 B 得知了此消息,A
补充了一句,“收到请回复”。B 收到了之后,立即回复:“已收到,明天 10:00
不见不散”。不过,B 也有他自己的担忧:A
不是只在确认我要去了之后才会去吗?万一对方没有收到我的确认短信,届时没有到场让我白等一中午怎么办?因此
B 也附了一句:“收到此确认信请回复”。A
收到确认信之后,自然会回复“收到确认信”。但 A 又产生了新的顾虑:如果 B
没收到我的回复,一定会担心我因为没收到他的回复而不去了,那他会不会也就因此不去了呢?为了确保
B 收到了回复,A
也在短信末尾加上了“收到请回复”。这个过程继续下去,显然是没完没了。其结果是,A、B
两人一直在确认对方的信息,但却始终无法达成共识:“我们都将在明天 10:00
到达 XX 大厦”。

提到区块链的共识机制,就来谈谈拜占庭将军问题。拜占庭将军问题也是一个共识问题,有兴趣的可以继续深究,解决方案也很多。

协同进攻问题

当然,在现实生活中,一次回执基本上就足够了,再纠结下去成本也太高了;毕竟也就是吃个饭谈个事,如果对方没到,大不了自己在寒风中干等半个小时罢了。况且,直接通话也比短信来往靠谱多了(消息保证传达到,不会弄丢)。不过,换作另外一些情况,这个问题可就得严肃对待了。1978
年,美国计算机科学家吉姆·格雷(Jim
Gray)在一篇文献中提到了“协同进攻问题”(Coordinated Attack Problem):

两支军队均已部署完毕,他们需要约定一个同时进攻敌人的时间。只要有一方没能协同作战,他们都无法把敌人打下来。因而,两支军队都需要百分之百地确定对方将会进攻,自己才会进攻。两位将军需要用信件交流,确定出一个同时进攻的时间。但是,信使有可能被敌人抓获,信件不保证总能寄到。其实,约定一个进攻时间并不难,只需要将军
A 给将军 B 发送一条包含进攻时间的信息,让将军 B
给个回执就行了;如果过了很久都没收到回执,就再次发送,直到收到回执为止。但难就难在,如何让双方达成共识:“我们都会在那个时候发起进攻”。显然,问题就又变成了之前的无限循环。

有没有什么解决方法呢?让我们来试一试。比方说,A 可以发信说,“明天 10:00
进攻,收到请回复,只要我收到了你的回复,就表明我们达成共识了”。这样其实一点用处都没有,B
发出确认信后,他还是不知道 A
有没有收到这封确认信,因而还是不知道双方有没有达成共识。那么,A
能不能发信息说,“明天 10:00
进攻,然后我们互发确认信,确认到第三轮就表示真的确认了”?这样也没用,发完第三轮确认信后,双方还是不知道对方有没有收到第三轮的确认信,因而不得不再确认一句“我收到第三轮的确认信了”等等,问题又变回去了。

会不会有什么非常巧妙的协议,能够让双方达成共识呢?没有。事实上,我们能够从理论上证明,要想用互发信息的方式达成共识,这是一件不可能完成的任务。证明的基本思路就是,假设某种方案能够满足要求,那么这个方案一定考虑到了达成目标所需的最后一条信息寄丢了的情况。也就是说,即使这最后一条信息被寄丢了,仍然不影响整个方案的可行性。因而,这最后一条信息是无关紧要的,可以把这个步骤去掉。照此推下去,我们总能不断去掉方案的最后一步,最后的结果就是这样一个荒谬的推论:什么都不做,就能让双方达成共识。这显然是不可能的,因此我们的假设是错误的。

很多现实问题都有这样的困境。例如,ATM
机在吐钱的同时,需要确信银行系统会给相应的账户扣钱,而银行系统也需要事先确定
ATM
将会吐钱,这就又陷入了死循环。在你打开这个网页时,客户端和服务器都要确信彼此已做好连接,才能开始传输数据,这也会导致没完没了的确认程序。在工程上,人们普遍采用“三次握手”的方案;但正如前文所说,这个问题永远没有万无一失的解决方法。

1.拜占庭领军问题

首先由Leslie Lamport与另外两人在1982年提出,被称为The Byzantine Generals
Problem或者Byzantine
Failure。核心描述是军中可能有叛徒,却要保证进攻一致,由此引申到计算领域,发展成了一种容错理论。随着比特币和区块链的出现和兴起,这个著名问题又重入大众视野。关于拜占庭将军问题,一个简易的非正式描述如下:拜占庭帝国想要进攻一个强大的敌人,为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国,但也足以抵御5支常规拜占庭军队的同时袭击。基于一些原因,这10支军队不能集合在一起单点突破,必须在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算,除非有至少6支军队同时袭击才能攻下敌国。他们分散在敌国的四周,依靠通信兵相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是,他们不确定他们中是否有叛徒,叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下,拜占庭将军们能否找到一种分布式的协议来让他们能够远程协商,达成共识,从而赢取战斗?这就是著名的拜占庭将军问题。

应该明确的是,拜占庭将军问题中并不去考虑通信兵是否会被截获或无法传达信息等问题,即消息传递的信道绝无问。Lamport已经证明了在消息可能丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。所以,在研究拜占庭将军问题的时候,我们已经假定了信道是没有问题的,并在这个前提下,去做一致性和容错性相关研究。如果需要考虑信道是有问题的,这涉及到了另一个相关问题:两军问题。

2.两军问题

正如前文所说,拜占庭将军问题和两军问题实质是不一样的,两军问题是用来解决通信通道的可靠性,而拜占庭将军问题是来解决共识机制的。两军问题:白军驻扎在沟渠里,蓝军则分散在沟渠两边。白军比任何一支蓝军都更为强大,但是蓝军若能同时合力进攻则能够打败白军。他们不能够远程的沟通,只能派遣通信兵穿过沟渠去通知对方蓝军协商进攻时间。是否存在一个能使蓝军必胜的通信协议,这就是两军问题。

看到这里您可能发现两军问题和拜占庭将军问题有一定的相似性,但我们必须注意的是,通信兵得经过敌人的沟渠,在这过程中他可能被捕,也就是说,两军问题中信道是不可靠的,并且其中没有叛徒之说,这就是两军问题和拜占庭将军问题的根本性不同。由此可见,大量混淆了拜占庭将军问题和两军问题的文章并没有充分理解两者。

澳门新葡亰平台游戏app,两军问题的根本问题在于信道的不可靠,反过来说,如果传递消息的信道是可靠的,两军问题可解。然而,并不存在这样一种信道,所以两军问题在经典情境下是不可解的,为什么呢?

倘若1号蓝军(简称1)向2号蓝军(简称2)派出了通信兵,若1要知道2是否收到了自己的信息,1必须要求2给自己传输一个回执,说“你的信息我已经收到了,我同意你提议的明天早上10点9分准时进攻”。然而,就算2已经送出了这条信息,2也不能确定1就一定会在这个时间进攻,因为2发出的回执1并不一定能够收到。所以,1必须再给2发出一个回执说“我收到了”,但是1也不会知道2是否收到了这样一个回执,所以1还会期待一个2的回执。

虽然看似很可笑,但在这个系统中永远需要存在一个回执,这对于两方来说都并不一定能够达成十足的确信。更要命的是,我们还没有考虑,通信兵的信息还有可能被篡改。由此可见,经典情形下两军问题是不可解的,并不存在一个能使蓝军一定胜利的通信协议。

不幸的是,两军问题作为现代通信系统中必须解决的问题,我们尚不能将之完全解决,这意味着你我传输信息时仍然可能出现丢失、监听或篡改的情况。但我们能不能通过一种相对可靠的方式来解决大部分情形呢?这需要谈到TCP协议。事实上,搜索“两军问题与三次握手”,您一定可以找到大量与TCP协议相关的内容。若您是通信方面的专家,权当笔者是班门弄斧,这里仅用最浅显易懂的方式科普TCP协议。

  1. 拜占庭将军问题实质

回顾问题,一群将军想要实现某一个目标(一致进攻或者一致撤退),但是单独行动行不通,必须合作,
达成共识;由于叛徒的存在,将军们不知道应该如何达到一致。注意,这里“一致性”才是拜占庭将军问题探讨的内容,如果本来叛徒数量就已经多到了问题不可解的地步,这个就是“反叛”的问题了;同时,我们的目标是忠诚的将军能够达成一致,对于这些忠诚的将军来说,进攻或者撤退都是可以的,只要他们能够达成一致就行。

但是,光靠“一致”就可以解决问题吗?考虑一下,如果万事俱备,客观上每个忠诚的将军只要进攻了就一定能够胜利,但是却因为叛徒的存在他们都“一致的”没有进攻;反之,条件不利,将军们不应该进攻,但是却因为叛徒的存在所有人都“一致的”进攻了。

可以发现,只有“一致性”是不足以解决拜占庭将军问题的,我们还需要提出一个“正确性”要求。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章