当前位置:   article > 正文

FLP 定理

flp

FLP 定理

  1. 在异步通信场景,即使只有一个进程失败了,没有任何算法能够保证进程能够达到一致性

系统模型

  1. 系统模型
    1.1 异步通信 > 异步通信与同步通信最大区别是没有时钟,不能时间同步,不能使用超时,不能探测失败,
    消息可任意延迟,消息可乱序
    1.2 通信健壮 > 只要进程非失败,消息虽会被无限延迟,但最终会被送达,且消息只会被送达一次(无重复)
    1.3 Fail-Stop模型 > 进程失败如同宕机,不再处理任何消息。相对Byzantine模型,不会产生错误消息;
    1.4 协议约束 > 不要求所有非故障进程都达成一致,只要有一个进程进入决定状态就算达成一致,且一致的结果只能是
    属于{0,1};
    1.5 失败进程数量 > 最多只有一个进程失败或单节点宕机

推导证明

  1. 进程自己必须在接受别人请求后作出正确决定,最不出正确决定视为无法达成一致
  2. 如果非故障节点投票结果为 1 : 1,故障节点无法投票会导致失败

结论

  1. 不存在在异步网络上容忍各种故障并保持一致的分布式系统
  2. 无法同时保证safety,liveness的一致性算法,但保证其中一个,失败概率比较低
  3. 现实中并不存在完全分布式场景
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/一键难忘520/article/detail/984070
推荐阅读
相关标签
  

闽ICP备14008679号