知识卡片
异步共识无法保证有限时间
分布式系统关心的是异步共识:消息可能无限延迟。算法分崩溃后不可恢复与可恢复两类,后者更实用,因多数故障是网络变慢、重启这类暂时问题;能应对节点发错误消息的拜占庭式算法成本更高、也少见。FLP 结论指出,不稳定网络下没有异步共识算法能保证一定达成共识。实践中靠足够多的健康副本、良好网络,加上随机化指数退避,让共识在多数情况下有限时间内完成。发散:理论上不可能,工程上靠概率兜住。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第23章 管理关键状态:利用分布式共识来提高可靠性 · 查看原书依据
拜占庭式问题指的是当某个进程由于程序Bug或者恶意行为发送不正确的消息的问题,这种问题相对来说处理成本更高,同时也更少见。 严格来讲,在有限时间内解决异步式分布式共识问题是不可能的。正如Dijkstra 的获奖文章—FLP impossibility result(参见文献[Fis85])写的那样,在不稳定的网络条件下,没有任何一种异步式分布式共识算法可以保证一定能够达成共识。 在实际操作中,我们通过保证给系统提供足够的健康的副本,以及良好的网络连接状态来保障分布式共识算法在大多数情况下是可以在有限时间内达成共识的。
参考来源
- 位置:《SRE:Google运维解密》第23章《管理关键状态:利用分布式共识来提高可靠性》(源文件:`_epub-src/OEBPS/Text/0009_0014.xhtml`)
- 结论依据:原文区分异步与同步、崩溃可恢复与不可恢复、拜占庭与非拜占庭共识,引用 FLP 结论,并说明实践中如何在有限时间内达成共识。
- 原始内容:严格来讲,在有限时间内解决异步式分布式共识问题是不可能的。