二维码

4.2　共识算法 - 数据结构 - 机器学习

1156 人阅读 | 时间：2021年01月15日 01:18
4.2　共识算法 - 数据结构 - 机器学习 #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: "u3646201", container: s }); })();
(function() { var s = "_" + Math.random().toString(36).slice(2); document.write('
'); (window.slotbydup = window.slotbydup || []).push({ id: "u3646162", container: s }); })();

4.2　共识算法

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

共识 （consensus）在很多时候会与一致性 （consistency）术语放在一起讨论。严谨地讲，两者的含义并不完全相同。

一致性往往指分布式系统中多个副本对外呈现的数据的状态。如前面提到的顺序一致性、线性一致性，描述了多个节点对数据状 态的维护能力。而共识则描述了分布式系统中多个节点之间，彼此对某个状态达成一致结果的过程。因此，一致性描述的是结果状态，共识则是一种手段。达成某种 共识并不意味着就保障了一致性。

实践中，要保障系统满足不同程度的一致性，核心过程往往需要通过共识算法来达成。

共识算法解决的是对某个提案（proposal）大家达成一致意见的过程。提案的含义在分布式系统中十分宽泛，如多个事 件发生的顺序、某个键对应的值、谁是领导……等等。可以认为任何可以达成一致的信息都是一个提案。对于分布式系统来讲，各个节点通常都是相同的确定性状态 机模型（又称为状态机复制问题，state-machine replication），从相同初始状态开始接收相同顺序的指令，则可以保证相同的结果状态。因此，系统中多个节点最关键的是对多个事件的顺序进行共 识，即排序。

4.2.1　问题与挑战

实际上，如果分布式系统中各个单节点都能保证以十分“理想”的性能（瞬间响应、超高吞吐）无故障地运行，节点之间通信瞬时送达，则实现共识过程并不十分复杂，简单地通过广播进行瞬时投票和应答即可。

可惜的是，现实中这样的“理想”系统并不存在。不同节点之间通信存在延迟（光速物理限制，通信处理延迟），并且任意环节 都可能存在故障（系统规模越大，发生故障可能性越高）。如通信网络会发生中断、节点会发生故障、甚至存在恶意节点故意要伪造消息，破坏系统的正常工作流 程。

一般地，把出现故障（crash或fail-stop，即不响应）但不会伪造信息的情况称为“非拜占庭错误”（non- byzantine fault）或“故障错误”（Crash Fault）；伪造信息恶意响应的情况称为“拜占庭错误”（Byzantine Fault），对应节点为拜占庭节点。

4.2.2　常见算法

根据解决的是非拜占庭的普通错误情况还是拜占庭错误情况，共识算法可以分为Crash Fault Tolerance（CFT）类算法和Byzantine Fault Tolerance（BFT）类算法。

针对常见的非拜占庭错误的情况，已经存在一些经典的解决算法，包括Paxos、Raft及其变种等。这类容错算法往往性能比较好，处理较快，容忍不超过一半的故障节点。

对于要能容忍拜占庭错误的情况，一般包括PBFT（Practical Byzantine Fault Tolerance）为代表的确定性系列算法、PoW为代表的概率算法等。对于确定性算法，一旦达成对某个结果的共识就不可逆转，即共识是最终结果；而对 于概率类算法，共识结果则是临时的，随着时间推移或某种强化，共识结果被推翻的概率越来越小，成为事实上的最终结果。拜占庭类容错算法往往性能较差，容忍 不超过1/3的故障节点。

此外，XFT（Cross Fault Tolerance）等最近提出的改进算法可以提供类似CFT的处理响应速度，并能在大多数节点正常工作时提供BFT保障。

注意 　实践中，一致性的结果往往还需要客户端的额外支持，典型情况如通过访问足够多个服务节点来比对验证，确保获取共识后的正确结果。

4.2.3　理论界限

数学家都喜欢对问题先确定一个最坏的理论界限。那么，共识问题的最坏界限在哪里呢？很不幸，在推广到任意情形时，分布式 系统的共识问题无通用解。这似乎很容易理解，当多个节点之间的通信网络自身不可靠的情况下，很显然，无法确保实现共识（例如，所有涉及共识的消息都在网络 上丢失）。那么，对于一个设计得当，可以大概率保证消息正确送达的网络，是不是就一定能保证达成共识呢？

科学家们证明，即便在网络通信可靠情况下，可扩展的分布式系统的共识问题，其通用解法的理论下限是——没有下限（无解） 。

这个结论称为“FLP不可能原理”。该原理极其重要，可以看做是分布式领域里的“测不准原理”。

提示 　不仅在分布式系统领域，实际上在很多领域都存在类似“测不准原理”的约束。


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

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

(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 }); })();
搜索

网站分类

标签列表

最近发表

    (function(){ var bp = document.createElement('script'); var curProtocol = window.location.protocol.split(':')[0]; if (curProtocol === 'https'){ bp.src = 'https://zz.bdstatic.com/linksubmit/push.js'; } else{ bp.src = 'http://push.zhanzhang.baidu.com/push.js'; } var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(bp, s); })();

全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试

var cnzz_protocol = (("https:" == document.location.protocol) ? "https://" : "http://");document.write(unescape("%3Cspan id='cnzz_stat_icon_1276413723'%3E%3C/span%3E%3Cscript src='" + cnzz_protocol + "s23.cnzz.com/z_stat.php%3Fid%3D1276413723%26show%3Dpic1' type='text/javascript'%3E%3C/script%3E"));本站资源大部分来自互联网，版权归原作者所有！

jQuery(document).ready(function($){ /* prepend menu icon */ $('#daohangs-around').prepend('
'); /* toggle nav */ $("#caidan-tubiao").on("click", function(){ $("#daohangs").slideToggle(); $(this).toggleClass("active"); }); });

©著作权归作者所有：来自ZhiKuGroup博客作者没文化的原创作品，如需转载，请注明出处，否则将追究法律责任 来源：ZhiKuGroup博客，欢迎分享。

评论专区
  • 昵 称必填
  • 邮 箱选填
  • 网 址选填
◎已有 0 人评论
相关文章
搜索
作者介绍
superadmin

superadmin

30天热门
热评文章
最近发表
标签列表

©2012-2022 Think tank 鄂ICP备19030179号-1| 使用Chrome浏览本站最佳 | 声明：本站的文章和资源来自互联网或者站长的原创，按照 CC BY -NC -SA 3.0 CN协议发布和共享，转载或引用本站文章<应遵循相同协议。如果有侵犯版权的资源请尽快联系站长，我们会在24h内删除有争议的资源；本站所有收费以及免费的信息和数据仅供参考，不构成投资建议，本网站不承担由此导致的任何责任。 登陆

Powered By Z-BlogPHP

×
×
本站会员尊享VIP特权，现在就加入我们吧！登录注册×
»
会员登录
新用户注册
×
会员注册
已有账号登录
×