4.3　FLP不可能原理 - 数据结构 - 机器学习

1337 人阅读 | 时间：2021年01月15日 01:18

4.3　FLP不可能原理 - 数据结构 - 机器学习 #daohang ul li t,.reed .riqi,a.shangg,a.xiatt,a.shangg:hover,a.xiatt:hover,a.shang,a.xiat,a.shang:hover,a.xiat:hover,.reed-pinglun-anniu,span.now-page,#daohangs-around,#caidan-tubiao,#daohangs,#daohangs li,#btnPost{background-color:#D10B04;} .dinglanyou1 h3{border-bottom:3px solid #D10B04;} #dibuer{border-top:2px solid #D10B04;}.cebianlan .rongqi h3{border-bottom:1px solid #D10B04;} #edtSearch{border:1px solid #D10B04;} #daohang .zuo ul li{border-right:1px solid #;} #daohang ul li t a{border-top:1px solid #;border-right:1px solid #D10B04;} #daohang ul li t a:hover{border-right:1px solid #;} #daohang .you ul li a:hover,#daohang .zuo ul li a:hover,.reed-pinglun-anniu:hover{background-color:#;} a:hover,.reed h6 a:hover,#dibuer a:hover,.reed .riqiding,.cebianlan .rongqi li a:hover,#pinglun-liebiao ul.fubens li.depth-1 dl dd span.shu a,#pinglun-liebiao ul.fubens li.depth-1 dl dd span.huifuliuyan a:hover,.reed-biaoti h6 span{color:#D10B04;} .reed .kan a{color:#0A0AF5;}.reed .kan a:hover{color:#D10101;} @media screen and (max-width:1492px){a.shang,a.xiat{background:none;} a.xiat:hover,a.shang:hover{background-color:#f9f9f9;background-image:none;text-decoration:none;}} var _hmt = _hmt || [];(function() { var hm = document.createElement("script"); hm.src = "https://hm.baidu.com/hm.js?b19db5ba3b437a9e8698d2bc8fc64334"; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(hm, s);})(); var _hmt = _hmt || []; (function() { var hm = document.createElement("script"); hm.src = "https://hm.baidu.com/hm.js?b19db5ba3b437a9e8698d2bc8fc64334"; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(hm, s); })(); var _hmt = _hmt || []; (function() { var hm = document.createElement("script"); hm.src = "https://hm.baidu.com/hm.js?2d748c9763cfc72fb7d1ccab29f0770d"; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(hm, s); })(); var _hmt = _hmt || []; (function() { var hm = document.createElement("script"); hm.src = "https://hm.baidu.com/hm.js?f6d451f3f1be23f3abf240c64c469c1b"; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(hm, s); })();

数据结构 - 深度学习

当前位置：首页 » 区块链精品文章 » 正文

