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 将会吐钱,这就又陷入了死循环。在你打开这个网页时,客户端和服务器都要确信彼此已做好连接,才能开始传输数据,这也会导致没完没了的确认程序。在工程上,人们普遍采用“三次握手”的方案;但正如前文所说,这个问题永远没有万无一失的解决方法。

46条评论















































发表评论

电子邮件地址不会被公开。