🧭
区块链技术指南
  • 前言
  • 修订记录
  • 如何贡献
  • 区块链的诞生
    • 记账科技的千年演化
    • 分布式记账与区块链
    • 集大成者的比特币
    • 区块链的商业价值
    • 本章小结
  • 核心技术概览
    • 定义与原理
    • 技术的演化与分类
    • 关键问题和挑战
    • 趋势与展望
    • 认识上的误区
    • 本章小结
  • 典型应用场景
    • 应用场景概览
    • 金融服务
    • 征信管理
    • 权属管理与溯源
    • 资源共享
    • 物流与供应链
    • 物联网
    • 数字艺术品和 NFT
    • 其它场景
    • 本章小结
  • 分布式系统核心技术
    • 一致性问题
    • 共识算法
    • FLP 不可能原理
    • CAP 原理
    • ACID 原则与多阶段提交
    • Paxos 算法与 Raft 算法
    • 拜占庭问题与算法
    • 可靠性指标
    • 本章小结
  • 密码学与安全技术
    • 密码学简史
    • Hash 算法与数字摘要
    • 加解密算法
    • 消息认证码与数字签名
    • 数字证书
    • PKI 体系
    • Merkle 树结构
    • Bloom Filter 结构
    • 同态加密
    • 其它技术
    • 本章小结
  • 比特币 —— 初露锋芒的区块链
    • 比特币项目简介
    • 比特币诞生背景
    • 工作原理
    • 挖矿过程
    • 共识机制
    • 闪电网络
    • 侧链
    • 热门问题
    • 相关工具
    • 本章小结
  • 以太坊 —— 挣脱加密货币的枷锁
    • 以太坊项目简介
    • 核心概念
    • 主要设计
    • 相关工具
    • 安装客户端
    • 使用智能合约
    • 智能合约案例:投票
    • 本章小结
  • 超级账本 —— 面向企业的分布式账本
    • 超级账本项目简介
    • 社区组织结构
    • 顶级项目介绍
    • 开发必备工具
    • 贡献代码
    • 本章小结
  • Fabric 安装与部署
    • 简介
    • 本地编译组件
    • 容器方式获取
    • 本地方式启动 Fabric 网络
    • 容器方式启动 Fabric 网络
    • 本章小结
  • 管理 Fabric 网络
    • 简介
    • 使用通道
    • 管理节点
    • 管理链上代码
    • 监听网络事件
    • 自动发现网络信息
    • 使用运维服务
    • 如何升级网络版本
    • 使用 SDK
    • 注意事项与最佳实践
    • 本章小结
  • 智能合约开发
    • 简介
    • 链码概念与结构
    • 示例一:信息公证
    • 示例二:交易资产
    • 示例三:数字货币发行与管理
    • 示例四:学历认证
    • 示例五:社区能源共享
    • 小结
  • Fabric 架构与设计
    • 简介
    • 架构设计
    • 消息协议
    • 小结
  • 区块链服务平台设计
    • 简介
    • IBM Bluemix 云区块链服务
    • 微软 Azure 云区块链服务
    • 使用超级账本 Cello 搭建区块链服务
    • 本章小结
  • 性能与评测
    • 简介
    • Hyperledger Fabric v0.6
    • 小结
  • 附录
    • 术语
    • 常见问题
    • Go 语言开发相关
      • 安装与配置 Golang 环境
      • 编辑器与 IDE
      • 高效开发工具
      • 依赖管理
    • ProtoBuf 与 gRPC
    • 参考资源链接
由 GitBook 提供支持
在本页
  • 定义
  • 如何理解

这有帮助吗?

在GitHub上编辑
  1. 分布式系统核心技术

FLP 不可能原理

定义

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 不可能原理告诉我们,不要浪费时间去试图为异步分布式系统设计面向任意场景的共识算法。

如何理解

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

在分布式系统中,同步和异步这两个术语存在特殊的含义:

  • 同步,是指系统中的各个节点的时钟误差存在上限;并且消息传递必须在一定时间内完成,否则认为失败;同时各个节点完成处理消息的时间是一定的。因此同步系统可以轻易判断是节点宕机还是传输消息丢失;

  • 异步,则意味着系统中各个节点可能存在较大的时钟差异;同时消息传输时间是任意长的;各节点对消息进行处理的时间也可能是任意长的。这就造成无法判断某个消息迟迟没有被响应是哪里出了问题(节点故障还是传输故障?)。不幸地是,现实生活中的系统往往都是异步系统。

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

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

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

那么,这是否意味着研究共识算法压根没有意义?

不必如此悲观。学术研究,往往考虑地是数学和物理意义上理想化的情形,很多时候现实世界要稳定得多(感谢这个世界如此鲁棒!)。例如,上面例子中描述的最坏情形,每次都发生的概率其实并没有那么大。工程实现上,若某次共识失败,再尝试几次,很大可能就成功了。

科学告诉你,什么是不可能的;工程则告诉你,付出一些代价,可以把它变成可行。

这就是科学和工程不同的魅力。FLP 不可能原理告诉大家不必浪费时间去追求完美的共识方案,而要根据实际情况设计可行的工程方案。

那么,退一步讲,在付出一些代价的情况下,共识能做到多好?

回答这一问题的是另一个很出名的原理:CAP 原理。

注:科学告诉你去赌场是愚蠢的,因为最终总会输钱;工程则告诉你,如果你愿意接受最终输钱的风险,中间说不定能偶尔小赢几笔呢!

上一页共识算法下一页CAP 原理

最后更新于3年前

这有帮助吗?