(function() { var s = "_" + Math.random().toString(36).slice(2); document.write('

'); (window.slotbydup = window.slotbydup || []).push({ id: "u3646162", container: s }); })();

4.3　FLP不可能原理

1476 人参与 2018年09月30日 10:48 分类 : 区块链精品文章评论

4.3.1　定义

FLP不可能原理：在网络可靠，但允许节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性共识算法（No completely asynchronous consensus protocol can tolerate even a single unannounced process death）。

提出并证明该定理的论文《Impossibility of Distributed Consensus with One Faulty Process》由Fischer、Lynch和Patterson三位科学家于1985年发表，该论文后来获得了Dijkstra（就是发明最短路径算法的那位计算机科学家）奖。

FLP不可能原理实际上告诉人们，不要浪费时间，去为异步分布式系统设计在任意场景下都能实现共识的算法。

4.3.2　正确理解

要正确理解FLP不可能原理，首先要弄清楚“异步”的含义。

在分布式系统中，同步和异步这两个术语存在特殊的含义。同步是指系统中的各个节点的时钟误差存在上限；并且消息传递必须在一定时间内完成，否则认为失败；同时各个节点完成处理消息的时间是一定的。对于同步系统，可以很容易地判断消息是否丢失。异步是指系统中各个节点可能存在较大的时钟差异，同时消息传输时间是任意长的，各节点对消息进行处理的时间也可能是任意长的，这就造成无法判断某个消息迟迟没有被响应是哪里出了问题（节点故障还是传输故障？）。不幸地是，现实生活中的系统往往都是异步系统。

FLP不可能性在原始论文中以图论的形式进行了严格证明。要理解这一基本原理并不复杂，一个不严谨的例子如下。

三个人在不同房间进行投票（投票结果是0或者1）。彼此可以通过电话进行沟通，但经常有人会时不时睡着。比如某个时候，A投票0，B投票1，C收到了两人的投票，然后C睡着了。此时，A和B将永远无法在有限时间内获知最终的结果，究竟是C没有应答还是应答的时间过长。如果可以重新投票，则类似情形可以在每次取得结果前发生，这将导致共识过程永远无法完成。

FLP原理实际上说明对于允许节点失效情况下，纯粹异步系统无法确保一致性在有限时间内完成。即便对于非拜占庭错误的前提下，包括Paxos、Raft等算法也都存在无法达成共识的情况，只是在工程实践中这种情况出现的概率很小。

那么，FLP不可能原理是否意味着研究共识算法压根没有意义？

先别这么悲观。学术界做研究，往往考虑地是数学和物理意义上最极端的情形，很多时候现实生活要美好得多（感谢这个世界如此鲁棒！）。例如，上面例子中描述的最坏情形，每次都发生的概率其实并没有那么大。工程实现上多尝试几次，很大可能就成功了。

科学告诉你什么是不可能的；工程则告诉你，付出一些代价，可以把它变成可行。这就是科学和工程不同的魅力。

那么，退一步讲，在付出一些代价的情况下，我们在共识的达成上，能做到多好？回答这一问题的是另一个很出名的原理：CAP原理。

提示　科学告诉你去赌场赌博从概率上总会是输钱的；工程则告诉你，如果你愿意接受最终输钱的风险，中间说不定能偶尔小赢几笔呢！

来源：我是码农，转载请保留出处和链接！

本文链接：http://www.54manong.com/?id=971

(function() { var s = "_" + Math.random().toString(36).slice(2); document.write('

'); (window.slotbydup = window.slotbydup || []).push({ id: "u3646208", container: s }); })();

(function() { var s = "_" + Math.random().toString(36).slice(2); document.write('

'); (window.slotbydup = window.slotbydup || []).push({ id: "u3646147", container: s }); })();

window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdPic":"","bdStyle":"0","bdSize":"16"},"share":{},"image":{"viewList":["qzone","tsina","tqq","renren","weixin"],"viewText":"分享到：","viewSize":"16"},"selectShare":{"bdContainerClass":null,"bdSelectMiniList":["qzone","tsina","tqq","renren","weixin"]}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];

区块链是什么

微信号：qq444848023 QQ号：444848023

加入【我是码农】QQ群：864689844（加群验证：我是码农）

(function() { var s = "_" + Math.random().toString(36).slice(2); document.write('

'); (window.slotbydup = window.slotbydup || []).push({ id: "u3646186", container: s }); })();

(function() { var s = "_" + Math.random().toString(36).slice(2); document.write('

'); (window.slotbydup = window.slotbydup || []).push({ id: "u3646175", container: s }); })();

搜索

4.3　FLP不可能原理 - 数据结构 - 机器学习

数据结构 - 深度学习

数据结构 - 机器学习

当前位置：首页 » 区块链精品文章 » 正文

4.3　FLP不可能原理

1476 人参与 2018年09月30日 10:48 分类 : 区块链精品文章评论

网站分类

标签列表

最近发表

评论专区

搜索

作者介绍

30天热门

热评文章

最近发表

标签列表

4.3 FLP不可能原理 - 数据结构 - 机器学习

数据结构 - 深度学习

数据结构 - 机器学习

当前位置：首页 » 区块链精品文章 » 正文

4.3 FLP不可能原理

1476 人参与 2018年09月30日 10:48 分类 : 区块链精品文章 评论

网站分类

标签列表

最近发表

评论专区

相关文章

搜索

作者介绍

30天热门

热评文章

最近发表

标签列表

4.3　FLP不可能原理 - 数据结构 - 机器学习

4.3　FLP不可能原理

1476 人参与 2018年09月30日 10:48 分类 : 区块链精品文章评论