FLP不可能定理是什么? | 盘他财讯
  1. 首页
  2. 文章资讯

FLP不可能定理是什么?

我们都知道在任何一个的分布式系统之中可能会存在各种各样的问题。例如服务器上运行的某些进程不可靠。例如服务器硬件可能会发生故障,操作系统可能会出现崩溃,进程会出现故障等。再比如进程之间的网络通讯不可靠。消息可能会丢包、延时,网络可能会出现分区。除了上述硬件或网络的故障外,系统进程甚至会出现一些任意或者欺诈的问题,即所谓的拜占庭故障。例如,在航天仪器上安装的多种传感器,可能会在极端的环境下,呈现出任意的行为,例如传送错误的参数。而在类似比特币等区块链网络,黑客会控制部分进程,故意伪造、篡改各类交易,以达到不可告人的目的。因此,对于一个分布式的系统而言,故障简直就是家常便饭;假定一个分布式网络系统的所有的进程都会在任何场景下运行正常才是一个疯狂的想法。那么问题来了,在一个分布式的异步网络中,要使得所有可靠的进程能够通过通讯达成共识是否可能呢?答案是惊人的,那就是不可能。

你可能会问,现在的分布式系统怎么可能无法达成共识呢?答案是,这里的前提是异步网络。在21世纪20年代的今天,我们已经知道有很多能够达成共识的经典算法,不过他们基本上都是在同步网络模型的基础上构建的。而在异步网络模型中,只有关于进程计算和消息传输的最少量的约束和规则。算法是基于事件的,例如一个进程可以给所有其他进程广播发送信息。在完全的异步网络中,我们对于进程处理的速度和消息传递的速度都是无法参照和分析的。消息本身可以任意延迟,接收的消息也可能任意乱序。我们假定进程无法参照同步的时钟,这也意味着我们在算法设计过程中无法使用基于超时机制的算法。我们也无法检测一个进程是否故障,因为我们无法判断和区分出这个进程究竟是执行得太慢,还是消息传递速度太慢,亦或是该进程已经挂了。

FLP不可能定理是什么?

FLP 不可能定理是分布式共识领域的核心成果,该定理指出:在一个由分散的计算机组成的系统中,不可能同时具备安全性、活性以及通信完全异步性;除非你对系统作了一些不合理的假设。

安全性 指的是,已经得到处理的事务不会再被撤销;活性 指的是,新的事务总是能得到处理。异步性 是指,消息从发起方到接收方的传输时间是没有上限的。

如果参与系统的节点能够可靠地相互通信、总是诚实地遵守协议而且永不宕机,那达成共识就不是一个难事。问题在于,现实中很难同时满足这几个要求。只要我们不作这样不切实际的假设,FLP 不可能定理就意味着:在设计一个分布式系统时,安全性、活性、完全异步性,我们至少得牺牲一个。

FLP 不可能定理就是在一个完全异步通讯的模型下,只要存在一个故障节点,就不存在一种确定的共识算法。当然,这个结果更多的是理论上的,在实际中无法达成终止的概率非常低。这个结论只是表明了,不存在一个完美的解决方案;在实际工程中,需要理解这个FLP 不可能定理,并在设计协议的时候做到有效的取舍;毕竟,一个号称实现了异步网络下的完全正确的共识算法的协议都是垃圾。

原创文章,作者:盘他财讯 Shining,如若转载,请注明出处:https://www.pantacx.com/archives/675

盘他区块链作为区块链信息平台,本站所提供的资讯信息不代表任何投资暗示,本站所发布文章仅代表个人观点,与盘他财讯官方立场无关。鉴于中国尚未出台数字资产相关政策及法规,请中国大陆用户谨慎进行数字货币投资。

发表评论

邮箱地址不会被公开。

联系我们

17606005547

邮件:184116859@qq.com

工作时间:周一至周五,9:00-18:00,节假日休息

QR code